Title of Invention	METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION
Abstract	A cryptographic calculation is carried out in an electronic component according to a specific cryptographic algorithm including at least one specified non-linear operation on blocks of data of k bits, k being a whole number of more than 2. Several blocks of masked intermediate data of j bits (b?m1, c?m2, ??n) are generated from an initial block of data of k bits (a), j being a whole number that is smaller than k. Then a non-linear operation S is applied to at least one of the masked intermediate data blocks of j bits (??n) with the aid of a substitution table (106) with 2j inputs producing a modified data block of j bits (S(?)?n'). The modified data block of j bits and some, at least the masked intermediate data blocks of j bits are combined to form a result block of k bits (a') corresponding to the initial data block of k bits by means of a transformation including the specified non linear operation.

Title of Invention

METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION

Abstract

A cryptographic calculation is carried out in an electronic component according to a specific cryptographic algorithm including at least one specified non-linear operation on blocks of data of k bits, k being a whole number of more than 2. Several blocks of masked intermediate data of j bits (b?m1, c?m2, ??n) are generated from an initial block of data of k bits (a), j being a whole number that is smaller than k. Then a non-linear operation S is applied to at least one of the masked intermediate data blocks of j bits (??n) with the aid of a substitution table (106) with 2j inputs producing a modified data block of j bits (S(?)?n'). The modified data block of j bits and some, at least the masked intermediate data blocks of j bits are combined to form a result block of k bits (a') corresponding to the initial data block of k bits by means of a transformation including the specified non linear operation.

Full Text	FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 COMPLETE SPECIFICATION (See section 10, rule 13) “METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION" SAGEM DEFENSE SECURITE, a French company of Le Ponant de Paris 27, rue Leblanc 75015 Paris, France. The following specification particularly describes the invention and the manner in which it is to be performed. WO 2006/008355 -2- PCT/FR2005/001376 Method and device for carrying out a cryptographic calculation The present invention pertains to the area of 5 cryptography and more particularly to the protection of the confidentiality of the keys used by cryptographic algorithms. It is described hereinbelow in its nonlimiting application to encryption or decryption functions. 10 Algorithms for encryption, respectively for decryption, or again for enciphering, are aimed at encrypting, respectively decrypting, data. Such algorithms generally comprise a chaining together of several 15 operations, or calculations, that are applied successively to a data item to be encrypted so as to obtain an encrypted data item. These algorithms use secret keys. 20 Such encryption algorithms may suffer from "attacks" which are aimed at violating the confidentiality of keys used. Numerous types of attacks are known today. Thus, certain attacks are based on information leaks 25 detected during the execution of the encryption algorithm. These attacks are generally founded on a correlation between the information leaks detected during the processing by the encryption algorithm of the data item and of the key or keys (attacks by 30 analyzing the consumption of current, electromagnetic emanations, calculation time, etc). Procedures for protecting against such attacks are known. One of the protection procedures commonly used 35 is the random masking of the intermediate data manipulated by the encryption or decryption algorithm. In this type of protection, the input data are masked by random values. Thus, the intermediate data resulting WO 2006/008355 -3- PCT/FR2005/001376 from the operations performed in the algorithm may be decorrelated from the key or keys. The attacks which are aimed at violating the 5 confidentiality of the secret keys of an encryption algorithm are similar to the attacks aimed at violating the confidentiality of the secret keys of a decryption algorithm. In the following sections the characteristics described in relation to an encryption 10 algorithm also relate to a decryption algorithm. An encryption algorithm generally comprises several linear and/or nonlinear operations. For an initial data item to be encrypted, an intermediate data item is 15 obtained after each of the operations of the encryption algorithm. When masked intermediate data are manipulated, a masked intermediate data item is obtained after each operation. The encryption algorithm is thus protected. 20 It is however useful to recover the unmasked intermediate data item after each of these operations by "demasking" the data item. It is easy to demask an intermediate data item resulting from a linear 25 operation. Specifically, a linear operation L applied to a data item x masked by an exclusive or with a random mask m, may be written in the form: L(x Å m)=L(x) Å L(m) . 30 Thus, knowing m, it is easy to demask L(xÅm) to obtain L(x). It is entirely otherwise for nonlinear operations. Specifically, for a nonlinear operation F applied to a 35 data item x masked by an exclusive or with a random mask m, it is generally possible to write: F(xÅm)*F(x) ÅF(m) . WO 2006/008355 - 4 - PCT/FR2005/001376 In order to demask an intermediate data item manipulated by the encryption algorithm, it is necessary to perform a series of calculations which may 5 be complex and expensive depending on the encryption algorithm to be protected. Encryption algorithms are known that use nonlinear operations, such as the DES ("data encryption 10 standard") algorithm or else the AES ("advanced encryption standard") algorithm. Several methods of protection by masking of the AES algorithm have already been proposed. 15 In such algorithms, the nonlinear operations are generally implemented in the form of substitution tables. Thus, a nonlinear operation corresponding to a substitution table tab[i], applied to a data item x may be written in the following form: 20 y=tab [x] . The protection by masking in this case requires the generation on the fly of the randomly masked tables. Thus, a masked nonlinear operation corresponding to a 25 masked substitution table tab’ [i], applied to a data item x masked by a random mask ml may be written in the form: y'=tab' [xÅml]=yÅm2 30 In order to be able to demask the data item y' thus obtained, a solution consists in storing the masked tables. Protection procedures of this type are proposed for the DES encryption algorithm in the document by Louis Goubin and Jacques Patarin 'DES and Differential 35 Power Analysis - The "Duplication" Method', in Cetin Kaya Koc and Christof Paar, editors, Proceedings of CHES'99, volume 1717 of 'Lecture Notes in Computer WO 2006/008355 - 5 - PCT/FR2005/001376 Science’, pages 158-172, Springer-Verlag, 2000, as well as in patent FR 2802741 'Dispositif mettant en oeuvre un algorithme de chiffrage par bloc a repetition de rondes' [device implementing a blockwise encryption 5 algorithm with repetition of rounds]. However, such a solution may turn out to be extremely expensive in terms of memory room, in particular when the unmasked substitution table is of relatively large 10 size. For example, the nonlinear operation of the AES may be implemented using a substitution table having a size of 256 bytes. The simultaneous encryption of 16 bytes of a 15 message requires the storage of 16 masked substitution tables each of 256 bytes. The memory size required to mask the nonlinear operation thus implemented is consequently 4 Kb. 20 A drawback of this type of protection is therefore that it requires a consequential memory size. Also known is the document 'Provably Secure Masking of AES’ by Johannes Blomer, Guarjardo Merchan, and Volker 25 Krummel published on 04-30-04 and the document 'Secure and Efficient Masking of AES - A Mission Impossible' version 1 of E. Oswald, Stephan Mangard and Norbert Pramstaller dated from 4 June 2004 which propose that the nonlinear operation of the AES algorithm be carried 30 out in the finite field GF(4). The latter article proposes a procedure for masking the operations of the AES algorithm in which the nonlinear operation of an intermediate masked data item is 35 transformed into a linear operation by transposition from one finite field (GF(28)) to another (GF(4)). WO 2006/008355 - 6 - PCT/FR2005/001376 However, such a method of masking of the AES proposes that the nonlinear operations be carried out in GF(4) and hence that bits be manipulated 2 by 2. 5 In general, it is easier to efficaciously implement operations carried out on blocks of bits of size substantially equal to the number of bits processed simultaneously by the microprocessor used rather than operations carried out on blocks of bits of size very 10 substantially different from the number of bits processed simultaneously by the microprocessor. Thus, an efficacious implementation of an encryption algorithm manipulating bits 2 by 2 is not easy on 8, 15 16, 32 or even 64-bit microprocessors. The present invention is aimed at proposing a solution to alleviate these drawbacks. 20 A first aspect of the invention proposes a method of executing a cryptographic calculation in an electronic component, according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer 25 greater than 2, the method comprising the following steps: generating several masked intermediate data blocks of j bits from an initial data block of k bits, j being an integer smaller than k; 3 0 applying a nonlinear operation to at least one of the masked intermediate data blocks of j bits by means of a substitution table with 2j entries producing a modified data block of j bits; 35 combining the modified data block of j bits and certain at least of said masked intermediate data blocks of j bits into a result block of k WO 2006/008355 - 7 - PCT/FR2005/001376 bits corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation. 5 Thus, it is possible to carry out the nonlinear operation specified on data blocks of size k on data blocks of size j by generating several intermediate data blocks of size j, the sizes being expressed in bits, from a data block of size k. After having 10 manipulated the intermediate data blocks, and in particular applying a nonlinear operation, data blocks thus obtained are combined to recover a data block of size k corresponding to a transformation of the initial data block. This transformation includes the specified 15 nonlinear operation. It may also include other operations of the algorithm. Specifically, it may be advantageous to carry out other operations of the algorithm on data blocks of j bits rather than data blocks of k bits, before combining these blocks to 20 again obtain a data block of k bits. The step of generating several intermediate data blocks from an initial data block may comprise several steps, as detailed in the following sections. Thus, 25 advantageously data blocks of smaller size than the initial data block to be encrypted by the algorithm are manipulated. Consequently the nonlinear operation specified, included in the encryption algorithm may be applied to the intermediate data blocks of smaller size 30 and therefore the substitution table corresponding to the nonlinear operation applied to the intermediate data blocks is of strictly smaller size than the size of a substitution table which would correspond to the specified nonlinear operation of the algorithm applied 35 to the initial data block. By virtue of these provisions, it is possible to WO 2006/008355 - 8 - PCT/FR2005/001376 protect by masking the cryptographic calculations of an encryption algorithm which comprises a nonlinear operation, in particular in the case where this nonlinear operation would correspond to a substitution 5 table of relatively large size. The masking step may advantageously be carried out either on the initial data blocks, before the step consisting in generating the intermediate data blocks, 10 or on the intermediate data blocks. In an embodiment of the present invention, the generating step comprises a decomposition operation (T) consisting in decomposing a data block of k bits into 15 data blocks of j blocks (b, c) and the combining step comprises an inverse decomposition operation(T-1) consisting in composing a data block of k bits(a’) from the data blocks of j bits (B, C). 20 In an embodiment of the present invention, the cryptographic calculation furthermore includes at least one linear operation and the masked linear operation is performed before the decomposition operation T or after the inverse decomposition operation T-1. In this case, 25 when the encryption algorithm comprises linear operations before the nonlinear operation, the decomposition operation T is performed after the linear operations. When the encryption algorithm comprises linear operations after the nonlinear operation, the 30 inverse decomposition operation T-1 is performed before the linear operations. In another embodiment, when the encryption algorithm includes linear operations, these masked linear 35 operations are performed after the decomposition operation T and before the inverse decomposition operation T-1. Thus, when an encryption algorithm is an WO 2006/008355 - 9 - PCT/FR2005/001376 algorithm with repetition of rounds, each of the rounds comprising at least one linear operation and at least one nonlinear operation, each round is performed after the decomposition operation T and before the 5 decomposition operation T-1. It is also possible to apply the decomposition operation T at the start of the encryption algorithm and the inverse decomposition operation T-1 at the end 10 of the encryption algorithm. Thus, when such an algorithm is an encryption algorithm with repetition of rounds, all the operations of all the rounds of the algorithm are performed by manipulating blocks of strictly smaller size than the size of the initial data 15 block. Figure 2 illustrates such an embodiment applied to an algorithm of ABS type. Thus, a data block of size k to be encrypted 201 is decomposed by the decomposition 20 operation T into several intermediate data blocks (202) to be encrypted of size j. The operations protected by masking 203, which are equivalent to those of the AES type algorithm that are specified for data blocks of size k, are then applied to the intermediate data 25 blocks of size j. Encrypted intermediate data blocks 204 are obtained. Next, the inverse decomposition operation T-1 is applied to obtain the encrypted data block 205 of size k. Such an embodiment therefore requires a modification of the operations of the 30 algorithm so that they are applicable to the intermediate data blocks. The step of generating the masked intermediate data blocks may comprise masked additions and masked 35 multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and WO 2006/008355 - 10 - PCT/FR2005/001376 providing a masked product of the two unmasked data blocks. The step of combining the intermediate data blocks and 5 the modified data block may likewise comprise masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two 10 unmasked data blocks. As detailed in a following section, when the initial data block has a size of a byte and when the nonlinear operation specified can be implemented by means of a 15 substitution table of size equal to 256 bytes, as in an AES type algorithm, it is advantageously possible to apply the nonlinear operation to an intermediate data block using a substitution table having a size of 8 bytes. 20 In an embodiment of the present invention, the nonlinear operation is bijective and, for the non null elements, is a multiplicative inversion in a finite field. Preferably, by convention, this operation maps 25 the element 0 to the element 0. In an embodiment of the present invention, the encryption algorithm, taking as input a message comprising a determined number of initial data blocks 30 of size k, processes each of the initial data blocks sequentially. Thus, a substitution table is generated and stored for each initial data block and then each data block is processed one after the other. 35 In another embodiment of the present invention, the encryption algorithm processes all the data blocks of an input message simultaneously. Thus, the substitution WO 2006/008355 -11 - PCT/FR2005/001376 tables are generated and stored simultaneously for each of the initial data blocks of the message, then said data blocks of the message are processed simultaneously. This type of simultaneous processing of 5 blocks requires a memory area of larger size than the sequential processing of data blocks. In such a context, as detailed in a following section, it turns out to be very advantageous to reduce the substitution table corresponding to the nonlinear operation, as is 10 proposed by the present invention. In an embodiment of the present invention, an initial data block is processed using, each time the nonlinear operation of the encryption algorithm is carried out, a 15 substitution table generated at the start of the encryption algorithm. Thus, the same substitution table is used throughout the processing of an initial data block by the encryption algorithm. 20 It is also possible to generate and store a substitution table before each masked nonlinear operation. In this embodiment, a new substitution table is used before each application of the nonlinear operation. 25 Such algorithms conventionally comprise several rounds each comprising linear operations and at least one nonlinear operation. The most frequent attacks of the execution of calculations in such algorithms are based 30 on detections of information leakage during the execution of the first rounds and of the last rounds, since it is the rounds that manipulate data blocks close to the data blocks to be encrypted and encrypted data blocks. Thus, to protect such algorithms from 35 these attacks, it is possible to mask the data blocks manipulated in the first round or rounds and/or in the last round or rounds. Consequently, it may be WO 2006/008355 - 12 - PCT/FR2005/001376 advantageous to generate and store substitution tables for at least the first round and at least the last round. 5 A second aspect of the present invention proposes an electronic component for executing a cryptographic calculation according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer 10 greater than 2, the component comprising, means for generating several masked blocks of j bits from an initial data block of k bits, j being an integer smaller than k; means for applying a nonlinear operation to at 15 least one of the masked blocks of j bits by means of a substitution table with 2j entries producing a modified block of j bits; means for combining the modified block of j bits and certain at least of said masked blocks 20 of j bits into a result block of k bits corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation. 25 By virtue of these provisions, it is possible to protect, from information leakage detection attacks, an electronic component employing an encryption algorithm of AES type comprising a nonlinear operation by manipulating masked data blocks and by using masked 30 substitution tables of size equal to 8 bytes instead of masked substitution tables of size equal to 256 bytes. Consequently, such a method of protecting an encryption algorithm requires a relatively small memory size. It 35 may therefore be employed in electronic encryption components exhibiting a memory area of relatively small size WO 2006/008355 - 13- PCT/FR2005/001376 Additionally, in an embodiment of the present invention, intermediate data blocks of size 4 bit are manipulated. Such a size allows efficacious 5 implementation that is easier to carry out than when data blocks of lesser size are manipulated. Other aspects, aims and advantages of the invention will become apparent on reading the description of one 10 of its embodiments. The invention will also be better understood with the aid of the drawings, in which: - figure 1 illustrates a method of protecting an 15 encryption algorithm according to an embodiment of the present invention; - figure 2 illustrates a method of protecting an encryption algorithm of AES type according to an embodiment of the present invention. 20 In an embodiment of the present invention, use is made of well-known mathematical properties of finite fields (or Galois fields (GF)) so as to generate from an initial data block of size k several data blocks of 25 size strictly less than k. An embodiment of the present invention is described for protecting by masking an encryption algorithm of AES type, taking as input a message composed of 16 bytes, each of the bytes being processed by a repetition of rounds each comprising a 30 sequence of linear operations and at least one nonlinear operation. The invention covers other types of encryption algorithm comprising at least one nonlinear operation, whether or not there is repetition of rounds. 35 In an AES type algorithm, the nonlinear operation corresponds to a multiplicative inversion, for the non WO 2006/008355 - 14 - PCT/FR2005/001376 null elements, in the finite field GF(28). Thus, to generate from a data block several intermediate data blocks of strictly smaller size, in an embodiment of the invention, it is proposed that the nonlinear 5 operation be transposed from the field GF(28) to the field GF((24)2) . The document by Tsing-Fu Ling, Chih-Pin Su, Chih-Tsun Huang, and Cheng-Wen Wu 'A high-throughput low-cost AES 10 cipher chip’, and also the document by Vincent Rijmen 'Efficient implementation of the Rijndael S-box' and the document by Atri Rudra, Pradeep K. Dubey, Charanjit S. Jutla, Vijay Kumar, Josyula R. Rao, and Pankaj rohatgi 'Efficient Rijndael Encryption Implementation 15 with Composite Field Arithmetic' and then the document by R.W. Ward and T.C.A. Molteno 'Efficient hardware calculation of inversion in GF (28) ' are known which show how the nonlinear operation of the AES algorithm can be transported into the compound field GF((24)2) and 20 which show that such a transposition makes it possible to improve the performance of the encryption algorithm. Conventionally, the AES therefore takes as input a message composed of 16 bytes. Several rounds are 25 applied to each of these bytes, each round using a subkey derived from the main secret key. The AES generally comprises the following operations: - a nonlinear operation, conventionally referenced SubBytes, corresponding to a substitution table 30 from 8 bits to 8 bits which is applied to each of the 16 bytes of the input message; - a linear exclusive or operation, conventionally referenced AddRoundKey, applied between the 16 bytes of the subkey and the 16 bytes of the input 35 message; - a linear operation, conventionally referenced ShiftRows, corresponding to a permutation applied WO 2006/008355 - 15 - PCT/FR2005/001376 to the 16 bytes; - a linear operation, conventionally referenced mixed columns, applied to the 16 bytes. 5 The SubBytes operation of the AES algorithm comprises a nonlinear operation which corresponds, in the finite field GF(28), for the non null elements, to a multiplicative inversion. Such an operation may be transported into the compound field GF((24)2, so that 10 data blocks of size 4 bits are manipulated, before carrying out the inverse decomposition operation T-1 for other operations manipulating bytes. We choose a representation of GF(24) and the field 15 polynomial as follows: P(x)=x2+Dx+E; D and E being elements of the finite field GF(24)) So that we may write: 20 GF(28)=GF(24) [x]/P(x) Figure 1 illustrates an embodiment of the present invention. 25 We construct the decomposition operation T 102 which may be written: T(a)=bx+c; where a is an element of GF(28) where (bx + c) is an element of GF((24)2), and b and c 30 are elements of the finite field GF(24)). This decomposition operation T generates from the data block a of size equal to one byte intermediate data blocks b and c of size equal to 4 bits. 35 This decomposition operation may be implemented in the form of a multiplication with an 8x8 matrix. WO 2006/008355 - 16 - PCT/FR2005/001376 After this decomposition operation, the data blocks manipulated are intermediate data blocks of size 4 bits, strictly smaller than the size of the initial 5 8-bit block. Such a decomposition operation T makes it possible to reduce the size of the data blocks manipulated in such a way as to be able to reduce the size of the 10 substitution table corresponding to the first nonlinear operation. It is therefore carried out before performing the nonlinear operation. However, it may be carried out at various steps of the encryption algorithm. Thus, on each of the 16 bytes of the input 15 message, this decomposition operation can be carried out either at the start of the algorithm, or at the start of each of the rounds of the algorithm, or else before each application of the nonlinear operation. 20 The present invention covers the embodiments wherever the algorithm step in which this decomposition operation is carried out. Next, when the nonlinear operation using the 25 substitution table has been performed, it is possible to carry out the inverse decomposition operation T-1 to return to the finite field GF(28) and again manipulate bytes. 30 The present invention covers the embodiments wherever the algorithm step in which the inverse decomposition operation is carried out. According to the steps in which the decomposition 35 operation T and the inverse decomposition operation T-1 are carried out, other determined operations of the algorithm in GF(28) are adapted to the finite field WO 2006/008355 - 17- PCT/FR2005/001376 GF((24)2) . Thus, if the decomposition operation T is performed before the nonlinear operation and then if the inverse 5 decomposition operation T-1 is performed after the nonlinear operation, it is not necessary to adapt other operations of the algorithm to the finite field GF((24)2). On the other hand, in the case where the decomposition operation T is performed at the start of 10 the algorithm and the inverse decomposition operation T-1 at the end of the encryption algorithm, all the operations of the algorithm are adapted to the finite field GF((24)2). The operations of the encryption algorithm are then replaced by their equivalents in the 15 finite field GF((24)2). In an embodiment of the present invention, we mask 103 at least the intermediate data blocks manipulated at the time of the nonlinear operation for at least the 20 first round and the last round of the AES algorithm, as detailed by the following sections. The invention also covers an embodiment in which the intermediate blocks manipulated at the time of the nonlinear operation are masked for all the rounds of the algorithm or else an 25 embodiment in which all or part of the intermediate data blocks manipulated in the course of the execution of the algorithm are masked, whether these data blocks are elements of GF(28) or of GF((24)2) . 30 In an embodiment of the present invention, the nonlinear operation is a multiplicative inversion in GF(24) for the non null elements. In the finite field GF((24)2), the inversion of an 35 element (bx + c) may be written in the following form: (bx+c)-1=bΔ-1x + (c + b D) Δ-1; where Δ=b2E + bcD + c2. WO 2006/008355 -18 - PCT/FR2005/001376 Thus, the first nonlinear operation of multiplicative inversion of the finite field GF(28) transposed into the finite field GF((24)2), corresponds to multiplications, 5 additions and the nonlinear operation of the multiplicative inversion. This nonlinear operation in the finite field GF((24)2) may be implemented through a 4-bit to 4-bit substitution table occupying 8 bytes. 10 As was described, one wishes to mask the data blocks thus manipulated. The masking of the additions is well known. In order to mask the multiplications, a masked 15 multiplication algorithm M(x, y, z))104 is introduced. In what follows, the elements ml, m2, m3, n, n', nl, n2 are random masks. Such an algorithm takes as input: - masked elements of GF(24), (b Å ml) and (c Å m2) ; - a mask m3. 20 Such an algorithm outputs the masked product in the form: bc Å m3. 25 The following steps may be written: u = (b Å ml) (c Å m2) = bc Å bm2 Å cml Å mlm2 v = (c Å m2)ml = cml Å mlm2 w = (b Å ml)m2 = bm2 Å mlm2 M(bÅml, cÅm2, m3) = uÅvÅwÅ mlm2 Å 30 m3 = bc Å m3. In an embodiment of the present invention, the first intermediate data blocks are masked. One thus obtains a first masked decomposition which may be written in the 35 following form: (b Å ml)x + (c Å m2) . Next we use the masked multiplication algorithm to calculate the masked multiplication in the following form: M(b Å ml, c Å m2, m3) = bc Å m3. 5 Next, in the same way, we calculate, according to step 105, the following products to obtain the masked data block Δ: p = (bc Å m3)D = bcD Å m3D; 10 q = (b Å ml)2E = b2E Å ml2E; r = (c Å m2)2 = c2 Å m22. Consequently we obtain the following equation: p Å q Å r Å ml2E Å m22 Å m3DÅ n = Δ Å n. 15 Thus, in the finite field GF(24) by addition and multiplication we obtain the masked data block, A © n, to which the nonlinear operation of multiplicative inversion is applied. 25 20 In an embodiment of the present invention, this nonlinear operation is carried out on the masked data block using a masked substitution table, tab[x], according to step 106, satisfying the following equation: tab[x Å n] = x-1 Å n' . This masked substitution table therefore makes it possible to obtain the inversion of the masked data 30 block, i.e. Δ-1 Å n' . By applying the masked multiplication algorithm, we calculate: -M(b Å ml, Δ-1 Å n', n1)=bΔ-1 Å nl = B; 35 - M(bD + c) Å (mlD + m2) , Δ-1 Å n', n2) = (bD + c) . Δ-1 Å n2 = C. WO 2006/008355 - 20 - PCT/FR2005/001376 Thus, by combining 108 the masked data blocks b Å ml, c Å m2 and Δ-1 Å n', we obtain Bx +C. We therefore obtain a masked value of (bx+c)-1 without 5 having to manipulate, in order to carry out this nonlinear operation, the unmasked data blocks b, c and Δ. Next, the inverse decomposition operation T-1 109 is 10 carried out to obtain an element 110: a' = T-1 (Bx + C) . In an embodiment of the present invention, D is determined equal to 1 so as to reduce the number of 15 multiplications to be performed. Advantageously, a nonlinear operation is therefore transposed from the finite field 6P(28) to the finite field GF((24)2) in which the nonlinear operation 20 corresponds to a combination, of additions, of multiplications and of an equivalent nonlinear operation in a field having fewer elements. Thus, it is possible to protect electronic components 25 from attacks by detection of information leakage during the execution of a cryptographic calculation comprising a nonlinear operation by carrying out operations equivalent to this nonlinear operation on data blocks of reduced size, thereby making it possible to carry 30 out these calculations on masked data blocks since the corresponding substitution table is of reduced size. - 21 -CLAIMS 1. A method for carrying out a cryptographic calculation in an electronic component, according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer greater than 2, the method comprising the following steps: -generating several masked intermediate data blocks of j bits (bÅml, cÅm2, ΔÅn) from an initial data block of k bits (a) , j being an integer smaller than k; applying a nonlinear operation S, corresponding to said specified nonlinear operation, to at least one of the masked intermediate data blocks of j bits (ΔÅn) by means of a substitution table (106) with 2j entries producing a modified data block of j bits (S(Δ) Ån’) ; combining the modified data block of j bits and certain at least of said masked intermediate data blocks of j bits into a result block of k bits (a’) corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation. 2. The method as claimed in claim 1, according to which the initial data block is masked before the step consisting in generating the intermediate data blocks. 3. The method as claimed in claim 1, according to which the intermediate data blocks (103) are masked before applying the nonlinear operation. 4. The method as claimed in any one of the preceding claims, according to which the generating step comprises a decomposition operation (T) consisting in AMENDED SHEET - 22 - decomposing a data block of k bits into data blocks of j blocks (b, c) and the combining step comprises an inverse decomposition operation (T-1) consisting in composing a data block of k bits from the data blocks of j bits (B, C) into a data block of k bits (a’). 5. The method as claimed in claim 4, according to which the cryptographic calculation furthermore includes at least one linear operation and according to which said masked linear operation is performed before the decomposition operation (T) or after the inverse decomposition operation (T-1). 6. The method as claimed in claim 4, according to which the cryptographic calculation furthermore includes a linear operation and according to which said masked linear operation is performed after the decomposition operation (T) and before the inverse decomposition operation (T-1) . 7. The method as claimed in claim 4, according to which the decomposition operation (T) is applied at the start of the cryptographic algorithm and the inverse decomposition operation (T-1) at the end of the cryptographic algorithm. 8. The method as claimed in any one of the preceding claims, according to which the step of generating the masked intermediate data blocks comprises masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two unmasked data blocks. 9. The method as claimed in any one of the preceding claims, according to which the step of combining the AMENDED SHEET - 23 - intermediate data blocks and the modified data block comprises masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two unmasked data blocks. 10. The method as claimed in any one of the preceding claims, according to which a data block has a size of a byte, the substitution table has a size of 8 bytes; and according to which the nonlinear operation is bijective and, for the non null elements, is a multiplicative inversion in a finite field. 11. The method as claimed in any one of the preceding claims, according to which a data block is masked by carrying out an exclusive or between the data block and a random mask. 12. The method as claimed in any one of the preceding claims, according to which the cryptographic algorithm takes as input a message comprising a determined number of initial data blocks of size k, and according to which, sequentially for each of the initial data blocks of said message, a substitution table is generated and stored and then said data block is processed. 13. The method as claimed in claim 12, according to which the substitution tables are generated and stored simultaneously for each of the initial data blocks of the message, then said data blocks of the message are processed simultaneously. 14. The method as claimed in claim 12 or 13, according to which, a data block is encrypted using, for all the operations of the cryptographic algorithm, a AMENDED SHEET - 24 - substitution table generated at the start of the cryptographic algorithm. 15. The method as claimed in claim 12 or 13, according to which a substitution table is generated before each masked nonlinear operation. 16. The method as claimed in claim 12 or 13, according to which the algorithm comprises a determined number of rounds, and according to which a substitution table is generated and stored for at least the first round and at least the last round. 17. The method as claimed in any one of the preceding claims, according to which the cryptographic algorithm is the AES. 18. An electronic component for carrying out a cryptographic calculation according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer greater than 2, the component comprising, means for generating several masked blocks of j bits from an initial data block of k bits, ^ being an integer smaller than k; means for applying a nonlinear operation S, corresponding to said specified nonlinear operation, to at least one of the masked blocks of j bits by means of a substitution table with 2j entries producing a modified block of j bits; means for combining the modified block of j bits and certain at least of said masked blocks of j bits into a result block of k bits corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation. AMENDED SHEET - 25 - 19. The electronic component as claimed in claim 18, according to which the cryptographic algorithm is the AES. Dated this 11th day of December, 2006 AMENDED SHEET ABSTRACT "METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION" A cryptographic calculation is carried out in an electronic component according to a specific cryptographic algorithm including at least one specified non-linear operation on blocks of data of k bits, k being a whole number of more than 2. Several blocks of masked intermediate data of j bits (b?ml, c?m2, ??n) are generated from an initial block of data of k bits (a), j being a whole number that is smaller than k. Then a non-linear operation S is applied to at least one of the masked intermediate data blocks of j bits (??n) with the aid of a substitution table (106) with 2 inputs producing a modified data block of j bits (S(?)?n). The modified data blocks of j bits and some, at least the masked intermediate data blocks of j bits are combined to form a result block of k bits (a) corresponding to the initial data block of k bits by means of a transformation including the specified non linear operation.

Full Text

FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
“METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION"
SAGEM DEFENSE SECURITE,
a French company of Le Ponant de Paris 27, rue Leblanc 75015 Paris, France.
The following specification particularly describes the invention and the manner in which it is to be performed.

WO 2006/008355

-2-

PCT/FR2005/001376

Method and device for carrying out a cryptographic
calculation
The present invention pertains to the area of
5 cryptography and more particularly to the protection of the confidentiality of the keys used by cryptographic algorithms. It is described hereinbelow in its nonlimiting application to encryption or decryption functions.
10
Algorithms for encryption, respectively for decryption, or again for enciphering, are aimed at encrypting, respectively decrypting, data. Such algorithms generally comprise a chaining together of several
15 operations, or calculations, that are applied successively to a data item to be encrypted so as to obtain an encrypted data item. These algorithms use secret keys.
20 Such encryption algorithms may suffer from "attacks" which are aimed at violating the confidentiality of keys used. Numerous types of attacks are known today.
Thus, certain attacks are based on information leaks
25 detected during the execution of the encryption algorithm. These attacks are generally founded on a correlation between the information leaks detected during the processing by the encryption algorithm of the data item and of the key or keys (attacks by
30 analyzing the consumption of current, electromagnetic emanations, calculation time, etc).
Procedures for protecting against such attacks are known. One of the protection procedures commonly used
35 is the random masking of the intermediate data manipulated by the encryption or decryption algorithm. In this type of protection, the input data are masked by random values. Thus, the intermediate data resulting

WO 2006/008355

-3- PCT/FR2005/001376

from the operations performed in the algorithm may be decorrelated from the key or keys.
The attacks which are aimed at violating the
5 confidentiality of the secret keys of an encryption algorithm are similar to the attacks aimed at violating the confidentiality of the secret keys of a decryption algorithm. In the following sections the characteristics described in relation to an encryption
10 algorithm also relate to a decryption algorithm.
An encryption algorithm generally comprises several linear and/or nonlinear operations. For an initial data item to be encrypted, an intermediate data item is
15 obtained after each of the operations of the encryption algorithm. When masked intermediate data are manipulated, a masked intermediate data item is obtained after each operation. The encryption algorithm is thus protected.
20
It is however useful to recover the unmasked intermediate data item after each of these operations by "demasking" the data item. It is easy to demask an intermediate data item resulting from a linear
25 operation. Specifically, a linear operation L applied to a data item x masked by an exclusive or with a random mask m, may be written in the form:
L(x Å m)=L(x) Å L(m) .
30 Thus, knowing m, it is easy to demask L(xÅm) to obtain L(x).
It is entirely otherwise for nonlinear operations. Specifically, for a nonlinear operation F applied to a
35 data item x masked by an exclusive or with a random mask m, it is generally possible to write:
F(xÅm)*F(x) ÅF(m) .

WO 2006/008355 - 4 - PCT/FR2005/001376
In order to demask an intermediate data item manipulated by the encryption algorithm, it is necessary to perform a series of calculations which may
5 be complex and expensive depending on the encryption algorithm to be protected.
Encryption algorithms are known that use nonlinear operations, such as the DES ("data encryption
10 standard") algorithm or else the AES ("advanced encryption standard") algorithm. Several methods of protection by masking of the AES algorithm have already been proposed.
15
In such algorithms, the nonlinear operations are generally implemented in the form of substitution tables. Thus, a nonlinear operation corresponding to a substitution table tab[i], applied to a data item x may be written in the following form:
20
y=tab [x] .
The protection by masking in this case requires the generation on the fly of the randomly masked tables. Thus, a masked nonlinear operation corresponding to a
25 masked substitution table tab’ [i], applied to a data item x masked by a random mask ml may be written in the form:
y'=tab' [xÅml]=yÅm2
30 In order to be able to demask the data item y' thus obtained, a solution consists in storing the masked tables. Protection procedures of this type are proposed for the DES encryption algorithm in the document by Louis Goubin and Jacques Patarin 'DES and Differential
35 Power Analysis - The "Duplication" Method', in Cetin Kaya Koc and Christof Paar, editors, Proceedings of CHES'99, volume 1717 of 'Lecture Notes in Computer

WO 2006/008355 - 5 - PCT/FR2005/001376
Science’, pages 158-172, Springer-Verlag, 2000, as well as in patent FR 2802741 'Dispositif mettant en oeuvre un algorithme de chiffrage par bloc a repetition de rondes' [device implementing a blockwise encryption
5 algorithm with repetition of rounds].
However, such a solution may turn out to be extremely expensive in terms of memory room, in particular when the unmasked substitution table is of relatively large
10 size.
For example, the nonlinear operation of the AES may be implemented using a substitution table having a size of 256 bytes. The simultaneous encryption of 16 bytes of a
15 message requires the storage of 16 masked substitution tables each of 256 bytes. The memory size required to mask the nonlinear operation thus implemented is consequently 4 Kb.
20 A drawback of this type of protection is therefore that it requires a consequential memory size.
Also known is the document 'Provably Secure Masking of AES’ by Johannes Blomer, Guarjardo Merchan, and Volker
25 Krummel published on 04-30-04 and the document 'Secure and Efficient Masking of AES - A Mission Impossible' version 1 of E. Oswald, Stephan Mangard and Norbert Pramstaller dated from 4 June 2004 which propose that the nonlinear operation of the AES algorithm be carried
30 out in the finite field GF(4).
The latter article proposes a procedure for masking the operations of the AES algorithm in which the nonlinear operation of an intermediate masked data item is
35 transformed into a linear operation by transposition from one finite field (GF(28)) to another (GF(4)).

WO 2006/008355 - 6 - PCT/FR2005/001376
However, such a method of masking of the AES proposes that the nonlinear operations be carried out in GF(4) and hence that bits be manipulated 2 by 2.
5 In general, it is easier to efficaciously implement operations carried out on blocks of bits of size substantially equal to the number of bits processed simultaneously by the microprocessor used rather than operations carried out on blocks of bits of size very
10 substantially different from the number of bits processed simultaneously by the microprocessor.
Thus, an efficacious implementation of an encryption algorithm manipulating bits 2 by 2 is not easy on 8,
15 16, 32 or even 64-bit microprocessors.
The present invention is aimed at proposing a solution to alleviate these drawbacks.
20 A first aspect of the invention proposes a method of executing a cryptographic calculation in an electronic component, according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer
25 greater than 2, the method comprising the following steps:
generating several masked intermediate data
blocks of j bits from an initial data block of
k bits, j being an integer smaller than k;
3 0 applying a nonlinear operation to at least one
of the masked intermediate data blocks of j
bits by means of a substitution table with 2j
entries producing a modified data block of j
bits;
35 combining the modified data block of j bits and
certain at least of said masked intermediate data blocks of j bits into a result block of k

WO 2006/008355 - 7 - PCT/FR2005/001376
bits corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation.
5 Thus, it is possible to carry out the nonlinear operation specified on data blocks of size k on data blocks of size j by generating several intermediate data blocks of size j, the sizes being expressed in bits, from a data block of size k. After having
10 manipulated the intermediate data blocks, and in particular applying a nonlinear operation, data blocks thus obtained are combined to recover a data block of size k corresponding to a transformation of the initial data block. This transformation includes the specified
15 nonlinear operation. It may also include other operations of the algorithm. Specifically, it may be advantageous to carry out other operations of the algorithm on data blocks of j bits rather than data blocks of k bits, before combining these blocks to
20 again obtain a data block of k bits.
The step of generating several intermediate data blocks from an initial data block may comprise several steps, as detailed in the following sections. Thus,
25 advantageously data blocks of smaller size than the initial data block to be encrypted by the algorithm are manipulated. Consequently the nonlinear operation specified, included in the encryption algorithm may be applied to the intermediate data blocks of smaller size
30 and therefore the substitution table corresponding to the nonlinear operation applied to the intermediate data blocks is of strictly smaller size than the size of a substitution table which would correspond to the specified nonlinear operation of the algorithm applied
35 to the initial data block.
By virtue of these provisions, it is possible to

WO 2006/008355 - 8 - PCT/FR2005/001376
protect by masking the cryptographic calculations of an encryption algorithm which comprises a nonlinear operation, in particular in the case where this nonlinear operation would correspond to a substitution
5 table of relatively large size.
The masking step may advantageously be carried out either on the initial data blocks, before the step consisting in generating the intermediate data blocks,
10 or on the intermediate data blocks.
In an embodiment of the present invention, the
generating step comprises a decomposition operation (T)
consisting in decomposing a data block of k bits into
15 data blocks of j blocks (b, c) and the combining step
comprises an inverse decomposition operation(T-1)
consisting in composing a data block of k bits(a’)
from the data blocks of j bits (B, C).
20 In an embodiment of the present invention, the cryptographic calculation furthermore includes at least one linear operation and the masked linear operation is performed before the decomposition operation T or after the inverse decomposition operation T-1. In this case,
25 when the encryption algorithm comprises linear operations before the nonlinear operation, the decomposition operation T is performed after the linear operations. When the encryption algorithm comprises linear operations after the nonlinear operation, the
30 inverse decomposition operation T-1 is performed before the linear operations.
In another embodiment, when the encryption algorithm includes linear operations, these masked linear
35 operations are performed after the decomposition operation T and before the inverse decomposition operation T-1. Thus, when an encryption algorithm is an

WO 2006/008355 - 9 - PCT/FR2005/001376
algorithm with repetition of rounds, each of the rounds comprising at least one linear operation and at least one nonlinear operation, each round is performed after the decomposition operation T and before the
5 decomposition operation T-1.
It is also possible to apply the decomposition operation T at the start of the encryption algorithm and the inverse decomposition operation T-1 at the end
10 of the encryption algorithm. Thus, when such an algorithm is an encryption algorithm with repetition of rounds, all the operations of all the rounds of the algorithm are performed by manipulating blocks of strictly smaller size than the size of the initial data
15 block.
Figure 2 illustrates such an embodiment applied to an algorithm of ABS type. Thus, a data block of size k to be encrypted 201 is decomposed by the decomposition
20 operation T into several intermediate data blocks (202) to be encrypted of size j. The operations protected by masking 203, which are equivalent to those of the AES type algorithm that are specified for data blocks of size k, are then applied to the intermediate data
25 blocks of size j. Encrypted intermediate data blocks 204 are obtained. Next, the inverse decomposition operation T-1 is applied to obtain the encrypted data block 205 of size k. Such an embodiment therefore requires a modification of the operations of the
30 algorithm so that they are applicable to the intermediate data blocks.
The step of generating the masked intermediate data blocks may comprise masked additions and masked
35 multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and

WO 2006/008355 - 10 - PCT/FR2005/001376
providing a masked product of the two unmasked data blocks.
The step of combining the intermediate data blocks and
5 the modified data block may likewise comprise masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two
10 unmasked data blocks.
As detailed in a following section, when the initial data block has a size of a byte and when the nonlinear operation specified can be implemented by means of a
15 substitution table of size equal to 256 bytes, as in an AES type algorithm, it is advantageously possible to apply the nonlinear operation to an intermediate data block using a substitution table having a size of 8 bytes.
20
In an embodiment of the present invention, the nonlinear operation is bijective and, for the non null elements, is a multiplicative inversion in a finite field. Preferably, by convention, this operation maps
25 the element 0 to the element 0.
In an embodiment of the present invention, the encryption algorithm, taking as input a message comprising a determined number of initial data blocks
30 of size k, processes each of the initial data blocks sequentially. Thus, a substitution table is generated and stored for each initial data block and then each data block is processed one after the other.
35 In another embodiment of the present invention, the encryption algorithm processes all the data blocks of an input message simultaneously. Thus, the substitution

WO 2006/008355 -11 - PCT/FR2005/001376
tables are generated and stored simultaneously for each of the initial data blocks of the message, then said data blocks of the message are processed simultaneously. This type of simultaneous processing of
5 blocks requires a memory area of larger size than the sequential processing of data blocks. In such a context, as detailed in a following section, it turns out to be very advantageous to reduce the substitution table corresponding to the nonlinear operation, as is
10 proposed by the present invention.
In an embodiment of the present invention, an initial data block is processed using, each time the nonlinear operation of the encryption algorithm is carried out, a
15 substitution table generated at the start of the encryption algorithm. Thus, the same substitution table is used throughout the processing of an initial data block by the encryption algorithm.
20 It is also possible to generate and store a substitution table before each masked nonlinear operation. In this embodiment, a new substitution table is used before each application of the nonlinear operation.
25
Such algorithms conventionally comprise several rounds each comprising linear operations and at least one nonlinear operation. The most frequent attacks of the execution of calculations in such algorithms are based
30 on detections of information leakage during the execution of the first rounds and of the last rounds, since it is the rounds that manipulate data blocks close to the data blocks to be encrypted and encrypted data blocks. Thus, to protect such algorithms from
35 these attacks, it is possible to mask the data blocks manipulated in the first round or rounds and/or in the last round or rounds. Consequently, it may be

WO 2006/008355 - 12 - PCT/FR2005/001376
advantageous to generate and store substitution tables for at least the first round and at least the last round.
5 A second aspect of the present invention proposes an electronic component for executing a cryptographic calculation according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer
10 greater than 2, the component comprising,
means for generating several masked blocks of j
bits from an initial data block of k bits, j
being an integer smaller than k;
means for applying a nonlinear operation to at
15 least one of the masked blocks of j bits by
means of a substitution table with 2j entries
producing a modified block of j bits;
means for combining the modified block of j
bits and certain at least of said masked blocks
20 of j bits into a result block of k bits
corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation.
25 By virtue of these provisions, it is possible to protect, from information leakage detection attacks, an electronic component employing an encryption algorithm of AES type comprising a nonlinear operation by manipulating masked data blocks and by using masked
30 substitution tables of size equal to 8 bytes instead of masked substitution tables of size equal to 256 bytes.
Consequently, such a method of protecting an encryption algorithm requires a relatively small memory size. It
35 may therefore be employed in electronic encryption components exhibiting a memory area of relatively small size
WO 2006/008355 - 13- PCT/FR2005/001376
Additionally, in an embodiment of the present invention, intermediate data blocks of size 4 bit are manipulated. Such a size allows efficacious
5 implementation that is easier to carry out than when data blocks of lesser size are manipulated.
Other aspects, aims and advantages of the invention will become apparent on reading the description of one
10 of its embodiments.
The invention will also be better understood with the aid of the drawings, in which:
- figure 1 illustrates a method of protecting an
15 encryption algorithm according to an embodiment of the present invention;
- figure 2 illustrates a method of protecting an encryption algorithm of AES type according to an embodiment of the present invention.
20
In an embodiment of the present invention, use is made of well-known mathematical properties of finite fields (or Galois fields (GF)) so as to generate from an initial data block of size k several data blocks of
25 size strictly less than k. An embodiment of the present invention is described for protecting by masking an encryption algorithm of AES type, taking as input a message composed of 16 bytes, each of the bytes being processed by a repetition of rounds each comprising a
30 sequence of linear operations and at least one nonlinear operation. The invention covers other types of encryption algorithm comprising at least one nonlinear operation, whether or not there is repetition of rounds.
35
In an AES type algorithm, the nonlinear operation corresponds to a multiplicative inversion, for the non

WO 2006/008355 - 14 - PCT/FR2005/001376

null elements, in the finite field GF(28). Thus, to generate from a data block several intermediate data blocks of strictly smaller size, in an embodiment of the invention, it is proposed that the nonlinear
5 operation be transposed from the field GF(28) to the field GF((24)2) .
The document by Tsing-Fu Ling, Chih-Pin Su, Chih-Tsun Huang, and Cheng-Wen Wu 'A high-throughput low-cost AES
10 cipher chip’, and also the document by Vincent Rijmen 'Efficient implementation of the Rijndael S-box' and the document by Atri Rudra, Pradeep K. Dubey, Charanjit S. Jutla, Vijay Kumar, Josyula R. Rao, and Pankaj rohatgi 'Efficient Rijndael Encryption Implementation
15 with Composite Field Arithmetic' and then the document by R.W. Ward and T.C.A. Molteno 'Efficient hardware calculation of inversion in GF (28) ' are known which show how the nonlinear operation of the AES algorithm can be transported into the compound field GF((24)2) and
20 which show that such a transposition makes it possible to improve the performance of the encryption algorithm.
Conventionally, the AES therefore takes as input a message composed of 16 bytes. Several rounds are
25 applied to each of these bytes, each round using a subkey derived from the main secret key. The AES generally comprises the following operations:
- a nonlinear operation, conventionally referenced SubBytes, corresponding to a substitution table
30 from 8 bits to 8 bits which is applied to each of the 16 bytes of the input message;
- a linear exclusive or operation, conventionally referenced AddRoundKey, applied between the 16 bytes of the subkey and the 16 bytes of the input
35 message;
- a linear operation, conventionally referenced ShiftRows, corresponding to a permutation applied

WO 2006/008355 - 15 - PCT/FR2005/001376
to the 16 bytes;
- a linear operation, conventionally referenced
mixed columns, applied to the 16 bytes.
5 The SubBytes operation of the AES algorithm comprises a nonlinear operation which corresponds, in the finite field GF(28), for the non null elements, to a multiplicative inversion. Such an operation may be transported into the compound field GF((24)2, so that
10 data blocks of size 4 bits are manipulated, before carrying out the inverse decomposition operation T-1 for other operations manipulating bytes.
We choose a representation of GF(24) and the field
15 polynomial as follows:
P(x)=x2+Dx+E;
D and E being elements of the finite field GF(24))
So that we may write:
20 GF(28)=GF(24) [x]/P(x)
Figure 1 illustrates an embodiment of the present invention.
25 We construct the decomposition operation T 102 which
may be written: T(a)=bx+c;
where a is an element of GF(28)
where (bx + c) is an element of GF((24)2), and b and c 30 are elements of the finite field GF(24)).
This decomposition operation T generates from the data block a of size equal to one byte intermediate data blocks b and c of size equal to 4 bits.
35
This decomposition operation may be implemented in the form of a multiplication with an 8x8 matrix.

WO 2006/008355

- 16 -

PCT/FR2005/001376

After this decomposition operation, the data blocks manipulated are intermediate data blocks of size 4 bits, strictly smaller than the size of the initial
5 8-bit block.
Such a decomposition operation T makes it possible to reduce the size of the data blocks manipulated in such a way as to be able to reduce the size of the
10 substitution table corresponding to the first nonlinear operation. It is therefore carried out before performing the nonlinear operation. However, it may be carried out at various steps of the encryption algorithm. Thus, on each of the 16 bytes of the input
15 message, this decomposition operation can be carried out either at the start of the algorithm, or at the start of each of the rounds of the algorithm, or else before each application of the nonlinear operation.
20 The present invention covers the embodiments wherever the algorithm step in which this decomposition operation is carried out.
Next, when the nonlinear operation using the
25 substitution table has been performed, it is possible to carry out the inverse decomposition operation T-1 to return to the finite field GF(28) and again manipulate bytes.
30 The present invention covers the embodiments wherever the algorithm step in which the inverse decomposition operation is carried out.
According to the steps in which the decomposition
35 operation T and the inverse decomposition operation T-1
are carried out, other determined operations of the
algorithm in GF(28) are adapted to the finite field

WO 2006/008355 - 17- PCT/FR2005/001376
GF((24)2) .
Thus, if the decomposition operation T is performed before the nonlinear operation and then if the inverse
5 decomposition operation T-1 is performed after the nonlinear operation, it is not necessary to adapt other operations of the algorithm to the finite field GF((24)2). On the other hand, in the case where the decomposition operation T is performed at the start of
10 the algorithm and the inverse decomposition operation T-1 at the end of the encryption algorithm, all the operations of the algorithm are adapted to the finite field GF((24)2). The operations of the encryption algorithm are then replaced by their equivalents in the
15 finite field GF((24)2).
In an embodiment of the present invention, we mask 103 at least the intermediate data blocks manipulated at the time of the nonlinear operation for at least the
20 first round and the last round of the AES algorithm, as detailed by the following sections. The invention also covers an embodiment in which the intermediate blocks manipulated at the time of the nonlinear operation are masked for all the rounds of the algorithm or else an
25 embodiment in which all or part of the intermediate data blocks manipulated in the course of the execution of the algorithm are masked, whether these data blocks are elements of GF(28) or of GF((24)2) .
30 In an embodiment of the present invention, the nonlinear operation is a multiplicative inversion in GF(24) for the non null elements.

In the finite field GF((24)2), the inversion of an 35 element (bx + c) may be written in the following form: (bx+c)-1=bΔ-1x + (c + b D) Δ-1;
where Δ=b2E + bcD + c2.

WO 2006/008355 -18 - PCT/FR2005/001376
Thus, the first nonlinear operation of multiplicative inversion of the finite field GF(28) transposed into the finite field GF((24)2), corresponds to multiplications,
5 additions and the nonlinear operation of the multiplicative inversion. This nonlinear operation in the finite field GF((24)2) may be implemented through a 4-bit to 4-bit substitution table occupying 8 bytes.
10 As was described, one wishes to mask the data blocks thus manipulated. The masking of the additions is well known.
In order to mask the multiplications, a masked
15 multiplication algorithm M(x, y, z))104 is introduced. In what follows, the elements ml, m2, m3, n, n', nl, n2 are random masks. Such an algorithm takes as input:
- masked elements of GF(24), (b Å ml) and (c Å m2) ; - a mask m3.
20
Such an algorithm outputs the masked product in the form:
bc Å m3.
25 The following steps may be written:
u = (b Å ml) (c Å m2) = bc Å bm2 Å cml Å mlm2
v = (c Å m2)ml = cml Å mlm2
w = (b Å ml)m2 = bm2 Å mlm2
M(bÅml, cÅm2, m3) = uÅvÅwÅ mlm2 Å
30 m3 = bc Å m3.
In an embodiment of the present invention, the first intermediate data blocks are masked. One thus obtains a first masked decomposition which may be written in the
35 following form:
(b Å ml)x + (c Å m2) .

Next we use the masked multiplication algorithm to calculate the masked multiplication in the following form:
M(b Å ml, c Å m2, m3) = bc Å m3.
5
Next, in the same way, we calculate, according to step 105, the following products to obtain the masked data block Δ:
p = (bc Å m3)D = bcD Å m3D; 10 q = (b Å ml)2E = b2E Å ml2E;
r = (c Å m2)2 = c2 Å m22.
Consequently we obtain the following equation: p Å q Å r Å ml2E Å m22 Å m3DÅ n = Δ Å n.
15
Thus, in the finite field GF(24) by addition and multiplication we obtain the masked data block, A © n, to which the nonlinear operation of multiplicative inversion is applied.
25
20
In an embodiment of the present invention, this nonlinear operation is carried out on the masked data block using a masked substitution table, tab[x], according to step 106, satisfying the following equation:
tab[x Å n] = x-1 Å n' .
This masked substitution table therefore makes it possible to obtain the inversion of the masked data
30 block, i.e. Δ-1 Å n' .
By applying the masked multiplication algorithm, we calculate:
-M(b Å ml, Δ-1 Å n', n1)=bΔ-1 Å nl = B;
35 - M(bD + c) Å (mlD + m2) , Δ-1 Å n', n2) = (bD + c) . Δ-1 Å n2 = C.

WO 2006/008355 - 20 - PCT/FR2005/001376
Thus, by combining 108 the masked data blocks b Å ml, c Å m2 and Δ-1 Å n', we obtain Bx +C.
We therefore obtain a masked value of (bx+c)-1 without
5 having to manipulate, in order to carry out this nonlinear operation, the unmasked data blocks b, c and Δ.
Next, the inverse decomposition operation T-1 109 is 10 carried out to obtain an element 110:
a' = T-1 (Bx + C) .
In an embodiment of the present invention, D is determined equal to 1 so as to reduce the number of
15 multiplications to be performed.
Advantageously, a nonlinear operation is therefore transposed from the finite field 6P(28) to the finite field GF((24)2) in which the nonlinear operation
20 corresponds to a combination, of additions, of multiplications and of an equivalent nonlinear operation in a field having fewer elements.
Thus, it is possible to protect electronic components 25 from attacks by detection of information leakage during the execution of a cryptographic calculation comprising a nonlinear operation by carrying out operations equivalent to this nonlinear operation on data blocks of reduced size, thereby making it possible to carry
30 out these calculations on masked data blocks since the corresponding substitution table is of reduced size.

- 21 -CLAIMS
1. A method for carrying out a cryptographic
calculation in an electronic component, according to a
determined cryptographic algorithm including at least
one nonlinear operation specified on data blocks of k
bits, k being an integer greater than 2, the method
comprising the following steps:
-generating several masked intermediate data blocks of j bits (bÅml, cÅm2, ΔÅn) from an initial data block of k bits (a) , j being an integer smaller than k;
applying a nonlinear operation S, corresponding to said specified nonlinear operation, to at least one of the masked intermediate data blocks of j bits (ΔÅn) by means of a substitution table (106) with 2j entries producing a modified data block of j bits (S(Δ) Ån’) ;
combining the modified data block of j bits and certain at least of said masked intermediate data blocks of j bits into a result block of k bits (a’) corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation.
2. The method as claimed in claim 1, according to which the initial data block is masked before the step consisting in generating the intermediate data blocks.
3. The method as claimed in claim 1, according to which the intermediate data blocks (103) are masked before applying the nonlinear operation.
4. The method as claimed in any one of the preceding claims, according to which the generating step comprises a decomposition operation (T) consisting in

AMENDED SHEET

- 22 -
decomposing a data block of k bits into data blocks of j blocks (b, c) and the combining step comprises an inverse decomposition operation (T-1) consisting in composing a data block of k bits from the data blocks of j bits (B, C) into a data block of k bits (a’).
5. The method as claimed in claim 4, according to which the cryptographic calculation furthermore includes at least one linear operation and according to which said masked linear operation is performed before the decomposition operation (T) or after the inverse decomposition operation (T-1).
6. The method as claimed in claim 4, according to which the cryptographic calculation furthermore includes a linear operation and according to which said masked linear operation is performed after the decomposition operation (T) and before the inverse decomposition operation (T-1) .
7. The method as claimed in claim 4, according to which the decomposition operation (T) is applied at the start of the cryptographic algorithm and the inverse decomposition operation (T-1) at the end of the cryptographic algorithm.
8. The method as claimed in any one of the preceding claims, according to which the step of generating the masked intermediate data blocks comprises masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two unmasked data blocks.
9. The method as claimed in any one of the preceding claims, according to which the step of combining the
AMENDED SHEET

- 23 -
intermediate data blocks and the modified data block comprises masked additions and masked multiplications which are carried out according to a masked multiplication algorithm taking masked data blocks of size j and a random mask as input and providing a masked product of the two unmasked data blocks.
10. The method as claimed in any one of the preceding claims, according to which a data block has a size of a byte, the substitution table has a size of 8 bytes; and according to which the nonlinear operation is bijective and, for the non null elements, is a multiplicative inversion in a finite field.
11. The method as claimed in any one of the preceding claims, according to which a data block is masked by carrying out an exclusive or between the data block and a random mask.
12. The method as claimed in any one of the preceding claims, according to which the cryptographic algorithm takes as input a message comprising a determined number of initial data blocks of size k, and
according to which, sequentially for each of the initial data blocks of said message, a substitution table is generated and stored and then said data block is processed.
13. The method as claimed in claim 12, according to which the substitution tables are generated and stored simultaneously for each of the initial data blocks of the message, then said data blocks of the message are processed simultaneously.
14. The method as claimed in claim 12 or 13, according to which, a data block is encrypted using, for all the operations of the cryptographic algorithm, a
AMENDED SHEET

- 24 -
substitution table generated at the start of the cryptographic algorithm.
15. The method as claimed in claim 12 or 13, according to which a substitution table is generated before each masked nonlinear operation.
16. The method as claimed in claim 12 or 13, according to which the algorithm comprises a determined number of rounds, and according to which a substitution table is generated and stored for at least the first round and at least the last round.
17. The method as claimed in any one of the preceding claims, according to which the cryptographic algorithm is the AES.
18. An electronic component for carrying out a cryptographic calculation according to a determined cryptographic algorithm including at least one nonlinear operation specified on data blocks of k bits, k being an integer greater than 2, the component comprising,
means for generating several masked blocks of j bits from an initial data block of k bits, ^ being an integer smaller than k;
means for applying a nonlinear operation S, corresponding to said specified nonlinear operation, to at least one of the masked blocks of j bits by means of a substitution table with 2j entries producing a modified block of j bits; means for combining the modified block of j bits and certain at least of said masked blocks of j bits into a result block of k bits corresponding to the initial data block of k bits through a transformation including said specified nonlinear operation.
AMENDED SHEET

- 25 -
19. The electronic component as claimed in claim 18, according to which the cryptographic algorithm is the AES.

Dated this 11th day of December, 2006

AMENDED SHEET

ABSTRACT
"METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION"
A cryptographic calculation is carried out in an electronic component according to a specific cryptographic algorithm including at least one specified non-linear operation on blocks of data of k bits, k being a whole number of more than 2. Several blocks of masked intermediate data of j bits (b?ml, c?m2, ??n) are generated from an initial block of data of k bits (a), j being a whole number that is smaller than k. Then a non-linear operation S is applied to at least one of the masked intermediate data blocks of j bits (??n) with the aid of a substitution table (106) with 2 inputs producing a modified data block of j bits (S(?)?n). The modified data blocks of j bits and some, at least the masked intermediate data blocks of j bits are combined to form a result block of k bits (a) corresponding to the initial data block of k bits by means of a transformation including the specified non linear operation.

METHOD AND DEVICE FOR CARRYING OUT A CRYPTOGRAPHIC CALCULATION

Documents:

Inventors:

PCT Conventions: