0001 The present invention concerns a secure method for performing an exponentiation operation, with application in particular in the field of cryptography. The invention applies in particular to cryptographic algorithms implemented in electronic devices such as smart cards. 0002 Many cryptographic algorithms are based on exponentiation calculations of the type UV{circumflex over ()}W modulo X, where U, V and X are integer numbers most often large in size, and W is a predetermined number. The numbers U, V can correspond for example to an encrypted text or one to be encrypted, a signed data item or one to be signed, a verified data item or one to be verified, etc. The numbers W and X can correspond to elements of keys, either private or public, used for encryption or decryption of the numbers U, V. 0003 One of these algorithms is the RSA (Rivest, Shamir and Adleman) algorithm, which makes it possible to obtain a signature or a decrypted message s using a private key comprising three integer numbers d, p and q, p and q being large prime numbers, the product of which is equal to N. In a typical example, d and N have 1024 bits, and p and q have 512 bits. 0004 Many works present the RSA algorithm in detail; it is however necessary to repeat here the basic principles of this algorithm, which makes it possible to calculate the signature s:

sm{circumflex over ()}d mod(p.q)m{circumflex over ()}d mod(N)

0005 The RSA algorithm can be implemented using the Chinese Remainder Theorem. Through the application of this theorem, the signature s is obtained by:

sm{circumflex over ()}d mod(N)CRT(sp, sq)

0006 The function CRT(sp, sq) is commonly referred to as the recombination formula according to the Chinese Remainder Theorem. The CRT function is calculated for example as follows:

CRT(sp, sq)sppY,

with:

Yip(sqsp) mod(q)

dpd mod(p1), spm{circumflex over ()}dp mod(p)

dqd mod(q1), sqm{circumflex over ()}dq mod(q)

ip(1/p) mod(q)

0007 The same algorithm makes it possible to verify the validity of the signature s of a message m by verifying that the equation:

ms{circumflex over ()}e mod(N)

0008 is satisfied. 0009 The numbers e and N form the public key associated with the private key (d, p, q); the numbers e and N verify the equations:

Npq

pgcd(e, (N))1

ed1 mod((N)),

0010 (N) being Euler's totient function defined by (N)(p1)(q1). 0011 It should be noted that all the elements d, p, q of a private key and all the elements e, N of an associated public key are odd. This is because, p and q being large prime numbers, they are necessarily odd. (N)(p1)(q1) is therefore even and Npq is odd. As e and (N) are mutually prime, e is odd. As ed1 mod((N)), ed is odd, and therefore d is also odd. 0012 Other algorithms, cryptographic or not, also use exponentiation operations of the type UV{circumflex over ()}W modulo X, possibly implemented by the Chinese Remainder Theorem, for example the Rabin-Williams cryptosystem or else the Diffie-Hellman key exchange modulo a composite number. 0013 A malicious user can possibly institute covert channel attacks, aiming to discover in particular confidential information (like for example the numbers d or p) contained and manipulated in processing performed by the calculation device executing an exponentiation operation. The best-known covert channel attacks are referred to as simple or differential. Simple or differential covert channel attack means an attack based on a physical quantity measurable from outside the device, and whose direct analysis (simple attack) or analysis according to a statistical method (differential attack) makes it possible to discover information contained and manipulated in processing carried out in the device. These attacks can thus make it possible to discover confidential information. These attacks have in particular been disclosed by Paul Kocher (Advances in CryptologyCRYPTO'99, vol. 1666 of Lecture Notes in Computer Science, pp. 388-397. Springer-Verlag, 1999). 0014 Amongst the physical quantities that can be exploited for these purposes, there can be cited the execution time, the current consumption, the electromagnetic field radiated by the part of the component used for executing the calculation, etc. These attacks are based on the fact that, during the execution of an algorithm, the manipulation of a bit, that is to say its processing by a particular instruction, leaves a particular print on the physical quantity under consideration, according to the value of this bit and/or according to the instruction. 0015 The aforementioned exponentiation algorithms have had to include countermeasures for preventing such attacks from succeeding. 0016 Paul Kocher proposed in particular, in the document WO 99/35782, a procedure which consists in particular of masking the derived variables dp, dq of the number d by the addition of a random integer number. More precisely, the variables dp, dq are not used directly in the algorithm, but are used in the form of masked numbers di*diri(p1), with i equal to p or q, and ri (rp or rq) random integer numbers, modified at each implementation of the algorithm. In one example disclosed in the document WO 99/35782, this procedure is used within the context of an RSA algorithm implemented according to the Chinese Remainder Theorem. The algorithm then breaks down as follows: 0017 First of all sp* and sq* are calculated:

sp*m{circumflex over ()}dp* mod(p)m{circumflex over ()}(dprp(p1)) mod(p)

sq*m{circumflex over ()}dq* mod(q)m{circumflex over ()}(dqrq(p1)) mod(q)

0018 Next the number s is calculated by means of the recombination formula:

ss*CRT(sp*, sq*)

0019 The equality ss* is deduced from the definition of dp, dq, dp*, dq* and Fermat's theorem, according to which A{circumflex over ()}(B1)1 mod(B) when B is a prime integer number and A is relatively prime with B. In the present case, the following is deduced from Fermat's theorem: 1

\begin{matrix} m^d_{p}^{*} = m^(d_{p} + r_{p} (p - 1)) \\ = m^d_{p} m^(r_{p} (p - 1)) \\ = m^d_{p} 1 [\mod (p)] . \end{matrix}

0020 Since m{circumflex over ()}dp*m{circumflex over ()}dp mod(p), this gives spsp*. A similar reasoning makes it possible to deduce sqsq*. Finally, as spsp* and sqsq*, ss*. 0021 The procedure disclosed in the document WO 99/35782 is in particular effective for countering differential covert channel attacks. It also complicates simple attacks. 0022 However, this procedure is not effective against a particular attack detailed below (which, for the sake of simplification, will subsequently be referred to as a CRT attack) within the context of an example relating to the RSA algorithm. More generally, the CRT attack can be envisaged for any algorithm implemented by means of the Chinese Remainder Theorem. 0023 In the example of an RSA algorithm implemented by means of the Chinese Remainder Theorem, the CRT attack makes it possible to obtain the number p of the private key. It has been seen previously that the recombination formula making it possible to calculate s is written:

sCRT(sp, sq)sppY,

with

Yip(sqsp) mod(q)

0024 If p, q have a bits (for example 512 bits), then ip, sp, sq have a bits, and so has Y. The product pY and the number s therefore have 2a bits. As sp has a bits, it is deduced therefrom that the a most significant bits of s are equal to the a most significant bits of the product pY. 0025 Furthermore, the Hamming weight H(Y) of the number Y can be obtained by a simple covert channel attack during the calculation of Y. It should be noted that the Hamming weight of the number Y is the number of bits at 1 in the number Y. 0026 Knowing the most significant bits of the product pY and the Hamming weight of the number Y, it is possible to find the number p by successive iterations as follows: 0027 an assumption is made on the value of b (for example b8) most significant bits of p and the corresponding b most significant bits of Y are determined from the most significant bits of the product pY, which are given by the value of s. The probability that the assumption on the b most significant bits of p is correct is then calculated from the Hamming weight of Y, measured by a covert channel; 0028 a reiteration is performed for each possible value of the b most significant bits of p and finally the most probable assumption for these b bits is adopted; 0029 a reiteration is then performed for each packet of b bits of p, until a sufficient number of bits of p is obtained. 0030 The procedure disclosed in the document WO 99/35782 is not effective against this CRT attack. This is because, in the document WO 99/35782, the recombination formula used is written:

sCRT (sp*, sq*)sp*pY*,

0031 with s, pY* having a size of 2a bits and sp* having a size of a bits. 0032 It is therefore possible, by means of a CRT attack as just described, to determine the number p from the known number s, the product pY* and the Hamming weight of (Y*). 0033 In view of the limitations of the procedure disclosed in the document WO 99/35782, one object of the invention is to propose a secure method for performing an exponentiation operation, protected against all attacks, including the CRT attacks as described above. 0034 Another object of the invention is to propose a secure method for performing an exponentiation operation, at least as efficient as the method disclosed in the document WO 99/35782, in particular in terms of circuit size and calculation time. 0035 Finally, another object of the invention is to implement a secure method for calculating an exponentiation operation, capable of being incorporated into any calculation method during which a calculation of the type UV{circumflex over ()}W modulo X has to be performed. 0036 With these objectives in view, the object of the invention is a secure method for performing an exponentiation operation during which an operation of the type UV{circumflex over ()}W modulo X is performed, U, V, X being integer numbers, W being an integer number used in the form of a number W* masked by a masking parameter chosen randomly at each execution of the method. 0037 According to the invention, the masking parameter is a fractional number. 0038 The numbers W, X are in practice numbers that must be kept concealed, like elements of a private key, and/or numbers derived from such a key. For example, if the method according to the invention is used within the context of an RSA algorithm implemented according to the Chinese Remainder Theorem, the number W can be the variables dp, dq used in a customary manner. The size of the numbers W, X is immaterial; it is for example 1024 bits. 0039 The use of a fractional random masking parameter, instead of an integer random masking parameter, makes it impossible to obtain information on the number W by means of a covert channel attack or a CRT attack, as will be seen more clearly below in some examples.

0040 According to preferred embodiments, the masking parameter is of the form R/K. R is a random integer number modified at each execution of the method. The size of the number R determines the security of the algorithm with respect to the so-called differential attacks; R can be chosen for example with a size of 32 bits. K is an integer number that is a divisor of the number (X), being Euler's totient function. K can be chosen constant or else can be modified at each execution of the method. The size of K is immaterial; it is for example close to the size of the number R. 0041 Advantageously, the masked number W* is of the form W*{overscore (W)}{overscore (R)}. {overscore (W)} is the default part of the result of the division of W by K, and {overscore (R)} is equal to the product of the masking parameter (R/K) and the number (X). 0042 The result U can then be expressed as a function of (U*){circumflex over ()}K modulo X, with U*V{circumflex over ()}W* modulo X. 0043 More precisely, the result U is equal to U(U*){circumflex over ()}KV{circumflex over ()}Z modulo X, with U*V{circumflex over ()}W* modulo X. Z is the remainder from the integer division of W by K. 0044 The method of the invention, as described above, can be used advantageously in a global cryptographic method. 0045 In an example that will be described more precisely, the cryptographic method is of RSA type, and is implemented according to the Chinese Remainder Theorem. In this case, the invention is used in particular for masking a possibly derived key (for example the derived keys dp, dq) by a masking parameter chosen randomly at each execution of the method, the masking parameter being a fractional number. 0046 Another object of the invention is an electronic component comprising a calculation circuit for implementing a method according to the invention, for example, but not necessarily, within the context of a cryptographic algorithm. 0047 Finally, another object of the invention is a smart card comprising said electronic component. 0048 The invention and the advantages ensuing therefrom will emerge more clearly from a reading of the following description of a particular embodiment of the invention, given purely for information only and with reference to the single accompanying figure. This is an electronic device making it possible to implement the invention. 0049 The single figure depicts in block diagram form an electronic device 1 capable of performing exponentiation calculations. In the example, this device is a smart card intended to execute a cryptographic program. To that end, the device 1 combines, in a chip, programmed calculation means consisting of a central unit 2 connected functionally to a set of memories including: 0050 a memory 4 accessible for reading only, in the example of the mask ROM (mask read-only memory) type; 0051 an electrically reprogrammable memory 6, in the example of the EEPROM (electrically erasable programmable ROM) type; and 0052 a working memory 8 accessible for reading and writing, in the example of the RAM (random access memory) type. This memory comprises in particular the registers used by the device 1. 0053 The executable code corresponding to the exponentiation algorithm is contained in program memory. This code can in practice be contained in the memory 4, accessible for reading only, and/or in the memory 6, which is rewritable. 0054 The central unit 2 is connected to a communication interface 10 which provides the exchange of signals with regard to the outside and the powering of the chip. This interface can comprise pads on the card for a so-called contact-based connection with a reader, and/or an antenna in the case of a so-called contactless card. 0055 One of the functions of the device 1 is to encrypt or decrypt a confidential message m respectively transmitted to, or received from, the outside. This message can concern for example personal codes, medical information, accounting on banking or commercial transactions, authorisations for access to certain restricted services, etc. Another function is to calculate or verify a digital signature. 0056 To that end, the central unit 2 executes a cryptographic algorithm, using an exponentiation calculation, on programming data which are stored in the mask ROM 4 and/or EEPROM 6 parts. 0057 In the example described here, the exponentiation algorithm is of RSA type, implemented by the use of the Chinese Remainder Theorem. The algorithm is used for signing a message m using a private key comprising three integer numbers d, p and q. In the example, d has 1024 bits, and p and q have 512 bits. 0058 In the example, an exponentiation calculation sm{circumflex over ()}d mod(p.q) is performed, where m is a predetermined message and d, p, q are integer numbers which are elements of the private key. The number s obtained constitutes a signature of the message m. 0059 The numbers d, p, q (elements of the key) are stored in a portion of the rewritable memory 6, of EEPROM type in the example. 0060 When the exponentiation calculation device 1 is called upon for the exponentiation calculation, the central unit first of all stores the number m, transmitted by the communication interface 10, in working memory 8, in a calculation register. The central unit will next read the keys d, p, q contained in rewritable memory 6, in order to store them temporarily, for the time of the exponentiation calculation, in a calculation register in the working memory 8. The central unit then initiates the exponentiation algorithm. 0061 According to the invention, the derived keys dp, dq of the key d are masked by a random fractional number as follows. 0062 The central unit first of all chooses a number kp which is a divisor of p1, and a number kq which is a divisor of q1, with p, q being elements of the key; kp, kq are stored in another calculation register in the working memory 8. According to the embodiment chosen, kp can be modified at each implementation of the algorithm or else can be kept constant. The size of kp is immaterial, but necessarily less than the size of p1. 0063 The central unit also chooses two random numbers rp, rq and stores them in two other calculation registers in the working memory. rp, rq are preferably modified at each implementation of the algorithm. The size of the numbers rp, rq is generally a compromise between, on the one hand, the size of the memory 8 in which they are stored and the calculation times (which increase with the size of the numbers rp, rq) and, on the other hand, the security of the algorithm (which also increases with the size of the numbers rp, rq). 0064 The central unit next calculates the following variables dp*, ap, dq*, aq:

dp*{overscore (d)}p{overscore (r)}p,(Formula 1)

apdp mod kp(Formula 2)

0065 with {overscore (d)}pdp/kp and {overscore (r)}prp(p1)/kp

dq*{overscore (d)}q{overscore (r)}q,(Formula 3)

aqdq mod kq(Formula 4)

0066 with {overscore (d)}qdq/kq and {overscore (r)}qrq(q1)/kq 0067 {overscore (d)}p, ap are respectively the result and the remainder from the integer division of dp by kp. 0068 {overscore (d)}q, aq are respectively the result and the remainder from the integer division of dq by kq. 0069 The central unit stores the variables dp*, ap, dq*, aq in registers in the working memory. Subsequently, the intermediate variables obtained throughout the calculation will also be stored in a portion of the working memory 8. 0070 The central unit next calculates the variables:

sp*m{circumflex over ()}dp* mod p

sq*m{circumflex over ()}dq* mod q

0071 and then the signature s using the variables sp*, ap, kp, sq*, aq, kq. For this, the central unit uses the fact that:

sp(m{circumflex over ()}dp*){circumflex over ()}kpm{circumflex over ()}ap mod(p),(Formula 5)

sq(m{circumflex over ()}dq*){circumflex over ()}kqm{circumflex over ()}aq mod(q),(Formula 6)

sCRT(sp, sq)(Formula 7)

0072 It should be noted that the above expressions of sp, sq are deduced from the fact that {overscore (d)}p, {overscore (d)}q and ap, aq are defined so that dp{overscore (d)}pkpap and dp{overscore (d)}pkpap, which makes it possible to write: 2

\begin{matrix} \begin{matrix} s_{p} = [m^d_{p}] \mod (p) \\ = (m^{\overline{d}}_{p})^k_{p} m^a_{p} \mod (p) \\ = m^({\overline{d}}_{p} k_{p}) m^a_{p} \mod (p) \\ = m^({\overline{d}}_{p} k_{p}) m^(r_{p} (p - 1)) \\ m^a_{p} \mod (p) \\ = m^[({\overline{d}}_{p} + {\overline{r}}_{p}) k_{p}] m^a_{p} \mod (p) \\ = (m^d_{p}^{*})^k_{p} m^a_{p} \mod (p) \\ = (s_{p}^{*})^k_{p} m^a_{p} \mod (p) . \end{matrix} & (Fermat' s theorem) \end{matrix}

0073 The demonstration of the correctness of the expression for sq is of course similar. 0074 In a practical example implementation where kpkq and apaq, the equalities 5 and 6 make it possible to simplify the equality 7 in the form: 3

\begin{matrix} \begin{matrix} s = CRT (s_{p}, s_{q}) = {[CRT (s_{p}^{*}, s_{q}^{*})]^k_{p} m^a_{p}} \mod N \\ = {(s_{p}^{*} + p Y^{*})^k_{p} m^a_{p}} \mod N \\ = {[CRT (s_{p}^{*}, s_{q}^{*})]^k_{p} m^a_{p}} \mod N \end{matrix} & (Formula 7^{}) \end{matrix}

0075 In a numerical example, kpkq2 is chosen. In this case, apaq1 since all the elements of a secret key and of an associated public key are odd (see above). This is because, d, p and q being odd numbers, the numbers dpd mod(p1) and dqq mod(q1) are also odd. Consequently, ap, the remainder from the division of dp by kp2, is necessarily equal to 1. For the same reasons, aq, the remainder from the division of dq by kq2, is of course equal to 1. 0076 The equality 7 is insensitive to differential and simple covert channel attacks. This is because the random terms in the numbers sp*, sq* mask the data dp, dq, just as in the document WO 99/35782. 0077 Furthermore, the equality 7 is insensitive to CRT attacks. This appears more clearly in the simplified formula 7. The sum sp*pY*, essential for successfully concluding a CRT attack, does not appear directly in the equation 7; it appears only to the power kp. However, it is surmised to be impossible to extract from s a kpth root without knowing the modulus N. It is therefore not possible to calculate sp*pY*; it is therefore not possible to obtain the bits of p by means of a CRT attack. 0078 An algorithm according to the invention is therefore well protected against all these attacks.