Modular exponentiation with randomized exponents

Translation of description of equivalent WO 2004070497 A2

description

Modular exponentiation with randomized exponent

The present invention relates to cryptographic systems and in particular to apparatus and methods for determining a result of a modular exponentiation within a cryptosystem.

In particular, in algorithms for the digital signature or other cryptographic applications, it is necessary secret data, to protect such. As a private key of the RSA algorithm prior to the so-called side-channel attacks. Such attacks are based on an analysis of current, power or radiation profile of a circuit treating the algorithm. Based on an evaluation of such a power profile of the circuit, it is possible to make statements about the secret key.

The basic concept of the digital signature on the basis of

RSA algorithm is illustrated with reference to FIG. 6, as described in the "Handbook of Applied Cryptography" by Menezes, van Oorschot, Vanstone, CRC Press, 1996, Chapter 11.3. To perform the digital signature 60 signed an entity A a message m. This allows each entity B to verify the signature of the entity A and recover the message m from the signature.

In the signature generation, as at 60 is shown in Fig. 6 illustrated, calculates the entity A to the signature, modular exponentiation at the base m, with the secret key d and the modulus N by the equation shown in block 60. As is known, belongs to the secret key d a public key e, which is needed by an entity B for one ne verification, as shown at 62 in Fig. 6. The entity B takes the corresponding public key to d e as exponent and exponenziert of the Entity A generated signature S with the public key. After a final reduction with respect to the modulus N results in a verified message '. If the entity B have the unsigned message known, it may be due to a comparison of m 'and determine whether the signature S actually came from the entity A or not. In other words, this means that the entity B can determine if the private key d is used for the signature actually belongs to the public key e. Does the entity B for other reasons that the entity A is authentic, it is clear that verification, ie the modular exponentiation of the signature with the public key as exponents, immediately the message m, since the second condition at 62 in FIG. 6 is fulfilled safely.

In an attacker might be the desire to detect the secret key d of the entity A, which is used for the signature at 60 in FIG. 6. For this, the attacker could conduct a performance analysis or a similar side- channel attack. To ward off such an attack based on a statistical side channel attack (DPA, EMA) usually randomization z. B. of the exponent in the RSA signature creation used, s = m^d mod N to be replaced here by s = m^d mod N, the result should be the same, the exponent d 'is, however, different for each calculation with the same key d. In general, the secret key of the pair (d, N) for the RSA algorithm. The public key consists of the pair (e, N). The module is typically known, so that the only secret information of the exponent d. It is also known that the product of d and e satisfies the following equation:

dxe = 1 mod λ (N)

λ (N) is the known Carmichael function. For the randomized exponent not be arbitrary. Therefore, usually as for Rando ization of the exponent is a multiple of the Carmichael function λ (N) needed. This however is not possible as a rule.

Furthermore, it is known for the signature-creation the Chinese Remainder Theorem (CRT) to use, which is also described in the Handbook of Applied Cryptography in chapter 14.5. In particular, a specific expression of CRT is used, which is known as Garner's algorithm. The Chinese remainder theorem is used to return the entire exponentiation on two exponentiations modulo p and q. The Chinese remainder theorem is particularly interesting, therefore, since the two exponentiations be performed with exponents that only half the length as the origi- nal exponent (d or e). A disadvantage, however, that the Chinese remainder theorem can only be applied if additional parameters p, q are present, the product of p and q the module N results. To secure the signature calculation using the Chinese Restsat- indices it is necessary to protect both exponentiations, ie provided with a randomization to prevent side channel attacks. The Carmichael functions loud while λ (p) = p-1 and λ (q) = q 1. These two Carmichael functions must be charged extra.

Regardless of whether the RSA algorithm is used with the Chinese remainder theorem or without the Chinese Remainder Theorem, it is undesirable to use no randomization of the exponent, since it is a security problem arises in circumstances. For this reason, there has been proposed a randomization of the exponent using the Euler Phi function Phi (N) carry out. However, randomization using the Euler phi function presupposes knowledge of Phi (N). Normally Phi is not gege- ben and must therefore, if this randomization is to be used, will be charged extra. An alternative approach is, instead of the Euler phi-function to be used with respect to the numerical value smaller Carmichael function λ-λ (N). This method has the advantage that the same security of randomized exponent is shorter so that computing time advantages arise over the use of Euler's phi function. A disadvantage of this process is again the fact that is λ (N) needed. The Carmichael function λ (N) must therefore be charged extra and is not available from vornher-.

An alternative randomization is that the exponent is to be randomized in two divided exponents. This has the advantage that you do not need additional information. On the other hand, one disadvantage is that the calculation takes as the other alternatives described, using the Euler phi function or the Carmichael λ function twice as much time to complete.

The object of the present invention is to provide a

creating concept for determining a result of a modular exponentiation within a cryptosystem that is secure and efficient.

This object is achieved by a device for determining a result in accordance with claim 1 or 6, a method for determining a result in accordance with claim 12 or 13 or by a computer program according to claim fourteenth

The present invention is based on the realization that the randomization of the exponent is the product of public and private key less the value "1", as exd - is 1, always a multiple of the Carmichael function λ (N) and thus used for randomization are can It should be noted that only one note, there exists that the term exd -.. 1 is a multiple of the Carmichael function However, it is not known which Multiples of expression exd - 1. However, such knowledge is not necessary to randomize the exponent. An advantage of the inventive randomization auxiliary number, as the term exd - is characterized 1 hereinafter described, is that the calculation of this term only from the outset known quantities are required, namely the public and private keys. It must be calculated no Euler phi function or no Carmichael λ function. Instead, only need a simple multiplication of the public key and the private key in the case of an application without Chinese Remainder Theorem or - with CRT - a simple multiplication between the public key and the first or second private key d auxiliary_p or d_q be carried out to then be subtracted from this value the value "1", to reach the auxiliary randomization number.

Although in principle it would be possible especially in general purpose computers or multifunctional crypto CPUs to compute the Euro- lersche phi function or the Carmichael λ function, it is in particular for example, signature CPUs, such as those used for example in chip cards, not possible or only with great effort, to calculate such specific functions. According to the invention, this disadvantage is bypassed by the randomization the randomization auxiliary number is used, the less the product of the private key and the public key to the value "l^λ is calculated.

The inventive concept for determining a result of a modular exponentiation using a randomization of the exponent is thus advantageous in that it reaches a high level of security due to the randomization that there is little effort to implement and is particularly suitable for protocols where the Euler phi function or the Carmichael λ function is not provided. Preferred embodiments of the present invention will be explained with reference to the accompanying drawings.

Fig. 1 shows a block diagram of the inventive concept with randomization of the exponent without using the Chinese remainder theorem;

2 shows a sequence of steps according to a preferred embodiment of the present invention to the concept of Fig. 1.

Figure 3 shows an alternative implementation of the present invention in which the Chinese Remainder Theorem is used.

Figure 4 is a detailed illustration of the means for modular exponentiation with a first and / or second partial keys.

Figure 5a shows a detailed implementation of the modular exponentiation with the first partial key of FIG. 3.

5b is a detailed implementation of the modular exponentiation to the second partial key.

5c is a detailed implementation of the means for combining the results according to the Chinese remainder theorem of Fig. 3. and

Fig. 6 is an overview diagram illustrating a known signature algorithm and a known Ve- rifikationsalgorithmus. Fig. 1 shows a schematic block diagram of an apparatus for determining a result of a modular exponentiation within a cryptographic system having a first and an associated second key. The apparatus comprises an input device in the cryptographic parameters m, E, D and N are provided. The input stage is designated in FIG. 1 by 10. Here, m is the message to be signed, for example, is. E represents the first key, which is also known as public key referred to hereinafter, d represents the second key of the cryptosystem is, which is hereinafter also referred to as secret key. Finally, N represents the module with respect to which is to carry out the modular exponentiation. It should be noted that the modulus N p and q may be formed from a product of the two numbers, as is known from the RSA algorithm. however for the concept illustrated in FIG. 1, these two auxiliary numbers p and q are not required. The entire calculation can take place exclusively using the input parameters m, e, d and N.

The input stage 10 is a means 12 for calculating a randomization auxiliary number on the basis of the product of the first key e and the second key d less the number "l^Λ shown. Preferably the corresponding

Randomization auxiliary number Exact phrase exd - 1. Alternatively, however, a multiple of this expression could be used, but in this case is to ensure that this multiple expression exd - 1 to be used as a randomization auxiliary number may, at the same time a multiple of λ-Carmichaelschen function.

The means 12 for calculating is a means 14 for obtaining a random number and calculating a randomized exponent downstream, executes the following equation: d ^{^} = D + R x (exd - 1).

In other words, the combined device 14 to obtain the product of the random number and the randomization ative auxiliary number with the exponent d preferably additively. then there exists a randomized ter exponent at the output of the device 14th Using the randomized exponent calculated by the device 14, then operates a device 16 for calculating the modular exponentiation in order to obtain the result S of the modular exponentiation, which may be a digital signature typically. An output stage 18 finally is provided to output the signature in any form, for example graphically, binary, or on any other way.

In the embodiment shown in Fig. 1 only the exponent is randomized. As will be explained below, however, with reference to FIG. 2, may also produce, in addition to the exponents who are randomized to be signed or to be encrypted message m. Regarding the notation in FIG. 2, it should be noted that this is already a register custom implementation. To carry out the algorithm shown in FIG. 1, including the additional randomization of the message to be signed m the register R, X, D, m, n 'and S are needed. In the left column of

Step sequence of FIG. 2 are in these registers. In the right column of the sequence of steps of FIG. 2 on the other hand is the mathematical operation to be performed, then to write the result of this operation to the left with respect to the register represented by leftist arrow.

The algorithm shown in Fig. 2 is presented below as a sequence of steps, although it may just as well be interpreted as a collection of various devices. In an input step 20, the data m, E, D and N are provided. In a step 21 the randomization auxiliary number is first exd - 1 and calculated into the Register X written. In a step 22, a random number is then compared with a length which is preferably between 16 and 32 bits are selected and written to the R register. In a step 23 the contents of register X is then multiplied by the contents of register R and the result of this multiplication is again written in the X register. In a step 24 the randomization of the exponents is performed, as shown at 14 in FIG. 1. This takes place in particular in that the content of the register X is the second key, ie, the private key d, added, wherein the result of this addition is again written into the D register. In a step 25, a random number is preferably selected with a length between 16 or 32 bits and written in the Regis- ter R again. In a step 26, the content of the register R is multiplied by the modulus N, being added to the result of this multiplication nor the message to be signed m.

The overall result of this addition is in turn written to a register for the message to be signed, which is denoted by m. The step 26 thus provides the additional randomization of the value to be processed, so the message to be signed, is to achieve additional security. In a step 27, a random number is then selected, for example with a length between 16 or 32 bit and written into the R register. In a step 28, a module-randomization is performed by the module N is the currently selected random number that is in the register R multiplied. The result of this multiplication is written into a register N '. In a step 29, a modular exponentiation is performed, wherein the content of the register m, which corresponds to the randomized message, is used as a base, the content of the register D, which contains the randomized exponent is used as the exponent, and wherein the content of the register N ', containing the randomized module as a module the modular lar exponentiation is used in step 29th The result of this modular exponentiation is written into the S registers. In a final reduction step 3, the content of the register is then a S modular reduction under using the supplied input in the step 20 the module is performed to finally obtain the desired result, which is written in the S register. In an output step 31 the contents of register S is then outputted, which is the modular exponentiation equal, which would also be obtained on the basis of the input provided in step 20 non-randomized parameters.

. In the embodiment shown in Figure 2 three randomization are used, namely the randomization of the module using the randomization auxiliary number exd - 1 (step 24), the randomization of the message in step 26 and the randomization of the module in step 28 . It should be noted that optionally, the randomization of the exponent with the invention RAN domisierungs auxiliary numbers alone, combined with the randomization of the message to be signed m and / or combined with the randomization of the modulus N can be performed.

It is also noted that the randomized exponent due to the addition of the expression R x (exd - 1) in block 14 of Figure 1 is a number greater than the exponent d (or in principle, e) is originally used.. After the key but anyway already can accept stately sizes, for example 1024 or 2048 binary digits, it is preferred as R Randomisierungszahl to take a relatively small number. On the other hand too small a random number would make the effect of randomization to naught. It is therefore preferred to use for the randomization of the exponent a random number that is greater than or equal to 8 bits and less than or equal to 128 bits. Preferably, a length of the random number is between 16 and 32 inclusive is used as shown in Fig. 2 is. It should also be noted that for the random number selected in steps 22, 25 and 27 of Fig. 2 are either always the same random number may be used, or various types of random numbers may be used. Will always the same random number is used, this random number must be generated only once and can then be stored in a separate random number register. This approach is advantageous in that once a random number must be generated. On the other hand a private random number register is required. an own random number If, however, in each step 22, 25 and 27 produced, which will be different with very high probability of the produce in each other's steps random numbers, so no separate random number register is needed, which could be even attacked under certain circumstances. The latter embodiment is therefore preferred, if a sufficiently strong performance random number generator is available.

In view of the detail in the steps 22, 25 and 27 selected random numbers should also be noted that the same do not necessarily have in each step are the same length. With regard to a discussion of the length of the random number that is selected at step 22 for the randomization of the exponent, reference is made to the discussion above. The random numbers are selected in steps 25 and 27 may be smaller or larger, with a total of smaller random numbers help to reduce the computational effort, but a minimum size of the random number should be maintained in order not the concept of randomization total in to ask the question. Also, the random numbers, which are selected in steps 25 and 27 should therefore have a length that is greater than or equal to 8 bits.

Fig. 3 shows a schematic block diagram of the inventive concept, but now using the Chinese see remainder theorem CRT. An input stage 100 represents cryptographic input parameters that now, however, as the Chinese remainder theorem to apply, more input parameters include, as in the embodiment shown in FIG. 1, for example. Specifically, the message to be signed m, the public key e, a first private key part dp, a second private key d be part_q, The numbers p, q, and the parameter q i_nv provided. In Fig. 3 is illustrated how the numbers d_p, d_q and q i_nv can be calculated from the quantities d, p and q.

The input stage 100 feeds means 102 for performing a first modular exponentiation (102a) using one of the first key d derived first subkey d_pTo obtain a first intermediate result, and for performing a second modular exponentiation (102b) using a first key derived from the second partial key d_qTo obtain a second intermediate result. The functionality of the input device to perform using the first partial key DP is designated in FIG. 3 with 102a, while the functionality of means for performing the modular exponentiation with the second partial key d_q is designated by 102b. The two devices 102a and 102b together form a device 102 for performing the first and second modular exponentiation using the respective subkey d_p and d_q, The block 102 provides as an output a first intermediate result S_p, Block 102b provides as a result a second intermediate result S_q, In one ner device 104 are the two intermediate results S_p and S_q combined according to the Chinese remainder theorem and particularly preferably in accordance with the Garner algorithm to finally return the result of the modular exponentiation, such as a signature, in the form of parameter S off, as illustrated by block 106 in FIG. 3. The means for performing, which is shown at 102 in Fig. 3, is divided into sub-units for each block 102a, 102b, and these subunits are represented schematically in Fig. 4, both for the block 102a, as well as for the block 102b. Specifically, the block comprises 102 a means 110 for calculating the auxiliary randomization number on the basis of the expression exd_p - 1. Analogously, contains the block 102b exd means for calculating the randomization auxiliary number on the basis of expression_q - Downstream of the first device 110 is a device 112 which receives a random number and then calculates the randomized exponent, either on the basis of the equation d_p + R x (exd_p - 1) for the block 102a, or on the basis of the equation d_q + R x (exd_q - 1) for setting up 102b, where R is the random number obtained by the block 112 in FIG. 4.

Finally, a modular exponentiation is carried out in the blocks 102a and 102b using the randomized exponent in a block 114 to the intermediate results S_p ,or. S_q to obtain.

In the following the functionality of the block 102 of device 102 of Fig. 3 with reference to FIG. 5a will be explained. In a first step 120, the randomization auxiliary number is ex dp - 1 calculated and stored in the X register. In step 122, a random number is selected and stored in the register R. In a step 124 the contents of register X and the content of the register R are multiplied with each other, the result of this multiplication is again stored in the register X. Then, in a step 126, the actual randomization of the exponents, namely the private key derived from the first partial key is d_p performed, and this result is stored in the register D. In a step 128, a random number is selected and stored in the register R again. In step 130, the message is now ran- misiert, namely analogous to step 26 of FIG. 2, but now instead of the module N of FIG. 2 with the first auxiliary module p in Fig. 5a. Then, in step 132, a random number will be re-elected, and multiplied in step 134, with the auxiliary module p. This now randomized auxiliary module which is stored in register p ', is used in a step 136, to the modular exponentiation in FIG. 5, step 136, shown. In a final step 138, then in step 136 in the register S_p written interim results yet with respect to the original auxiliary module p reduces to the first intermediate result S_p to obtain.

In Fig. 5b the analogous steps of the modular exponential tiation with a second partial key in block 102b of FIG. 3, where in Fig. 5b illustrated steps run basically the same as the corresponding steps of FIG. 5, but instead of first partial key d_p of FIG. 5 in Fig. 5b of the second partial key d_q is taken, and wherein instead of the first auxiliary module p in Fig. 5 in Fig., the second auxiliary module q is used 5b. Moreover, it is pointed out that the selected in FIGS. 5a and Fig. 5b random numbers may be independent of one another. Alternatively, however, the same random number could be read by a random number register in each corresponding step. In this respect are for the random numbers, the same conditions as they have been explained with reference to FIG. 2.

Fig. 5c, the designated by the in FIG. 3 by 104

Combiner executed implementation is to get out of the first intermediate result S_p and the second intermediate result S_q to obtain the result, for example in the form of the signature S.

The inventive concept is that - when the CRT is not used - a randomization of the exponent th principle - is buildable from the minimum RSA private data set, consisting of the modulus N, the public key e and the private key d - without further input parameters. Randomization is thus always possible, regardless of whether a security protocol, a Euler phi function, Carmichael λ function or something similar provides or not. The time required for the calculation of the number of randomization auxiliary functionality in the form of a multiplication and an addition is tocoprozessors present on any conventional crypto chip, such as. For example, in the form of a krypton. In addition, the randomization is apart from the steps of the generation or determination of the random numbers and slightly apart from the grown length of the exponent performance neutral. This means in other words that no substantial increase in the computational complexity and the calculation time takes place while at the same time a considerable degree of security is obtained, that is scalable with respect to the length of the random number.

Depending on the circumstances, the inventive method for determining a result of a modular exponentiation in hardware or in software may be implemented. The implementation may be on a digital storage medium, particularly a floppy disk or a CD with electronically Baren be read out control signals, which can cooperate with a programmable computer system such that the respective method is performed. Generally, the invention thus also consists in a computer program product having stored on a machine-readable carrier program code for performing the inventive method when the computer program product runs on a computer. In other words, the invention thus provides a computer program having a program code for performing the method is, when the computer program runs on to a computer. LIST OF REFERENCE NUMBERS

10 input stage

12 calculating the randomization auxiliary number

14 Get a random number and calculating a randomized exponent 16 calculating the modular exponentiation with the randomized exponent 18 output stage

20 input step

21 to 30 Abiaufschritte the algorithm without Chinese Remainder Theorem

60 signature verification equation 62 Equation 100 input stage 102 means for performing 102 a modular exponentiation with a first subkey 102b modular exponentiation with a second partial key 104 combining the results according to the Chinese remainder theorem 106 output stage

110 Calculate the randomization auxiliary number 112 will get a random number and computing the randomized exponent 114 computing the intermediate results

120-138 process steps of the algorithm for calculating the first intermediate result using the Chinese remainder theorem 140-158 process steps of the algorithm for calculating the second intermediate result, according to the Chinese remainder theorem