Abstract:
A data processing method, whereby an element is subjected to a first operation with a given operand. The method includes a step of updating by a second operation a first variable (B; a 0 ; S′ p , S′ q ) or a second variable (A; a 1 ; S p , S q ), depending on whether a corresponding bit of the operand=0 or 1; and a step of testing a relationship between a first value (B; a 0 ; S′) derived from the first variable and a second value (A; a 1 ; S) derived from the second variable. A related device is also disclosed.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention concerns a method for processing data involving modular exponentiation, and a related device. 
     2. Description of the Related Art 
     Modular exponentiation calculations are often used in cryptographic algorithms and in this context generally introduce a secret, that is to say a number stored by the device that uses the cryptographic algorithm and that is not accessible from the exterior. 
     The steps that implement the modular exponentiation are particularly subject to attacks by malicious persons; these may be error generation attacks (in particular of the DFA (Differential Fault Analysis) type) or attacks by analysis of the current consumption of the device that uses the algorithm (of the SPA (Statistical Power Analysis) or DPA (Differential Power Analysis) type). 
     Attempts have therefore been made to protect these steps, in particular in the case where the secret to be protected corresponds to the exponent used in the modular exponentiation. 
     Thus if a “square-and-multiply” type algorithm is used in which a variable is updated by multiplication for each bit of the exponent having the value 1 (and for those bits only), attempts have been made to render the process symmetrical, for example by effecting a snare multiplication if the bit of the exponent has the value 0, with the aim of countering attacks by measurement of current (sometimes called SPA attacks) or by measurement of time (“timing attacks”). 
     Starting from this general idea, various algorithms protected against SPA type attacks have been developed, such as that described in the paper “The Montgomery Powering Ladder”, B. S. Kaliski Jr., C. Q. Koc and C. Paar, “Cryptographic Hardware and Embedded Systems”—CHES 2002, pages 291-302. 
     Attempts have also been made to protect cryptographic algorithms, including those using modular exponentiation, from error generation attacks, by means of which an attacker attempts to deduce information on the internal operation of the device that uses the cryptographic method by generating a malfunction within that process. 
     One solution widely used to combat this latter type of attack consists in duplicating the calculations effected in order to verify that both iterations of the same calculation give the same result, which generally tends to prove that no error has occurred during their execution. However, this solution entails doubling the calculation time for each operation to be protected (not to mention the necessary subsequent verification step), which is naturally not desirable. 
     To remedy this problem, patent application WO 98/52319 proposes, when the Chinese Remainder Theorem (CRT) is used, to exploit the assumed identity of two values each obtained from one of the branches of the algorithm using this theorem to verify the a priori error-free execution of the algorithm in its two branches. 
     This solution, which exploits a particular feature of applications using the Chinese Remainder Theorem, is not applicable to other types of implementation, however. It should further be mentioned on this subject that using the Chinese Remainder Theorem involves knowing the decomposition into prime numbers p, q of the public module n=p·q. 
     Finally, this solution effects a verification by means of data employed at an intermediate stage of the process, and therefore cannot verify error-free operation at all points of the process, as the designer might wish: for example, this technique cannot protect the process in the case of error generation attacks upon recombination of the result obtained by each of the branches of the algorithm. 
     SUMMARY OF THE INVENTION 
     In order to improve upon this state of affairs, and therefore to propose a method of processing data involving modular exponentiation protected both against current analysis attacks and error generation attacks, the invention proposes a method for processing data (generally a cryptographic method) in which an element (such as a message) is subjected to a first operation with a given operand (for example a secret key), including a step of updating by a second operation either a first variable or a second variable, depending on whether a corresponding bit of the operand has the value 0 or 1, characterized by a step of testing a relationship between a first value derived from the first variable and a second value derived from the second variable. 
     Because the first and second variables are updated in a complementary manner, there exists a relationship between the two variables, or between the values derived from them, that should normally be satisfied. Non-verification of the test therefore indicates an error during the calculation and therefore enables an attack to be detected, even if the attack is directed against a snare operation (case of “safe error” attacks). 
     The first and second values are those of the first and second variables, respectively, for example; in this case, the first and second variables can themselves be used for the test, which in particular involves a saving in memory. 
     The first operation is a modular exponentiation, for example, in which case the second operation is a modular multiplication and the operand is an exponent. 
     The test step can then include comparing the product of the first and second variables to a third variable updated regardless of the value of the corresponding bit of the operand. 
     An alternative test step includes comparing the first variable to the product of the element and the second variable. 
     In another possible embodiment, the first operation is a multiplication on an elliptical curve and the second operation is an addition on the elliptical curve. 
     The relationship can be independent of the operand, which simplifies the test step. 
     The verification step can in particular be applied to the result of the first operation, that is to say after the calculation steps involving the second operation. 
     The method can equally include a step of verifying the relationship for each bit of the operand. This detects any error generation attack as soon as it has interfered with a calculation using the second operation, which guarantees a high level of security throughout the steps implementing the first operation. 
     In one possible embodiment, the first value results from a first recombination in accordance with the Chinese Remainders Theorem involving the first variable and the second value results from a second recombination in accordance with the Chinese Remainders Theorem involving the second variable. 
     The invention also proposes a device for processing data enabling a first operation on an element by means of an operand, including means for updating by a second operation either a first variable or a second variable, depending on whether a corresponding bit of the operand has the value 0 or 1, characterized by means for testing a relationship between the first and second variables. 
     A device of this kind is included in a microcircuit card, for example. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING FIGURES 
       Other features and advantages of the invention will become apparent in the light of the following description, given with reference to the appended drawings, in which: 
         FIG. 1  represents a first embodiment of a data processing method in accordance with the invention; 
         FIG. 2  represents a second embodiment of a data processing method in accordance with the invention; 
         FIG. 3  represents a third embodiment of a data processing method in accordance with the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  represents one example of a method for modular exponentiation calculation conforming to the teachings of the invention. The example given here is described in the form of a subroutine that receives input values and outputs the result of the modular exponentiation calculation. It is nevertheless clear that the invention is not limited to these subroutines. 
     The step E 100  in  FIG. 1  corresponds to the reception at the input of the values m, d and n as a function of which the modular exponentiation is to be effected, to obtain the number m d  mod n. 
     Hereinafter, the number d will be expressed in the form of its binary decomposition (d k , . . . , d 1 ), where k is the number of bits constituting the number d, where each d i  constitutes a bit of the corresponding number with in particular d 1  being the least significant bit and d k  being the most significant bit.
 
Thus  d=S d   i ·2 i-1 .
 
     In cryptographic algorithms, this kind of modular exponentiation calculation is generally used with the number m representing a message, the number d representing the secret key, and the number n representing the public module. Thus in this context the aim is to protect in particular the determination of the number d (that is to say its binary components d i ) by observation of the implementation of the method in an electronic entity or by generating errors in that process. 
     The process shown in  FIG. 1  begins, strictly speaking, with the step E 102  of initializing the registers used in this subroutine, namely the initialization to the value 1 of a variable A, the initialization to the value m of a variable B and a variable S, and the initialization to the value 1 of a variable i serving as an index. 
     Next is the step E 104  (which constitutes the first step of a loop as explained hereinafter) in which a test is effected to determine if the bit d i  (that is to say the bit of rank i in the number d) has the value 1. 
     If so, there follows the step E 106  in which the value A·S mod n is calculated, after which the result of this calculation is stored in the variable A (here overwriting the value previously stored in this variable). 
     In other words, the variable A is updated by means of a modular multiplication by the variable S which, because of the step E 110  described hereinafter, has the value m 2     i    at the time of this update, regardless of the iteration i concerned in the loop. 
     If the result of the test of the step E 104  is negative (that is to say if the bit d i  has the value zero), there follows the step E 108  of calculating B·S mod n, after which the variable B is updated with the result of this calculation. 
     Thus, depending on the value of the bit d i , either the variable A or the variable B is updated by modular multiplication by the variable S. 
     Regardless of the result of the test of the step E 104 , the process continues (after the step E 106  or the step E 108 ) to the step E 110 , in which S 2  mod n is calculated, after which the result of this calculation is stored in the variable S (overwriting the value previously stored in this variable). 
     Next the value of the index i is incremented in the step E 112 , after which the new value of the index i is tested in the step E 114 : if i is strictly greater than k, there follows the step E 116  described hereinafter, whereas if not (that is to say as long as i is less than or equal to k) the step E 114  is followed by the step E 104  described above (which effects the loop previously mentioned). 
     If i is strictly greater than k after incrementation, that is to say if all of the bits of the number d have been processed, there follows the step E 116  in which the validity of the following relationship is tested: S=A·B mod n. 
     In normal operation, because of the complementary updating of the variables A and B and the systematic updating of the variable S as described above, the relationship S=A·B mod n is verified. 
     Consequently, if the result of the test of the step E 116  is positive, it is considered that normal operation (that is to say error-free operation) has occurred and there follows the step E 120  which returns the output value A which, because it is updated by modular multiplication for only the bits of d having the value 1, itself has the value m d  mod n. 
     On the other hand, if the result of the test of the step E 116  is negative, it is considered that an error has occurred during the processing described, and there consequently follows the step E 118  which returns an error value. 
     In the context of cryptographic algorithms, such error detection is considered to be the consequence of an error generation attack aiming to determine the secret key d. Thus no information liable to assist the attacker in seeking to discover the secret key is returned, of course. On the other hand, protection measures can then be triggered, for example blocking the electronic entity implementing the process (which entity is a microcircuit card, for example). 
     Note that here the test uses variables that are necessary for performing the symmetrical calculation of the modular exponentiation; this embodiment therefore enables the test step to be carried out without necessitating the use of other variables. 
     Note also that the relationship tested does not involve the secret key d and does not necessitate a knowledge of the public key (that is to say a knowledge of the number e such that d·e=1 mod(p−1)(q−1)). 
     Moreover, the relationship involves the two variables A and B modified alternately during the modular exponentiation calculation process so that the modification of either of these two variables, for example by means of an error generation attack, is reflected in non-verification of the relationship. This effectively combats “safe error” attacks that seek to detect the absence of consequences of an error in order to deduce from this that the operation concerned is not actually used by the calculation. 
     Alternatively, the test of the step E 116  could be carried out on each iteration of the loop (that is to say a similar test step could be inserted between the steps E 110  and E 112 , for example), since in normal operation the relationship is verified on each iteration. 
     In this case, any detection of an error (through non-verification of the relationship) cold be interpreted as the result of an error generation attack; it is therefore preferable in this case for non-verification of the relationship to terminate the modular exponentiation calculation, whereas its verification leads to the iterations continuing normally. 
     Whichever variant is used (verification at the end of the calculation as in  FIG. 1  or on each iteration as just described), note that, as clearly seen in  FIG. 1 , the number of steps executed and the type of operations effected during those steps do not vary as a function of the secret key d, which renders the process secure against SPA type attacks by measurement of current. 
       FIG. 2  represents a second embodiment of the invention. 
     As for the first embodiment, the entry step E 200  denotes the reception by the subroutine described here of the values m, d and n. As before, this is naturally merely one possible example of the use of the invention. 
     Considering the above values, there follows an initialization step E 202  during which a variable a 0  is initialized to 1, a variable a 1  to m and a variable i to the value k that as before represents the number of bits of the secret key d (k is a fixed datum of the cryptographic system used). Also, d is decremented by one unit because of the way in which the modular exponentiation calculation is effected here. 
     The process then enters a loop for the modular exponentiation calculation as such, beginning with a step E 204  to test the value of the bit d i . (The notation relating to the decomposition of the key d into bits is identical to that explained in relation to the first embodiment and therefore is not repeated here.) 
     If the bit of rank i in the key d has the value 1, there follows the step E 206  in which the first operation is the multiplication of the variable a 0  by the variable a 1  (that is to say the calculation of a 0 *a 1  mod n), the result of which is overwritten in the variable a 0 . The step E 206  also includes the calculation of the value a 1   2  and the updating of the variable a 1  by the result of that calculation. 
     If it is determined in the step E 204  that the bit of rank i of the secret key d has the value zero (that is to say if d i =0), there follows the step E 208  during which there is calculated the product of the variable a 1 , by the variable a 0  (that is to say there is calculated a 1 *a 0  mod n), the value obtained is overwritten in a 1 , the modular square of the variable a 0  (that is to say the value a 0   2  mod n) is calculated, and the result of this latter operation is overwritten in the variable a 0 . 
     Note that the steps E 206  and E 208  executed if the bit of the secret key d concerned in the iteration i has the value 1 or 0, respectively, are totally symmetrical with respect to the variables a 0  and a 1 , one of these variables being in each case updated by multiplication by the other variable. 
     Regardless of the result of the test of the step E 204 , the step E 206  or the step E 208  is followed by the step E 210  in which the following relationship is tested: m*a 0 =a 1 . 
     In normal operation, that is to say if the operations of the preceding step E 206  or E 208  have been carried out without error, this relationship should be verified. 
     Consequently, if the result of the test of the step E 210  is positive, it is considered that the calculation was executed without error, and processing therefore continues with the step E 214  as described above. 
     On the other hand, if the test step E 210  fails to verify the relationship m*a 0 =a 1 , it is deduced from this that one of the calculations effected in the preceding step E 206  or E 208  was interfered with, for example by an error generation attack. 
     This is why, if the test step E 210  yields a negative result, there follows a step E 212  in which it is considered that an error has been detected and necessitates appropriate processing. As previously stated, this processing can vary depending on the applications. 
     As already indicated, normal operation leads to the step E 214 , in which the variable i is decremented. The step E 216  then tests if the variable i has reached 0. If not, not all the bits of the secret key d have been processed and the next iteration of the loop follows by going to the step E 204  described above. If so, all the bits of the secret key have been processed and the modular exponentiation is therefore finished: the variable a 1  corresponds to the required result, that is to say m d  mod n. The value a 1  is therefore returned at the output of the subroutine described here in the step E 218 . 
     Alternatively, the step E 210  can be executed between the steps E 216  and E 218 , instead of or in addition to the step E 210  described above. If the step E 210  is no longer performed in the loop, but only after the loop (for example between the steps E 216  and E 218 ), the test phases of the algorithm are simplified. 
     A third embodiment of the invention is described next with reference to  FIG. 3 , and is used in the context of modular exponentiation using the Chinese Remainders Theorem (CRT). 
     The algorithm shown in  FIG. 3  receives as input the number (or message) m to which the modular exponentiation is to be applied, the two prime numbers p, q constituting the public modulus n=p·q, the components d p , d q  of the secret key d relating to p and q (where d p =d mod(p−1) and d q =d mod(q−1)), and the number a such that a=p −1  mod q. 
     There follows in the step E 302  partial modular exponentiation of the number m with the exponent d p  using an algorithm of the type described above with reference to  FIG. 2 . At the end of this algorithm there is therefore obtained a number S p  (corresponding to the number a 1  in  FIG. 2 ) that is the result of the partial modular exponentiation (that is to say S p =m dp  mod p) and a number S′ p  (corresponding to the number a 0  in  FIG. 2 ) such that S p =m·S′ p . 
     There follows in a similar step E 304  partial modular exponentiation by means of the exponent d q  in accordance with an algorithm such as that described with reference to  FIG. 2 , which yields S q =M dq  mod q (S q  corresponding to the number a 1  in  FIG. 2 ) and S′q (corresponding to a 0  in  FIG. 2 ) which in normal operation verifies the relationship S q =m·S′q. 
     There follows a step E 306  of recombining the partial modular results in accordance with the Chinese remainders formula. Thus on the one hand the values S′ p  and S′ q  are combined to yield the result S′ and on the other hand the values S p  and S q  are recombined, which yields the value S. 
     The results of the partial modular exponentiation being S p  and S q , as explained for the steps E 302  and E 304 , respectively, the variable S contains the modular exponentiation result (that is to say S=m d  mod(p*q)). Moreover, because of the relationships referred to above between S′ p  and S p  on the one hand and S′ q  and S q  on the other hand, there is also obtained after recombination in normal operation the relationship S=m*S′ mod(p*q). 
     This is why the accuracy of this relationship is verified in the test step E 308 . 
     In the case of a negative verification result in the test step, there follows a step E 310  in which it is considered that an error has occurred during the calculation, probably caused by an error generation attack. Appropriate processing can then be applied, as described with reference to the other embodiment. 
     On the other hand, if the step E 308  finds that the relationship S=m*S′ mod(p*q) is verified, it is considered that the algorithm has been executed without error and there follows the step E 312  which returns the value S that corresponds, as indicated above, to the modular exponentiation result. 
     The embodiments that have just been described are merely possible embodiments of the invention. The invention naturally applies in other situations, for example it applies to operations other than modular exponentiation broken down into modular multiplications: thus it applies equally to cryptographic algorithms based on elliptical curves in which multiplications are effected on those curves decomposed as a set of additions. 
     Furthermore, the invention can be applied to calculation systems other than those described, for example Montgomery arithmetic. 
     Also, there are different recombination formulas for the CRT method and the invention can be applied to those different formulas.