EP1839125A1

EP1839125A1 - Secure and compact exponentiation method for cryptography

Info

Publication number: EP1839125A1
Application number: EP05819349A
Authority: EP
Inventors: Marc Joye
Original assignee: Gemplus Card International SA; Gemplus SA
Current assignee: Thales DIS France SA
Priority date: 2004-12-23
Filing date: 2005-12-09
Publication date: 2007-10-03
Also published as: JP2008525834A; US20080130877A1; FR2880148A1; WO2006067057A1

Abstract

The invention relates to a method for secure and compact exponentiation. The inventive method can be applied in the field of cryptology where cryptographic algorithms are used in electronic devices such as chip cards.

Description

SECURE AND COMPACT EXPONENTIATION METHOD FOR THE

CRYPTOGRAPHY

The present invention relates to a secure and compact exponentiation method, with particular application in the field of cryptology where cryptographic algorithms are implemented in electronic devices such as smart cards.

Many cryptographic algorithms are based on exponentiation calculations, in an algebraic group, of the type x ^d where x and d are respectively a predetermined element and exponent. This is particularly the case with the RSA algorithm (Rivest, Shamir and Adleman), which is based on the exponentiation in the multiplicative group of the ring of integers modulo N, where N is the product of two large prime numbers. The result of the exponentiation may correspond for example to an encrypted or decrypted text, a signed or verified data item. Other cryptographic algorithms such as the ElGamal or Diffie - Hellman algorithm rely on exponentiation in the multiplicative group of a body or in the group of points of an elliptic curve.

An electronic device intended to execute such an algorithm must contain in memory on the one hand the executory part to raise x to the power of d, and on the other hand the values of x and d.

There are different types of exponentiation algorithms. The binary method of the "squaring and multiplication" type is more particularly known. usually known in the English terminology "Square and Multiply".

This algorithm takes as input an element x and an exponent d whose binary representation is: {d [tl], d [t-2], ..., d [l], d [0]} with d [i] equal to 0 or 1, and returns the element y = x ^A d, that is to say x. xx (d times).

The "Square and Multiply" algorithm can be schematized as follows:

1) Initialize the register RO to 1 and the register

Rl to x

2) For i ranging from t-1 to 0, perform a) RO = R0 ^A 2 [squared]; b) if d [i] = 1, then perform RO = RO * Rl [multiplication];

3) Return RO.

Other algorithms known for exponentiation exist such as the method of Yacobi, called M, M ³ , the method of sliding windows, etc. But these algorithms are more complex to implement and therefore less suitable for electronic components constrained chip card type. In the following description, the electronic component comprises a main central unit and a working memory with at least three registers (RO, R1, R2).

The "Square and Multiply" algorithm (and the algorithms cited above) must include suitable countermeasures, that is, secure, against attacks aimed at discovering information contained and manipulated in processing by the computing device. In particular, countermeasures are against hidden channel attacks, simple or differential. A simple or differential hidden channel attack is defined as an attack based on a measurable physical quantity from outside the device, and whose direct analysis (single attack) or statistical analysis (differential attack) allows discover information contained and manipulated in treatments in the device. These attacks can thus reveal confidential information. These attacks have been unveiled by Paul Kocher (Advances in Cryptology - CRYPTO '99, 1966 issue of Notes in Computer Science, pp.388-397, Springer-Verlag, 1999). Among the physical quantities that can be exploited for these purposes are the current consumption, the electromagnetic field ... These attacks are based on the fact that the manipulation of a bit, that is to say its treatment by a particular instruction has a particular imprint on the physical quantity considered according to its value.

The aforementioned exponentiation algorithms had to include countermeasures to prevent these attacks from flourishing. For example, the "Square and Multiply Always" algorithm, which means "squaring and multiplying always", is a secure variant of the "Square and Multiply" algorithm in which the "Square and Multiply Always" algorithm is used. operation was conditional on the value of the bit being processed, thus allowing for hidden channel attacks. This algorithm takes as input an element x and an exponent d whose binary representation is:

{d [tl], d [t-2], ..., d [l], d [0]} with d [i] equal to 0 or 1, and returns the element y = x ^A d, that is x. xx (d times).

The "Square and Multiply Always" algorithm can be schematized as follows:

1) Initialize the registers RO and R1 to 1 and the register R2 to x;

2) For i ranging from t-1 to 0, perform a) RO = R0 ^A 2 [squared]; b) b = 1 - d [i]; Rb = Rb * R2

[multiplication]; 3) Return RO.

The "Square and Multiply Always" algorithm is resistant to certain simple attacks (so-called SPA for "Simple Power Analysis" in the English terminology) but requires an additional registry. It is important to notice that the register R1 is useless to the calculation itself; it is used to perform a dummy multiplication when at iteration i the bit d [i] of the exponent d is equal to 0 (and consequently b = 1) so that whatever the value of the bit of the exponent d, an iteration i consists of a squaring step followed by a multiplication.

Unfortunately, although resistant to SPA attacks, the introduction of dummy operations creates another type of weakness. A class of attacks (called "safe-error attacks") has been introduced by Sung-Ming Yen and Marc Joye ("Checking before output may not be enough"). against fault-based cryptanalysis ", IEEE Transactions on Computers, Vol. 49, pp. 967-970, 2000). Applied to the "Square and Multiply Always" algorithm, the idea is to induce a fault during the multiplication operation (Step 2b) at iteration i. If the result of the exponentiation y = x ^A d is correct, this means that this multiplication operation was dummy and therefore the corresponding bit of d is equal to 0 (i e, d [i] = 0). . On the contrary, if the result of the exponentiation is incorrect, it means that the corresponding bit of d is equal to 1 (i, e, d [i] = 1). An attacker can thus find bit by bit the value of the exponent d.

In the present invention, an exponentiation method having the same advantages as the "Square and Multiply Always" algorithm, namely the resistance against SPA type attacks, is of interest, but, unlike the latter, by not performing any dummy operation.

In addition, remarkably, the method according to the invention has the particularity of performing only multiplication operations. This is particularly interesting in more constrained environments of the smart card type because only the latter operation must be implemented, either software or hardware.

Thus, the result is: - either a gain in code memory size (of type

ROM or EEPROM for example) for a software implementation,

- a gain in circuit size for a hardware implementation, because the squaring operation is not necessary.

It will be recalled that on a set noted additively, such as the group of points of an elliptic curve, the exponentiation is written Q = d. P, where P and Q are elements of the set noted additively (elliptic curve) and d is an exponent. This is also the case when working in the additive group of a ring or a body. In the following, one places oneself in the general, conventional case, which means that one will use the multiplicative notation, except explicit mention opposite.

In more detail, the exponentiation method according to the invention is based on the following algorithm.

This algorithm takes as input an element x and an exponent d whose binary representation is: {d [tl], d [t-2], ..., d [l], d [0]} with d [i] equal to 0 or 1, and returns the element y = x ^A d, ie x. xx (d times).

In multiplicative notation, the method according to the invention can be schematized as follows:

1) Initialize the RO register to 1 and the registers

R1 and R2 to x;

2) For i ranging from 0 to t-1, perform a) b = 1 - d [i]; b) Rb = Rb * R2 [l multiplication ^era]; c) R2 = RO * R1 [2 ^{n of} multiplication];

3) Return RO.

The preceding algorithm can obviously be written additively. As before, it takes as input an element P and an exponent d whose binary representation is

{d [t-1], d [t-2], ..., d [1], d [0]} with d [i] equal to 0 or 1, and return the element Q = d. P, ie P + P ... + P (d times).

In this case, in additive notation, the method according to the invention can be schematized as follows:

1) Initialize the RO register to 0 and the registers

R1 and R2 to P;

2) For i ranging from 0 to t-1, perform a) b = 1 - d [i]; b) Rb = Rb + R2 [l addition ^era]; c) R2 = RO + Rl [2 ^nd addition];

3) Return RO.

In some algebraic groups, the addition with the neutral element 0 (respectively the multiplication with the neutral element 1 in multiplicative notation) may behave differently with respect to the hidden channel measurements and consequently generate a weakness. In this case, the method according to the invention can easily be adapted. We illustrate the technique for a group noted additively, such as the set of points of an elliptic curve. The algorithm starts at the iteration i = 1 so that none of the registers is initialized with the value 0 (called point at infinity for an elliptic curve) in the following manner.

Keeping the additive notation, there is a variant according to the invention which can be schematized as follows: 1) Initialize the register RO and R1 to P and the register R2 to 2. P;

2) For i ranging from 1 to t-1, perform a) b = 1 - d [i]; b) Rb = Rb + R2 [l addition ^era]; c) R2 = RO + Rl [2 ^nd addition];

3) If d [0] = 0 then perform RO = RO - P;

4) Return RO.

Note that the initialization of this variant

(step 1 above) requests that the R2 register contains the value of 2. P. This value can be either precalculated or calculated at the time of exponentiation Q = d. P. In the latter case, if no doubling routine is available, the evaluation of 2. P can be done from addition only by performing ((P + T) + (PT)) where T is a known element. , distinct from P, from the underlying group, typically an element of the public key.

The exponentiation method of the invention and its variants have the advantage of being resistant to SPA - type hidden channel attacks and "Safe - Error" attacks, contrary to the usual exponentiation algorithms which must integrate counter - attacks. measures to resist these attacks

In addition, and remarkably, the exponentiation method of the invention and its variants have the additional advantage of only performing multiplication operations (or additive addition). It will be understood that the invention lends itself to many variants of implementation.

The description was given in the context of a smart card type environment. However, it is clear that the teachings are transposed to other applications, such as in computer terminals, network communication or other, and any other electronic device that uses cryptographic calculations.

Claims

A method for performing exponentiation calculations in a multiplicatively noted algebraic group of the type x power d (x ^d ), where x is an element of said group and a predetermined exponent whose binary representation is {d [ t-1], d [t-2], ..., d [1], d [0]} with d [i] equal to 0 or 1, for an electronic component comprising a main CPU and a working memory with at least three registers (RO, R1, R2), characterized in that it returns the element y such that y

= x ^A d, that is x. xx (d times), and in that it comprises the following steps:

1) Initialize the register RO to 1 and the registers R1 and R2 to x;

2) For i ranging from 0 to t-1, perform: a) b = 1 - d [i]; b) Rb = Rb * R2 [l multiplication ^era]; c) R2 = RO * R1 [2 ^{n of} multiplication]; 3) Return RO.

2. A method of exponentiation in an additively denoted algebraic group, of the d-time type P (d, P), where P is an element of said group and a predetermined exponent whose binary representation is {d [t-1] , d [t-2], ..., d [1], d [0]} with d [i] equal to 0 or 1, for an electronic component comprising a main central unit and a working memory comprising at least three registers (RO, R1, R2), characterized in that it returns the element Q such that Q = d. P, that is P + P ... + P (d times), and in that it comprises the following steps:

1) Initialize the register RO to 0 and the registers R1 and R2 to P; 2) For i ranging from 0 to t-1, perform: a) b = 1 - d [i]; b) Rb = Rb + R2 [l addition ^era]; c) R2 = RO + Rl [2 ^nd addition]; 3) Return RO.

3. Process for exponentiation according to claim 2, characterized in that it comprises the following steps:

1) Initialize the register RO to P and the registers R1 and R2 to 2. P;

2) For i ranging from 1 to t-1, perform a) b = 1 - d [i]; b) Rb = Rb + R2 [l addition ^era]; c) R2 = RO + Rl [2 ^nd addition]; 3) If d [0] = 0 then perform RO = RO - P;

4) Return RO.

4. Exponentiation method according to claim 3, characterized in that the evaluation of the double of the element P (2. P) in said group is made from additions only ((P + T) + ( PT)) by adding a first element (P + T) formed of the sum of said element P and of another known element T, distinct from P, of said group and a second element (PT) formed by the difference of said element P and said element T.

5. Process for exponentiation according to claim 1, characterized in that said algebraic group is the multiplicative group of a ring or a body.

6. Process for exponentiation according to any one of claims 2 to 4, characterized in that said algebraic group is the additive group of a ring or a body.

7. Exponentation method according to any one of claims 2 to 4, characterized in that said algebraic group is the group of points of an elliptical curve.

5

8. Exponentiation method according to claim 4, applied to public key cryptography and characterized in that the known element (T) is an element of the public key.

10

9. Process for exponentiation according to any one of the preceding claims, characterized in that it is implemented in an electronic component.

10. Process for exponentiation according to claim 9, characterized in that said electronic component is a smart card.