Calculation of a masked value protected against spy out

The invention relates generally to the field of cryptography, and more particularly to the field of spy protection of cryptographic computations. The invention is particularly suitable for use with a portable data carrier. Such a portable data carrier can eg a smart card<i>(Smart card)</i> be in different designs or a chip module or other resource-limited system.

Portable data carriers are often used for safety-critical applications such as mobile-based authentication, financial transactions, electronic signatures, and so on. Since unauthorized use could cause a high level of damage, the secret data that is processed by such data carriers must be reliably protected against spying and manipulation.

Various attack methods for data spying are known in which the flow of information does not extend beyond the communication channels provided for the normal operation of the data carrier. Such methods are therefore called minor channel attacks<i>(Side Channel Attacks)</i> designated. Examples of side channel attacks are so-called SPA or DPA attacks (SPA =<i>Simple Power Analysis;</i> DPA = <i>Differential power analysis),</i> in which by measuring the current consumption of the data carrier during the execution of a program conclusions about the processed data are drawn. In a SPA attack, the current draw is examined during a single calculation process, while in a DPA attack, many calculation processes are statistically evaluated. In other side channel attacks in addition to the power consumption or instead at least one other physical parameters, eg the time required for the calculation, measured and evaluated.

A known technique for the defense against secondary channel attacks is to mask the data to be kept secret, ie to falsify it in such a way that the masked data is statistically independent of the data to be kept secret. Cryptographic calculations are then performed on the masked data. Even if an attacker succeeds, eg By means of a secondary channel attack, the masked data can be determined so that no conclusions can be drawn about the data to be kept secret.

The masking is done by applying a masking function to the data to be kept secret. In most cases, the masking function is formed from a predetermined masking rule with at least one masking parameter. The masking parameter is chosen randomly before the start of the cryptographic calculation. This is eg according to a method known as "Boolean masking", the masking rule uses exclusive-or-operation (XOR) with an operand specified by the masking parameter. The cryptographic calculation will then not match the value to be kept secret <i>x</i>but with its masked representation <i>x ⊕</i> r, where ⊕ denotes the exclusive-or operation in infix notation and r the randomly chosen masking parameter.

The masking technique just described is known for example from DE 198 22 217 A1. However, it is proposed there to perform arithmetic operations that are non-linear with respect to the selected masking function without masking with the data to be kept secret. This represents a potential security risk.

In many cryptographic methods, mappings to be calculated for unmasked input and result values ​​are given by tables. For the reasons mentioned above, however, a table access with the unmasked input value as a table index should be avoided, in particular when implemented on a portable data carrier. Rather, a masked table is to be accessed that is designed to provide a masked result value upon access to a masked table index.

In formula notation, for example, in the case of Boolean masking, the following steps are carried out each time the cryptographic process is run: First, two random numbers r and s are determined as masking parameters. Then, based on the given table T, a masked table<i>T '</i> generated, so that <i>T '(x</i> ⊕ r) = <i>T</i>(<i>x</i>) ⊕ <i>s</i> applies. In the masked table<i>T '</i> are therefore the input values ​​with the masking parameter <i>r</i> and masking the result values ​​with the masking parameter s. The cryptographic calculation is carried out so that the value x to be kept secret is not in unmasked form but in the masked form<i>x</i> ⊕ <i>r</i> is present. Instead of access to the table T at the point x now accesses the masked table<i>T '</i> at the point x ⊕ r. This results instead of an unmasked result<i>y</i> : = <i>T</i>(<i>x</i>) the desired result masked with the masking parameter s <i>y</i> ⊕ <i>s</i>,

Obviously, it is not practicable, even for the production of the data carrier for each possible later masking - in the above example all possible masking parameters r and s - in advance each have their own masked table <i>T '</i> to calculate and store in a read-only memory of the disk. The masked table<i>T '</i> Therefore, it can only be calculated at runtime of the cryptographic method for a specifically applicable masking - in the example above already selected masking parameters r and s - and written to a main memory of the data carrier.

However, this results in the problem of a relatively high memory requirement. In the case of common portable data carriers, the main memory is usually very tight, because the RAM, which is generally designed as RAM, requires a large amount of chip area per memory cell. If eg a table with 256 entries of one byte each as a masked table T 'is to be written into the main memory, 256 bytes are required for this purpose. This is more than some of today's usual disk storage, and definitely a sizeable portion of the total memory available, which is still needed for many other purposes. There is therefore a need to reduce the space required for the masked table in the main memory.

WO 03/017067 A2 discloses a method in which a common masked table with the size of an unmasked table is generated from two unmasked tables of equal size. Each entry in the common table is calculated as a function of a combination of two result values ​​of the unmasked tables. In order to determine a masked result value according to the mapping defined by one of the unmasked tables, access is made to the masked table whose result is linked to the result of access to the other unmasked table in order to undo the join made in the calculation of the masked table close.

In formula notation is thus according to WO 03/017067 A2 for the predefined in the read-only memory tables <i>T</i>₁ and <i>T</i>₂ and three masking parameters <i>r</i>₁. <i>r</i>₂ and s the masked table <i>T</i>₀ With <i>T</i>₀(<i>x</i>): = <i>T</i>₁(<i>x</i> ⊕ <i>r</i>₁) ⊕ <i>T</i>₂(<i>x</i> ⊕ <i>r</i>₂) ⊕ <i>s</i> calculated and stored in the working memory. For a masked input value<i>x</i>₁ : = <i>x ⊕ r</i>₁ becomes the masked result value <i>y</i>₁ : = <i>T</i>₁(<i>x</i>) ⊕ <i>s</i>₁ then by evaluating the equation <i>y</i>₁ = <i>T</i>₀(<i>x</i>₁) ⊕ <i>T</i>₂(<i>x</i>₁ ⊕ (<i>r</i>₁ ⊕ <i>r</i>₂)) ⊕ (<i>s</i> ⊕ <i>s</i>₁) calculated; this corresponds in the unmasked case to the application of the table<i>T</i>₁ defined picture. The application of the through the table<i>T</i>₂ defined mapping is analogous.

The technology disclosed in WO 03/017067 A2 thus enables the memory space required in the main memory to be halved or, if the method is used several times, reduced to a power of two fraction. Furthermore, WO 03/017067 A2 teaches the division of a large predetermined table into two smaller tables, which are then superimposed in the manner described above in a masked RAM table.

The object of the invention is to provide a technique for spy-out-calculated masked values ​​according to a predetermined image, which requires only a small amount of working memory with high spy protection. In particular, the invention should be suitable for use with portable data carriers.

According to the invention this object is achieved by a method having the features of claim 1, a computer program product according to claim 14 and a device, in particular a portable data carrier, according to claim 15. The dependent claims relate to preferred embodiments of the invention.

The invention is based on the basic idea of ​​sequentially switching all given images in the calculation of each entry in the masked table. In other words, when calculating each entry in the masked table, at least one input value of one of the predefined maps is determined as a function of at least one result value of another of the predefined maps. This operation requires little or no additional processing time; However, it increases the complexity of the process, making it particularly spy-proof.

The mappings can either be directly connected in series or indirectly, namely via at least one masking - that is, an existing masking type changing mapping or calculation rule - be connected in series.

In preferred embodiments of the invention, in the calculation of the masked result value, the at least one further image is evaluated in a direction which is opposite to the direction in the calculation of the entry in the masked table. As a result, the application of this further mapping, which took place during the calculation of the table entry used, can be reversed. Preferably, maskings that were used in the calculation of the masked table are also eliminated.

The first predetermined mapping, which defines the result value to be calculated in the non-masked case, is not evaluated in the preferred embodiment in the calculation of the masked result value. Indirectly, the first given mapping naturally flows into the result value, via the masked table. Preferably, the mappings are given for unmasked input and result values; however, it is also possible to use masked default images - eg masked by a predetermined, constant masking function - be used.

In advantageous embodiments, the predetermined mappings and / or reversals thereof are defined at least partially by a respective table located in a read-only memory. These tables are preferably one-unique. In order to achieve this, in some embodiments, empty data (<i>padding</i>) be provided. The masked table is preferably written to a working memory.

The computer program product according to the invention has program instructions in order to implement the method according to the invention. Such a computer program product may be a physical medium, eg a semiconductor memory or a floppy disk or a CD-ROM. However, the computer program product may also be a non-physical medium, eg a signal transmitted over a computer network. In particular, the computer program product may contain program instructions that are inserted into it in the course of the production or the initialization or the personalization of a portable data carrier.

In particular, the device according to the invention can be a portable data carrier, for example a chip card or a chip module.

In preferred developments, the computer program product and / or the device have features which correspond to the features mentioned in the present description and / or the features mentioned in the dependent method claims.

Further features, objects and advantages of the invention will become apparent from the following description of several embodiments and alternative embodiments. Reference is made to the schematic drawings in which:<ul id="ul0001" list-style="none"><li>1 shows an overview with functional units of a portable data carrier and data structures according to an embodiment of the invention,</li><li>2 shows an exemplary representation of calculation steps in generating a masked table, and</li><li>3 shows an exemplary representation of calculation steps when determining a masked result value.</li></ul>

The data carrier 10 shown schematically in FIG. 1 is in the present embodiment as a chip card (<i>Smart card</i>) or chip module - eg as SIM (<i>Subscriber Identity Module</i>) for a mobile telecommunication device - formed. The data carrier 10 has a processor 12, a memory 14 and an interface circuit 16 for contactless or contact-based communication with an external terminal (not shown).

In a manner known per se, the memory 14 is subdivided into a plurality of memory areas, which are configured in different technologies. In the exemplary embodiment described here, a read-only memory 18 configured as a mask-programmed ROM and a main memory 20 configured as a volatile RAM are provided. Furthermore, the data carrier 10 has a non-volatile rewritable memory 22, which may be, for example, an EEPROM or a flash EEPROM or a ferroelectric memory (FRAM). In alternative embodiments, the read-only memory 18 and / or the main memory 20 may be designed wholly or partly in EEPROM and / or flash EEPROM and / or FRAM technologies.

The methods described below are performed by the processor 12 of the data carrier 10. The methods are implemented in the form of program instructions (not shown) which are contained in the read-only memory 18 and / or the non-volatile rewritable memory 22.

In the present embodiment, the read-only memory 18 contains two tables 24, 26 with eg 256 entries of 1 byte each. These tables 24, 26 are derived from given figures, the example needed for cryptographic methods. More specifically, in the present embodiment, the tables 24, 26 correspond to the inversions of the given maps. During operation of the data carrier 10, a further table T 28 is calculated from the tables 24, 26 and written into the main memory 20. This table T 28 has the same size as each of the tables 24, 26, ie 256 bytes in the present example. Details of the calculation and use of Table T 28 are explained below.

Fig. 2, Fig. 3 and Fig. 4 illustrate a particularly simple embodiment of the process according to the invention. There are pictures here<i>T</i>₁ and <i>T</i>₂ predetermined, whose input and result values ​​each <i>b</i> Have bit. In other words, the pictures are<i>T</i>₁ and <i>T</i>₂ for all values ​​x in the range 0 ≤ x &lt;2^<i>b</i> define and deliver results in the same range. It is further assumed that the illustrations<i>T</i>₁ and <i>T</i>₂ one-unique, so that every picture <i>T</i>₁ and <i>T</i>₂ a permutation on the set {0, 1, ..., 2^<i>b</i>-1} represents. This condition is often met by mappings used for cryptographic techniques.

Because of their one-uniqueness, the pictures are <i>T</i>₁ and <i>T</i>₂ reversible; So there are reversals<i>T</i>₁^-1 and <i>T</i>₂^-1 with x = <i>T</i>_<i>i</i>(<i>T</i>_<i>i</i>^-1(<i>x</i>)) <i>T</i>_<i>i</i>^-1(<i>T</i>_<i>i</i>(<i>x</i>)) for all x ∈ {0, 1, ..., 2^<i>b</i>-1} and <i>i</i> = 1, 2. These inverse functions <i>T</i>₁^-1 and <i>T</i>₂^-1 be in the present embodiment by the tables in the read-only memory 18 24, 26 with 2 each^<i>b</i> Entries are defined for each b bit. In alternative embodiments, however, arithmetic instructions which contain the inverse functions can also be contained in the read-only memory 18<i>T</i>₁^-1 and <i>T</i>₂^-1 to implement. Such arithmetic rules can in turn be based on tables.

Tables 24, 26 have no masking. Therefore, the tables 24, 26 could possibly be accessed with an unmasked value x as a table index. However, this should be avoided for reasons of spying protection, because otherwise an attacker could possibly obtain information about the secret value x. Therefore, a cryptographically secure method is to be implemented, through which the mappings<i>T</i>₁ and <i>T</i>₂ for masked input values <i>x</i>₁. <i>x</i>₂ let calculate, resulting in masked result values <i>y</i>₁<i>y</i>₂ be achieved.

The method described here consists of two stages. In a preparatory stage, which is illustrated in FIG. 2, masking parameters are generated and the table T 28 is applied to the read-only memory 20 in a masking calculated according to these parameters. In a second stage, either a masked result value<i>y</i>₁ by accessing each of tables 28 and 26 or a masked result value <i>y</i>₂ each calculated by accessing Tables 28 and 24. The former variant is shown in FIG. 3 illustrated. This second stage can be repeated as often as desired in both variants. However, depending on the demands placed on cryptographic security, the masked table T 28 is usually provided only a few times - eg for a single pass of a cryptographic method - and then recompute the masked table T 28 with other masking parameters.

For the calculation of the masked table T 28 initially independent, evenly distributed random numbers <i>r</i>. <i>s</i>. <i>t</i> ∈ {0, 1, ..., 2^<i>b</i>-1} is selected as the masking parameter. Then the table T 28 is calculated such that for the table entries y at all index positions<i>x</i> ∈ {0, 1, ..., 2^<i>b</i>-1} holds: <maths id="math0001" num="(1)"><math display="block"><mrow><mi>T</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo><mi mathvariant="normal"> </mi><mo>:</mo><mo>=</mo></mrow><mi mathvariant="normal" /><mi>y</mi><mi>     With     </mi><mi>y</mi>&lt;mi /&gt;<mo>=</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><mi>x</mi><mo>⊕</mo><mi>r</mi><mo>)</mo><mo>⊕</mo><mi>s</mi></mrow><mo>)</mo><mo>⊕</mo><mi>t</mi></mrow></mrow></math><img file="EP1615098A2_D0001.tif" /></maths>

In the implementation on the data carrier 10, definition (1) can only be used directly for calculating the table entries T (x) if the images <i>T</i>₁ and <i>T</i>₂ in addition to Tables 24, 26 are available. This is usually not the case. Therefore, the following equation derived from Definition (1) is used:<maths id="math0002" num="(2)"><math display="block"><mrow><mi>T</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo><mi mathvariant="normal"> </mi><mo>:</mo><mo>=</mo></mrow><mi mathvariant="normal" />&lt;mi /&gt;<mi>y</mi><mi>     With     </mi><mi>x</mi>&lt;mi /&gt;<mo>=</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mrow><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup></mrow><mrow><mo>(</mo><mi>T</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo><mo>⊕</mo><mi>t</mi></mrow><mo>)</mo><mo>⊕</mo><mi>s</mi></mrow><mo>)</mo></mrow><mo>⊕</mo><mi>r</mi></mrow></math><img file="EP1615098A2_D0002.tif" /></maths>

To calculate the table T 28, for example, in a program loop, the value of y from 0 to 2^<i>b</i>-1 are counted up. By evaluating equation (2) it can then be determined for each value of y at which index position x this value is to be written in the memory area 20 provided for the table T 28 in the main memory 20.

After the table T 28 has been calculated, in the second process stage, the figures <i>T</i>₁ and <i>T</i>₂ be evaluated with masked input and result values. Fig. 3 illustrates the evaluation of the figure<i>T</i>₁ with a masked input value <i>x</i>₁ : = <i>x</i> ⊕ <i>r</i>₁ where a masked result value <i>y</i>₁ : = <i>T</i>₁(<i>x</i>) ⊕ <i>s</i>₁ should be calculated. The masking of the input or the result value is thus by the masking parameters<i>r</i>₁ and <i>s</i>₁ given; These masking parameters are used in the course of the execution of the cryptographic method as independent, uniformly distributed random numbers in the field<i>r</i>₁. <i>s</i>₁ ∈ {0, 1, ..., 2^<i>b</i>-1} determined. The masked result value<i>y</i>₁ is then determined according to the following equation: <maths id="math0003" num="(3)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>=</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>T</mi><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>⊕</mo><mrow><mo>(</mo><mi>r</mi><mo>⊕</mo><msub><mrow><mi>r</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>)</mo><mo>⊕</mo><mi>t</mi></mrow><mo>)</mo><mo>⊕</mo><mrow><mo>(</mo><mi>s</mi><mo>⊕</mo><msub><mrow><mi>s</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>)</mo></mrow></mrow></mrow></math><img file="EP1615098A2_D0003.tif" /></maths>

Although in equation (3) the figure <i>T</i>₁ is being calculated, there is currently no access to the table 24 which is the inverse function <i>T</i>₁^-1 Are defined. Furthermore, all the intermediate results resulting from the calculation according to FIG. 3 are independent of the unmasked values ​​x and y because of the additional maskings. Even if an attacker succeeds in spying on the calculation process of Fig. 3 and the various intermediate results, for example by means of a side channel attack, the attacker could not derive any information about the values ​​x and y to be kept secret.

The calculation of the figure <i>T</i>₂ takes place analogously. Here is a masked input value<i>x</i>₂ : = <i>x</i> ⊕ <i>r</i>₂ given, and it is a masked result value <i>y</i>₂ : = <i>T</i>₂(<i>x</i>) ⊕ <i>s</i>₂ to calculate. Again, the masking parameters<i>r</i>₂ and <i>s</i>₂ independent, evenly distributed random numbers in the range <i>r</i>₂. <i>s</i>₂ ∈ {0, 1, ..., 2^<i>b</i>-1}. The following equation is then evaluated:<maths id="math0004" num="(4)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><mi>T</mi><mrow><mo>(</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>⊕</mo><mrow><mo>(</mo><mi>s</mi><mo>⊕</mo><msub><mrow><mi>r</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>)</mo></mrow><mo>)</mo><mo>⊕</mo><mi>r</mi></mrow><mo>)</mo><mo>⊕</mo><mrow><mo>(</mo><mi>t</mi><mo>⊕</mo><msub><mrow><mi>s</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>)</mo></mrow></mrow></mrow></math><img file="EP1615098A2_D0004.tif" /></maths>

The exemplary embodiment described so far is generally usable because of the various re-masking (ie masking changes) at least for cryptographic methods in which Boolean masking is used. In particular, other masking parameters can be used in the table accesses than in the calculation of the table T 28.

In alternative embodiments, the table T 28 is calculated specifically for masking parameters, which also in the second process stage - that is, when evaluating the given mappings <i>T</i>₁ and <i>T</i>₂ - be used. It then applies<i>r</i> = <i>r</i>₁ and or <i>t = s</i>₂, Alternatively or additionally, the masking can also be used for calculations in which the illustrations<i>T</i>₁ and <i>T</i>₂ be applied consecutively, simplified or eliminated. It will then either<i>s</i> = <i>s</i>₁ ⊕ <i>r</i>₂ set if <i>s</i>₁ ≠ <i>r</i>₂ applies, or it will <i>s</i> = <i>s</i>₁ = <i>r</i>₂ selected. In all these alternatives, the resulting intermediate results are independent of the values ​​x and y to be kept secret. The advantage of these alternatives is the lower computational effort for a single evaluation; however, a new table T 28 may need to be calculated more frequently.

The exemplary embodiments described so far were based on a Boolean masking, that is, an XOR combination with a constant masking parameter. However, in alternative embodiments, other masking rules may be used. Such per se known masking rules are, for example, the modular addition, the modular subtraction, the modular multiplication, which for the IDEA algorithm (<i>International Data Encryption Algorithm</i>), modified multiplication and generally affine mappings. The modular addition with a constant addend as masking parameter is also known as "arithmetic masking". For example, the module used in arithmetic masking may have a power of two - often 2^8th or 2¹⁶ or 2³² - or the value 2¹⁶ + 1; the latter is also used for IDEA multiplication.

In a general formulation of the hitherto concretely specified exemplary embodiments, arbitrary permutations ρ are used as masks_<i>i</i>, σ_<i>i</i> on the set {0, 1, ..., 2^<i>b</i>-1} for <i>i</i> = 1, 2 considered. The permutations ρ_<i>i</i> serve here to mask input values, while the result values ​​are determined by the permutations σ_<i>i</i> be masked. If the permutations ρ_<i>i</i>, σ_<i>i</i> can be present, the table T 28 in the main memory 20 by means of the following definition of the table entries T (x) for all x ∈ {0, 1, ..., 2^<i>b</i>-1} are calculated; this definition is a generalization of the definition (1):<maths id="math0005" num="(5)"><math display="block"><mrow><mi>T</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo><mi mathvariant="normal"> </mi><mo>:</mo><mo>=</mo><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></mrow></math><img file="EP1615098A2_D0005.tif" /></maths>

To get out of that with the permutation ρ₁ masked input value <i>x</i>₁ : = ρ₁(<i>x</i>) with the permutation σ₁ masked result value <i>y</i>₁ : = σ₁(<i>T</i>₁(<i>x</i>)), the following equation is evaluated, which is a generalization of equation (3): <maths id="math0006" num="(6)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>=</mo><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>T</mi><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></math><img file="EP1615098A2_D0006.tif" /></maths>

Accordingly, the calculation of <i>y</i>₂ : = σ₂(<i>T</i>₂(<i>x</i>)) out <i>x</i>₂ : = ρ₂(<i>x</i>) by the following equation: <maths id="math0007" num="(7)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><mrow><mi mathvariant="normal">T</mi><mo>(</mo><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></math><img file="EP1615098A2_D0007.tif" /></maths>

In the generalization just described according to equations (5) - (7), the two maskings ρ₂ and σ₁ be independent of each other. However, in alternative embodiments, the overhead required for the masking (masking change between the cascaded mappings) can be reduced by using ρ₂ = σ₁ and instead of equations (5) - (7) the following equations (8) - (10) are used; the definition (8) holds for all x ∈ {0, 1, ..., 2^<i>b</i>-1}: <maths id="math0008" num="(8)"><math display="block"><mrow><mi>T</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo><mi mathvariant="normal"> </mi><mo>:</mo><mo>=</mo></mrow><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></math><img file="EP1615098A2_D0008.tif" /></maths><maths id="math0009" num="(9)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>=</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msup><mrow><msub><mrow><mi mathvariant="normal">σ</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>T</mi><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></math><img file="EP1615098A2_D0009.tif" /></maths><maths id="math0010" num="(10)"><math display="block"><mrow><msub><mrow><mi>y</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><mi>T</mi><mrow><mo>(</mo><msub><mrow><mi mathvariant="normal">ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mrow><mo>(</mo><msup><mrow><msub><mrow><mi>T</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>)</mo></mrow><mo>)</mo></mrow><mo>)</mo></mrow></mrow></math><img file="EP1615098A2_D0010.tif" /></maths>

The prerequisite for the applicability of the alternative embodiment according to equations (8) - (10), however, is that the masking ρ₂ = σ₁ is self-inverse, so that ρ₂ = ρ₂^-1 - and thus synonymous σ₁ = σ₁^-1 - applies. This requirement is always fulfilled, for example, in the case of Boolean masking, but not, for example, in the case of arithmetic masking. If necessary, an additional independent masking must be introduced and masked here.

In all embodiments described so far were as given pictures <i>T</i>₁ and <i>T</i>₂ Permutations on the set {0, 1, ..., 2^<i>b</i>-1} provided. Such permutations can be predefined directly by the cryptographic method. However, alternative embodiments of the invention can also be used in connection with cryptographic methods, in which tables with 2^<i>b</i> Entries are provided for each b 'bit, where <i>b '</i> &lt; <i>b</i> applies and every entry in every table occurs the same number of times. For reasons of security, these conditions are fulfilled in many cryptographic methods, such as, for example, in the S-boxes of the DES algorithm (<i>Data Encryption Standard),</i> the 2 each⁶ Have entries of 4 bits each.

In the stated alternative embodiments, each table with b 'bit payload per entry is random or systematic with each b - b' bit of empty data (<i>padding</i>) per word to a word width of b bits, so that an extended table with 2^<i>b</i> Entries to each <i>b</i> Bit results and everyone <i>b</i> Bit wide entry in the extended table occurs exactly once. The extended table is then one-unique and can be used in all the embodiments described above. In further embodiments, several predefined tables become a one-unambiguous table with 2^<i>b</i> Entries to each <i>b</i> Bit summarized. Again, if necessary, blank data may be inserted to ensure reversibility. Alternatively or additionally, such empty data can also be used to match the sizes of two predefined tables to one another.

The pictures <i>T</i>₁. <i>T</i>₂ or their inverse functions <i>T</i>₁^-1. <i>T</i>₂^-1 are in many embodiments of the invention as tables - such as tables 24, 26 - given. In alternative embodiments, on the other hand, calculation instructions can be contained in the read-only memory 18, which the illustrations<i>T</i>₁. <i>T</i>₂ and or <i>T</i>₁^-1. <i>T</i>₂^-1 at least partly implement. This may be useful, in particular, for images that are relatively easy to calculate, for example for images that are used in conjunction with masking rule transitions. The cryptographic security of the calculation rules need not or hardly be respected.

Calculation rules that the illustrations <i>T</i>₁. <i>T</i>₂ and or <i>T</i>₁^-1. <i>T</i>₂^-1 can be based on tables. In particular, a table-based calculation method can be used. Such a method can eg The method of the present invention, which can be recursively invoked to reduce the amount of memory in memory 20 to one quarter, one eighth, ... to reduce. Other applicable methods are described in the co-pending application of the same inventors having the same filing date and title and in WO 03/017067 A2; the content of these documents is hereby incorporated in full in the present description.

In the description so far, for reasons of clearer presentation, only the case of two given illustrations has been used <i>T</i>₁. <i>T</i>₂ expressly mentioned, which should be summarized in a table T 28 in memory 20. It will be understood that the method also applies to three or more predetermined figures<i>T</i>_<i>i</i><i>, i =</i> 1, 2, ..., n, can be applied. The above equations are then to be adjusted in a manner obvious to one skilled in the art. The space required in the working memory 20 is reduced - compared to the space requirement of all unmasked tables in the read-only memory 18 - to 1 /<i>n</i>, However, the computational effort increases, so that a meaningful balance must be made.

The details described above are not to be construed as limitations on the scope of the invention, but rather serve as examples of preferred embodiments. Many other modifications are possible and obvious to those skilled in the art. The scope of the invention should therefore be determined not by the illustrated embodiments, but by the claims and their equivalents.