Method and system for protecting a cryptographic operation

Abstract

There is provided a device or a method for executing an operation of a cryptographic scheme, the operation being applied to a given state of a data block of original data, the operation being defined in a basis ring corresponding to the quotient of a starting ring by a basis ideal generated by at least one element of the starting ring. The operation is executed from a state derived from the current state of the data block, in at least one reference ring, which provides a reference value for each reference ring, each reference ring being the quotient of the starting ring by a reference ideal. The operation is executed from the state derived from the current state of the data block in at least one extended ring corresponding to one or more reference rings, which provides at least one extension value for each extended ring, each extended ring corresponding to one or more reference ring being the quotient of the starting ring by the product of the basis ideal and of the reference ideals of the one or more corresponding reference rings.

Claims

1. A device for executing an operation of a cryptographic scheme, said operation being applied to a given current state of a data block of original data, said operation being defined in a basis ring corresponding to the quotient of a starting ring by a basis ideal generated by at least one element of the starting ring, wherein said device comprises: one or more processors configured to: execute the operation from a state derived from said current state of the data block, in at least one reference ring, which provides a reference value for each reference ring, each reference ring being the quotient of said starting ring by a reference ideal, and execute the operation from said state derived from said current state of the data block in at least one extended ring corresponding to one or more of said reference rings, which provides at least one extension value for each extended ring, each extension value comprises one or more bytes, each extended ring being the quotient of the starting ring by the product of the basis ideal and of the reference ideals of said one or more corresponding reference rings, determine the result of said operation from at least one of the reference values and/or of the extension values depending on the verification of a condition between the reference value obtained for each reference ring and the extension values obtained for the extended rings corresponding to said reference ring, map each byte of said at least one extension value to an element of the basis ring, in response to the verification of said condition, for at least one extension value, which provides a mapped value corresponding to said at least one extension value.

2. The device of claim 1, wherein the one or more processors are further configured to: select a set of elements in the basis ideal; modify the current state of the data block from said selected elements, which provides said state derived from the current state of the data block.

3. The device of claim 1, wherein the one or more processors are further configured to: execute said operation from said state derived from the current state of the data block in said extended ring, which provides an intermediary value for each extended ring comprises one or more bytes; map each byte of the intermediary value resulting from the execution of the operation in said extended ring to an element of the reference ring associated with said reference ring, which provides an extension value corresponding to said reference ring, wherein said condition comprises a comparison between each reference value and the extension value corresponding to said reference ring.

4. The device of claim 3, wherein said condition is verified if each reference value matches each extension value corresponding to said reference ring, the result of said operation depending on the verification of said condition for each reference value.

5. The device of claim 3, wherein said at least one reference rings comprises a set of two or more reference rings, the one or more processors are further configured to execute said operation in at least two reference rings of said set of reference rings; execute said operation in a unique extended ring depending on all the reference rings of said set of reference rings; apply a CRT transformation to all the reference values determined, which provides a reference parameter related to said set of reference rings, said condition comprising determining if said reference parameter is equal to an element corresponding to the extension value obtained for the extended ring in an ideal represented by the product of the reference ideals of said at least two reference rings.

6. The device of claim 3, wherein the one or more processors are further configured to execute said operation in at least two reference rings; execute said operation in at least two extended rings; each extended ring depending on a set of reference rings; apply a CRT transformation to each reference value determined, which provides a common reference parameter related to each said set of reference rings; for each extension value obtained as a result of the execution of the operation in an extended ring depending on a given set of reference rings, map each byte of the extension value to an element of a ring quotiented by the product of the reference ideals of each reference ring of said set of reference rings, which provides a common extension parameter, wherein said condition comprises comparing each common reference parameter related to a given set of reference rings to the common extension parameter obtained for the extended rings depending on said set of reference rings.

7. The device of claim 1, wherein the one or more processors are further configured to check an auxiliary condition, said auxiliary condition comprising comparing at least some of the mapped values to the reference values; and trigger a termination of the operations of said cryptographic scheme if at least one mapped value differs from a reference value.

8. The device of claim 7, wherein the one or more processors are further configured to return one of the mapped values as the operation result if the auxiliary condition is verified.

9. The device of claim 1, wherein the one or more processors are configured to execute said operation in a plurality of reference rings, which provides a set of reference values; and execute said operation in a unique extended ring corresponding to one or more reference rings.

10. A system for executing a cryptographic scheme comprising a set of successive operations on a given data block of original data using at least one secret key, wherein it comprises the device according to claim 1 configured to protect at least one operation of said cryptographic scheme.

11. The system of claim 10, wherein said operation execution device is applied to each operation of the cryptographic scheme.

12. The system of claim 10, wherein the cryptographic scheme comprises a plurality of rounds, and said operation execution device is applied to protect at least one operation of at least one round.

13. The system of claim 10, wherein the cryptographic scheme is an Advanced Encryption Standard scheme comprising a first non-linear substitution operation at each round, said non-linear substitution operation replacing each byte of a data block with another according to a lookup table, and successive operations.

14. The system of claim 13, wherein said successive operations comprise a final combination operation at each round, said combination operation combining each byte of the state of a data block with a block of the round key using a bitwise XOR operator, and wherein said operation execution device is only applied to the final combination operation at least one round.

15. A method of executing an operation of a cryptographic scheme, said operation being applied to a given current state of a data block of original data, said operation being defined in a basis ring corresponding to the quotient of a starting ring by a basis ideal generated by at least one element of the starting ring, wherein the method comprises executing the operation from a state derived from said current state of the data block, in at least one reference ring, which provides a reference value for each reference ring, and in at least one extended ring corresponding to one or more of said reference rings, which provides at least one extension value for each extended ring, each extension value comprises one or more bytes, each reference ring being the quotient of said starting ring by a reference ideal, and each extended ring being the quotient of the starting ring by the product of the basis ideal and of the reference ideals of said one or more corresponding reference rings; determining the result of said operation from at least one of the reference value and/or of the extension values depending on the verification of a condition between the reference value obtained for each reference ring and the extension values obtained for the extended rings corresponding to said reference ring; and mapping each byte of said at least one extension value to an element of the basis ring, in response to the verification of said condition, for at least one extension value, which provides a mapped value corresponding to said at least one extension value.

16. A method of executing a cryptographic scheme, the cryptographic scheme comprising a succession of operations on at least one data block of original data using at least one secret key, wherein the method applies the method of claim 15 to at least one operation of the cryptographic scheme.

17. A computer program product for executing an operation of a cryptographic scheme, said operation being applied to a given current state of a data block of original data, said operation being defined in a basis ring corresponding to the quotient of a starting ring by a basis ideal generated by at least one element of the starting ring, wherein the computer program product comprises: a non-transitory computer readable storage medium; and instructions stored on the non-transitory computer readable storage medium that, when executed by one or more processors, cause the one or more processors to; execute an operation from a state derived from said current state of the data block, in at least one reference ring, which provides a reference value for each reference ring, and in at least one extended ring corresponding to said one or more reference rings, which provides at least one extension value for each extended ring, each extension value comprises one or more bytes, each reference ring being the quotient of said starting ring by a reference ideal, and each extended ring being the quotient of the starting ring by a product of the basis ideal and of the reference ideals of said one or more corresponding reference rings; determine the result of said at least operation from at least one of the reference value and/or of the extension values depending on the verification of a condition between the reference value obtained for each reference ring and the extension values obtained for the extended rings corresponding to said reference ring; and map each byte of said at least one extension value to an element of the basis ring, response to the verification of said condition, for at least one extension value, which provides a mapped value corresponding to said at least one extension value.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate various embodiments of the invention and, together with the general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the embodiments of the invention.

(2) FIG. 1 illustrates a cryptographic system comprising a cryptographic processing unit implementing a cryptographic scheme, according to certain embodiments.

(3) FIG. 2 represents successive mathematical operations of a cryptographic scheme.

(4) FIG. 3 is a flowchart depicting the operation protection method according to certain embodiments.

(5) FIG. 4 is a flowchart depicting an embodiment of the invention of the condition step of the protection method.

(6) FIG. 5 is a flowchart an alternative embodiment of the condition step of the protection method.

(7) FIG. 6 is a flowchart depicting the step of updating the current state of the data block of the protection method, according to one embodiment.

(8) FIG. 7 is a flowchart depicting the protection method including an auxiliary condition according to an embodiment.

(9) FIG. 8 is a flowchart depicting an embodiment comprising the execution of the operation in one extended ring and the execution of the operation in several reference rings, according to certain embodiments.

(10) FIG. 9 is a flowchart depicting an exemplary embodiment of the operation protection method.

(11) FIG. 10 is a flowchart depicting an exemplary application of the invention to certain operations of the AES cryptographic scheme.

(12) FIG. 11 represents a subBytes operation of the AES scheme.

(13) FIG. 12 represents a shiftRows operation of the AES scheme.

(14) FIG. 13 represents a MixColumns operation of the AES scheme.

(15) FIG. 14 represents a AddRoundKey operation of the AES scheme.

(16) FIG. 15 is a flowchart illustrating an exemplary application of the invention to one operation of the AES cryptographic scheme, according to one embodiment.

DETAILED DESCRIPTION

(17) Embodiments of the present invention provide an improved method and system for executing a set of cryptographic operations on data, depending on the function of the application system in which the set of cryptographic operations occur. The application system may be an embedded system such as a smartcard implementing cryptographic operations to protect the data.

(18) FIG. 1 illustrates a system 100 comprising a cryptographic processing unit 10 (also referred to as a cryptosystem) implementing a cryptographic scheme 1 such as an encryption scheme, a decryption scheme or a signature scheme, using at least one secret key K to protect the data portions (also referred hereinafter as a data block) of incoming data. The incoming data may be for example binary data including N data blocks (referred to as plaintext for an encryption scheme), each block being a K-bit word of the incoming binary data. The cryptosystem 100 outputs a protected data block as a result of the execution of the operations defined by the cryptographic scheme 1 (referred to as ciphered text for an encryption scheme).

(19) As used herein, a key or a secret key refers to is a parameter used to implement a cryptographic operation. Each key may be any bit size. The cryptographic scheme comprising a set of successive operations, each executed on a current state of the data block 2 in a given starting ring. The cryptographic scheme 1 may include for example a symmetric key cryptographic function such as AES scheme (Advanced Encryption Standard), asymmetric key cryptographic functions, a hash function, etc.

(20) The cryptographic processing unit 10 may comprise logic for performing one or more rounds of the set of successive operations on the data block 2 (for example encryption operations on plaintext and/or decryption operations on ciphertext) using the keys. The keys may be provided by a key storage unit (not shown). The result of the successive operations 4 may be loaded into a result storage unit.

(21) To facilitate the understanding of certain embodiments of the invention, definitions of certain elements and notations are provided below: a ring designates communicative group with a second binary operation that is associative, distributive over the group operation and has an identity element. Usually, the two group operations are the addition and the multiplication. For example, the ring of integers with the group operations +, is a ring with the additive neutral element 0 and multiplicative neutral element 1 a field is a ring in whose nonzero elements form a commutative group under multiplication. For example, is not a field. However, the set of rational number is a field. a finite field refers to a field with a finite number of elements. Since all fields of size n are isomorphic, the field with n elements is usually denoted .sub.n. .sub.2 is the smaller field containing 0 and 1. The addition is the XOR bit-operation, the multiplication is the AND bit-operation. an ideal I of a ring A is a subgroup of A which is stable by multiplication: for every element x in I and every element a in A, axI. For example, in the ring , the multiples of 5 is an ideal, denoted 5. The product of two ideals I,J, denoted IJ, is an ideal generated by all elements xy with xI and yJ. Considering an ideal I of A, and a, bA, if abI, a and b are equal modulo I. the quotient ring A/I is the elements of A modulo I. If a and b are equal modulo I, then a and b are represented by the same element in A/I. As used herein, the operation which maps a or b to the same element in A/I is referred to as a modular reduction. The modular reduction of an element a modulo an ideal I will thus designate the operation consisting in mapping a to an element in A/I. In the following description of certain embodiments of the invention, the expression reduced value or mapped value will be used to designate the result of a modular reduction; When the ring A is the ring of the integers and the ideal I is n, then, by convention, A/I is represented by the integers comprised between 0 and n1. The modular reduction of an element a by the ideal consists in returning the remainder of the division of a by n. When A is a finite field with a number of elements p.sup.m, where p is a prime, and I is the ideal of the multiple of a polynomial P, denoted (P), A/I (A quotiented by I) is represented by the polynomials of degree smaller than P, with coefficients in A. The operation modular reduction of an element A by the ideal consists in returning the remainder of the division of a by P. An element x in .sub.q[X]/I is noted x mod I. Two ideals I,J are said coprime if 1 can be written as a combination of elements of I and J. For example, in , 5 and 3 are coprime since 109=1 and 105 and 93. 3 and 6 are not coprime.

(22) Further, as used herein: a starting ring, noted A, in relation with a cryptographic operation on a data block refers to the ring defined for the cryptographic operation; a basic ring, noted A/J, refers to the quotient of said starting ring by a basis ideal J generated by at least one element of the starting ring; a reference ring, noted A/I.sub.k, refers to the quotient of said starting ring by a reference ideal I.sub.k,k being an integer; an extended ring, noted A/JI.sub.k1I.sub.k2 . . . I.sub.kN, refers to the quotient of the starting ring by the product of the basis ideal I.sub.k1I.sub.k2 . . . I.sub.kN and of the reference ideal J; an extension value, noted C.sub.r, k1k2 . . . kN, refers to the result of a cryptographic operation run in an extended ring; a reference value, noted C.sub.k, refers to the result of a cryptographic operation run in a reference ring A/I.sub.k;

(23) According to an aspect of the invention, the cryptographic system 100 further comprises an operation executing device 12 for executing at least one of the operation of the cryptographic scheme 1 in a given basis ring. The operation executing device 12 may comprise a first execution unit 120 for executing the operation on a state of the data block m derived from the current state of data block m in at least one reference ring and a second execution unit 122 for executing the operation in at least one extended ring and by checking a condition between: at least one value derived from the results of the operation executed in one or more reference rings, and at least one value derived from the result of the operation executed in one or more extended rings.

(24) If the condition is not verified, a fault attack is detected, and a termination unit 14 may terminate the execution of the operations by the cryptographic processing unit 10. In addition, an alarm may be triggered or the error may be notified.

(25) If the condition is verified, the execution of the operations by the cryptographic processing unit 10 proceeds. The result of the operation executed in the reference rings and/the result of the operation executed in the extended ring.

(26) In addition, an alarm may be triggered or the error may be notified.

(27) The operation executing device 12 may further comprise a state updating unit 123 configured to update the current state of the data block from elements selected in the basis ideal J.

(28) Embodiments of the invention thus allow detection of an abnormal condition or defect at a component or system level triggered by a fault-attack before the fault attack results in a failure or an improper operation or an alteration of the data.

(29) As represented in FIG. 2, the cryptographic protection of a given message is typically implemented by applying one or more successive mathematical operations to this message, the operations being functions of at least one secret key and being defined in a ring A.

(30) The conventional cryptographic processing method starts on the reception of an initial state of data block m.sub.0 (200).

(31) In step 202, the round index i is initialized. For each round i (204), the set of successive operations are performed in a given ring (steps 206 to 210). This comprises running a first operation on the initial state of the data block m.sub.0, in the given ring, which provides a new state of the data block m.sub.0.sup.(1), in step 206. In step 208, the next operation (operation 2) is then run on the new state of the message m.sub.0.sup.(1) in the given ring, which provides an new state of the message m.sub.1.sup.(1). When the last round has been executed, the operation result is returned in step 216.

(32) The remaining operations j are similarly executed on each state of the message m.sub.j.sup.(1), until the last operation p is run (step 210) which provides a final state of the data block for the current round m.sub.p-1.sup.(1). If the cryptographic scheme comprises several rounds of the successive operations, steps 206 to 212 are iterated for each round I based on the final state of the data block m.sub.p-1.sup.(i-1) obtained for the previous round i1.

(33) To overcome the vulnerability of conventional cryptographic processing method to fault attack, there is provided a method for executing at least one of the operations of the set of successive mathematical operations defined in a starting ring by the cryptographic scheme, in a way that protect the operation against fault attack (the operation executing method will be also referred to hereinafter as an operation protection method).

(34) FIG. 3 is a flowchart depicting the operation protection method according to certain embodiments.

(35) The operation protection method may be applied to only one operation, to all the operations or to a set of selected operations among the set of successive operations defined in a starting ring A by the cryptographic scheme. The number of protected operations may depend on the cryptographic scheme itself and/or the level f protection required. Further, the operation protection method may be applied to only one round or to a number of rounds, depending on the application of the invention and/or criteria related to the attacks such as the values that are identified as being targetable by an attacker. For example, in the AES, an attacker will generally introduce a fault in the last round or the before last round. The protection method may thus be applied at least for the last two rounds in this example.

(36) The operation protection method applies to each target operation of the set of successive operations, the target operation being defined in a basis ring corresponding to the quotient of the starting ring A by a basis ideal J. The operation protection method starts with the reception of the current state of the data block (for example block of a message) in step 300. The state of the message may have undergone several changes as a result of the previous operations (whether protected or not).

(37) In step 302, the current state m of the data block may be modified, for example by deriving a modified state m from the current state.

(38) In step 304, the operation to be protected is executed in each reference ring A/I.sub.k (303), which provides a reference value C.sub.k corresponding to the result of the execution of the operation in the reference ring A/I.sub.k. Each reference ring represents the quotient of the starting ring A by a reference ideal I.sub.k.

(39) In step 307, the operation to be protected is further executed in each extended ring (306) of a set of extended rings A/(JI.sub.k1I.sub.k2 . . . I.sub.kN, each extended ring depending on one or more extended rings A/I.sub.k1, A/I.sub.k2, . . . , A/I.sub.N, which provides an intermediary extension value C.sub.r, k1k2 . . . kN for each extended ring A/JI.sub.k1I.sub.k2 . . . I.sub.kN (the number N is inferior or equal to the number of reference rings). Each extended ring A/JI.sub.k1I.sub.k2 . . . . I.sub.kN corresponding to one or more reference ring A/I.sub.k1, A/I.sub.k2, . . . , A/I.sub.N represents the quotient of the starting ring A by the product of the basis ideal J and of the reference ideals I.sub.k1, I.sub.k1, . . . , I.sub.kN of the corresponding reference rings.

(40) In step 312, it is determined if a condition between a reference parameter derived from one or more reference values C.sub.k and an extension parameter derived from the corresponding extension values C.sub.r, k1k2 . . . kN is satisfied.

(41) As used herein an extended ring is referred to as corresponding to or depending on a particular reference ring if the extended ring is the quotient of the starting ring A by the product of the basis ideal and one or more reference ideals associated with reference rings including that particular reference ring.

(42) In one embodiment, the condition step 312 may comprise, for each reference ring A/I.sub.k (block 310), a comparison between the reference value C.sub.k obtained as a result of the execution of the operation in this reference ring and an extension parameter derived from the intermediary extension values C.sub.r, k1k2 . . . kN obtained as a result of the execution of the operation in extended rings depending on the considered reference ring A/I.sub.k (one of the indexes k.sub.i is equal to k).

(43) If the condition is not satisfied for at least one reference ring, in step 314, a fault attack on the operation is detected and the execution of the operations of the cryptographic scheme may be terminated. In addition a report may be notified to a monitoring device monitoring the operation of the system 100.

(44) If the condition is satisfied for each reference ring, the operation value m may be determined from the reference values C.sub.k and/or the intermediary extension values C.sub.r, k1k2 . . . kN in step 318. The operation value m may be stored as the new current state of the data block, for use for the execution of the next operation of the cryptographic scheme or the next round of the cryptographic scheme. Otherwise, if all the operations and rounds of the cryptographic scheme have been run, the operation value may be returned to the user.

(45) This allows for high level of assurance of the result integrity. Further, security parameters are related to the size of reference ideal I.sub.ki (typically, fault detection probability is equal to 11/|I.sub.ki|, the size of I.sub.ki being generally a prime).

(46) The protection thus obtained may be complementary to other protection solutions such as physical sensors or higher level checks (verification of computation by checking the initial message if the message is encrypted and then decrypted . . . ).

(47) FIG. 4 is a flowchart depicting an embodiment of the invention in which the condition step is determined from an extension parameter computed for each intermediary extension value. The main steps of the flowchart of FIG. 4 are similar to the flowchart of FIG. 3, but the operation protection method further comprises for each intermediary extension value C.sub.r,k1k2 . . . kN the step of reducing each byte of the intermediary extension value modulo each reference ideal I.sub.k1, I.sub.k2, . . . I.sub.kN to obtain a set of extension values per reference ring C.sub.k1, C.sub.k2, . . . , and C.sub.kN (i.e. for each reference ring I.sub.ki, each byte of the intermediary extension value is mapped to an element of the reference ring I.sub.ki, which provides a mapped value for each reference ring comprising the mapped bytes in correspondence with the bytes of the intermediary extension value, the set of extension values C.sub.k1, C.sub.k2, . . . , and C.sub.kN comprising the mapped values).

(48) Further, in such embodiment, the extension parameter is derived from each extension value C.sub.k obtained from the execution of the operation in an extended ring depending on the reference ring A/I.sub.ki, in step 312. More specifically, for each reference ring A/I.sub.ki, in step 312, it is determined if a condition between the reference value C.sub.ki obtained as a result of the execution of the operation in the reference ring A/I.sub.ki and an extension parameter derived from the extension values C.sub.ki obtained from the execution 307 of the operation in each extended ring depending on the reference ring A/I.sub.ki and the reduction step 308 is satisfied.

(49) FIG. 5 is a flowchart depicting the condition step 312 according to one particular embodiment. In this embodiment, for each reference ring A/I.sub.ki (500), the condition step comprises comparing the reference value C.sub.ki obtained as a result of the execution of the operation in the reference ring A/I.sub.ki and each extension value C.sub.ki obtained from the operation execution step 307 in an extended ring depending on the reference ring A/I.sub.ki and the reduction step 308 (502). Each extension value C.sub.ki per reference ring is thus used as such as the extension parameter. In one embodiment, the condition may comprise comparing the reference value C.sub.ki and each extension value C.sub.ki, the condition being satisfied if the value C.sub.ki and the value C.sub.ki are equal (504). For each reference ring, step 312 may be iterated as many times as the number of extended rings depending on the reference ring.

(50) FIG. 6 is a flowchart depicting the step of updating the current state of the data block m (step 302 of FIGS. 3 and 4) according to one embodiment.

(51) In step 600, a set of K elements of the reference ring are selected. The selection may be performed randomly.

(52) In step 602, the current state of the data block is updated from the K elements selected in the basis ideal J, which modifies the current state of the data block.

(53) Without a modification of the input message block, in certain cases, the operation to execute may not be complex enough. Consequently, the error might not be detected. For example, if m=0, then the data block m will be equal to 0 in every reference ring and every starting ring.

(54) Preferably, the update of the current state may be performed randomly to add a protection against some side-channel analysis such as the DPA.

(55) This step of updating the current state of the data block may be performed using a reduction modulo J. The K elements may be selected in the basis J according to different selection criteria. In particular, the K elements may be randomly selected in the basis J. They may be also randomly pre-computed. Alternatively they may be constant.

(56) It should be noted that a random selection of the K elements in the basis ideal J allows to add a protection against some side-channel analysis such as the DPA.

(57) For example, the cryptographic scheme is AES and the protection method may apply to one of the operation of the AES in the ring .sub.2[X]/(PQ), with Q being an irreducible polynomial over .sub.2 of degree k and P being the ideal of .sub.2[X] representing the set of all polynomials that are multiple of P. (P) is referred to as the basis ideal of .sub.2[X] with:
(P)={P, . . . ,XP,X.sup.2P, . . . ,(X+1)P,(X+1).sup.2P, . . . }

(58) In such AES exemplary application, step 500 may comprise randomly selecting K polynomial R.sub.i to randomize the message, and step 502 may comprise adding each bit i of the current state of the data bloc m.sub.i to PR.sub.i, where PR.sub.i is a polynomial binary multiplication.

(59) In the embodiment where extension values C.sub.k per reference ring A/I.sub.k are computed from the execution of the operation in an extended ring depending on the reference ring A/I.sub.k (step 307) and the reduction step (step 308), the operation protection method may comprise checking an auxiliary condition related to the reference values and/or the extension values per reference ring C.sub.k, if all the iterations of the condition step 312 succeed, before returning an operation value in step 318.

(60) FIG. 7 is a flowchart depicting the protection method including an auxiliary condition according to such embodiment.

(61) The steps of the flowchart of FIG. 7 are similar to the steps of the flowchart of FIG. 4, but the operation protection method further comprises, if the main condition of step 312 is satisfied for all the reference values, a step 319 comprising, for each extension value, the reduction of each byte of the extension value per reference ring C.sub.k modulo the basis ideal J, which provide C.sub.k (i.e. each byte of the extension value per reference ring C.sub.k is mapped to an element of the basis ring J, the mapped value thus obtained providing the extension value C.sub.k).

(62) The auxiliary condition may be checked in step 321. Step 321 may comprise determining whether the reduced extension value C.sub.k obtained in correspondence with the reference ring are equal. If at least one reduced extension value C.sub.k differs from the other reduced extension values, an error is detected which may be representative of a fault attack and the execution of the operations is terminated in step 322 similarly to step 314. Otherwise (i.e; all the reduced extension value C.sub.k are equal), the operation result is returned in step 324 similarly to step 318 of FIG. 4.

(63) In one embodiment, the operation protection method may comprise the execution of the operation in only one extended ring in step 307 and the execution of the operation in a set of reference rings.

(64) FIG. 8 is a flowchart depicting such an embodiment with the execution of the operation in one extended ring and the execution of the operation in several reference rings, according to certain embodiments. Steps 800, 802, 804, 805, 806 are respectively similar to steps 300, 302, 304, 305, and 306 of FIG. 3. Step 811 is similar to step 307 of FIG. 4.

(65) However, in step 810, a Chinese Remainder Theorem (CRT) transformation may be applied to the N reference values C.sub.1, . . . , C.sub.k, . . . C.sub.N obtained as a result of the execution of the operation in each reference ring among the N reference rings A/I.sub.1, . . . , A/I.sub.k, . . . , A/I.sub.N, which provides a unique value derived from the N reference values, referred to hereinafter as the reference parameter.

(66) In step 812, the condition comprises a comparison between the reference parameter and the unique extension value C.sub.r,1,2, . . . , N obtained as the result of the execution of the operation in the unique extended ring A/JI.sub.1I.sub.2 . . . I.sub.N (step 811).

(67) A unique iteration of the condition step 812 is thus performed. In particular, the condition may comprise determining if the extension value C.sub.r, 1,2, . . . , N is equal to the reference parameter C.sub.1, . . . , N and, if not terminating the operations of the cryptographic scheme in step 814 as described previously in relation to step 318 of FIG. 3. Otherwise, if the condition is satisfied (C.sub.r, 1,2, . . . , N=C.sub.1, . . . , N), each byte of the extension value or the reference parameter may be reduced modulo the basis ideal J (i.e. each byte of the extension value or the reference parameter may be mapped to an element of the basis ring J, which provides a mapped value formed by the mapped bytes corresponding to the bytes of the extension value or the reference parameter) and the reduced value (corresponding to the mapped value) may be returned as the operation result m in step 816. The execution of the remaining cryptographic operations or round may proceed based on the state m of the data block, while ensuring that no fault attack has been performed on the operation.

(68) A CRT (Chinese Remainder Theorem) transformation provides that if I,J are two coprime ideals in A, then, there exists an isomorphism between the quotient ring A/(IJ) and A/IA/J. That is for a pair (a, b) with aA/I and bA/J, there exists an unique corresponding element in A/(IJ). Reciprocally, for any element xA/(IJ) there exists a unique pair of elements in A/IA/J corresponding to x. The Chinese Remainder Theorem can also be generalized to several ideals pairwise coprime.

(69) Step 810 uses specifically the CRT transformation A/I.sub.1A/I.sub.2 . . . A/I.sub.N.fwdarw.A/(I.sub.1 . . . I.sub.N) to determine C.sub.1, . . . , NA/(I.sub.1 . . . I.sub.N) from (C.sub.1, C.sub.2, . . . C.sub.N)A/I.sub.1A/I.sub.2 . . . A/I.sub.N.

(70) This comprises defining i.sub.1, . . . , kI.sub.1 . . . I.sub.k, such that i.sub.1, . . . , k+i.sub.k+1=1 for some i.sub.k+1I.sub.k+1. They can be computed using an extended Euclidean algorithm. This also comprises defining x.sub.1, . . . , k the element verifying:
x.sub.1, . . . ,k=C.sub.1 mod I.sub.1
x.sub.1, . . . ,k=C.sub.k mod I.sub.k

(71) The seek value C.sub.1, . . . , NA/(I.sub.1 . . . I.sub.N) will be obtained as C1, . . . , N=x.sub.1, . . . , N.

(72) x.sub.1, . . . , N may be recursively constructed according to the CRT as follows:

(73) 1. At the beginning, x.sub.1 is set as equal C.sub.1 (x.sub.1=C.sub.1).

(74) 2. x.sub.2 is then set as equal to x.sub.2=x.sub.1+(C.sub.2x.sub.1)i.sub.1 mod I.sub.1I.sub.2.

(75) 3. x.sub.1, . . . , k,k+1 is then constructed from
x.sub.1, . . . ,k,k+1=x.sub.1, . . . ,k+(C.sub.k+1x.sub.1, . . . ,k,k+1)I.sub.1, . . . ,k mod I.sub.1. . . I.sub.kI.sub.k+1

(76) C.sub.1, . . . , N is then obtained for k+1=N (C.sub.1, . . . N=x.sub.1, . . . , N-1,N).

(77) FIG. 9 is a flowchart illustrating another exemplary embodiment of the operation protection method comprising the execution of the operation in a set of extended rings and the execution of the operation in a set of reference rings, each extended ring A/JI.sub.kiI.sub.kj being the quotient of the starting ring A by the product of the basis ideal J and of the reference ideals I.sub.ki, I.sub.kj of two reference rings A/I.sub.ki and A/I.sub.kj. Steps 900, 902, 904, 905, 906 are respectively similar to steps 300, 302, 304, 305, and 306 of FIG. 4. Step 907 and 908 are similar to step 307, and 308 of FIG. 4.

(78) The execution of the operation in each reference ring A/I.sub.k (steps 904, 905) provides a reference value C.sub.k. In step 910, a CRT is applied to a set of pairs of reference values {C.sub.ki,C.sub.kj} obtained as a result of the execution of the operation in each reference ring A/I.sub.ki and A/I.sub.kj, which provides a unique reference value C.sub.kikj for the pair of reference rings {A/I.sub.ki,A/I.sub.kj}, referred to hereinafter as a pair reference parameter.

(79) The operation is further executed in each reference ring A/JI.sub.kiI.sub.kj (step 908) depending on a reference rings, A/I.sub.ki and A/I.sub.kj, for each pair of reference rings {A/I.sub.ki,A/I.sub.kj}, which provides an intermediary extension value C.sub.r,ki,kj. In step 909, each byte of the extension value C.sub.r,ki,kj thus obtained is reduced modulo the product I.sub.kiI.sub.kj, which provides a pair extension value C.sub.ki,kj for each extended ring (i.e. each byte of the extension value C.sub.r,ki,kj is mapped to an element of a ring A/I.sub.kiI.sub.kj quotiented by the product I.sub.kiI.sub.kj of the reference ideals, which provides a mapped value comprising the mapped bytes in correspondence with the bytes of the extension value, the mapped value forming the pair extension value C.sub.ki,kj).

(80) The condition step 912, is iterated for each pair of reference rings {A/I.sub.ki,A/I.sub.kj}. For each pair of reference rings {A/I.sub.ki,A/I.sub.kj}, step 912 comprises checking a condition comprising a comparison between the pair reference parameter C.sub.kikj and the corresponding pair extension value C.sub.kikj obtained as the result of the execution of the operation in the extended ring A/JI.sub.kiI.sub.kj (step 908) and the reduction step 909.

(81) In particular, the condition may comprise determining if the pair extension value C.sub.kikj is equal to the pair reference parameter C.sub.kikj and, if not terminating the operations of the cryptographic scheme in step 914 as described previously. Otherwise, if the condition is satisfied (C.sub.kikj=C.sub.kikj), each byte of the extension value or the reference parameter may be reduced modulo the basis ideal J (i.e. each byte of the extension value or the reference parameter is mapped to an element of the basis ring J, which provides a mapped value formed by the mapped bytes in correspondence with the bytes of the extension value) and the reduced value (corresponding to the mapped value) may be returned as the operation result m in step 916 as described in relation with FIG. 3 to proceed with the execution of the remaining cryptographic operations or round.

(82) The CRT operation applied in step 910 is the CRT transformation A/I.sub.ki, A/I.sub.j.fwdarw.A/(I.sub.kiI.sub.kj).

(83) According to this CRT transformation operation, if I.sub.ki and I.sub.kj are coprime, there exists iI.sub.ki and jI.sub.kj such that i+j=1. An element C.sub.kikjA/(I.sub.kiI.sub.kj) is obtained from (C.sub.ki,C.sub.kj)A/I.sub.ki,A/I.sub.kj. In other terms, C.sub.kikjA/(I.sub.kiI.sub.kj) may be determined such that C.sub.kikj=C.sub.ki mod I.sub.ki and C.sub.kikj=C.sub.kj mod I.sub.kj.

(84) This comprises finding the elements i, j, using for example the Extended Euclidean Algorithm. They can also be pre-computed and stored. C.sub.kikj is then set as x=C.sub.kij+C.sub.kii mod I.sub.kiI.sub.kj.

(85) Alternatively C.sub.kikj can also be computed as C.sub.kikj=(C.sub.kiC.sub.kj)j+C.sub.kj mod I.sub.kiI.sub.kj. In that way, only j has to be computed.

(86) While the embodiment of FIG. 9 has been described with reference to an example where the operation is executed in three reference rings, and in two extended rings, each extended ring depending on a pair of the reference rings, to facilitate the understanding of this embodiment, more generally this embodiment may be used to execute the operation in: any number of reference rings (904), and in at least two extended rings (907), each extended ring depending on a set of reference rings.

(87) According to this embodiment, the operation protection method may comprise: applying the CRT transformation (910) to the reference values obtained as a result of the execution of the operation in each set of reference rings corresponding to one of the extended ring, which provides a common reference parameter related to each said set of reference rings, for each extension value obtained as a result of the execution of the operation in one of the extended ring depending on a given set of reference rings, reducing each byte of the extension value modulo the product of the reference ideals of each reference ring of the set of reference rings (908), with provides a common extension parameter.

(88) The condition step (912) may then comprise a comparison between each common reference parameter related to a given set of reference rings and the common extension parameter obtained for the extended rings depending on this set of reference rings.

(89) Even if not limited to symmetric cryptographic schemes, the invention has particular advantages to protect the cryptographic operations against fault attacks in symmetric cryptographic schemes (the same key is used for encryption and decryption as opposed to a public key cryptosystem), and in particular for a AES cryptographic scheme.

(90) FIG. 10 is a flowchart illustrating an exemplary application of the invention to certain operations of the AES cryptographic scheme. The flowchart of FIG. 10 is similar to the flowchart of FIG. 2 but some AES operations are protected according to the protection method.

(91) The Advanced Encryption Standard (AES) is the specification of a symmetric encryption scheme standardized in 2001.

(92) The AES cryptographic scheme consists in performing rounds (or repetitions) of a set of successive operations on a 128-bit data block (or message). It supports three different key lengths and the number of rounds is fixed for each key length: for a 128-bit key, the number of rounds is 10 for a 192-bit key, the number of rounds is 12 for a 256-bit key, the number of rounds is 14

(93) The AES cryptographic scheme comprises 4 different operations operating on a 128-bit block represented by a matrix of 44 bytes: a subBytes operation according to which each byte of the current state of the data block is replaced with its entry in a fixed 8-bit lookup table S (bij=S(aij)) as illustrated in FIG. 11. a shiftRows operation according to which the bytes in each row of the current state of the data block are shifted cyclically to the left, the number of places each byte is shifted differing for each row as illustrated in FIG. 12. a MixColumns operation according to each column of the current state of the data block is multiplied with a fixed polynomial c(x) as illustrated in FIG. 13, and an AddRoundKey operation according to which each byte of the current state of the message is combined with a byte of the round subkey using XOR operation, as represented in FIG. 14.

(94) The AES uses a representation of the binary values included in each data blocks into ring of polynomials .sub.2[X] (corresponding to the starting ring A) where all polynomials are representations of the binary values.

(95) The polynomial ring [X] over a field is defined as the set of expressions, called polynomials in X of the form:
P=a.sub.0+a.sub.1X+a.sub.2X.sup.2+ . . . +a.sub.n-1X.sup.n-1+a.sub.nX.sup.n

(96) where a.sub.0, a.sub.1, . . . , a.sub.n are elements of . They are called coefficients of P. If a.sub.n0, n is called the degree of P.

(97) The quotient ring [X]/(P) is the ring containing polynomials over [X] where two polynomials Q, R are identical on [X]/(P) if their remainder of the division by P is the same.

(98) This means that Q and Q+RP are identical on [X]/(P) for any R in [X].

(99) The elements of [X]/(P) are represented by a polynomial of degree smaller than n. Generally, additions and multiplications in [X]/(P) are performed modulo P thus the result is a polynomial of degree smaller than n.

(100) One property is that if P is irreducible, [X]/(P) is a field.

(101) If is a finite field of m element, and P is an irreducible polynomial of degree n, then [X]/(P) is a field of degree m.sup.n. It can thus be denoted .sub.m.sub.n (see previous sections).

(102) .sub.m.sub.n can be represented by any irreducible polynomial over .sub.m of degree n.

(103) Most operations of the AES cryptographic scheme (Subbytes, MixColumns and AddRoundKey) are defined specifically on a basis field called the Rijndael's finite field and noted .sub.256 with the reducing polynomial P=X.sup.8+X.sup.4+X.sup.3+X+1 defined over .sub.2[X].

(104) .sub.256 can also be denoted .sub.2[X]/(X.sup.8+X.sup.4+X.sup.3+X+1).

(105) In the embodiment of FIG. 10, the operation protection method is applied to each of the following operations, for each round: the shiftRows operation (step 925); the MixColumns operation (step 926), and the AddRoundKey operation (step 927).

(106) The execution of the subBytes operation (923) may be performed according to the convention method in the Rijndael's finite field.

(107) Alternatively, the operation protection method may be applied to only some of the previous operations, during one round, all the rounds or a selected number of rounds.

(108) FIG. 15 is a flowchart illustrating an exemplary application of the invention to one operation of the AES cryptographic scheme, corresponding to the embodiment of FIG. 3. To facilitate the understanding of this application, similar reference numbers as the reference numbers used in FIG. 3 will be used, although the flowchart of FIG. 15 corresponds to a particular embodiment and application.

(109) In the following description Q is an irreducible polynomial over .sub.2[X] of degree k.

(110) In step 302, a number of random polynomials of degree k are chosen (for example 16 random polynomials). This comprising choosing random bit strings of length k. Each bit represents the coefficient of the polynomial. The use of random polynomials allows protection against side-channel attacks. For protection against fault attacks only, constant polynomials may be alternatively loaded from the ROM.

(111) The selected polynomials R.sub.i are used to randomize the message. Each byte of the message m.sub.i is added to PR.sub.i, using a polynomial binary multiplication, which provides the modified state of the message.

(112) In step 304, the AES operation is run on each reference ring .sub.2[X]/(Q.sub.k) with the polynomial Q.sub.k representing the reference ideal of the reference ring .sub.2[X]/(Q.sub.k), which provides a reference value C.sub.Q.sub.k for each reference ring.

(113) In step 307, the AES operation is performed in each extended ring .sub.2[X]/(PQ.sub.k.sub.1 . . . Q.sub.k.sub.i . . . Q.sub.k.sub.N), P being the basis ideal of the basis ring, N being inferior or equal to the total number of reference rings, and Q.sub.ki representing the reference ideal of one of reference rings .sub.2[X]/(Q.sub.k.sub.i) on which the extended ring depends, which provides an intermediary extension value C.sub.PQk.sub.1.sub.. . . Qk.sub.i.sub.. . . Qk.sub.N for each extended ring .sub.2[X]/(PQ.sub.k.sub.1 . . . Q.sub.k.sub.i . . . Q.sub.k.sub.N).

(114) In step 308, each byte of the result C.sub.PQk.sub.1.sub.. . . Qk.sub.i.sub.. . . Qk.sub.N obtained for each extended ring .sub.2[X]/(PQ.sub.k.sub.1 . . . Q.sub.k.sub.i . . . Q.sub.k.sub.N) is reduced modulo each polynomial Q.sub.k.sub.i, which provides N extension values

(115) $C_{Q_{k_1}}^{},\mathrm{.Math.}{C}_{Q_{k_i}}^{},\mathrm{.Math.}\mathrm{and}{C}_{Q_{k_N}}^{}$
for the considered extended ring .sub.2[X]/(PQ.sub.k.sub.1 . . . Q.sub.k.sub.i . . . Q.sub.k.sub.N).

(116) Each reduced result

(117) $C_{Q_{k_i}}^{}$
is then equivalent to a result of the AES operation that would have been obtained from the execution of the AES operation over the field .sub.2[X]/(Q.sub.k.sub.i).

(118) In step 312, for reference ring .sub.2[X]/(Q.sub.k)(block 310), it is determined if each reference value C.sub.Q.sub.k obtained as a result of the execution of the operation on the reference ring .sub.2[X]/(Q.sub.k) (step 304) is equal to the different extension values C.sub.Qk obtained in step 308 for the extended ring .sub.2[X]/(PQ.sub.k.sub.i . . . Q.sub.k.sub.i . . . Q.sub.k.sub.m) depending on this reference ring .sub.2[X]/(Q.sub.k) (one of the indexes k.sub.i is equal to k).

(119) If the condition of step 312 is satisfied for each reference value C.sub.Q.sub.k and each corresponding extension value C.sub.Q.sub.k, each byte of at least one extension value C.sub.Q.sub.k is further reduced modulo P in step 318. The obtained result is then equivalent to a result that would have been directly obtained from the execution of the AES operation in the field .sub.2[X]/(P). The obtained value may be returned in step 318 and may be used for the remaining AES operations or round as the new state of the data block. In one embodiment, as described in relation with steps 318 to 324 of FIG. 7, all or a subset of the extension values obtained as a result of step 306 to 308 may be reduced modulo P and compared all together, the detection of a mismatch between two reduced extension values triggering an error report and/or a termination of the operations.

(120) Otherwise, if it is determined in step 312 that at least one reference value C.sub.Q.sub.k is different from one corresponding extension value C.sub.Q.sub.k, an error has occurred which may stem from a fault attack and no result may be returned. The operations may be terminated in step 314.

(121) It should be noted that the above description of the flowchart of FIG. 12 corresponds to a simplified embodiment of the operation protection method with only one reference ring and one extended ring. The skilled person will readily understand that the AES application is not limited to such embodiment and also applies to the use of a plurality of reference rings using several polynomials Q.sub.1, . . . , Q.sub.N as the reference ideals, and to several extended rings depending on one or more reference rings as described in relation with FIGS. 3, 4, 5, 6, 7, 8 and 9.

(122) While embodiments of the invention have been illustrated by a description of various examples, and while these embodiments have been described in considerable detail, it is not the intention of the applicant to restrict or in any way limit the scope of the appended claims to such detail. The invention in its broader aspects is therefore not limited to the specific details, representative methods, and illustrative examples shown and described. In particular, the operation protection method may be applied to execute one or more operations of a same cryptographic scheme (also known as a cryptographic algorithm), during one or more rounds. Further the invention may apply to any symmetric or asymmetric cryptographic scheme. Also the operation protection method may use any condition 312 between a reference parameter derived from the reference values of one or more reference rings and an extension parameter derived from the corresponding extended rings. Also the skilled person will readily understand that the step of executing the considered operation in the extended rings (306-309) may be implemented according to any order with respect to the step of executing the considered operation in the reference rings (303-305), independently of the reference numbers used to reference these steps. For example, the step of executing the considered operation in the extended rings (306-309) may be implemented simultaneously, before or after the step of executing the considered operation in the reference rings (303-305).