FR2942560A1 - Data processing method for securing Rivest Shamir Adleman cryptographic algorithms on chip card, involves testing relation between values by comparing values with neutral element of finite group based on internal rule of finite group - Google Patents

Abstract

The method involves realizing double exponentiation of an element (m) of a finite group by exponents (d, b) for providing corresponding values (R0, R1), where one the exponents is equal to difference between the other exponent and an order or multiple of the finite group (vG). A relation between the values provided by the corresponding exponents is tested by comparing the values with a neutral element (1G) of the finite group based on internal rule of the finite group. An independent claim is also included for a data processing device comprising a double exponentiation calculation unit.

Description

The present invention relates to a processing method involving an exponentiation, and an associated device. Exponentiation calculations are frequently used in cryptographic algorithms and generally involve, in this context, a secret, that is to say a number stored by the device that implements the cryptographic algorithm and that is not not accessible from the outside. For example, cryptographic computations use modular exponentiation to limit the size of values to manipulate. Modular exponentiation is particularly used in smart card type applications.

The stages that implement the exponentiation, for example modular, are particularly the object of attacks and physical cryptanalysis on the part of malicious people; they may be hidden channel attacks consisting of an analysis of physical quantities (electrical current circulating in the device for example) during cryptographic calculations ("side channe / analysis" according to the English terminology) or attacks by fault consisting of exploiting an erroneous result to deduce the secret ("fault analysis" according to the English terminology). We have already sought to protect these steps, especially in the case where the secret to protect corresponds to the exponent involved in the exponentiation. A conventional method for protecting a cryptographic algorithm against fault attacks is to execute it twice, and to compare the two results obtained so that if they are equal, the computed value is provided outside the cryptographic device. If not, the attack has been detected. An alternative to this method is to decrypt the encrypted message during the algorithm to verify that it has not been modified.

However, these solutions are costly in time and processing resources when implemented to protect cryptographic processes involving exponentiation, for example the Rivest Shamir Adleman (RSA) cryptosystem. This disadvantage is all the more true as many common cryptographic devices are provided with limited execution resources. The RSA cryptosystem uses a public key composed of a public module N expressing itself as the product of two secret prime numbers p and q as well as a public exponent e co-prime with the Euler indicator of N defined by (p (N) = (pl) (ql) The corresponding private key is composed of the public module N as well as the private exponent d defined as the inverse of e modulo (p (N). The RSA signature (or further decryption of a message m (whose binary representation results in a number strictly less than N) is obtained as follows: s = mdmodN The keys and module are large, typically 256, 512 or 1024 bits. In the RSA frame, the keys are chosen smaller than cp (N) = (p-1) (q-1) <N. A mathematical group conventionally used for the RSA algorithm is the group Z * N representing the integers between 1 and N-1, which are invertible modulo N. This group corresponds to binary words on log2 (N) bits, an implementation of the exponentiation of m 'by' d 'is called' square and multiply 'where we update a variable by multiplication for each bit of the exponent' of 1, by a value derived from 'm'. In the mathematical sense, exponentiation is defined as an external law of relative integers on a group (G,.), With mainly for any element 'x' of the group G: xn = xxx [...]. X (x appearing n times).

The RSA algorithm has been made more efficient by using the known Chinese Remainder Theorem (CRT). by calculating separately sp = m 'mod p, where dp = d mod (p-1) and sq = mdg mod q, where dq = d mod (q-1), then recovering s from sp and sq, by example using the Garner recombination. To secure this RSA algorithm against fault attacks, it was possible to introduce a verification of the signature before returning it as a result of the calculations, this verification being carried out in particular by means of the corresponding decryption formula: In case of inequality with the value of the initial message 'm', a fault is detected. However, this solution has the disadvantage of requiring a new and expensive modular exponentiation, this time of the value 's'.

As a result, other protection solutions have been developed; on the one hand, those based on the extension of the module consisting of adding redundancy data to the public module N but which are not satisfactory because of the cyclic properties of the modulo function applied to the redundancy data of the module; and on the other hand, those based on a self-protected exponentiation ("self secure exponentiation" according to Anglo-Saxon terminology). In this last group of solutions, it is the very exponentiation algorithm that offers a direct means for verifying the consistency of the cryptographic calculations carried out.

In particular, the Giraud solution "An RSA Implementation Resistant to Fault Attacks and Simple Power Analysis", IEEE Transactions on Computers, 55 (9): 1116-1120, September 2006, which proposes a method of data processing, including a a double exponentiation step of an element belonging to a finite group by a first exponent, 'd-1', to provide a first value and a second exponent, 'd', bound to the first exponent to provide a second value, and a step of testing a relationship between said first and second values. A similar solution is described in application FR 2 884 004, in which a double exponentiation is carried out (md md + 1). In detail, the exponentiation algorithm of the Giraud solution evolved a pair of intermediate variables (ao, a ,) storing the values (ma, m ° `+ ') to obtain, for calculation purposes, the values (md-', md). The consistency of the cryptographic calculation is then verified by comparing ao.m with a ,. In case of inequality, a fault is detected. These solutions have certain disadvantages. On the one hand, the calculations to pass from (1, m) to (md- ', md), requiring no less than (d-1) iterations. On the other hand, these calculations require two modular multiplications per bit of the exponent. Finally, the final comparison again involves the value of the message 'm' leading to the detection of a fault if this message was modified by fault at the end of the algorithm even though the calculations of ao and a, have could be carried out correctly.

An alternative to the Giraud solution is that of Boscher et al. described in the "RSA Algorithm Protected against Fault Attacks" publication, Information Security Theory and Practices - WISTP 2007, volume 4462 of Lecture Notes in Computer Science, pages 229 and 243, 2007. Like Giraud's solution, the latter solution also requires two modular multiplications by bit of the exponent. In addition, it has the disadvantage of using, at each iteration in the method, four registers for storing a triplet (ao, a ,, a2) and the value 'm' of the message. The present invention aims to propose an alternative solution to these known solutions of the prior art in order to overcome at least one of the aforementioned drawbacks. For this purpose, the invention particularly relates to a method of data processing, comprising a step of double exponentiation of an element of a finite group by a first exponent to provide a first value and a second exponent related to the first exponent for providing a second value, and a step of testing a relationship between said first and second values, wherein: - the second exponent is 1eG û d, where d is the first exponent and 15'6 is the order group or a multiple of it; and said testing step comprises a comparison between said first and second values and the neutral element of the group. The order 15'6 of the group G is defined as the number of elements it contains, also called "cardinal".

According to the invention, one relies on the properties connecting this order for a finite group and the neutral element of this group to verify, in an efficient and inexpensive way, the coherence of the cryptographic computation led by exponentiation. If the comparison is inconclusive, a fault is detected. In particular, the final comparison between the two exponentiation results and the neutral element does not imply again the intervention of the message 'm' encrypted. In one embodiment, during said test, the product of the first value and the second value are compared according to the internal law of said group with said neutral element, in particular the following formula is verified: md. m "-d = 1G The property is thus directly applied according to which for every element x of a finite group of order 15.6 and of neutral element 1G, we have: xeG = 1G.

In one embodiment, said double exponentiation is performed iteratively, by placing, at each iteration, squared according to the group law a first parameter and up to date two variables, each for respectively each bit of the first exponent and each bit of the second exponent, by application of said first parameter according to the internal law of the group, generally a multiplication. We operate here the two exponentiations of the element according to mechanisms close to the "square and multiply" algorithm in the case of modular exponentiation, also applicable to another type of exponentiation. However, in this configuration, it avoids squaring the first parameter twice, reducing the complexity of the double exponentiation with regard to many solutions of the prior art. In addition, this configuration requires the use of only three registers: two for the two variables and one for the parameter. In an alternative embodiment, said double exponentiation comprises a step of calculating said first and second values using a double chain of additions, said double chain being determined for the two exponents. Thanks to the use of such a chain of additions, the number of multiplication (or addition, according to the internal law of the group) during the double exponentiation operation is significantly reduced compared to the solutions of the art. previous such as the "square and multiply" algorithm. Correlatively, the required memory space is reduced.

It is notably because of the computation of the same element with two different powers that one can use such a chain of additions and profit from the common calculation of the two powers which results from it. In particular, said dual chain of additions is stored at the initialization of a device implementing the double exponentiation. In this case, the addition string is pre-calculated and stored in non-volatile memory as a parameter of the exponentiation. This avoids to recalculate this double chain with each use. However, an adaptation of the programming interface (API) of the cryptographic function (for example the RSA) is performed in order to no longer take an exponent parameter but an addition string. This configuration is however effective in that it reduces the processing time and the available memory resources. As a variant, the double exponentiation comprises an operation for determining said double chain of additions, in particular during the implementation of the double exponentiation. This configuration makes it possible in particular to apply other protective measures before calculating the double exponentiation, such as for example the masking of the exponent by the addition of random values as described below. In addition, because the string is dynamically calculated, the programming interface (API) does not change.

In particular, said determination operation comprises the iterative decomposition of the two exponents into pairs of intermediate values until the pair (0,1) is obtained, each element of an intermediate pair resulting from an operation on the elements of the preceding pair chosen from: - the conservation of a preceding element, - the subtraction of a preceding element to the other, - the division of a preceding element by two, said preceding element being previously decremented by 1 when is odd. We see here that the number of possible operations on the elements of the chain of additions are limited (to the conservation, the addition, the multiplication by 2 [which is therefore an addition of an element to itself] and the incrementation of 1 [the latter being generally the first element of the chain]). In this configuration, it is possible to restrict the useful memory depth to 3, that is to say to three times the size of the exponent. The depth of memory is seen here as the maximum number of intermediate variables to keep simultaneously in order to continue the calculations. According to a particular characteristic, said decomposition comprises the following iterations: (a1, 13Z / 2) sial 13Z / 2 and (3Zmod2 = O (III31) = (a1, (13Zu1) / 2) if ai 13i / 2 and Pi mod2 = 1 Where (a, 130) = (a, b), and the said chain of additions is represented in the form of a binary string where each bit informs of the result of the comparisons of the This binary string is a very compact representation of the string of additions used for the double exponentiation calculations, and in particular the decomposition includes the following operations: 1.RZ, 4-a; RZR 4-b; j4- n 2. as long as (RZ ,,, RZR) ≠ (0,1) do steps 3 to 9 below 3. RZmP 4-RZR R 4. RZR mod2 5. RZR 4- RZR / 2 6 4 (RZR Rla) 7. coJ1t; coi tvv 8. (iu, ip,) F (iA (it.p 9. ju1u (tO1) 10. return cO 1R the y ((tO1) A (iii , LR where Ro, RI and R2 are used to store the values a ;, pi and a temporary value, the indices ia, ia, itmp E {0, 1,2}, are such that Ri ,, stores a ;, RZR stores pi and R. stores the temporary value, w; denotes a bit of index i in the bit string (w), n * is the length of the bit string, t and v are two internal variables, A represents the AND logical operation, and v represents the logical OR operation ( by disjunction) and the logical operations being extended to the spaces {0,1} x {0,1} n _> {0,1} n between the left argument and each coordinate of the right argument. This realization of decomposition is based on an algorithm called "atomic", in the sense that the same operations are conducted whatever the secret to protect. In this configuration, the treatment according to the invention is resistant to attacks by analysis of hidden channels ("side channe / analysis"). According to a particular characteristic of the invention, during the execution of the iterations, a memory space initially reserved for said registers is used for at least partially storing said bit string.

This economical management of the memory relies in particular on the fact that the algorithm above gradually reduces the size of the data to be stored in the registers (because of the division by two) whereas the binary chain is progressively constructed. This reduces the memory space required for processing, in particular it can be limited to 4.2 I (where I is the length of the exponents used, the length of the bit string being estimated at a limit greater than 2.2 I) 5.2 According to one characteristic of the invention, the double exponentiation comprises the following iterations: i (ma ', m zb,) if t i i + I (a, b) = 0 and v i + 1 ( a, b) = 0 (1) (m a-, mb = ~) = (ma,, m zbi ') if ti i + 1 (a, b) = 0 and v i + l (a, b) = 1 (2) (mb,, ma, + b,) if t (a, b) = 1 (3) OÙ-C. = 0 if a ni Ç 13, _i / 2 1 If a ni> 13 n / 2 and vi = Rn mod2. It is observed here that the values of i and v correspond to the values stored in the binary chain w representative of the corresponding chain of additions. In particular, said double exponentiation comprises the following calculations: R (0,0) 4- 1; R (0,1) m; R (1 0) 4- m y-1; 4-1; i4-0 as long as i <n * do the steps below t ~ ct) iAg; V COi + 1A R (oror) R (oror) .R ((ol), rA) mod N 1.1 4 -tv (v1); y4-ye + t + iA (t0 + 1) return (Rrol, Rr) where R (o, o), R (o, l) and R (l, o) are registers, t , and y are internal variables, w is the binary string and n * is the length of the binary string. In this case, the proposed algorithm is also atomic so that double exponentiation is protected against hidden channel analysis attacks. In one embodiment, said intermediate pairs are successively stored in the same pair of two registers, the association between each register and an element of the pairs being a function of a previously generated random bit. The introduction of a random value in the determination of the registers used renders the treatment according to the invention resistant to "safe-error" type attacks, that is to say when the fault 20 does not impact the result directly, but other values. In another embodiment, possibly combined, is added, before said double exponentiation and each of the first and second exponents, a multiple of the order of said function group respectively of a first and a second randomly generated values. The introduction of a multiple of the order of the group to each of the exponents masks the secret to protect while not modifying the outcome of the proposed treatment. This provision makes it possible to guard against the differential differential channel analysis ("Differential Side Channel Analysis") attacks. In particular, one can calculate a single random value that is used for both exponents. In cryptography, one generally uses the group of invertible integers modulo a certain module provided with the multiplicative internal law '.', But also the group constituted by the points of an elliptic curve provided with the additive internal law '+'.

According to one characteristic of the invention, said group has an internal law of modular multiplication type and the double exponentiation is a double modular exponentiation. This may be for example the group Z * N provided with the operation conventionally known multiplication. In a specific embodiment, the modular double exponentiation of the N element of the element m is calculated using the Chinese remainders by carrying out the following steps: a first modular double exponentiation, of module p, of the element m by a first derivative exponent dp equal to d mod (p-1) and a second derivative exponent equal to n (p-1) -dp, so as to provide a first intermediate value and a second intermediate value; a second double modular exponentiation, of modulus q, of the element m by a third derived exponent dq equal to d mod (q-1) and a fourth derived exponent equal to n '(ql) -dq, so as to providing a third intermediate value and a fourth intermediate value; where p and q are two prime integers such that N = pq, and n, n 'are two non-zero positive integers, and said test step comprises a step of recombining said first and third intermediate values so as to obtain said first value, and at least one step of comparing between said first value obtained, the neutral element and the second and fourth intermediate values.

These embodiments implement the Chinese remains theorem in the context of the present invention. The second and fourth values may individually be compared to the first recombined value, or may be recombined before the result of the recombination is compared to said first recombined value. According to one variant, said group has an internal addition type law on an elliptic curve and the double exponentiation is a double scalar multiplication on the elliptic curve. This configuration corresponds more specifically to cryptography based on elliptic curves. The corresponding group consists of the points of an elliptic curve, which is classically associated with an additive internal law "+" that we do not detail here. Correlatively, the invention also provides a data processing device, comprising - means capable of calculating a double exponentiation of an element of a finite group by a first exponent to provide a first value and a second exponent related to the first exponent. first exponent for providing a second value; means for testing a relationship between said first and second device values wherein: the second exponent is equal to 1G-d, where d is the first exponent and 15'6 is the order of the group or a multiple of it; and the test means are able to compare said first and second values and the neutral element of the group. Optionally, the device may comprise means relating to the characteristics of the treatment method described above. According to one embodiment, the device comprises means for determining a double chain of additions as a function of said two exponents so as to calculate said double exponentiation from said double chain. In particular, said determination means comprise a memory space initially dedicated to registers for storing intermediate values of said string and progressively released for the at least partial storage of a bit string representative of said additive string.

The advantages of such devices are similar to the advantages of the process having corresponding characteristics. The invention also relates to a microcircuit card comprising a device above, and has similar advantages. Other features and advantages of the invention will become apparent in the following description, illustrated by the accompanying drawings, in which: - Figure 1 shows schematically the main elements of a possible embodiment for a card to microcircuit; FIG. 2 represents the general physical appearance of the microcircuit card of FIG. 1; FIG. 3 represents, in the form of a logic diagram, steps of the method according to the invention; FIG. 4 represents, in the form of a logic diagram, double exponentiation steps implemented during the steps of FIG. 3; FIG. 5 represents, in the form of a logic diagram, steps for calculating a chain of additions of FIG. 4; FIG. 6 represents, in the form of a logic diagram, another example of double exponentiation; and FIG. 7 represents, in the form of a logic diagram, another example of the invention. Figure 1 schematically shows a data processing device 40 in which the present invention is implemented. This device 40 comprises a microprocessor 10, to which is associated on the one hand a random access memory 60, for example by means of a bus 70, and on the other hand a non-volatile memory 20 (for example of the EEPROM type), for example through a bus 50.

The data processing device 40, and precisely the microprocessor 10 that it incorporates, can exchange data with external devices by means of a communication interface 30. FIG. 1 schematically shows the transmission of data input E received from an external device (not shown) and transmitted from the communication interface 30 to the microprocessor 10. Similarly, there is shown the transmission of an output data S of the microprocessor 10 to the interface communication device 30 to an external device. This output data S is derived from a data processing by the microprocessor 10, generally on the input data E using a secret datum 80 internal to the system, for example a private key. Although, for the illustration, the input data and the output data appear on two different arrows, the physical means which allow the communication between the microprocessor 10 and the interface 30 may be made by unique means, for example a serial communication port or a bus. The microprocessor 10 is capable of executing software (or computer program) which enables the data processing device 40 to execute a method according to the invention, examples of which are given hereinafter. The software consists of a series of instructions for controlling the microprocessor 10 which are for example stored in the memory 20. In a variant, the microprocessor assembly 10 - non-volatile memory 20 - random access memory 60 may be replaced by a circuit specific application which then comprises means for implementing the various steps of the data processing method. FIG. 2 represents a microcircuit card which constitutes an example of a data processing device according to the invention as represented in FIG. 1. The communication interface 30 is in this case realized by means of the contacts of the card to microcircuit. The microcircuit card incorporates a microprocessor 10, a random access memory 60 and a non-volatile memory 20 as shown in FIG.

This microcircuit card is, for example, in accordance with the ISO 7816 standard and provided with a secure microcontroller which groups together the microprocessor (or CPU) 20 and the random access memory 60. In a variant, the data processing device may be a USB key, a document or a paper information medium comprising in one of its sheets a microcircuit associated with contactless communication means. This is preferably a portable or pocket electronic entity.

With reference to FIG. 3, an example of a processing method according to the invention in which the microprocessor 10 wishes to encrypt a message m into a signature s: s = md is now described. This method allows an exponentiation calculation made in accordance with the teachings of the invention. Conventionally in computer, messages m belonging to the group G = Z * N provided with the law of internal composition type multiplication ". widely known are binary words of [log2 (N) 1 bits ([x1 being the upper integer value). It is noted here that the neutral element of this group is 1, which is noted hereinafter 1G. In the case of such groups Z * N, composed of integers between 1 and N-1 which are invertible modulo N, the following multiplications on the messages m are made modulo N (N is the public encryption module). This is the so-called modular exponentiation, and the order 1G = 15.Z, is cp (N), where cp is the function N

Totient (indicator) of Euler. If the set of binary messages does not directly form the group G (or Z * N), it is possible to use an invertible mapping function f which, to a message m, associates an element of the group G. By way of illustration, if the messages m are formed of i bits (i <[log2 (N) 1), it is possible to use the identity function towards Z * N which fills the message m with bits '0' necessary for its compatibility with the algorithm.

In step E100, the microprocessor receives as input the message m, the secret key d (of length /), the order 15'6 of the group, the neutral element 1G and, if necessary, the encryption module N for perform the calculation above. As described hereinafter, the processing performs a double exponentiation of this message, with a first exponent equal to d and a second exponent equal to the order 15'6 of the group minus d (1eG-d). The two results, md and meG-d are then compared to the neutral element 1G to ensure that the treatment went well. Thus, in step E102, the microprocessor registers are initialized, namely the initialization to the value d of a first variable a (the first exponent) and the initialization to the value 13G-d of a second variable b (the second exponent). In general, it is ensured that the order 13G is greater than d, so that d and 13G-d are positive and presented on the same number of bits.

This is particularly the case for the RSA algorithm where generally the exponent d is the inverse of the public key 'e' modulo cp (N). If this is not the case, we can use a multiple of the order 13G which we subtract 'd so as to obtain a positive value, and we express d on the same number of bits as the multiple obtained.

In step E104, it is determined whether a is equal to d, so as to detect a possible execution fault (possibly in the event of malignant injection of fault) in which case the processing returns an error E106 and the processing ends. The secret key d is in particular loaded from a nonvolatile memory of the device 40 during the test E104 in order to determine a possible corruption of the value d. If so, we initialize, in step E108, a binary variable 8 by 1 if a> b and by 0 otherwise. In step E110, the variable 8 to 1 is compared. If so, we invert a and b (step E112) and then go to step E114, otherwise we go directly to step E114. During the latter, a double exponentiation is performed as described hereinafter in different embodiments, to obtain in registers Ro and RI, respectively ma and mb. When the exponentiations are modular, it is reloaded at this time the encryption module N from a nonvolatile memory of the device 40 to determine a possible corruption of this value N.

In step E116, Ro.R1 is compared to the neutral element 1G, here 1, that is to say that the following equality is satisfied: ma.mb = 1G, ie md.mbG d = 1 G. As mentioned above, we note here that in the case of a modular exponentiation, the multiplication is carried out modulo N.

If the equality is verified, the processing returns (step E118) the value RS which corresponds to the expected value md, and the processing ends. Otherwise, an error is returned (step El 06). The treatment described here is based on the following property of the finite groups: mbG = 1G, for any element m of the group G, in order to effectively detect a fault injected during the treatment. In the above example, we can abstain from using the variable 8. In this case, we choose a double exponentiation function used during the step E114 which itself carries out the initial permutation between a and b so as to have ab and return to the register Ro, the value ma (a before permutation).

Step E118 then returns Ro. With reference to FIG. 4, an example of calculation of the double exponentiation implemented during step E114 is now described. In step E150, the microprocessor 10 receives as input the values m, a and b mentioned in step E114 supra.

In step E152, the register Ro referred to above is initialized to the value 1G (here 1), the register RI to the value m, a variable y of a bit to the value 1 and a variable i of incrementing iterations to the value 1. In step E154, calculating a bit string w = (w;); for the values a and b as described below with reference to FIG.

The binary string w represents in a synthetic way a double chain of additions related to a and b. This binary string w can be calculated dynamically during each double exponentiation as described here in connection with FIG. 4, or it can be pre-configured in volatile memory of the processing device before proceeding with double exponentiation. A string of additions (x;); for a value a is known as a set of values x ;, where each element is the sum of lower subscript values, for example such that: xo = 1, xn = a and for all k, xk = x; x1 where i, j <k Such a chain of additions makes it possible to carry out an exponentiation of m by the exponent a by reducing the number of multiplication operations carried out. Indeed, we calculate mk = mxk = mx, + x; = ml m1 whereas m; and m / have already been calculated and so we get m = ma. A double chain of additions (x;); for the values a and b is defined as the set above such that x; = a (i E {0 ... n-1}) and xn = b, in particular xn-1 = a. We choose in particular the double chain of additions composed of the values a; and B; such that: (agi, 2bi) if t i + 1 (a, b) = 0 and v i + 1 (a, b) = 0 (1) (agi + 1, bi + 1) = (agi, 2bi + 1) if t i + 1 (a, b) = 0 and v +1 (a, b) = 1 (2) (bi, ai + bi) if t i + 1 (a, b) = 1 (3) with (ao, bo) = (0, 1), n such that (an, bn) = (a, b), and t; +1 = 0 If a; +1 <ù b; +1 / 2 t; +1 = 1 If a; +1> b; +1 / 2 v; +1 = b; +1 mod 2. A method for calculating this string will be described below. This double chain of additions has the advantage of having a memory depth of 3. In fact, the evolution of the intermediate values (a; b;) of the chain of additions is limited by the following operations: addition of a value to itself (ie a multiplication by 2), addition of the two intermediate values between them, and incrementation of a value by 1. It follows that at a given instant, it is only necessary to store these two intermediate values (a;, b;) and the value 1 (these values respectively corresponding to ma, mb and m in the double exponentiation calculations). On the contrary, conventional solutions for using simple addition strings require a large memory space in order to store the set of intermediate powers m, used for the calculation of the following powers. The invention is however not limited to this double chain of additions and any longer or shorter chain may be used.

The binary string w is composed, for increasing i, of values Ti each followed when Ti = 0 of the value v ;. This binary chain is a compressed representation of the double chain of additions making it possible to optimize the memory of the device 40. It is understood here that the aforementioned operations linking the values (a; +1, b; +1) and (a; b;) are not limiting and may be more numerous. The restricted choice above, however, makes it possible to obtain a very compact bit string w because of the small number of bits used to code each operation. Thanks to this double chain of additions, we will compute the two desired exponentiations: (m ° ^, mbn) _ (m °, mb) by iterations of the pairs mb ') i = o ... n Back to the figure 4, we continue by comparing w; to 0 (to determine the operations connecting (a; +1, b; +1) to (a ;, b;)) in step E156. If w; = 0 in step E156 (corresponding to Ti = 0), one goes up to the square (step E158, corresponding to the fact that b; +1 = f (2b;)) the register R7. This register corresponds initially to the value 0 and as it is modified, the register R7 stores at any time the value mb = One also increments the index i = i + 1 so as to recover the next bit in the string w (here including the value v;).

In step El 60, this new bit w; is compared to 1. In case of equality, the register R7 is multiplied by the message m during the step E162, to take into account that it increments 2b; previously obtained to obtain b; +1 (equation (2)). We continue at step E164. If this new bit w; is 0, go directly to step E164.

Indeed, equation (1) does not imply incrementation of the value 2b;

Following the test of step E156, if the bit w; is equal to 1 (Ti = 1), the two registers R7 and R701 are multiplied (step El 66) and the result is stored in the register R701. We then replace y with yO1, so the result of the previous calculation is now stored in R7 (the one that stores mbi + 1) and R701 includes mai + 1 = mb = as we see in formula (3). And we continue at step E164. At this last step, the value i is incremented to go to the bit w; following (step E164). In step E168, the index i is compared with the value n *, where n * is the length of the bit string w; (determined during step E154 for example). If i <n *, we return to step E156 so as to traverse the sequence of the chain w and successively calculate all the (ma ', mb) i = o ... n. If i n *, the string w has been traversed entirely. We thus have in the registers Ro and RI values ma and mb. We return (E170) therefore the values stored in these registers in form (R701, R7), that is to say (ma, mb). The calculation of the double exponentiation then ends. The processing for the double exponentiation calculation presented here with reference to FIG. 4 has the advantage of averaging 1.65 multiplication per component bit of the exponent, whereas algorithms of the prior art such as Giraud require two multiplications per exponent bit. In order to avoid any corruption of the index y just before returning the values of the registers in step E170 (which would cause a reversal between ma and mb and therefore an erroneous output in step E118, even though the equality ma.mb = 1 is always verified), it is planned to store throughout the algorithm of FIG. 4 twice the value y in two distinct registers. In step E170, a comparison is then made between these two registers, which must contain the same value y for the registers (R701, R7) to be returned. This protection of the index is implemented in particular during the CRT-RSA algorithms explained below.

Moreover, in order to avoid any intentional modification of the additive chain w, for example by replacing a final bit "1" in two final bits "01" or "00", provision is made in step El 70 to carry out a more precise verification of the index 'i' compared to the value n *: - if i = n *, the registers can be returned, - if i> n *, an error message is then returned. The determination of the binary string w evoked in step E154 is now described with reference to FIG. The solution adopted here consists of starting from the pair (a, b) and decreasing these values up to (0, 1) by limiting itself to the operations of division by two, subtraction of the intermediate values and decrementation by 1. In indeed, if ao Ro then we have the following properties: ai pi there exists n such that (an, tan) = (0, 1).

This computation of the values (a ;, 13;) is carried out using the following relations: (ai, (3i / 2) siai 13i / 2 and (3i mod2 = 0 (il31) = (ai, (t3 -1 ) / 2) siaiRi / 2and (3i mod2 = 1 (13i -ai, ai) if ai> '3i / 2 where the values a and 13 are such that: (ao, 130) = (a, b) and ( an, (3n) = (0, 1).

We initially invert a and b so that ao (30) We notice that (a ;, b;) = (an_ ;, 13n_;) and that to obtain w; we have: tii = 0sian_i13n_i / 2 ti = 1 sian _;> (3n _; / 2 v; = 13n_; mod 2.

We seek here to reduce as quickly as possible the values a; and 13, decreasing progressively 13; until he is close to a; (limit to a;> 13; / 2). We subtract then a; at 13; and the two values are inverted to retain property a; 13 ;. The largest of the numbers is thus reduced faster than a simple division by 2. As a result, the chain of additions is shorter and the exponentiation calculations are faster. Returning to FIG. 5, the intermediate values (a;, pi) are thus calculated and the bits Ti and v are deduced therefrom; component w chain: In step E200, the microprocessor receives as input the values a and b with a b. In step E202, a first register Ro is initialized to the value a (that is to say ao) and a second register RI to the value b (that is to say (3o). , a boolean y (later used to indicate the register Ry storing pi, Ryal storing a;) is initialized to 1 while an incrementation variable j is initialized to n * corresponding to the length of the string w. At this stage, the string w is not known, therefore n * either, but we can prove that n * is statistically bounded (upper bound) by the value 2.2 log2 b, so we plan to store w in a memory Q buffer of length 2.2 log2b by initializing j by the final bit index of this buffer: j = 1-2,2 log2 dl -1 At step E204, it is checked whether (Ry, Ry ) is equal to (0, 1) in which case the decomposition of (a, b) has been completed, and in the case where this equality is not satisfied, Ry / 2 and Ryal are compared (step E206), in order to determine what a decomposition among the three f above, we apply here, and note that the result of this comparison corresponds to the value of i for this decomposition. If Ry / 2 Ryal (i = 0), then we memorize 52.1 = Ti = 0, then s = v; = Ry mod 2 and divide (Ry - Ry mod 2) by two (the indices 'i' are given here as an indication with reference to a, and pi, and vary nonlinearly with the index 'j'). When the division keeps only the entire part of the quotient, one can only perform the division of Ry by two. Decremented by 2 (step E208). If Ry / 2 <Ryal (i = 1), we go to step E210 where we memorize ni = Ti = 1, we subtract Ryal from Ry (which gives pi-ai), then we modify the bit y = yO1 so that the result obtained is in Ryal, that is to say corresponds to a; in accordance with the operations provided for above. We decrement 1 index j. Following steps E208 and E210, return to step E204 to determine if the decomposition of (a, b) has been completed. In the affirmative of the comparison E204, the decomposition is finite and the chain w is returned to the step E212. It should be noted that the returned string w is formed from the only bits g + 1 to g-2.2 log dl-1 (so we have n * _ 1-2,2 box dl -j-1) because no value t or v was not recorded in the bits nor at no. In this case, the length of the string w used in step E168 counts only the bits returned here. In one embodiment, it is planned to carry out the operations of FIGS. 4 and 5 in the form of atomic algorithms so as to thwart any side channe / analysis attacks. To do this, the determination of the chain w (FIG. 5) is carried out as follows: 1.Ri ,, 4-a; Rip 4-b; j4- [2,21og2blu1 2. as long as (R. ~ p) ≠ (0,1) do steps 3 to 9 below 3. R. 4- R. û ~ tp ~ p 4. v ~ R. 5. RZR 4- RZR / 2 6. t - (R ~ p R ~ e,) 7. t; SZ14-tvv 8. (la, l R lep) (t / ~ (Ltmp La, i (3) ) v ((t 0 l) A (La, i (3)) 9. j4-jû1û (tO1) 10. returnw = (52; +1, ..., ~~ z, zlogzbi_1) Ro, R1 and R2 are used to store the values a ;, pi and a temporary value The indices ia, ia, itmp e {0,1,2}, are such that Ri ,, stores a ;, RZR stores 20 R; the temporary value A represents the AND logical operation, v represents the OR logical operation (by disjunction) and the logical operations are extended to the spaces {0,1} x {0,1} n _> {0,1} n between the left argument and each coordinate of the right argument T - (AB) represents the operation that returns '1' if the comparison (AB) is true and '0' otherwise (A> B).

Here, we observe that all operations are calculated at each iteration, whatever the values of t (corresponding to i) and v (corresponding to v). The algorithm is therefore atomic. It has been seen above that the length of the chain w has an upper limit equal to 2.2 housing b or 2.2 / where the length of the exponents.

Instead of providing a memory of 5.2 / to store w and the three registers, initially 1.2 / memory is reserved for the bits w; larger index. Then during the above calculations, especially when one filled these 1.2 / bits and the values a; and pi (after the many operations above) have a length substantially equally at / = 2, it is possible to compress the three registers on 2 / bits and thus to recover / bits for storing the bits w; lower indexes. Similar to the calculations of the binary string w, an atomic realization of the double exponentiation calculation (FIG. 4) can be envisaged as follows: 1. R (0,0) 1; R (0.1) m; R (1.0) m 2.y 4-1; g 1; i 4- 0 3.w 4- f (a, b) where f is the above atomic algorithm for calculating the chain w 4. as long as steps 5 to 8 below are carried out in the following manner: ## EQU1 ## where R (or) R (orot) 4 R (orot) .R ((oi), rA) modN 7 tv (vO1); y4-yOt 8. i-i + 1.t + gA (tO1) 9. return (Rron, Rr) Three registers are used here: R (o, 7el) and R (o, Y) storing the intermediate values mai and mbj, as well as R (l, o) storing m The variable corresponds, for its part, to v so as to indicate if it is necessary to proceed with a multiplication by m (R ( l, o of the register R (o, 7) or not.

Referring now to FIG. 6, another exemplary embodiment of the double exponentiation calculation of step E114 is illustrated. This example is of type square and multiply. In step E300, the microprocessor receives as input the parameters m, a = {a, _1 ... ao} and b = {b1_1 ... bo} provided during step E114. In step E302, two variables A and B are initialized each to the value 1, a variable M to the value m, and an iteration variable i to 0. Proceed to step E304 by comparing the bit a; to 1. In the case of a tie, the operation A = A.M is performed in step E306 and then step E308. In case of inequality, go directly to step E308. At the latter, we compare the bit b; to 1. In the case of a tie, the operation B = B.M is performed in step E310 and then step E312. In case of inequality, go directly to step E312. The value i is then incremented during step E312.

If i = l (test in step E314), that is to say if all the bits of the exponents a and b have been traversed, the processing is ended by returning the values A and B corresponding to the exponentiations ma and mb desired (E316). If the test of step E314 is false, step E318 is continued by squaring the variable M, and return to step E304.

An adaptation of the teachings of the invention to the case of RSA-CRT type encryption, based on modular exponentiations, will now be described with reference to FIG. In the specific case of the group Z * N, the encryption module N is worth pq (two large prime numbers) and the group order is equal to the Euler indicator cp (N) = (p-1). 1). As seen above in the CRT case, the signature is determined from sp and sq, for example using Garner's recombination: s = CRT (sp, Sc) = sq + q. mod p). (sp - Sc) mod p). Under the conditions of the invention, we calculate the pairs (sp, cp) and (Sc ', cq) where cp = mp-1 dP mod p and cq = mq-1 dg mod q, then we combine these two pairs using the CRT function to get (md, m`'Rd) mod N.

In detail, the steps E100 'to E114' are similar to the aforementioned steps E100 to E114, except that the input data is m, d, N and (p (N) to perform modular exponentiations during the step E114 'In step E116', the process outputs the pair (Ra, Rso1) corresponding to (md, m`'nd) and ends, so these steps are used to calculate (sp, cp) [respectively (sq, cq)] providing, as input data, the values m mod p, dp, p and cp (p) = (p-1) [respectively m mod q, dq, q and 9 (q) = (q-1)] The combination of these two pairs is then carried out: s <_ CRT (sp, sq) c <ù CRT (cp, Cq) Then, in accordance with the teaching of the invention, the relationship between the two exponentiations calculated and the neutral element 1 zN (here 1) of the group (step E116 of Figure 3) .Therefore we check whether the equality sc mod (pq) = 1 is obtained. we return the calculated signature s If no, an error is returned Alternatively, one can check the two following equalities and return an error if one of them is not verified: s.cpmodp = 1 s. cg mod q = 1 In order to guarantee the security of the CRT-RSA algorithm with regard to attacks that can take place on the message m before each of the double exponentiations, it is expected to calculate, at the beginning of the CRT-RSA algorithm, a cyclic redundancy check code (CRC) for each of the values m modulo p and m modulo q (these values are taken as first parameters during step E114 ') (respectively, m modulo N in the case of step E114 for a modular exponentiation). These CRC codes are stored. Then, at the beginning of the double exponentiation of the step E114 ', we recalculate m modulo p (respectively m modulo q; resp. M modulo N for the step E114) starting from the value m, we store these values in two registers (R1 [step E152] and the storing register m [used in step E162]), and then checking the integrity of this newly calculated value by comparing its CRC with that initially calculated. In case of negative verification, an error is returned, otherwise the double exponentiation can be conducted. Any subsequent corruption (after the beginning of the corresponding double exponentiation) of these values m modulo p and m modulo q (respectively m modulo N) is detectable through the final verification (after step E116 '). In one embodiment for protecting the invention against "safe-error" type attacks, the indexes of the registers involved in the above-mentioned processes (for example those in FIGS. 4 and 5) are randomized. In particular, a random value r is generated at the beginning of each specific processing, and the processes are carried out on the registers R7, R7 and O + r, RS O + r and RS O + 1 O + r. Similarly, in one embodiment to protect the invention against attacks of the type of differential analysis of the hidden channels (or "differential side channe / analysis"), one does not directly manipulate the secret value d (also p and q) that one masks. To do this, we add to the different exponents a random multiple of the order 13G of the group. Two random integers ri and r2 are generated for the two exponents of the double exponentiation.

Thus, we calculate (md + r1.14G 13G-d), md ,, + n (P (P) mod p, mr2 (P (P) -dp mod p, d4 + ri. (q) modq mrr (P (q) -dq modq) and the verification E116 according to the invention is always carried out: md + ri.14G .mr2. $ Gd_m (ri + r2) .14G = 1G. In particular, r1 = 0 and r2 = 2 make it possible to obtain more easily the condition a <_b sought during the steps E112 and E112 'Thus, in general, md and m2u''Gdd are computed. after compare the theoretical performance of the invention with respect to the solutions of the prior art for an RSA-CRT encryption of length 1024. The Vigilant solution is described for example in the publication "RSA with CRT: A New Cost-Effective Solution to Thwart Fault Attacks ", Cryptographic Hardware and Embedded Systems - CHES 2007, Volume 5154 of Lecture Notes in Computer Science, pages 130-145, Spring 2008. For this solution, measurements were made for a module extension of {68, 80 } bits for a sliding window exponentiation of v alue q Protection algorithm Time (10b.to) Memory (Kb) Vigilant q = 1 {511, 484} {2,4; 2,3} Vigilant q = 2 {468, 444} {2,6; 2.5} Vigilant q = 3 {440, 417} {3.7; 3.6} Giraud 537 3.5 Invention 443 2.5 (+1.1) The invention thus provides one of the most effective solutions to fight against fault analysis for an implementation RSA 1024, and thus secure cryptographic algorithms. The foregoing examples are only embodiments of the invention which are not limited thereto. In particular, we illustrated above the invention using a group G provided with an internal composition law "." and explained the adaptations for the case of modular exponentiation. The invention, which targets any group G, is particularly suitable for cryptography on elliptic curve. In this case, the group G, consisting of the points of an ellipse, is provided with an additive internal composition law '+' and the exponentiation corresponds to a scalar multiplication. We then have an invertible function f associating with any binary message a point P of the group G, consisting of the points of an ellipse. To encrypt the message with a key d in a signature s, then the exponentiation of P by d is calculated, which corresponds to a scalar multiplication of P by d: s = Pd According to the teachings of the invention, we calculate also the exponentiation of P by 1G-d: c = P (1G-d) One then checks, on the basis of the property P.1G = 1G, that c + s = 1G.

If yes, we can return the expected signature.

Claims (19)

REVENDICATIONS1. A data processing method comprising a double exponentiation step (E114, E114 ') of an element (m) of a finite group (G) by a first exponent (a) to provide a first value (Ro, R8, ma) and a second exponent (b) bound to the first exponent to provide a second value (R1, RSO1, mb), and a test step (E116) of a relationship between said first and second values characterized in that: the second exponent (b) is equal to 1eG-d, where d is the first exponent and 15'6 is the order of the group (G) or a multiple thereof; and said testing step comprises a comparison between said first and second values and the neutral element (1 G) of the group. 2. Method according to claim 1, wherein during said test (E116), comparing the product of the first value and the second value according to the internal law (*) of said group (G) with said neutral element (1G). 3. Method according to one of claims 1 and 2, wherein said double exponentiation (E114, E114 ') is performed iteratively, putting, at each iteration, squared (E318) according to the law of the group a first parameter (M) and up to date two variables (A, B), each for each bit (a;) of the first exponent (a) and each bit (b;) of the second exponent (b), respectively, by applying said first parameter (M ) according to the internal law of the group. 4. Method according to one of claims 1 and 2, wherein said double exponentiation (E114, E114 ') comprises a step of calculating said first and second values using a double chain of additions (w), said double chain being determined for the two exponents (a, b). 5. Method according to claim 4, wherein said dual additions chain (w) is stored at the initialization of a device implementing the double exponentiation. 6. The method of claim 4, the double exponentiation (E114, E114 ') comprises an operation of determination (E154) of said double chain of additions (w). 7. Method according to the preceding claim, wherein said determination operation (E154) comprises the iterative decomposition of the two exponents (a, b) into pairs of intermediate values (a ;, 13;) until the pair is obtained. (0,1), each element of an intermediate pair (a ;, 13;) resulting from an operation on the elements of the preceding pair (a; _ ,, chosen from: - the conservation of a preceding element, the subtraction of a preceding element to the other, the division of a preceding element by two, said preceding element being previously decremented by 1 when it is odd. 8. Method according to the preceding claim, wherein said decomposition (E154) comprises the following iterations: (ai, (3i / 2) siai 13i / 2 and (3i mod2 = 0 (il31) = (ai, (t3 -1) 12) siai13i / 2et (3i mod2 = 1, (13i ùai, ai) if ai> 3i / 2 where (ao, 13o) = (a, b), and we represent the said chain of additions in the form of a binary string (w) where each bit (w;) gives the result of the comparisons of the iteration. 9. The method according to the preceding claim, wherein said decomposition (E154) comprises the following operations: 1. R 1, 4-a; Rip 4_b; j4_n * 2. while (Ri ,,, Rip) ≠ (0.1 ) do steps 3 to 9 below 3. R. mP 4- R ~~ R. 4. v - RZR mod2 5. RZR 4- RZR / 2 6. t 4_ (R. ≤R a) 7. coj_1 t; 8. (la, ip, lbnp) (t (Ltmp, La, L (3)) v ((t01) n (La, L (3, ibn)) 10. return where 0, R1 and R2 are used to store the values a; R1 and a temporary value, the indices ia, ia, itmp E {0,1,2}, are such that Ria stores a ;, RiR stores the temporary value, w; denotes a bit of index i in the bit string (w), n * is the length of the bit string, t and v are two internal variables, A represents the AND logical operation, and v represents the logical OR operation ( by disjunction) and the logical operations being extended to the spaces {0,1} x {0,1} n _> {0,1} n between the left argument and each coordinate of the right argument. 10. Method according to the preceding claim, wherein, when performing the iterations, using a memory space initially reserved for said registers (Ro, RI, R2) for at least partially storing said bit string (w). 15 11. Method according to one of claims 8 to 10, wherein the double exponentiation (E114) comprises the following iterations: (May, mzb,) if ti i + 1 (a, b) = 0 and v i + 1 ( a, b) = 0 (1) (ma, m zb '+ 1) if ti i + 1 (a, b) = 0 and v i + 1 (a, b) = 1 (2) (mb' ma ' + b,) if 2 i + 1 (a, b) = 1 (3) where T. = 1 If a ni> 13 ni / 2 and vi = Rn-imod2. 20 12. The method according to the preceding claim, wherein said double exponentiation (E114, E114 ') comprises the following calculations: pi and Ri ,,,, 5, if a n-i Ç R n-i / 2R (0,0) 4- 1; R (0.1) m; R (1.0) 4- m y4-1; 4-1; i4-0 as long as i <n * do the steps below t 4ù Ct) i A i; V COQ + 1 AR (oror) R (oror) .R ((ol), rA) mod N 1.1 4-tv (v0 + 1); y4-y0 + t i4-i + 1.1 + iA (t0 + 1) return (Rrol, Rr) where R (o, o), R (o, l) and R (l, o) are registers, t, .i and y are internal variables, w is the binary string and n * is the length of the binary string. 13. A method according to any one of the preceding claims, wherein before said double exponentiation (E114, E114 ') and to each of the first and second exponents (a, b) is added a multiple of the order (1o). said group respectively function of randomly generated first and second values (ri, r2). 14. Method according to one of claims 1 to 13, wherein said group (G) has an internal law of modular multiplication type and the double exponentiation is a double modular exponentiation. 15. Method according to the preceding claim, in which the modular double exponentiation of the N module of the element m is calculated using the Chinese remains by carrying out the following steps: a first double modular exponentiation, of module p, of the element m by a first derivative exponent dp equal to d mod (p-1) and a second derivative exponent equal to n (p-1) -dp, so as to provide a first intermediate value (sp) and a second intermediate value (cp); a second double modular exponentiation, of modulus q, of the element m by a third derived exponent dq equal to d mod (q-1) and a fourth derived exponent equal to n '(ql) -dq, so as to providing a third intermediate value (Sc ') and a fourth intermediate value (cq); where p and q are two prime integers such that N = pq, and n, n 'are two non-zero positive integers, and said test step comprises a step of recombining said first and third intermediate values (sp, sq) so as to obtainingladite first value (s), and at least one step of comparing said first obtained value (s), the neutral element (1G) and the second and fourth intermediate values (cp, cq); 16. Method according to one of claims 1 to 13, wherein said group (G) has an internal addition type law on an elliptic curve and the double exponentiation is a double scalar multiplication on the elliptic curve. A data processing device, comprising - means for calculating a double exponentiation of an element (m) of a finite group (G) by a first exponent (a) to provide a first value (Ro, R8, ma) and by a second exponent (b) linked to the first exponent to provide a second value (R1, Rso1, mb) - means for testing a relationship between said first and second values characterized in that: - the second exponent (b) is equal to 1eG ù d, where d is the first exponent and 15'6 is the order of the group (G) or a multiple of it; and the test means are able to compare said first and second values and the neutral element (1 G) of the group. 18. Apparatus according to the preceding claim, comprising means for determining a double chain of additions as a function of said two exponents so as to calculate said double exponentiation from said double chain. 19. Microcircuit card comprising a device according to one of claims 17 and 18.