Device and method for executing a cryptographic algorithm

DEVICE AND METHOD FOR PERFORMING A CRYPTOGRAPHIC ALGORITHM

The invention relates to the field of cryptographic algorithms intended in particular for communicating electronic devices, a non-restrictive example of which is a smart card. Cryptographic algorithms are commonly executed in such devices to provide encryption of transmitted data and / or decryption of received data when they must remain confidential. To this end, there is provided a microprocessor capable of executing the cryptographic algorithm, associated with a frozen memory (ROM) for recording the program containing the algorithm and a re-inscriptibe memory (RAM) for constituting registers and containing the evolutionary data. The encoded information of the device passes between the microprocessor and a communication interface, forming an outward port.

It is possible for fraudsters to interfere with the cryptographic algorithm by acting either at the communication interface, or within the microprocessor and its memories, in order to break the code in order to make intelligible the encoded data. or modify this data to their advantage.

To minimize this type of attack risk, several protection strategies have already been considered, both in terms of the hardware realization of the devices and at the level of the calculation processes.

In the field of smart cards, among others, there are several possible attacks, including a so-called "fault attack". In this type of attack, the attacker induces any fault during the calculation of a cryptographic algorithm, in order to exploit the presence of this fault to extract secret information.

This type of attack can be envisaged in particular with the RSA algorithm (Rivert, Shamir, Adleman), which is the one most used in cryptography in this field of application. Security is based on factoring. We establish a number N which is the product of two large prime numbers p and q, ie N = pq To sign a number x which expresses a message, we use a secret key d in order to calculate the value y = x^d modulo N. It is generally remembered that a value v expressed modulo N (abbreviation "v mod N") is equal to the remainder less than N at the end of a subtraction of an integer multiple of N; for example 11 modulo 3 = 2, the remainder less than 3 after the subtraction of the multiple 3 times 3.

To verify that the code signature is correct, we use a corresponding key, called public key, which is an exponent e. We just check that x = y^e mod N is equal to the constituent value of the message.

Figure 1 illustrates the process of calculating the signature y = x^d modulo N using the Chinese Remainder Theorem (TRC). The theorem of Chinese remains is also known by its Anglo-Saxon name "Chinese remainder theorem" (CRT).

To save time, four times faster execution of the algorithm, one does not carry out the calculations directly modulo N, but one carries out first modulo calculations p and modulo q.

We denote the values ​​of x modulo p and x modulo q respectively by x_p and x_q. Moreover, denote by dp the value d modulo (p-1), and by d_q the value d modulo (q-1). We calculate modulo p by calculation of y_p = x_p exhibitor d_p modulo p. Similarly, we calculate modulo q the value y_q = x_q exhibitor d_q modulo q.

After getting the values ​​y_p and there_q respectively modulo p and modulo q, they are recombined by the Chinese remains theorem to obtain the value y mentioned above.

Now suppose that an attacker, by any method, causes an error during the calculation of_p, but not during that of_q. This would imply that the value of y_p will be incorrect. The fact that it is an incorrect value is indicated by a circumflex accent above the "y" in Figure 1. However, the value of y_q will be correct. As a result, when values ​​are recombined^ATthere_p and there_q by the TRC, the resulting signature will be incorrect.

If the attacker knows the value of the verification public key e, he can calculate the value ^ATthere^e - x modulo N. We also have the correct signature y, equal to x^d modulo N. From the pre-established relation x = y^e, the attacker only has to calculate that there^e - x modulo N. It extracts the greatest common divisor (gcd) with N, ie: pgdc (^Λthere^e - x mod N, N) = q. He then obtains the secret factor q. As a result, the RSA code is effectively broken.

In other words, if someone is able to induce any error during a modulo calculation while the modulo q calculation is correct, it can completely break the RSA code. A first countermeasure to avoid this kind of scenario is to recalculate the entire algorithm. We compare the values ​​obtained at the end of the successive calculations. If they are identical, it is assumed that there was no error induced. A problem with this approach is that it does not detect a permanent fault. For example, it will not be possible to detect an attack in which the induced error consists in systematically forcing a bit to a determined logical state. Another method of countering such an attack is based on verification. A signature is obtained which is calculated by the TRC. Then we check that the signature is correct and that the public key is good. This approach is very reliable, but the signature algorithm does not always know the verification key e, which prevents it from being able to implement it in certain applications.

Another disadvantage of this method is that if e is large, it implies two exponentiations. The signature is then twice as slow.

According to a countermeasure to the fault attack described by Shamir in patent document 5,633,929, the following algorithm is used:

1. Choose a random number r of low value, 2. Calculate:

Yr = x^d mod rp, and y_rq = x^d mod rq;

3. If there_rp ≠ y_rq (mod r), then there is an error, (maybe induced by an attack, and therefore an interruption of the algorithm, otherwise;

4. Output: y = TRC (y_rp mod p, q_rq mod q⁾.

Thus, for a random number r, instead of calculating modulo p, one calculates modulo rp and modulo rq Then, one verifies that these two values ​​are equal modulo r. If these two values ​​are different, it is certain that there was an error. On the other hand, if they are equal, we can suppose that there was no error, with a probability of l / r being wrong in this assumption.

A disadvantage of this method is that one calculates_rp = x^d mod rp, not x^dp mod rp. Now, the value of the module size, which is usually a 1024-bit number, while dp is a number of the size of half the module, or 512 bits in

1 example.

This implies that in the normal scheme, without fault detection, a first exponentiation with an exponent and a module of 512 bits, and a second exponentiation with an exponent and a module of 512 bits is carried out. On the other hand, with the method of countermeasure according to the patent document 5 633 929, it is not necessary to use_p, but D. This implies that the exponent will have a size of 1024 bits on each side.

So we lose in effectiveness.

Another disadvantage of the Shamir method is that it only works for the TRC-based calculation mode. However, it is also possible to calculate directly x^d modulo n, that is, without resorting to the theorem of Chinese remains.

Indeed, there are two ways to store the secret key. Either we keep the value d, or we keep the values ​​of_p, d_q, p and q. When calculating directly, the standard mode is used; when we calculate modulo p and modulo q, we use the TRC mode.

In view of the above, the invention proposes three countermeasures, including default attacks, which allow exponentiation with an exponent of the size of the module and which can adapt to standard mode or TRC mode.

More particularly, the first countermeasure of the invention concerns, according to a first object, a device for executing a cryptographic algorithm, comprising calculation means, data storage means and data communication means, characterized in that the storage means contain: determined values ​​r and N, a predetermined function f (x) of a value x, and an algorithm allowing the calculation means to establish:

the value of z = f (x) modulo rN;

- the value of y_r = f (x) modulo r; - if z modulo r is equal to or not equal to y_r, for :

- in the case where z modulo r is not equal to y_r, find an error in the calculation of the cryptographic algorithm, and - in the case where z modulo r is actually equal to y_r, calculating the value y = z modulo N. In an embodiment where the algorithm is of the execution type in standard mode, it allows the calculation means to establish:

- the value of z = x^d mod rN;

- if x^{d mod 2 Power s} is equal to or not equal to z modulo (r), for:

- in the case where x^{d mod 2 Power s} does not equal z modulo (r), find an error in the calculation of the cryptographic algorithm, and

- in the case where x^{d mod 2 Puisseles} is equal to z modulo (r), calculate the value y = z mod N.

In one embodiment where the algorithm is of the execution type in the mode of the Chinese Remainder Theorem (TRC), the algorithm allows the computation means to establish: the value of R_p = rr_p = r_p || r_p and K_p = d_p + k_p (p

- 1), where: r_p is a value in [0.2^S), k_p e [0,2^t), p is a prime number, and d_p = d modulo (p - 1);

- the value of z_p = x^Kp mod R_pp; - the finding of an error in the calculation of the cryptographic algorithm if x^{Kp mod 2 Power s} does not equal z_p (mod r);

- the value of R_q = rr_q = r_q || r_q and Kg = d_q + k_q(q - 1), where: r_q is a value in [0.2^S), k_q e [0,2^fc), q is a prime number, and d_q = (d modulo q) - 1;

- the value of z_q = x^kq mod R_qq; the finding of an error in the calculation of the cryptographic algorithm if x^{Kq mod 2 Power s} does not equal z_q (mod r); - the value y = TRC (z_p mod p, z_q mod q) if there has been no error found.

In the preferred embodiments, s = 16, t = 32, the value r is a prime number, advantageously equal to 2^1S + 1, where the value of r is a multiple of a prime number.

Advantageously, the value N = pq is established, where p and q are prime numbers.

The value x can correspond to protected information, with the function f (x) being given by f (x) = x^d, where d is a private key.

Advantageously, the function f (x) is equal to g (x) modulo Φ, where g (x) = x^d, and Φ is the indicator function of Euler of the module. The second countermeasure of the invention applies to an embodiment where the algorithm is of the execution type in the mode of the Chinese Remainder Theorem (TRC), the algorithm allowing the computation means to establish: The value of z_pxD =_p mod p * r and the value of z_qxD =_q mod q * r where r is a random integer;

The value of b_p= z_p^ATd_q mod r and the value of b_q= z_q d_p mod r; - The finding of an error in the calculation if the value of b_p mod r is not equal to the value of b_q mod r;

The value y = TRC (z_p mod p, z_q mod q) if there has been no error found.

In a variant of the algorithm above applied to the second countermeasure, it is possible to use the integer of_p= d_p + rl * (p-1) where ri is a random integer. It is also possible to use the result of the calculation of (x + t * n) instead of x, where t is a random integer. The advantage of the second countermeasure as the first countermeasures is that they protect the execution of the cryptographic algorithm against fault attacks on exponentiation.

The third countermeasure of the invention consists in protecting the step of calculating the value y = TRC (z_p mod p, z_q mod q) from the following method:

Determine the value y = TRC (z_p mod p, z_q mod q);

Check that (y-z_p ) * (y-z_q ) = 0 mod N. If this is not the case, return an error message. Otherwise, return y.

The third countermeasure therefore makes it possible to protect the cryptographic algorithm against a possible fault attack on the calculation step of y by theorem of the Chinese remainder. A variant of the third countermeasure is to execute the following method:

Determine the value y = TRC (z_p mod p, z_q mod q);

Calculate α = (y-z_p) mod p * r and β = (y-z_q) mod q * r; Let τ be twice the size of the integer r expressed in number of bits; - Calculate t = α * β / N mod 2^ATτ;

Check that α.β-t * N = 0, the computation being carried out on the integers. If it does not, return an error message. If not send back y.

The advantage of the variant of the third countermeasure is that the calculations are effected by using shorter integers than in the third countermeasure.

In the embodiment, the algorithm is of the RSA type (Rivert, Shamir, Adleman); however, other types of algorithms may be considered.

Preferably, the device interrupts the data communication in the event of an error in said calculations.

The device in question can be a smart card.

According to a second object, the invention relates to the use of the aforementioned device to counter default attacks.

According to a third object, the invention relates to a method for executing a cryptographic algorithm, characterized in that it comprises, from determined values ​​r and N, and a predetermined function f (x) of a value x, the steps of:

- calculate the value of z = f (x) modulo rN;

- calculate the value of y_r = f (x) modulo r;

- determine if z modulo r is equal to or not equal to y_r, for :

- in the case where z modulo r is not equal to y_r, find an error in the calculation of the cryptographic algorithm, and - in the case where z modulo r is actually equal to y_r, calculate the value y = z modulo N. According to a fourth object, the invention relates to the use of the method for countering fault attacks.

The optional features presented above under the device apply mutatis mutandis to this method.

The invention and the advantages thereof will appear more clearly on reading the description which follows of the preferred embodiments, given purely by way of non-limiting examples, with reference to the appended drawings in which: FIG. analyzed, is a symbolic representation of the cryptographic calculation method of the signature y = x^d mod N using the Chinese Remainder Theorem (TRC);

FIG. 2 is a block diagram schematically representing the elements of a smart card capable of implementing the invention; and

FIG. 3 is a symbolic representation of the general approach to error detection in a cryptographic algorithm according to the invention.

The embodiments are described in the context of smart cards, but can of course apply to all other devices equipped with cryptographic calculation means.

As shown in FIG. 1, the smart card 1 comprises a microprocessor 2 coupled to a frozen memory (ROM) 4 and to a random access memory (RAM) 6, the whole forming a set allowing, among other things, the execution of cryptographic algorithms. More precisely, the microprocessor 2 comprises the arithmetic calculation means necessary for the algorithm, as well as data transfer circuits with memories 4 and 6. The frozen memory 4 contains the executable program of the cryptographic algorithm in the form of source code, while the random access memory 6 includes registers that can be updated for the storage of calculation results.

The smart card 1 also includes a communication interface 8 connected to the microprocessor 2 to enable the exchange of data with the external environment. The communication interface 8 may be of the "contact" type, being in this case formed of a set of contact pads intended to connect to a contactor of an external device, such as a card reader, and or "contactless" type. In the latter case, the communication interface 8 comprises an antenna and radio communication circuits for wireless data transfer. This link may also allow a transfer of power supply of the circuits of the card 1. All the material means constituting the card are known and will not be described in detail for the sake of brevity.

In the example, the cryptographic algorithm is of the RSA type (Rivert, Shamir, Adleman), the characteristics of which have been described in the introductory part.

In the following, we will focus more particularly on the detection of errors in the algorithmic calculation and the countermeasures according to the present invention. The error in question may be deliberately provoked by an attacker who aims to break the cryptographic code used by the smart card, as explained in the introductory part. Thus, to face this eventuality, the countermeasures make it possible to detect such errors and react accordingly.

The principle of error detection is shown schematically in FIG. 3. In general, the execution of the cryptographic algorithm involves a computation of a function f (x) modulo N, whatever the function f (x) . Thus, for the case of an RSA algorithm, we take a value of N which is the product of two large prime numbers p and q. As shown in Figure 3, we take a random number r, and we calculate on the one hand z = f (x) modulo rN, and y_r = f (x) modulo r. Then we check that z mod r = y_r. If this is not the case, we are certain that there is an error; otherwise it is assumed, with a probability of being wrong of l / r, that there is no error.

Then, to find the value of y = f (x) modulo N, we simply calculate y = z mod N.

In the implementation, r is a 32-bit number. It will now be described how to apply a countermeasure according to the invention when the algorithm is executed in standard mode. In standard mode, the value of x is calculated "brutally"^d mod N, where d is a number which constitutes a secret key of the code.

In general, the procedure is as follows. We calculate the value of one part of f (x) modulo rN, and on the other hand of f (x) modulo r; we check that these two calculated values ​​are equal. If this is the case, assume there is no error.

When applying this to the RSA algorithm, proceed as follows. We no longer take a random number, but a specific number, which is here the number 2¹⁶1. This number has the interesting property of being a prime number. We simply calculate the value z = x^d modulo (2¹⁶+1) .N. Then, we calculate the value x^d mod (2¹⁶ + 1).

In the embodiment, the value of x is not calculated^d, but instead we calculate the value of x^{d mod φ} mod (2^1S + 1), where Φ is the Euler indicator function of the module. We can reduce modulo Φ

(2^ιe + 1).

We note that when a number takes as value a prime number P, we have the condition: Φ (P) = Pl. Applied to the example, this condition gives: Φ (2¹⁶ +

1) = 2¹⁶.

Because of this, we do not have to calculate x^d modulo (2^1S +

1), but rather x^{d mod 2 Power 1S} modulo (2¹⁶ + 1). This value is a number of 16 bits only. The operation is very fast.

Another advantage of this way of proceeding is that modulo 2¹⁶ is easy to calculate, in terms of

16 last bits of the secret key d.

In standard mode, we will no longer take a random number, but a prime number, or a prime number multiplied by a random number. The verification will each time be done modulo the prime number that we chose. By proceeding in this way, the calculation time can be reduced. Indeed, the Φ indicator function of Euler can be evaluated easily only for prime numbers.

On the other hand - and this is where the strength of the RSA algorithm lies - to break the RSA code modulo N (= pq), we have to calculate Φ (N). The value of this function is equal to (pl). (q-1). If we do not know the factorization of N, we can not calculate Φ (N). Thus, the countermeasure according to the example for the standard mode amounts to performing the following algorithm:

1. Calculate z = x^d mod (2¹⁶ + 1) N {no random number used, but an Φ indicator function of Euler};

2 . Yes_χdr od ₂ power 16 _≠ _. _{(mQd (2} _.6 _{+ 1} d mQd 2} 6 is the 16 low-order bits of d}, then output ERROR and stop the algorithm, otherwise;

3. Output y = z mod N.

It is understandable that it is thus possible to detect a fault having as a possible origin an attack, and therefore to take preventive measures. These consist in particular in stopping the algorithmic process and interrupting any data exchange with the communication interface 8.

It will now be described how to apply a countermeasure according to the invention when the algorithm is executed in calculation mode based on the Chinese Remainder Theorem (TRC), hereinafter referred to as TRC mode.

In TRC mode, we simply perform modulo p and modulo q calculations. We can perform calculations on the basis of a modulo of a prime number multiplied by the module (N), or we can take a prime number multiplied by a random number. We will always check on the basis of a modulo of a prime number. This produces a calculation with a modulo of a first - 1.

As an example, we will consider, in TRC mode, the modulo calculation p. We choose a random number k, for example 16 bits. We will use it to counter other attacks. We will also take k_p, a 32-bit number, to avoid further attacks, such as current attacks or others. It will be recalled that a current attack is based on the analysis of the current consumed by the processor at various stages of the calculation, aiming to determine, for example, the characteristics of a current exponentiation calculation.

We establish the following relation: 2¹⁶+1 multiplied by a value r_p, is equal to this value r_p that one concatenates with oneself (here, r_p is a value of 16 bits). This applies to any prime number.

We calculate a K value_p (to make the exponent random).

We calculate the z value_p = x^Kp modulo R_p.p. Then we check that modulo 2 calculations^1G+1 are equal. If this is the case, we can assume, with a risk of being wrong 2^lδ, that we will not have an error.

The above reflects the general principle. For the RSA cryptographic algorithm, we will not take a random number, but a prime number. In this way, we can reduce the exponent modulo a prime number - 1. We can also take any number multiplied by a prime number.

In summary, the countermeasure according to the example for the TRC mode amounts to performing the following algorithm:

1. Choose randomly r_p in [0.2¹⁶) and k_p e [0,2³²) (to counter current attacks); 2. Let R be_p = (2¹⁶ + l) r_p = r_p || r_p and K_p = d_p + k_p (p -

D;

3 . calculate z_p = x^Kp mod R_pp; 4. Yes_XKP tnod ₂ power 16 _≠ ^ _{(mQd (2} 6 _{+ 1)} al ors} output ERROR and stop the algorithm, otherwise;

5. Repeat steps 1 to 4 modulo q; 6. Output y = TRC (z_p mod p, z_q mod q).

(The symbol || indicates a concatenation, so a || b = the concatenation of a and B. For example, for a = 1011 and b = 1101, then a || b = 10111101.)

It is noted from the foregoing that these operations are carried out for an R which is either a prime number or a prime number multiplied by any number. Verification is always modulo this prime number, more generally, a prime power. The invention is valid not only for the RSA cryptographic algorithms, presented here for illustrative purposes only, but for all cryptographic algorithms where modular arithmetic is used, since this technique makes it possible to verify that any modular function is correct or not.