COUNTERMEASURE TO SAFE-ERROR FAULT INJECTION ATTACKS ON CRYPTOGRAPHIC EXPONENTIATION ALGORITHMS

Abstract

There is disclosed a countermeasure using the properties of the Montgomery multiplication for securing cryptographic systems such as RSA and DSA against, in particular, safe-error injection attacks. In the proposed algorithm, the binary exponentiation b=a.sup.d mod n is iteratively calculated using the Montgomery multiplication when the current bit d.sub.i of the exponent d is equal to zero. In that case, the Montgomery multiplication of the actual result of the exponentiation calculation by R is realized. Thanks to this countermeasure, if there is any perturbation of the fault injection type introduced during the computation, it will have visible effect on the final result which renders such attack inefficient to deduce the current bit d.sub.i of the private key d.

Claims

1. A cryptographic method comprising: receiving a first message a-; generating a second message b by computing a modular exponentiation b=a.sup.d mod n, where d is an integer expressed in binary representation as d=(d.sub.k1 d.sub.k2 . . . d.sub.1d.sub.0)2 such that d=.sub.i=0.sup.k1d.sub.i2.sup.i, with variable d.sub.i (0,1), where n is a positive integer modulus, and where R is the Montgomery constant defined as the smallest power of g greater than n, where g is a machine-word base, wherein computing the modular exponentiation b=a.sup.d mod n comprises: initializing a first variable to R modulus n-; computing an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R, modulus n.

2. The cryptographic method of claim 1, wherein computing the modular exponentiation b=a.sup.d mod n uses the Montgomery transformation and comprises: initializing the first variable and a second variable to R modulus n and to cR modulus n respectively; computing an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: replacing the first variable by the Montgomery multiplication of said first variable with itself modulus n; if d.sub.i is equal to 1, then replacing the first variable by the Montgomery multiplication of said first variable with the second variable modulus n; and, if d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R, modulus n; and, replacing the first variable by the Montgomery multiplication of said first variable with unity, modulus n.

3. The cryptographic method of claim 1, wherein a is an encrypted message c and b is a clear text message m in case of RSA encryption or decryption operation.

4. The cryptographic method of claim 1, wherein a is an integer g and b is the public key y and the exponent d is the secret key x in case of DSA cryptographic system.

5. The cryptographic method of claim 1, wherein the modulus n is the public modulus of a public key cryptographic system.

6. The cryptographic method of claim 1, wherein the integer d is a private key of public key cryptographic system.

7. The cryptographic method of claim 1 wherein the integer d is a 16-bit long or 32-bit long random integer.

8. The cryptographic method of claim 1, further comprising the implementation of a sliding window optimization algorithm to speed up computation.

9. A computer program product comprising one or more stored sequences of instructions that are accessible to a processor and which, when executed by the processor, cause the processor to carry out the steps of the method comprising: receiving a first message a; generating a second message b by computing a modular exponentiation b=a.sup.d mod n, where d is an integer expressed in binary representation as d=(d.sub.k1 d.sub.k2 . . . d.sub.1d.sub.0).sub.2 such that d=.sub.i=0.sup.k1d.sub.i2.sup.i, with variable d.sub.i {0,1}, where n is a positive integer modulus, and where R is the Montgomery constant defined as the smallest power of g greater than n, where g is a machine-word base, wherein computing the modular exponentiation b=a.sup.d mod n comprises: initializing a first variable to R modulus n; computing an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: if d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R, modulus n.

10. A cryptographic system comprising: an interface (34) for receiving a first message a; a computer unit (30) adapted to generate a second message b by computing a modular exponentiation b=a.sup.d mod n, where d is an integer expressed in binary representation as d=(d.sub.k1 d.sub.k2 . . . d.sub.1d.sub.0).sub.2 such that d=.sub.i=0.sup.k1d.sub.i2.sup.i, with d.sub.i {0,1}, where n is a positive integer modulus, and where R is the Montgomery constant defined as the smallest power of g greater than n, where g is a machine-word base, wherein the computer unit is configured, for computing the modular exponentiation b=a.sup.d mod n, to: initialize a first variable to R modulus n, and compute an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: if d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R modulus n.

11. The cryptographic system of claim 8, wherein the computer unit is configured to use the Montgomery transformation for computing the modular exponentiation b=a.sup.d mod n, and to: initialize the first variable and a second variable to R modulus n and to aR modulus n respectively; compute an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: replacing the first variable by the Montgomery multiplication of said first variable with itself modulus n; if d.sub.i is equal to 1, then replacing the first variable by the Montgomery multiplication of said first variable with the second variable modulus n; and, if d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R, modulus n; and, replace the first variable by the Montgomery multiplication of said first variable with unity, modulus n.

12. The cryptographic system of claim 8, wherein the machine-word base g equals 2.sup.32.

13. The computer program product of claim 9, wherein computing the modular exponentiation b=a.sup.d mod n uses the Montgomery transformation and comprises: initializing the first variable and a second variable to R modulus n and to cR modulus n respectively; computing an iterative process a number k of times, with d.sub.i successively taking values d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0, respectively, each iteration of said iterative process comprising: replacing the first variable by the Montgomery multiplication of said first variable with itself modulus n; if d.sub.i is equal to 1, then replacing the first variable by the Montgomery multiplication of said first variable with the second variable modulus n; and, if d.sub.i is equal to 0, then inserting a counter measure replacing the first variable by the Montgomery multiplication of said first variable with R, modulus n; and, replacing the first variable by the Montgomery multiplication of said first variable with unity, modulus n.

14. The computer program product of claim 9, wherein a is an encrypted message c and b is a clear text message m in case of RSA encryption or decryption operation.

15. The computer program product of claim 9, wherein a is an integer g and b is the public key y and the exponent d is the secret key x in case of DSA cryptographic system.

16. The computer program product of claim 9, wherein the modulus n is the public modulus of a public key cryptographic system.

17. The computer program product of claim 9, wherein the integer d is a private key of public key cryptographic system.

18. The computer program product of claim 9, wherein the integer d is a 16-bit long or 32-bit long random integer.

19. The computer program product of claim 9, wherein the sequence of instructions further comprises instructions to cause the processor to implement of a sliding window optimization algorithm to speed up computation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0072] Embodiments of the present invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings, in which like reference numerals refer to similar elements and in which:

[0073] FIG. 1 is a flow chart illustrating steps of an algorithm of the Square-And-Multiply Always type to calculate the binary exponentiation without the proposed Montgomery multiplication countermeasure;

[0074] FIG. 2 is a flow chart illustrating steps of the algorithm to calculate the binary exponentiation calculation with the Montgomery multiplication counter-measure; and,

[0075] FIG. 3 is a block diagram of an embodiment of the cryptosystem according to the third aspect of the invention, which is adapted to run a computer program product according to the second aspect.

DESCRIPTION OF PREFERRED EMBODIMENTS

[0076] With reference to the flow chart of FIG. 1 there will first be described an embodiment of the binary algorithm to calculate the exponentiation b=a.sup.d mod n without the proposed Montgomery multiplication countermeasure. Stated otherwise, FIG. 1 shows a flowchart of a method wherein a countermeasure such as Square-And-Multiply Always, for instance, is introduced in the binary exponentiation process.

[0077] In case of RSA encryption or decryption operation, the message a is the encrypted message c, and b is a clear text message m.

[0078] In case of DSA cryptographic system, the first message a is an integer h and the second message b is the public key y and the exponent d is the secret key x.

[0079] The algorithm according to the shown embodiment comprises the following steps 11 to 16.

[0080] At 11, various inputs used in the decryption operation are defined: these variables include the public modulus n, the private key d and the first message a.

[0081] In one embodiment, the public modulus n is a large number. In one example, n can be a prime number. It will be appreciated by the one with ordinary skills in the art, however, that embodiments of the invention are not intended to be limited to such an example.

[0082] The private key d can be expressed in binary representation, such as d=(d.sub.k1 d.sub.k2 . . . d.sub.1 d.sub.0).sub.2, where k is an integer greater than unity.

[0083] At 12 the variables result and dummy are both initialized to unity, namely result=1 and dummy=1.

[0084] At 13, an iterative for-loop process is started, which is run a number k of times, for index i ranging from k1 down to 0, respectively, namely for each one of the k binary elements (bits) d.sub.k1, d.sub.k2, . . . d.sub.1, and d.sub.0 of the exponent d successively, starting for instance from the MSB (Most Significant bit) and ending with the LSB (least significant bit).

[0085] At 14 the squaring calculation of variable result is realized. More specifically, the variable result is replaced by resultresult mod n.

[0086] If the current bit d.sub.i of the exponent is equal to 1, then, at 15, the variable result is replaced by resulta mod n.

[0087] Else, namely when the current bit d.sub.i of the exponent is equal to 0, the counter-measure dummya mod n is inserted at 16. This is obtained by replacing the variable result by dummya mod n.

[0088] The idea behind the invention is to replace dummy operations by other operations that always have a visible effect on the final result a.sup.d mod n.

[0089] A simple way would be to replace the dummy operation by a multiplication by 1. The final result would not be affected in the absence of perturbation, and a perturbation during this computation would result with high probability in a modification of the final result. It may thus counter fault injection attacks in some cases. However, since the Hamming weight of 1 is 1, a modification of this unique bit will result in a null output. Thus, this would give information about operations being performed and could help an attacker to deduce the value of the private key.

[0090] A more secure way to achieve the same result makes use, according to embodiments, of the Montgomery multiplication.

[0091] While modular exponentiation is considered to be a complicated arithmetic operation because of the inherent multiplication and division operations, the mathematician Peter L. Montgomery introduced (in 1985) the modular reduction algorithm for multiplying two integers (called n-residues) modulo n while avoiding division by n. In the technical literature (see for instance HandBook of Applied Cryptography, Menezes, van Oorschot, Vanstone, Chapter 14), the properties of the Montgomery calculation have been used to speed-up the modular multiplication and squaring operations required for exponentiation. It is implemented as a simple long-integer multiplication followed by a Montgomery reduction, said Montgomery reduction being so-to-speak the reverse operation of the Montgomery transform.

[0092] Namely, assuming that: [0093] n is a large integer modulus, [0094] p is an integer less than 2n (i.e., p <2n). [0095] R is the so-called Montgomery constant,

[0096] then the Montgomery form of a is defined by: pR mod n,

[0097] the Montgomery reduction is defined by: pR.sup.1 mod n, where R.sup.1 is the inverse of R; and,

[0098] the Montgomery multiplication MontMul computes on input (p,q,n) the value pqR.sup.1 mod n.

[0099] With reference to the flow chart of FIG. 2, an exemplary embodiment of the first aspect of the invention will now be described. This aspect relates to a cryptographic method based on an algorithm allowing the calculation of the exponentiation a.sup.d modulus n with the Montgomery multiplication counter-measure proposed according to embodiments of the invention. The so-called Montgomery constant R is defined as the smallest power of g greater than n, where g is a machine-word base (on 32-bit systems, for instance, g=2.sup.32). In one example, g is equal to 2.sup.32. This is purely illustrative, however, as g may also be equal to 2.sup.16 or 2.sup.64, for instance.

[0100] At 21, the different inputs used by the computer means to carry out the method are defined or received: the modulus n, the private key d expressed in binary representation as d=(d.sub.k1 d.sub.k2 . . . d.sub.1 d.sub.o).sub.2, and the first message a.

[0101] At 22, the variables, result and aare initialized to R mod n and to aR mod n, respectively, with R being the smallest power of f greater than n.

[0102] At 23, there is launched the for-loop realizing the iteration from k1 to 0 of the k binary elements, namely bits, of the exponent d. More specifically, in this example the k bits of the exponent d are processed from the MSB to the LSB. It will be appreciated by the one with ordinary skills in the art that running the calculations from the LSB toward the LSB is also a valid option.

[0103] At 24, the Montgomery multiplication of the squared variable result (namely resultxresult) is performed: resultresultR.sup.1 mod n. At 25 if the bit d.sub.i of the exponent d is equal to 1, the Montgomery multiplication of result with a, i.e. resultaR.sup.1 modulus n is computed and the variable result is updated to, i.e. replaced by same.

[0104] The countermeasure realizing the Montgomery multiplication of result with R is inserted at 26, when the current bit of the exponent is equal to 0. More specifically, the variable result is replaced by resultRR.sup.1 modulus n.

[0105] At 27, the process ends-up with the return back from the Montgomery form to normal form. This can be achieved by computing the Montgomery multiplication of the variable result with unity. Namely, result is replaced by result1'R.sup.1 modulus n.

[0106] One of the countermeasures readily known in the art consists in adding a dummy multiplication in the binary exponentiation algorithm. According to embodiments of the present invention, there is proposed to change this dummy multiplication by performing a Montgomery multiplication MontMul(result,R,n).

[0107] Using this method, a perturbation of any operand and/or any step during this computation will not allow the hacker to identify the current bit d.sub.i of the private key d because it will result in a modification of the final result. Accordingly, the proposed counter-measure is efficient against safe-error fault injection attacks.

[0108] The modification of the dummy multiplication by the Montgomery multiplication will not modify the final result in normal cases, namely absent any injection attack. This is due to the definition of the Montgomery multiplication which provides the following identity property:

MontMul(result,R,n)=resultRR.sup.1 mod n=result mod n

[0109] A particularly advantageous effect of the present invention is achieved when the method is used while the modular exponentiation is computed using Montgomery transformation. Indeed, the consumption signature of Montgomery multiplication may differ from the one of a modular multiplication, and thus the advantage of using the proposed <<Montgomery multiplication>> countermeasure when the modular exponentiation is computed using Montgomery transformation, is that the countermeasure totally eliminates any difference in power consumption for the computation performed when d.sub.i equals 0 and when d.sub.i equals 1.

[0110] The one with ordinary skills in the art will appreciate, however, that computing the modular exponentiation using Montgomery transformation is not essential. Indeed, the <<Montgomery multiplication>> countermeasure according to embodiments of the present invention can be implemented only by changing the processing of the iterations in cases where d.sub.i equals 0. In such implementations, all other steps are identical to steps of FIG. 1 where a standard <<dummy calculation>> countermeasure is used. In particular, the processing of the iterations in cases where d.sub.i equals 1 can be a standard, modular multiplication.

[0111] In embodiments, the exponentiation algorithm with the proposed <<Montgomery multiplication>> countermeasure may be implemented, for instance, by the following pseudo-code:

TABLE-US-00003 Input: n, d = (d_k1,...,d_1, d_0).sub.2, a R = smallest power of b greater than n result = R mod n a = a.R mod n for i = k1 dowto 0 do result = MontMul(result, result, n) if d_i == 1 then result = MontMul(result, a, n) else result = MontMul(result, R, n) end if end for return MontMul(result, 1, n)

[0112] With reference to the block diagram of FIG. 3, there will now be described an embodiment of a cryptosystem according to the third aspect of the invention. Such cryptosystem can comprise a computer unit adapted to run a computer program product comprising one or more stored sequences of instructions that are accessible to a processor and which, when executed by the processor, cause the processor to carry out the cryptographic method.

[0113] In the shown embodiment, the computer unit 30 comprises at least one processor 31, at least one memory 32 to store data used during the execution of the calculations by the processor 31, and at least one rewritable non-volatile memory 33 used to store e.g. specific parameters or running commands to properly execute the method.

[0114] Memory 32 can be a Random Access Memory (RAM) of any suitable type, for instance a SRAM, a DRAM or SDRAM. Memory 33 can be a Read Only Memory (ROM), of any suitable type for instance an EPROM or a Flash memory.

[0115] The cryptosystem further comprises an interface 34 (I/F) for receiving the message a, for instance a message c to be decrypted in the context of the RSA, and for issuing the message b, for instance the clear text m once decrypted in said context.

[0116] This invention avoids the need of using an extra check to guarantee that no safe-error fault has been introduced during computations. It allows getting a faster computation of the algorithm. This algorithm is also memory-optimized since it does not need an extra register to store additional data.

[0117] It is also immune to Simple Power Analysis (SPA). SPA is based on the natural idea that multiplication and squaring may not result in the same power consumption. It is therefore a passive attack, where the hacker monitors power traces of a cryptographic device executing a modular exponentiation. One expects to retrieve the sequence of squaring and multiplication that was actually executed, from the power traces, to deduce therefrom critical information used in the cryptosystem.

[0118] Embodiments of the invention have been described in the foregoing within the context of the decryption operation in a RSA algorithm. It shall be noted, however, that the invention is not limited to this example and that it can be embodied in many other public key cryptographic systems (cryptosystems) like, for instance, DSA.

[0119] In addition, the present invention can also be used in any application where a computing device implements an operation that computes the calculation of efR.sup.1 mod n for any variables e, f, R, n. In that case, the device shall first compute e=eR mod n and f=fR mod n to transform variables e and f in the Montgomery form, and then runs with the operations described above using e and f in lieu of e and f, respectively.

[0120] Finally, it will be further appreciated by the one with ordinary skills in the art that the proposed method is compatible with the implementation of various known additional optimization processes to speed up computation, as for example the sliding window algorithm.