MICROPROCESSOR EQUIPPED WITH AN ARITHMETIC AND LOGIC UNIT AND WITH A HARDWARE SECURITY MODULE

Abstract

This microprocessor is configured to compute a code C.sub.1, used to detect an execution fault, using a relationship C.sub.i=P o F.sub.α(D.sub.i), where: F.sub.α(D.sub.i)=E.sub.0 o . . . o E.sub.q o . . . o E.sub.NbE−1(D.sub.i), E.sub.q(x)=T.sub.αm,q o . . . o T.sub.αj,q o . . . o T.sub.α1,q o T.sub.α0,q(X), and T.sub.αj,q is a conditional transposition, configured by a secret parameter α.sub.j,q, that permutes two blocks of bits B.sub.2j+1,q and B.sub.2j,q of the variable x only when the parameter a.sub.j,q is equal to a first value, the blocks B.sub.2j+1,q and B.sub.2j,q of all of the transpositions T.sub.αj,q of the stage E.sub.q being different from one another and not overlapping and the blocks B.sub.2j+1,q and B.sub.2j,q are placed within one and the same block of greater size permuted by a transposition of the higher stage E.sub.q+1.

Claims

1. Microprocessor equipped with an arithmetic and logic unit and with a hardware security module, wherein: a) the arithmetic and logic unit is capable of executing an arithmetic instruction, comprising an opcode and one or more operands, that, when executed by the arithmetic and logic unit of the microprocessor, causes a mathematical operation D.sub.1*D.sub.2* . . . *D.sub.n to be performed and the result of this operation to be stored in a register R.sub.res−p where: the subscript n is equal to the number of data items D.sub.1 processed by the arithmetic instruction, the subscript n being greater than or equal to one, D.sub.1 to D.sub.n are data items that are stored in registers R.sub.1 to R.sub.n, respectively, of the microprocessor, the size, in terms of the number of bits, of each of these data items D.sub.i being equal to 2.sup.d, where d is an integer greater than two, the registers R.sub.1 to R.sub.n are the registers denoted by the operands of the arithmetic instruction, the symbol “*” is the arithmetic operation denoted by the opcode of the arithmetic instruction, b) the microprocessor is configured to perform the following operations: 1) for each data item D.sub.i, computation of a code C.sub.i using a relationship C.sub.i=Q.sub.a(D.sub.i) and association of the computed code C.sub.i with the data item D.sub.i, the function Q.sub.α being a pre-programmed function configured by a secret key a that is pre-stored in the microprocessor and known only to the microprocessor, 2) each time an instruction for loading a data item D.sub.i into a register R.sub.i of the microprocessor is executed by the microprocessor, the loaded data item D.sub.i is stored in the register R.sub.i and the code C.sub.i associated therewith is stored in the same register R.sub.i or in a register associated with the register R.sub.i, then 3) execution of the arithmetic instruction and storage of the result D.sub.res−p of this execution in the register R.sub.res−p, and computation, by the security module, of a code C.sub.res−t using the codes C.sub.1, C.sub.2, . . . , C.sub.n and without using the result D.sub.res-p, then 4) checking that the computed code C.sub.res−t corresponds to a code C.sub.res−p obtained from the result D.sub.res−p and triggering of the signalling of an execution fault if the code C.sub.res−t does not correspond to the code C.sub.res−p and, otherwise, suppressing this signalling, wherein the function Q.sub.α is defined by the following relationship: Q.sub.a(D.sub.i)=P o F.sub.α(D.sub.i), where P is a predetermined function and F.sub.α is a function defined by the following relationship: F.sub.α(D.sub.i)=E.sub.0 o . . . o E.sub.q o . . . o E.sub.NbE−1(D.sub.i), where each function E.sub.q is a stage of transpositions and the index q is an order number between zero and NbE−1, where NbE is a whole number greater than one and less than or equal to d, each stage E.sub.q of transpositions being defined by the following relationship: E.sub.q(x)=T.sub.αm,q o . . . o T.sub.αj,q o . . . o T.sub.α1,q o T.sub.α,q(x), where: x is a variable whose size, in terms of the number of bits, is equal to the size of the data item D.sub.i, T.sub.αj,q is a conditional transposition, configured by the parameter α.sub.j,q, that permutes two blocks of bits B.sub.2j+1,q and B.sub.2j,q of the variable x when the parameter α.sub.j,q is equal to a first value and that does not permute these two blocks of bits when the parameter α.sub.j,q is equal to a second value, the transposition T.sub.αj,q being distinguished from all of the other transpositions of the function F.sub.α by the fact that it is the only one that permutes the two blocks B.sub.2j+1,q and B.sub.2j,q when the parameter α.sub.j,q is equal to the first value, the blocks B.sub.2j+1,q and B.sub.2j,q of all of the transpositions T.sub.αj,q of the stage E.sub.q being different from one another and not overlapping in such a way that all of the transpositions T.sub.αj,q of the stage E.sub.q can be executed in parallel, “m+1” is the total number of transpositions T.sub.αj,q of the stage E.sub.q, “j” is an order number identifying the transposition T.sub.αj,q among the other transpositions of the stage E.sub.q, the symbol “o” denotes the function-composition operation, the concatenation of the bits of all of the parameters α.sub.j,q of all of the stages E.sub.q is equal to the value of the secret key α, and for all of the stages E.sub.q for which q is less than NbE−1 and for all of the transpositions T.sub.αj,q of this stage, the blocks B.sub.2j+1,q and B.sub.2j,q are placed within one and the same block of greater size permuted by a transposition of the higher stage E.sub.q+1 when the parameter of this transposition of the higher stage E.sub.q+1 is equal to the first value.

2. Microprocessor according to claim 1, wherein the number NbE is equal to d, the sizes of the blocks permuted by all of the transpositions T.sub.αj,q of one and the same stage E.sub.q are equal to 2.sup.q, the blocks B.sub.2j+1,q and B.sub.2j,q permuted by each transposition T.sub.αj,q are adjacent.

3. Microprocessor according to claim 2, wherein the arithmetic instruction is a shift instruction for shifting the bits of the data item D.sub.1 one bit to the left or to the right and the code C.sub.res−t is equal to Q.sub.a(D.sub.res−p) in the absence of an execution fault, the security module comprising, to this end, a computation circuit for computing the code C.sub.rest−t from the code C.sub.1 and without using the result D.sub.res−p, this computation circuit comprising: for each stage E.sub.q of the function F.sub.α, a stage ED.sub.q comprising components CD.sub.αj,q, each component CD.sub.αj,q being associated with a respective transposition T.sub.αj,q of the stage E.sub.q, the components CD.sub.αj,q of the stages ED.sub.0 to ED.sub.NbE−2 all being structurally identical to one another and each having a first, a second, a third and a fourth input and a first, a second and a third output: the first output delivering the result a.k′+c.k, where: “a”, “k” and “c” are the values received at the first, third and fourth inputs, respectively, of this component, the symbol “ + ” denotes the “OR” logic operation, the symbol “ . ” denotes the “AND” logic operation, and the symbol “ ′ ” denotes the “NOT” logic operation, the second output delivering the result b.k+c.k′, where “b” is the value received at the second input of this component, the third output delivering the result a.k+b.k′, the component CD.sub.αj,NbE−1 of the stage ED.sub.NbE−1 having a first, a second and a third input and a first and a second output: the first and second outputs delivering the results “a” and “0”, respectively, when the third input is equal to “0”, where “a” is the value received at the first input and “0” is the value zero, and the first and second outputs delivering the results “0” and “b”, respectively, when the third input is equal to “1”, where “b” is the value received at the second input, for q equal to zero, the first and second inputs of each component CD.sub.αj,0 of the stage ED.sub.0 being connected to the 2j-th bit and to the (2j+1)-th bit, respectively, of the code C.sub.1, and for q greater than zero, the first and second inputs of each component CD.sub.αj,q of the stage ED.sub.q being connected, respectively, to the third outputs of the 2j-th and (2j+1)-th components, respectively, of the stage ED.sub.q−1, the third input of each component CD.sub.αj,q is connected to the parameter α.sub.j,q when the instruction is a left shift and to the complement α.sub.j,q′ of the parameter α.sub.j,q when the instruction is a right shift, for q greater than zero, the first and second outputs of each component CD.sub.αj,q are connected to the fourth input of the (2j+1)-th and 2j-th components, respectively, of the stage E.sub.q−1, and for q equal to zero, the first and second outputs of each component CD.sub.αj,0 deliver the (2j+1)-th and 2j-th bits, respectively, of the code C.sub.rest−t.

4. Microprocessor according to claim 2, wherein the arithmetic instruction is a shift instruction for shifting the bits of the data item D.sub.1 2.sup.r bits to the left or to the right, where r is a whole number greater than one and less than NbE, and the code C.sub.rest−1 is equal to Q.sub.a(D.sub.res−p) in the absence of an execution fault, the security module comprising, to this end, a computation circuit for computing the code C.sub.rest−t from the code C.sub.1 and without using the result D.sub.res−p, this computation circuit comprising a block permutator and a bit scheduler, the permutator comprises, for each stage E.sub.q of transpositions included in the group of stages E.sub.r to E.sub.NbEt that permute blocks of size greater than or equal to 2.sup.r, a stage ED.sub.q comprising components CD.sub.αj,q, each component CD.sub.αj,q being associated with a respective transposition T.sub.αj,q of the stage E.sub.q, the components CD.sub.αj,q of the stages ED.sub.r to ED.sub.NbE−2 all being structurally identical to one another and each having a first, a second, a third and a fourth input and a first, a second and a third output: the first output delivering the result a.k′+c.k, where: “a”, “k” and “c” are the values received at the first, third and fourth inputs, respectively, of this component, the symbol “ + ” denotes the “OR” logic operation, the symbol “ . ” denotes the “AND” logic operation, and the symbol “ ′ ” denotes the “NOT” logic operation, the second output delivering the result b.k+c.k′, where “b” is the value received at the second input of this component, the third output delivering the result a.k+b.k′, the component CD.sub.αj,NbE−1 of the stage ED.sub.NbE−1 having a first, a second and a third input and a first and a second output: the first and second outputs delivering the results “a” and “0”, respectively, when the third input is equal to “0”, where “a” is the value received at the first input and “0” is the value zero, and the first and second outputs delivering the results “0” and “b”, respectively, when the third input is equal to “1”, where “b” is the value received at the second input, the first and second inputs of each component CD.sub.αj,r of the stage ED.sub.r being connected to the 2j-th block of 2.sup.r bits and to the (2j+1)-th block of 2.sup.r bits, respectively, of the code C.sub.1, and for q greater than r, the first and second inputs of each component CD.sub.αj,q of the stage ED.sub.q being connected, respectively, to the third outputs of the 2j-th and (2j+1)-th components, respectively, of the stage ED.sub.q−1, the third input of each component CD.sub.αj,q is connected to the parameter α.sub.j,q when the instruction is a left shift and to the complement α.sub.j,q′ of the parameter α.sub.j,q when the instruction is a right shift, for q greater than r, the first and second outputs of each component CD.sub.αj,q are connected to the fourth input of the (2j+1)-th and 2j-th components, respectively, of the stage E.sub.q−1 , and for q equal to r, the first and second outputs of each component CD.sub.αj,r deliver the (2j+1)-th intermediate block BCI.sub.2j+1,r of 2.sup.r bits and the 2j-th intermediate block BCI.sub.2j,r of 2.sup.r bits, respectively, of an intermediate code CI.sub.rest−t, each block BCI.sub.x,r being identical to a respective block BC.sub.y,r of the code C.sub.1, the order of the bits within this block BC.sub.y,r having been obtained, during computation of the code C.sub.1, by applying a first set of transpositions of the stages E.sub.r−1 to E.sub.0 to a respective block BD.sub.z,r of 2.sup.1 bits of the data D.sub.1, where the subscripts x, y and z are each an identifier of a position of a block of 2.sup.1 bits in a data item or a code of 2.sup.d bits, the subscript x being equal to 2j+1 if the order number of the block of 2.sup.r bits is odd and equal to 2j otherwise, and the first set of transpositions being dependent on the position y, the scheduler capable of replacing each intermediate block BCI.sub.x,r of the intermediate code with a block BCR.sub.x,r of 2.sup.r bits that is equal to the result of the application of a second set of transpositions of the stages E.sub.r−1 to E.sub.0 to the block BD.sub.x,r of 2.sup.r bits of the data item D.sub.1, the second set of transpositions being dependent on the position x.

5. Microprocessor according to claim 4, wherein the scheduler is capable, for each block BCI.sub.x,r: of comparing each parameter of a current permutation key with the corresponding parameter of a desired permutation key, the current key containing the parameters of all of the transpositions of the first set of transpositions used, during computation of the code C.sub.1, to permute the bits placed within the block BD.sub.z,r, the desired key containing the parameters of all of the transpositions of the second set of transpositions used, during a computation of F.sub.α(D.sub.res−p), to permute the bits placed within the block BD.sub.x,r, and, each time the compared parameters are different, of executing the transposition configured by this parameter on the bits of the block BCI.sub.x,r and, each time the compared parameters are identical, of keeping the order of the bits of the block BCI.sub.x,r unchanged.

6. Microprocessor according to claim 2, wherein the arithmetic instruction is a rotation instruction for rotating the bits of the data item D.sub.1 one bit to the left or to the right and the code C.sub.res−t is equal to Q.sub.a(D.sub.res−p) in the absence of an execution fault, the security module comprising, to this end, a computation circuit for computing the code C.sub.rest-t from the code C.sub.1 and without using the result D.sub.res−p, this computation circuit comprising: for each stage E.sub.q of the function F.sub.α, a stage ED.sub.q comprising components CC.sub.αj,q, each component CC.sub.αj,q being associated with a respective transposition T.sub.αj,q of the stage E.sub.q, the components CC.sub.αj,q of the stages ED.sub.0 to ED.sub.NbE−2 all being structurally identical to one another and each having a first, a second, a third and a fourth input and a first, a second and a third output: the first output delivering the result a.k′+c.k, where: “a”, “k” and “c” are the values received at the first, third and fourth inputs, respectively, of this component, the symbol “ + ” denotes the “OR” logic operation, the symbol “ . ” denotes the “AND” logic operation, and the symbol “ ′ ” denotes the “NOT” logic operation, the second output delivering the result b.k+c.k′, where “b” is the value received at the second input of this component, the third output delivering the result a.k+b.k′, the component CC.sub.αj,NbE−1 of the stage ED.sub.NbE−1 having a first and a second input and a first and a second output, the first and second outputs delivering the results “a” and “b”, respectively, where “a” and “b” are the values received at the first and second inputs, respectively, and for q equal to zero, the first and second inputs of each component CC.sub.αj,0 of the stage ED.sub.0 being connected to the 2j-th bit and to the (2j+1)-th bit, respectively, of the code C.sub.1, and for q greater than zero, the first and second inputs of each component CC.sub.aj,q of the stage ED.sub.q being connected, respectively, to the third outputs of the 2j-th and (2j+1)-th components, respectively, of the stage ED.sub.q−1, the third input of each component CC.sub.αj,q is connected to the parameter α.sub.j,q when the instruction is a left rotation and to the complement α.sub.j,q′ of the parameter α.sub.j,q when the instruction is a right rotation, for q greater than zero, the first and second outputs of each component CC.sub.αj,q are connected to the fourth input of the (2j+1)-th and 2j-th components, respectively, of the stage E.sub.q−1, and for q equal to zero, the first and second outputs of each component CC.sub.αj,0 deliver the (2j+1)-th and 2j-th bits, respectively, of the code C.sub.rest−t.

7. Microprocessor according to claim 2, wherein the arithmetic instruction is a shift instruction for shifting the bits of the data item D.sub.1 a.sub.NbE−12.sup.NbE−1+ . . . +a.sub.q2.sup.q+ . . . +a.sub.0 bits to the left or to the right, where the coefficients a.sub.q are predetermined coefficients, and the security module comprises a computation unit for computing the code C.sub.rest−t from the code C.sub.1 and without using the result D.sub.res−p, this code C.sub.rest−t being identical to the result D.sub.res−p in the absence of an execution fault during the execution of this shift instruction by the arithmetic and logic unit, this computation circuit comprising, for each stage E.sub.q of the function F.sub.α, a stage ET.sub.q, each stage ET.sub.q having: a first input for receiving a code to be permuted, this code to be permuted being formed by a juxtaposition of blocks BCP.sub.y,q of 2.sup.q bits each, the subscript y being the order number of the block of 2.sup.q bits in this juxtaposition, this first input receiving the code C.sub.1 when q=NbE−1, a second input for receiving the parameters α.sub.m,q to α.sub.0,q of the transpositions of the stage E.sub.q, this second input receiving the parameters α.sub.0,NbE−1 when q=NbE−1, a third input for receiving a permutation key for the next stages, this permutation key being formed by a juxtaposition of blocks BK.sub.y,q of 2.sup.q bits each, each block BK.sub.y,q containing only the parameters of the transpositions of the next stages E.sub.chi to E.sub.0 that permute the bits placed within the block BCP.sub.y,.sub.q of the code received at the first input, this third input receiving the private key a of the parameter α.sub.0,NbE−1 when q=NbE−1, a first permutator capable of performing the permutation T.sub.αm,q o . . . o T.sub.αj,q o . . . o T.sub.α1,q o T.sub.αo,q(x) in order to obtain a permuted code, where the variable x is equal to the code to be permuted that is received at the first input and the permutation parameters α.sub.m,q to α.sub.0,q are those received at the second input, a first shift register capable of performing a shift of 2.sup.q bits for the permuted code in order to obtain a permuted and shifted code, a first multiplexer configured to select the permuted code if the coefficient a.sub.q is equal to “0” and to select the permuted and shifted code if the coefficient a.sub.q is equal to “1”, this first multiplexer having an output that delivers to the first input of the next stage ET.sub.q−1 the code selected from the permuted code and the permuted and shifted code, a second permutator capable of executing the permutation T.sub.αm,q o . . . o T.sub.αj,q o . . . o T.sub.α2,q o T.sub.α0,q(k) in order to obtain a permuted key, where the variable k is equal to the permutation key received at the third input, a second shift register capable of performing a shift of 2.sup.q bits for the permuted key in order to obtain a permuted and shifted key, the first and second shift registers shifting the bits to the left if the shift instruction is a shift instruction for shifting the bits to the left and, otherwise, shifting the bits to the right if the shift instruction is a shift instruction for shifting the bits to the right, a second multiplexer configured to select the permuted key if the coefficient a.sub.q is equal to “0” and to select the permuted and shifted key if the coefficient a.sub.q is equal to “1”, this second multiplexer having: a first output that delivers, to the second input of the next stage ET.sub.q−1, the parameters α.sub.m,q−1 to α.sub.0,q−1 extracted from predetermined locations of the key selected from among the permuted key and the permuted and shifted key, and a second output that delivers, to the third input of the next stage ET.sub.q−1, a permutation key for the next stages comprising the parameters α.sub.m,q−2 to α.sub.0,0 extracted from predetermined locations of the key selected from among the permuted key and the permuted and shifted key, the permutation key delivered at the second output being formed by a juxtaposition of blocks BK.sub.y,q−1 of 2.sup.q−1 bits each, each block BK.sub.y,q−1 containing the parameters of the transpositions of the next stages E.sub.q−2 to E.sub.0 to be applied to the block BCP.sub.y,q−1 of the data item received at the first input of the next stage ET.sub.q−1, and during operation 4), the microprocessor is configured to compare the code C.sub.res−t with the result D.sub.res−p and to trigger the signalling of a fault only if they are not identical.

8. Microprocessor according to claim 2, wherein the arithmetic instruction is an addition instruction for adding the data item D.sub.1 to a data item D.sub.2, and the security module comprises a computation circuit for computing the code C.sub.rest−t from the codes C.sub.1 and C.sub.2 and without using the result D.sub.res−p, this computation circuit comprising: an adder stage comprising, for each pair of bits of the codes C.sub.1 and C.sub.2 to be added, an adder AD.sub.p, where the subscript p is the order number of the two bits of the codes C.sub.1 and C.sub.2 to be added by this adder, this order number varying from zero to 2.sup.d−1, each adder AD.sub.p having: a first, a second and a third input, the first and second inputs being intended to receive the bit of the code C.sub.1 and the bit of the code C.sub.2 to be added, respectively, a first output delivering the result a.b, where: “a” and “b” are the values received at the first and second inputs, respectively, and the symbol “ . ” denotes the “AND” logic operation, a second output delivering the result a+b, where the symbol “+ ” denotes the “OR” logic operation, a third output delivering the result a XOR b XOR c, where “c” is the value received at the third input and XOR is the symbol of the “EXCLUSIVE-OR” logic operation, the concatenation of the bits delivered at the third outputs of the various adders AD.sub.p of the addition stage forming the code C.sub.res−t, a carry look-ahead unit having an input at which the permutation key a is received, this carry look-ahead unit being capable of determining the values of the third inputs of the adders of the adder stage that need to have a carry delivered to them from the results delivered at the first and second outputs of each adder and from the parameters α.sub.j,q, of the key a received at its input.

9. Microprocessor according to claim 8, wherein: the carry look-ahead unit comprises, for each stage E.sub.q of the function F.sub.α, a stage EA.sub.q comprising components CA.sub.αj,q, each component CA.sub.αj,q being associated with a respective transposition T.sub.αj,q of the stage E.sub.q, the components CA.sub.αj,q of the stages EA.sub.0 to EA.sub.NbE−2 all being structurally identical to one another and each having a first, a second, a third, a fourth, a fifth and a sixth input and a first, a second, a third and a fourth output: the first output delivering the result (G.sub.r+P.sub.r.G.sub.I).k+(G.sub.I+P.sub.I.G.sub.r).k′, where: G.sub.r, P.sub.r, G.sub.I, P.sub.I and k are the values received at the first, second, third, fourth and sixth inputs, respectively, of this component, the symbol “ + ” denotes the “OR” logic operation, the symbol “ . ” denotes the “AND” logic operation, and the symbol “ ′ ” denotes the “NOT” logic operation, the second output delivering the result P.sub.I. P.sub.r, the third output delivering the result c.sub.i.k′+(G.sub.I+P.sub.I.c.sub.i).k, where c.sub.i is the value received at the fifth input, the fourth output delivering the result c.sub.i.k+(G.sub.r+P.sub.r. C.sub.i_.k′, the component CA.sub.αj,NbE−1 of the stage EA.sub.NbE−1 has a first, a second, a third, a fourth, a fifth and a sixth input and a first and a second output: the first output delivering the result c.sub.i.k′+(G.sub.I+P.sub.I.c.sub.i).k, where c.sub.i is the value received at the fifth input, the second output delivering the result c.sub.i.k+(G.sub.r+P.sub.r.c.sub.i).k′, the first and second inputs of each component CA.sub.αj,0 of the stage EA.sub.0 are connected to the first and second outputs, respectively, of the adder AD.sub.2j, where the adder AD.sub.2j is the adder AD.sub.p, the subscript p of which is equal to 2j, the third and fourth inputs of each component CA.sub.αj,0 of the stage EA.sub.0 are connected to the first and second outputs, respectively, of the adder AD.sub.2j+1, where the adder AD.sub.2j+1 is the adder AD.sub.p, the subscript p of which is equal to 2j+1, the third and fourth outputs of each component CA.sub.αj,0 of the stage EA.sub.0 are connected, respectively, to the third inputs of the adders AD.sub.2j and AD.sub.2j+1, respectively, for q greater than zero, the first and second inputs of each component CA.sub.αj,q of the stage EA.sub.q are connected to the first and second outputs, respectively, of the component CA.sub.a2j,q−1 of the stage EA.sub.q−1, for q greater than zero, the third and fourth inputs of each component CA.sub.αj,q of the stage EA.sub.q are connected to the first and second outputs, respectively, of the component CA.sub.αa(2j+1),q−1 of the stage EA.sub.q−1, for q greater than zero, the third and fourth outputs of each component CA.sub.αj,q of the stage EA.sub.q are connected, respectively, to the fifth inputs of the components CA.sub.α2j,q−1 and CA.sub.α(2j+1),q−1, respectively, the sixth input of each component CA.sub.αj,q is capable of receiving the parameter α.sub.j,q.

10. Microprocessor according to claim 1, wherein: the arithmetic and logic unit is capable of executing a logic instruction that, when executed, causes a Boolean operation D.sub.1&D.sub.2& . . . &D.sub.n to be performed and the result of this Boolean operation to be stored in the register R.sub.res−p, where the “&” symbol denotes the Boolean operation, and the microprocessor is configured to perform operations 1) to 4) for this logic instruction and, during the execution of operation 3), to compute the code C.sub.res−t using the following relationship: C.sub.res−t=C.sub.1 & C.sub.2 & . . . &C.sub.n.

11. Microprocessor according to claim 1, wherein the arithmetic operation is chosen from the group made up of a bit shift, a bit rotation and an addition.

Description

[0013] The invention will be better understood on reading the description that follows, which is given solely by way of non-limiting example, with reference to the drawings, in which:

[0014] FIG. 1 is a schematic illustration of the architecture of an electronic apparatus capable of executing a binary code;

[0015] FIG. 2 is a schematic illustration of the structure of a register of the apparatus of FIG. 1,

[0016] FIG. 3 is a schematic illustration of a function F.sub.α executed by the apparatus of FIG. 1;

[0017] FIG. 4 is a flowchart of a method for executing the binary code by means of the apparatus of FIG. 1,

[0018] FIG. 5 is a schematic illustration of a computation circuit for computing a code C.sub.res−t in the case of an arithmetic shift operation for shifting one bit to the left,

[0019] FIGS. 6 and 7 are more detailed schematic illustrations of two components of the circuit of FIG. 5,

[0020] FIGS. 8 to 10 are schematic illustrations of various operating states of the circuit of FIG. 5,

[0021] FIG. 11 is a schematic illustration of a computation circuit for computing a code C.sub.res−t in the case of an arithmetic shift operation for shifting 2.sup.r bits to the left,

[0022] FIG. 12 is a schematic illustration of a computation circuit for computing a code C.sub.res−t in the case of an arithmetic shift operation for shifting α.sub.NbE−12.sup.NbE−1+ . . . +α.sub.q2.sup.q+ . . . +α.sub.0 bits to the left,

[0023] FIG. 13 is a schematic illustration of a computation circuit for computing a code C.sub.res−t in the case of an arithmetic rotation operation for rotating one bit to the left,

[0024] FIG. 14 is a schematic illustration of a computation circuit for computing a code C.sub.res−t in the case of an arithmetic addition operation, and

[0025] FIGS. 15 and 16 are more detailed schematic illustrations of two components of the circuit of FIG. 14.

SECTION I: CONVENTIONS, NOTATIONS AND DEFINITIONS

[0026] In the figures, the same references have been used to designate elements that are the same. In the rest of this description, features and functions that are well known to those skilled in the art will not be described in detail.

[0027] In this description, the following definitions have been adopted.

[0028] A “program” designates a set of one or more predetermined functions that it is desired to have executed by a microprocessor.

[0029] A “source code” is a representation of the program in a computer language, not being able to be executed directly by a microprocessor and being intended to be converted, by a compiler, into a machine code able to be executed directly by the microprocessor.

[0030] A program or a code is said to be “able to be executed directly” or “directly executable” when it is able to be executed by a microprocessor without this microprocessor needing to compile it beforehand by way of a compiler or to interpret it by way of an interpreter.

[0031] An “instruction” denotes a machine instruction able to be executed by a microprocessor. Such an instruction consists:

[0032] of an opcode, or operation code, that codes the nature of the operation to be executed, and

[0033] of one or more operands defining the value(s) of the parameters of this operation.

[0034] The registers in which the data item or data to be processed by an instruction are stored are typically identified by one or more operands of the instruction. Likewise, the register R.sub.res−p in which the result D.sub.res−p of the execution of an instruction needs to be stored can also be identified by an operand of this instruction.

[0035] “Logic instruction” is used to denote an instruction from the set of instructions of the microprocessor 2 that, when executed by the arithmetic and logic unit, stores the result of a Boolean operation in a register R.sub.res−p of the microprocessor. The opcode of the logic instruction identifies the Boolean operation to be executed by the arithmetic and logic unit in order to modify or combine the data item or data D.sub.1 to D.sub.n.

[0036] The “&” symbol is used below to generically denote a Boolean operation. Thus, the notation D.sub.1&D.sub.2& . . . &D.sub.n generically denotes a Boolean operation executed by the microprocessor 2 between the data D.sub.1 to D.sub.n. When n =1, the Boolean operation is the complement operation also known by the name “NOT”. When n is greater than or equal to two, the Boolean operation is chosen from the group made up of the following Boolean operations and their composition:

[0037] the “OR” logic operation,

[0038] the “EXCLUSIVE-OR” logic operation,

[0039] the “AND” logic operation.

[0040] The following notations are used to denote Boolean operations:

[0041] the “OR” logic operation is denoted by the symbol “ + ”,

[0042] the “EXCLUSIVE-OR” logic operation is denoted by the symbol “XOR”,

[0043] the “AND” logic operation is denoted by the symbol “ . ”,

[0044] the “NOT” Boolean operation is denoted by the symbol “ ′ ” placed after the variable for which the complement is computed.

[0045] “Arithmetic instruction” is used to denote an instruction from the set of instructions of the microprocessor 2 that, when executed by the unit 10, stores the result of an arithmetic operation in a register R.sub.res−p of the microprocessor. An arithmetic operation is different from a Boolean operation. An arithmetic operation typically belongs to the group made up of bit shift operations, bit rotation operations, addition operations, multiplication operations and division operations.

[0046] “Arithmetic and logic instruction” denotes both a logic instruction and an arithmetic instruction. Unless indicated otherwise, the term “instruction” denotes an arithmetic and logic instruction below.

[0047] A “machine code” is a set of machine instructions. It typically is a file containing a sequence of bits with the value “0” or “1”, these bits coding the instructions to be executed by the microprocessor. The machine code is able to be executed directly by the microprocessor, that is to say without the need for a preliminary compilation or interpretation.

[0048] A “binary code” is a file containing a sequence of bits bearing the value “0” or “1”. These bits code data and instructions to be executed by the microprocessor. The binary code thus comprises at least one machine code and also, in general, digital data processed by this machine code.

[0049] The expression “execution of a function” is understood to designate execution of the instructions making up this function.

[0050] A block of bits of a data item or of a variable is a group of consecutive bits of this data item or of this variable. The size of a block of bits is equal to the number of bits contained in this block.

Section II: Architecture of the Apparatus

[0051] FIG. 1 shows an electronic apparatus 1 comprising a microprocessor 2, a main memory 4 and a mass storage medium 6. For example, the apparatus 1 is a computer, a smartphone, an electronic tablet, a chip card or the like.

[0052] The microprocessor 2 here comprises:

[0053] an arithmetic and logic unit 10;

[0054] a set 12 of registers;

[0055] a control module 14;

[0056] a data input/output interface 16,

[0057] an instruction loader 18 having a program counter 26,

[0058] a queue 22 of instructions to be executed, and

[0059] a hardware security module 28.

[0060] The memory 4 is configured so as to store instructions of a binary code 30 of a program to be executed by the microprocessor 2. The memory 4 is a random access memory. The memory 4 is typically a volatile memory. The memory 4 may be a memory external to the microprocessor 2, as shown in FIG. 1. In this case, the memory 4 is formed on a substrate that is mechanically separate from the substrate on which the various elements of the microprocessor 2, such as the unit 10, are formed.

[0061] By way of illustration, the binary code 30 notably comprises a machine code 32 of a secure function. Each secure function corresponds to a set of several lines of code, for example several hundred or thousand lines of code, stored at successive addresses in the memory 4. Each line of code corresponds here to a machine word. A line of code is thus loaded into a register of the microprocessor 2 in a single read operation. Likewise, a line of code is written to the memory 4 by the microprocessor 2 in a single write operation. Each line of code codes either a single instruction or a single data item.

[0062] By way of illustration, the microprocessor 2 is a reduced instruction set computer more commonly known by the acronym RISC.

[0063] The loader 18 loads the next instruction to be executed by the unit 10 into the queue 22 from the memory 4. More precisely, the loader 18 loads the instruction to which the program counter 26 points. To this end, the queue 22 comprises a succession of multiple registers.

[0064] The unit 10 is notably configured to execute one after another the instructions loaded into the queue 22. The instructions loaded into the queue 22 are generally consistently executed in the order in which these instructions were stored in this queue 22. The unit 10 is also capable of storing the result of these executed instructions in one or more of the registers of the set 12.

[0065] In this description, “execution by the microprocessor 2” and “execution by the unit 10” will be used synonymously.

[0066] The module 14 is configured to move data between the set 12 of registers and the interface 16. The interface 16 is notably able to acquire data and instructions, for example from the memory 4 and/or the medium 6 that are external to the microprocessor 2. To speed up transfers of data and instructions between the microprocessor 2 and the memory 4 here, the interface 16 comprises one or more cache memories. To simplify FIG. 1, only one cache memory 27 is shown. This cache memory 27 is used to temporarily store the data processed by the microprocessor 2 on the same chip as the unit 10.

[0067] The module 28 is capable of automatically executing the various operations described in detail in the sections that follow in order to make the execution of the arithmetic and logic instructions by the unit 10 secure. The module 28 operates independently and without using the unit 10. It is thus capable of processing the lines of code before and/or after they are processed by the unit 10. To this end, it notably comprises a secure nonvolatile memory 29 and various hardware computation circuits. This memory 29 can only be accessed via the module 28. In this embodiment, the module 28 is configured to execute operations such as the following operations:

[0068] verifying an integrity code,

[0069] constructing an integrity code from a data item,

[0070] constructing the integrity code for a result from the integrity codes of the processed data.

[0071] Each computation circuit constructs an integrity code C.sub.res−t for a result D.sub.res−p from the integrity codes C.sub.1 to C.sub.n of the data D.sub.1 to D.sub.n processed by the unit 10 and 30 without directly using the result D.sub.res−p. Here, there is a computation circuit 110 for the logic instructions. There is also a computation circuit for each arithmetic instruction whose execution needs to be made secure. Here, the module 28 comprises five computation circuits 120, 130, 140, 149 and 160, each associated with a respective arithmetic instruction. These computation circuits are described in more detail in section IV that follows.

[0072] The memory 29 is used to store the secret information required for the operation of the module 28. Here, it therefore notably comprises a pre-stored secret key α.

[0073] In this example of embodiment, the set 12 comprises general registers that can be used to store any type of data. The size of each of these registers is sufficient to store a data item or a result and the integrity code associated therewith.

[0074] A data interchange bus 24 that connects the various components of the microprocessor 2 to one another is shown in FIG. 1 in order to indicate that the various components of the microprocessor are able to interchange data with one another.

[0075] The medium 6 is typically a non-volatile memory. It is for example an EEPROM or flash memory. Here, it contains a backup copy 40 of the binary code 30. It is typically this copy 40 that is automatically copied to the memory 4 to restore the code 30, for example after a power failure or the like or just before the execution of the code 30 starts.

Section III—Making Arithmetic and Logic Instructions Secure

[0076] By injecting faults while the unit 10 is operating, it is possible to disrupt its operation so that the result of the execution of the arithmetic and logic instruction does not correspond to that expected. The unit 10 is then said to have been caused to malfunction. This section describes a solution for detecting such a malfunction of the unit 10.

[0077] The registers R.sub.1 to R.sub.n denote the registers of the set 12 comprising the data D.sub.1 to D.sub.n, respectively, to be processed when the instruction is executed. The register R.sub.res−p denotes the register of the set 12 in which the result, of the execution of the arithmetic and logic instruction, is stored.

[0078] The size, in terms of the number of bits, of each data item D.sub.1, D.sub.2 and D.sub.res−p is equal to 2.sup.d, where d is a whole number typically greater than four or five.

[0079] The structures of the registers R.sub.1, R.sub.2 and R.sub.res−p are identical and shown in the specific case of the register R.sub.i in FIG. 2. The register R.sub.i comprises:

[0080] a bit range containing the data item D.sub.i,

[0081] a range containing an integrity code C.sub.i allowing the integrity and the authenticity of the data item D.sub.i to be checked.

[0082] The code C.sub.i is generated by the module 28 using a pre-programmed relationship defined generically by the following relationship: C.sub.i=Q.sub.α(D.sub.i), where:

[0083] the subscript i identifies a register among the registers R.sub.1, R.sub.2 and R.sub.res−p, and

[0084] the function Q.sub.α is a function pre-programmed in the module 28 and configured by the secret key α.

[0085] The function Q.sub.α is defined by the following relationship: Q.sub.a(D.sub.i)=P o F.sub.α(D.sub.i), where the symbol “o” denotes the function-composition operation. The function P is a predetermined function. In the first embodiments described below, the function P is the identity function. Thus, in these first embodiments, the function Q.sub.α is equal to the function F.sub.α. Examples where the function P is different from the identity function are given in the section dealing with variants.

[0086] The function F.sub.α is a homomorphism of a set A equipped with the “&” Boolean operation towards a set B equipped with the same “&” Boolean operation such that F.sub.α(D.sub.1&D.sub.2)=F.sub.α(D.sub.1) & F.sub.α(D.sub.2), and such is the case for all “&” Boolean operations. Here, the sets A and B are each the set of numbers that can be coded over 2.sup.d bits, that is to say the set of possible data D.sub.1 and D.sub.2. Thus, using the notations introduced earlier, the function F.sub.α is such that for any & Boolean operation, the circuit 110 simply computes the integrity code C.sub.res−t associated with the result D.sub.res−p of the Boolean operation D.sub.1 & D.sub.2 using the following relationship C.sub.res−t=C.sub.1 & C.sub.2. When the Boolean operation executed is the complement operation of the data item D.sub.1, the circuit 110 computes the code C.sub.res−t associated with the result D.sub.res−p using the following relationship C.sub.res−t=C.sub.1′, where the symbol “ ′ ” denotes the complement operation that returns a “1” when D.sub.1=0 and that returns “0” when D.sub.1=1.

[0087] FIG. 3 shows the function F.sub.α used in this embodiment. The function F.sub.α is defined by the following relationship: F.sub.α(D.sub.i)=E.sub.0 o . . . o E.sub.q o . . . o .sub.ENbE−1(D.sub.i), where:

[0088] each function E.sub.q is a stage of transpositions that can be executed in parallel,

[0089] NbE is the number of stages of transpositions, and

[0090] the subscript q is an order number between zero and NbE−1.

[0091] The number NbE is greater than one and less than or equal to d. Preferably, the number NbE is equal to d. In FIG. 3, d=5 and NbE=5.

[0092] Each stage E.sub.q of transpositions is defined by the following relationship: E.sub.q(x)=T.sub.αm,q o . . . o T.sub.αj,q o . . . o T.sub.α1,q o T.sub.αo,q(X), where:

[0093] x is a variable whose size, in terms of the number of bits, is equal to the size of the data item D.sub.i,

[0094] T.sub.αj,q is a conditional transposition, configured by the parameter α.sub.j,q, that permutes two blocks of bits B.sub.2j+1,q and B.sub.2j,q of the variable x when the parameter α.sub.j,q is equal to “1” and that does not permute these two blocks of bits when the parameter α.sub.j,q is equal to “0”,

[0095] “m+1” is the total number of transpositions T.sub.αj,q of the stage E.sub.q,

[0096] “j” is an order number identifying the transposition T.sub.αj,q among the other transpositions of the stage E.sub.q. The subscript “j” therefore also identifies the position of the blocks B.sub.2j+1,q and B.sub.2j,q in the variable x. In this application, the blocks are classified in ascending order of their subscript, which depends on the value of the subscript j.

[0097] Each transposition T.sub.αj,q is distinguished from all of the other transpositions of the function F.sub.α by the fact that it is the only one that permutes the two blocks B.sub.2j+1,q and B.sub.2j,q when the parameter α.sub.j,q is equal to “1”. Moreover, the blocks B.sub.2j+1,q and B.sub.2j,q of all of the transpositions T.sub.αj,q of the same stage E.sub.q are different from one another and do not overlap. Thus, all of the transpositions T.sub.αj,q of the stage E.sub.q can be executed in parallel. Here, the stages E.sub.q are executed one after the other in descending order of the subscripts q.

[0098] Moreover, this function F.sub.α has the following characteristics:

[0099] the blocks B.sub.2j+1,q and B.sub.2j,q permuted by the transpositions T.sub.αj,q are adjacent blocks,

[0100] the size of the blocks B.sub.2i+1,q and B.sub.2j,q is equal to 2.sup.q,

[0101] the number m of transpositions T.sub.αj,q per stage E.sub.q is equal to 2.sup.d−q−1.

[0102] The notations B.sub.wj+1,q and B.sub.2j,q indicate that these are the (2j+1)-th and 2j-th blocks of 2.sup.q bits, respectively, of the variable x. In FIG. 3, the block B.sub.o,q is the least significant block of bits, the block B.sub.1,q the next block and so on. Each horizontal brace in FIG. 3 encompasses the two blocks and B.sub.2j,q and B.sub.2j,q of a transposition T.sub.αj,q for which the parameter is α.sub.j,q.

[0103] In the case of FIG. 3, for all of the stages E.sub.q for which q is less than NbE−1 and for all of the transpositions T.sub.αj,q of this stage, the blocks B.sub.2j+1,q and B.sub.2j,q are both placed within one and the same block B.sub.l,q+1 of the higher stage E.sub.q+1, where the subscript “l” denotes the block of the higher stage that contains the blocks B.sub.2i+1,q and B.sub.2j,q. For example, as can be seen in FIG. 3, the blocks B.sub.1,q and B.sub.o,q, of the stage E.sub.q are consistently placed within the block B.sub.0,q+1 of the higher stage E.sub.q+1. Moreover, here, each block of a higher stage E.sub.q+1 contains at most two blocks of the lower stage E.sub.q.

[0104] The operation of the microprocessor 2 in order to make the execution of arithmetic and logic instructions secure will now be described in more detail with reference to FIG. 4.

[0105] The method begins by providing, in a step 86, the binary code 30. During this step, in this example, the binary code 30 is loaded into the memory 4 from the medium 6. Next, execution of the binary code 30 by the microprocessor 2 begins.

[0106] In a step 88, each time a data item D.sub.i is stored in the cache memory 27, the module 28 computes the code C.sub.i using the relationship C.sub.i=F.sub.α(D.sub.i). Next, the data item D.sub.i and the code C.sub.i associated therewith are both stored in the memory 27.

[0107] Each time an instruction to load a data item into one of the registers R.sub.i is executed by the unit 10, in a step 90, the data item D, and the code C.sub.i are written to this register R.sub.i.

[0108] Prior to the execution of an arithmetic and logic instruction between two data items D.sub.1 and D.sub.2, step 90 is executed once for the data item D.sub.1 and once for the data item D.sub.2.

[0109] Next, each time an arithmetic and logic instruction is about to be executed by the unit 10, just before it is executed, in a step 94, the module 28 checks whether there is an error in the data item D, contained in the register R.sub.i identified by an operand of the instruction to be executed.

[0110] During this step, for each register R.sub.i in question, the module 28 checks, using the code C.sub.i contained in the register R.sub.i, whether or not the data item D.sub.i currently stored in this register has an error. For example, this involves the module 28 computing a code C.sub.i* using the relationship C.sub.i*=F.sub.α(D.sub.i) and without using the code C.sub.i stored in the register R. If the code C,* computed in this way is identical to the code C.sub.i stored in the register R.sub.i, then the integrity and authenticity of the data item D.sub.i are confirmed. In that case, the module 28 detects no error and proceeds to a step 96. Otherwise, the module 28 proceeds to a step 102.

[0111] In step 102, the module 28 triggers signalling of an execution fault.

[0112] If the module 28 detects no error, in step 96, the microprocessor 2 decodes the arithmetic and logic instruction and then the unit 10 executes it and stores its result D.sub.res−p in the register R.sub.res−p.

[0113] When the executed instruction is an arithmetic and logic instruction whose execution is secure, in parallel with step 96 or after the execution of step 96, in a step 98, the module 28 computes the code C.sub.res−t by using only the codes C.sub.i associated 10 with the data D.sub.i processed by the unit 10 in step 96. Thus, when it is the data D.sub.1 and D.sub.2 that are processed, the code C.sub.res−t is computed by combining the codes C.sub.1 and C.sub.2 stored in the registers R.sub.1 and R.sub.2, respectively, prior to execution of the logic instruction.

[0114] More precisely, when the executed instruction is a logic instruction, the circuit 110 computes the code C.sub.res−t using the following relationship: C.sub.res−t=C.sub.1 & C.sub.2, where the “&” symbol denotes the Boolean operation executed by the unit 10 in step 96.

[0115] When the executed instruction is an arithmetic instruction for which the module 28 comprises a specific computation circuit for computing the code C.sub.res−t, then this specific circuit is selected and the code C.sub.res−t is computed by this specific circuit. Examples of such specific computation circuits are described in detail in the section that follows.

[0116] Next, in a step 100, the module 28 checks whether the computed code C.sub.res−t corresponds to a code C.sub.res−p computed from the result D.sub.res−p stored in the register R.sub.res−p. In the case of the circuits 110, 120, 130, 149 and 160, the code C.sub.res−p is computed by implementing the relationship C.sub.res−p=F.sub.α(D.sub.res−p). When the code C.sub.res−t is computed by the circuit 140, the code C.sub.res−p is equal to the result D.sub.res−p.

[0117] Next, the module 28 compares the computed codes C.sub.res−p .sup.and C.sub.res−t. If these codes are different, the module 28 triggers the execution of step 102. Otherwise, this means that the code C.sub.res−t corresponds to the code C.sub.res−p and therefore that there was no fault during the execution of the instruction by the unit 10. In this last case, no signalling of an execution fault is triggered and the method continues with the execution of the next instruction in the queue 22.

[0118] The execution of steps 98 and 100 allows a malfunction in the unit 10 to be detected, because the computed codes C.sub.res−p and C.sub.res−t are identical only if the unit 10 has executed the arithmetic and logic instruction correctly. In the case of a logic instruction, this can be explained simply by the following relationship: C.sub.res−p=F.sub.α(D.sub.res−p)=F.sub.α(D.sub.1&D.sub.2)=F.sub.α(D.sub.1) & F.sub.α(D.sub.2)=C.sub.1 & C.sub.2=C.sub.res−t. In the case of arithmetic instructions, this can be explained by the structure and the operations performed by the implemented computation circuit.

[0119] If the instruction executed in step 96 is the complement operation for the data item D.sub.1, in step 98, the code C.sub.res−t is computed using the following relationship: C.sub.res−t=C.sub.1′. The remainder of the method is then identical to what was described earlier. In the case of the complement operation, the codes C.sub.res−p and C.sub.res−t are identical only if the unit 10 has operated correctly. This can be demonstrated using the following relationship: C.sub.res−p=F.sub.α(D.sub.res−p)=F.sub.α(D.sub.1′)=F.sub.α(D.sub.1)′=C.sub.1′=C.sub.res−t.

[0120] In response to an execution fault being signalled, in a step 104, the microprocessor 2 implements one or more countermeasures. A wide range of countermeasures are possible. The countermeasures implemented may have very different degrees of severity. For example, the countermeasures that are implemented may range from simply displaying or simply storing an error message without interrupting the normal execution of the machine code 32 as far as definitively taking the microprocessor 2 out of service. The microprocessor 2 is considered to be out of service when it is definitively put into a state in which it is incapable of executing any machine code. Between these extreme degrees of severity, there are many other possible countermeasures, such as:

[0121] using a human-machine interface to indicate detection of the faults,

[0122] immediately interrupting the execution of the machine code 32 and/or reinitializing it, and

[0123] deleting the machine code 32 from the memory 4 and/or deleting the backup copy 40 and/or deleting the secret data.

Section IV—Examples of Computation Circuits for Computing the Code C.SUB.res−t.:

[0124] The function F.sub.α described earlier allows the bit locality to be preserved. This denotes the property according to which the bits of a data item D.sub.i that are placed within the block B.sub.2j+1,q or B.sub.2j,q still remain within this block. In other words, the transpositions T.sub.αj,q−1 to T.sub.αj,0 that apply to the bits of this block B.sub.2j+1,q or B.sub.2j,q cannot permute a bit of this block with a bit placed outside this block. On the other hand, the bits of the block B.sub.4+1,q or B.sub.2bq can be moved within this block by applying these transpositions T.sub.αj,q−1 to T.sub.αj,0. This stems from the fact that, for all of the stages E.sub.q for which q is less than NbE−2 and for all of the transpositions T.sub.αj,q of this stage, the blocks B.sub.2j+1,q and B.sub.2j,q are both placed within one and the same block B.sub.l,q+1 of the higher stage E.sub.q+1 . It is this particular property of the function F.sub.α that allows simple and fast computation circuits for computing the code C.sub.res−t to be produced, for each arithmetic instruction. This is illustrated below in the particular case of bit shift instructions, a rotation instruction and an addition instruction. However, on the basis of these examples, a person skilled in the art is capable of producing other computation circuits for computing the code C.sub.res−t for other arithmetic instructions.

[0125] FIG. 5 shows the computation circuit 120 for computing the code C.sub.res−t when the arithmetic instruction executed by the unit 10 is a logic shift instruction for shifting the bits of the data item D.sub.1 1 bit to the left. The code C.sub.res−t is computed only from the code C.sub.1. To simplify FIG. 5, the circuit 120 is illustrated in the particular case where the size of the codes C.sub.i and C.sub.res−t C is equal to 8 bits. In this case, the number NbE of stages is equal to three. However, the description provided for this particular size can easily be generalized for all possible sizes.

[0126] In FIG. 5, the eight consecutive bits of the code C.sub.1 are denoted by the symbols a.sub.0 to a.sub.7, where a.sub.0 is the least significant bit and a.sub.7 is the most significant bit.

[0127] The bits of the code C.sub.res−t are denoted by the symbols a′.sub.0 to a′.sub.7, these bits a′.sub.0 to a′.sub.7 being classified in the same order as the bits of the code C.sub.1.

[0128] For each stage E.sub.q of the function F.sub.α, the circuit 120 comprises a corresponding stage ED.sub.q. Each stage ED.sub.q comprises a component CD.sub.αj,q for each transposition T.sub.αj,q of the stage E.sub.q. More precisely, each component CD.sub.αj,q is associated with a respective corresponding transposition T.sub.αj,q. The components CD.sub.αj,q are classified in ascending order of their subscript, which varies depending on the subscript j.

[0129] For q less than NbE−1, the components CD.sub.αj,q are all structurally identical to one another. One of these components CD.sub.αj,q is shown in more detail in FIG. 6. It has three outputs 122 to 124 and four inputs 126 to 129.

[0130] The output 122 delivers the result a.k′+c.k, where a, k and c are the values received at the inputs 126, 128 and 129, respectively.

[0131] The output 123 delivers the result b.k+c.k′, where b is the value received at the input 127.

[0132] The output 124 delivers the result a.k+b.k′.

[0133] The inputs 126 and 127 of each component CD.sub.αj,0 of the stage ED.sub.0 are connected to the 2j-th and (2j+1)-th bits, respectively, of the code C.sub.1. For q greater than zero and q less than NbE−1, the inputs 126 and 127 of each component CD.sub.αj,q are connected, respectively, to the outputs 124 of the components CD.sub.α2j,q−1 and CD.sub.α(2j+1),q−1, respectively, of the stage ED.sub.q−1.

[0134] The input 128 of each component CD.sub.αj,q receives the parameter α.sub.j,q of the transposition T.sub.αj,q with which it is associated.

[0135] For q greater than zero, the outputs 122 and 123 of each component CD.sub.αj,q are connected to the input 129 of the components CD.sub.α(2j+1),q−1 and CD.sub.α2j,q−1 , respectively. For q=0, the outputs 122 and 123 of each component CD.sub.αj,0 deliver the (2j+1)-th and 2j-th bits, respectively, of the code C.sub.res−t.

[0136] The stage ED.sub.NbE−1 comprises a single component CD.sub.α0,NbE−1. The component CD.sub.α0,NbE−1 is shown in more detail in FIG. 7. It has two outputs 132 and 133 and three inputs 136 to 138. The outputs 132 and 133 deliver the results “a” and “0”, respectively, when the input 138 is equal to “0”, where “a” is the value received at the input 136 and “0” is the value zero. The outputs 132 and 133 deliver the results “0” and “b”, respectively, when the input 138 is equal to “1”, where “b” is the value received at the input 137.

[0137] The inputs 136 and 137 of the component CD.sub.α0,NbEA−1 are connected to the outputs 124 of the components CD.sub.α0,NbE−2 and CD.sub.α1,NbE−2 respectively. The input 138 receives the parameter α.sub.0,NbE−1. The outputs 132 and 133 are connected to the inputs 129 of the components CD.sub.α1,NbE−2 and CD.sub.α0,NbE−2, respectively.

[0138] When the instruction executed in step 96 is a shift instruction for shifting one bit to the left, the circuit 120 is selected in order to perform step 98. To this end, the bits of the code C.sub.1 are delivered to the inputs 126 and 127 of the components CD.sub.αj,0. In response, the components CD.sub.αj,0 deliver the results present at their output 124 to the inputs 126 and 127 of the higher stage ED.sub.1. This process is repeated stage by stage until the component CD.sub.α0,NbE−1 is reached. The component CD.sub.α0,NbE−1 then delivers the results a.k′ and b.k that are present at its outputs 132 and 133, respectively, to the inputs 129 of the components CD.sub.60 j,NbE−2. In response, the component CD.sub.60 j,NbE−2 delivers the results a.k′+c.k and b.k+c.k′ to the inputs 129 of the components CD.sub.αj,q of the lower stage E.sub.q. The process is then repeated stage by stage until the components CD.sub.αj,0 of the stage ED.sub.0 are reached. The components CD.sub.αj,0 then deliver the various bits of the computed code C.sub.res−t at their outputs 122 and 123. Next, the method continues with step 100.

[0139] The operation of the circuit 120 is illustrated in FIGS. 8 to 10 in a simplified case where the size of the codes C.sub.1 and C.sub.res−t is equal to four bits. The number NbE of stages E.sub.q is therefore equal to two. Moreover, in this particular example, the parameters α.sub.0,0, α.sub.1,0 and α.sub.0,1 are equal to 0, 1 and 1, respectively. The bits a.sub.0, a.sub.1, a.sub.2 and a.sub.3 of the data item D.sub.1 are classified in ascending order starting from the least significant bit to the most significant bit. In these conditions, with the values given above for the parameters α.sub.0,0, α.sub.1,0 and α.sub.0,1, the code C.sub.1 is equal to a.sub.0, a.sub.1, a.sub.3, a.sub.2. The result D.sub.res−p itself is equal to a.sub.2, a.sub.1, a.sub.0, 0. In FIGS. 8 and 9, the “?” symbol indicates that this value is unknown at this stage of operation.

[0140] FIG. 8 shows that when the values α.sub.0,0 and α.sub.1,0 are equal to 0 and 1, respectively, the components CD.sub.α0,0 and CD.sub.α1,0 deliver the values a.sub.3 and a.sub.1, respectively, at their output 124. Next, in response (FIG. 9), the component CD.sub.α0,1 delivers the values 0 and a.sub.1 at its outputs 132 and 133, respectively. Finally (FIG. 10), the components CD.sub.α0,0 and CD.sub.α1,0 deliver the bits of the computed code C.sub.res−t at their outputs 122 and 123. In this example, the computed code C.sub.res−t is 0, a.sub.0, a.sub.2, a.sub.1. It can easily be checked that this computed code C.sub.res−t is equal to F.sub.α(D.sub.res−p) in the absence of an execution fault.

[0141] FIG. 11 shows the computation circuit 130 for computing the code C.sub.res−t when the arithmetic instruction executed by the unit 10 is a logic shift of 2.sup.r bits to the left, 30 where r is a whole number greater than one and less than NbE−1. In FIG. 11, the circuit 130 is shown in the particular case where NbE=d =4 and r=2.

[0142] The following notations are used below to describe the circuit 130. The symbols BC.sub.y,r, BCI.sub.x,r, BCR.sub.x,r and BD.sub.z,r denote the blocks of 2.sup.r bits at the position y in the code C.sub.1, at the position x in an intermediate code CI, at the position x in the code C.sub.res−p and at the position z in the data item D.sub.1, respectively. The subscripts y, x and z here are order numbers that begin at 0 and increase by 1 each time there is a move from one block of 2.sup.r bits to the next block of 2.sup.r bits, moving towards the most significant bits.

[0143] The circuit 130 comprises a higher permutator 131 and a scheduler 134. The permutator 131 allows the position of the blocks of 2.sup.r bits within the code C.sub.res−t to be computed from the code C.sub.1. To that end, here, the permutator 131 comprises stages ED.sub.r to ED.sub.NbE−1 , which are identical to the stages ED.sub.r to .sub.EDNbE−1 of the circuit 120 except that instead of manipulating blocks of 1 bit, it is blocks of 2.sup.r bits that are manipulated.

[0144] More precisely, the inputs 126 and 127 of each component CD.sub.αj,q, for q greater than or equal to r, receives blocks of 2.sup.r bits rather than of a single bit. Thus, the outputs 122 and 123 of the components CD.sub.αj,r deliver an intermediate code CI, in which each block BCI.sub.x,r of 2.sup.r bits is at the desired location, that is to say at the location that it needs to occupy in the code C.sub.res−t, to the scheduler 134.

[0145] Moreover, each block BCI.sub.x,r is identical to a corresponding block BC.sub.y,r of the code C.sub.1. The reason is that the permutator 131 is only able to move the blocks BC.sub.y,r with respect to one another in order to obtain the intermediate code CI. The permutator 131 does not permute the bits placed within a block BC.sub.y,r. The position of the block BC.sub.y,r which is identical to the block BCI.sub.x,r placed at the position x in the code CI, is denoted y below.

[0146] The order of the 2.sup.r bits within the block BCI.sub.x,r is identical to the order of the 2.sup.r bits within the corresponding block BC.sub.y,r. The arrangement of the 2.sup.r bits within the block BC.sub.y,r results from application of some of the transpositions of the stages E.sub.r−1 to E.sub.0 to a corresponding block BD.sub.z,r when the code C.sub.1 is calculated. The position of the block BD.sub.z,r from which the positions of the bits placed within the block BC.sub.y,r are computed is denoted z below. The position z of the block BD.sub.z,r is not necessarily the same as the position y of the block BC.sub.y,r because the transpositions of the stages E.sub.NbE−1 to E.sub.r may have moved this block BD.sub.z,r before applying the transpositions of the next stages thereto. The composition of the transpositions T.sub.αj,q of the stages E.sub.r−1 to E.sub.0 applied, during construction of the code C.sub.1, to the bits placed within the block BD.sub.z,r in order to obtain the block BC.sub.y,r is denoted F.sub.αcy. The key αc.sub.y is a subset of the key a that contains only the parameters of the transpositions of the function F.sub.αcy. The key αc.sub.y is called the “current key” below because it is the one that explains the present arrangement of the bits within the block BC.sub.y,r. The key αc.sub.y is dependent on the position y of the block BC.sub.y,r. The parameter of the transposition T.sub.αj,q that is contained in the current key αc.sub.y is also denoted αc.sub.j,q below.

[0147] In the code C.sub.resp−p, the arrangement of the 2.sup.r bits within the block BCR.sub.x,r results from application, to the corresponding block BD.sub.z,r, of some of the transpositions of the stages E.sub.r−1 to E.sub.o. The corresponding block BD.sub.z,r is the same as the one that corresponds to the block BC.sub.y,r. The composition of the transpositions T.sub.αj,q of the stages E.sub.r−1 to E.sub.0 applied, during construction of the code C.sub.resp−p, to the bits placed within the block BD.sub.z,r in order to obtain the block BCR.sub.x,r is denoted F.sub.αsx. The key αs.sub.x is called the “desired key” below because it is the one that determines the arrangement of the bits within the block BCR.sub.x,r. The key as.sub.x is dependent on the position x of the block BCR.sub.x,r. The parameter of the transposition T.sub.αj,q that is contained in the desired key as.sub.y is also denoted as.sub.j,q below.

[0148] The result of the explanations above is that the arrangement of the 2.sup.r bits within the block BCI.sub.x,r is not necessarily identical to the arrangement of the 2.sup.r bits within the block BCR.sub.x,r that occupies the same position x in the code C.sub.res−t. The reason is that the current key ac.sub.y is not necessarily identical to the desired key αs.sub.x. The scheduler 134 rearranges the order of the bits within each block BCI.sub.x,r to obtain the desired block BCR.sub.x,r.

[0149] To explain this, let us suppose that the data item D.sub.1 comprises four blocks, of 2.sup.r bits each, denoted in the order BD.sub.3,r, BD.sub.2,r, BD.sub.1,r and BD.sub.0,r. It is also supposed in this example that NbE=d=4 and r=2 and that the parameters α.sub.0,3, α.sub.1,2, α.sub.0,2 are equal to 1, 1 and 0, respectively. The computation of the code C.sub.1 is broken down into first and second successive phases. During the first phase, it is the transpositions of the stages E.sub.NbE−1 to E.sub.r that are applied. Thus, during this first phase, only the whole blocks BD.sub.z,r of the data item D.sub.1 are permuted. In this example, at the end of this first phase, the order of the blocks BD.sub.z,r is as follows: BD.sub.0,r, BD.sub.1,r, BD.sub.3,r and BD.sub.2,r.

[0150] Next, during the second phase, it is the transpositions of the stages E.sub.r−1 to E.sub.0 that are applied. This second phase permutes only the bits within each of the blocks BD.sub.z,r. During this second phase, no applied transposition moves a bit placed within a block BD.sub.z,r to another block. At the end of this second phase, the code C.sub.1 is obtained. The four blocks, of 2.sup.r bits each, of the code C.sub.1 obtained are denoted in the order BC.sub.3,r, BC.sub.2,r, BC.sub.1,r and BC.sub.0,r.

[0151] During the second phase, the bits of the block BD.sub.0,r are permuted by applying the transpositions of the stages E.sub.r−1 to E.sub.0, which are applied only to the 2.sup.r most significant bits. This stems from the fact that at the end of the first phase, the block BD.sub.0,r is at the location of the most significant bits, that is to say at the position y=3 here. The composition of the transpositions of the stages E.sub.r−1 to E.sub.0 that apply only to the 2.sup.r most significant bits is denoted F.sub.αc3. Similarly, the compositions of transposition of the stages E.sub.r−1 to E.sub.0 that permute only the bits placed within the blocks BD.sub.1,r, BD.sub.3,r and BD.sub.2,r respectively are denoted F.sub.αc2, F.sub.αc1 and F.sub.αc0. It is thus noted that the block BC.sub.3,r of the code C.sub.1 is the result of application of the function F.sub.αc3 to the bits of the block BD.sub.0,r. Similarly, the blocks BC.sub.2,r, BC.sub.1,r and BC.sub.0,r of the code C.sub.1 are the results of application of the functions F.sub.αc2, F.sub.αc1 and F.sub.αc0 to the blocks BD.sub.1,r, BD.sub.3,r and BD.sub.2,r, respectively.

[0152] Following the logic shift of 2.sup.r bits to the left, the result D.sub.res−p is equal to the concatenation, in order, of the blocks BD.sub.2,r, BD.sub.1,r, BD.sub.0,r and of a block [0] of 2.sup.r null bits.

[0153] Application of the function F.sub.α to the result D.sub.res−p in order to compute the code C.sub.res−p is broken down, similarly, into a first phase then a second phase. At the end of the first phase, the blocks of the result D.sub.res−p are classified in the following order: [0], BD.sub.0,r, BD.sub.2,r and BD.sub.1,r. During the second phase, the functions F.sub.αs3 to F.sub.αs0 are applied to the blocks [0], BD.sub.0,r, BD.sub.2,r and BD.sub.1,r, respectively. Thus, the blocks BCR.sub.3,r, BCR.sub.2,r, BCR.sub.1,4, BCR.sub.0,r of the code C.sub.res−p are the results of application of the functions F.sub.αs3 to F.sub.αs0 to the blocks [0], BD.sub.0,r, BD.sub.2,r and BD.sub.1,r, respectively.

[0154] The intermediate code CI delivered by the permutator 131 is the concatenation, in order, of the blocks [0], BC.sub.0,r, BC.sub.2,r and BC.sub.1,r. The block BCI.sub.2,r is the result of application of the function F.sub.αc3 to the block BD.sub.0,r. The desired block BCR.sub.2,r, which occupies the same position in the code C.sub.resp−p, is the result of application of the function F.sub.αs2 to the block BD.sub.0,r. Thus, in the case of the block BCI.sub.2,r, the role of the scheduler 134 is to cancel application of the transpositions of the function F.sub.ac3 and to apply the transpositions of the function F.sub.2 instead in order to obtain the desired block BCR.sub.2,r.

[0155] For this, for example, for each stage E.sub.r−1 to E.sub.0 of the function F.sub.α, the scheduler 134 comprises a stage corresponding to EO.sub.r−1 to EO.sub.0. Each stage EO.sub.q comprises 2.sup.d−q−1 comparators CO.sub.j,q. Each comparator CO.sub.j,q is associated with the corresponding transposition T.sub.αj,q that permutes the blocks BCI.sub.2j+1,q and BCI.sub.2j,q of the intermediate code CI when the value of its parameter is equal to one. The size of the blocks BCI.sub.2j+1,q and BCI.sub.2j,q is equal to 2.sup.q, To simplify FIG. 11, only some of these comparators are shown. Each comparator CO.sub.j,q receives the block BCI.sub.j,q+1, the parameter ac.sub.j,q of the current key and the parameter αs.sub.j,q of the desired key. If these two parameters are equal, the output of the comparator CO.sub.j,q delivers the blocks BCI.sub.2j+1,q and BCI.sub.2j,q to the comparators CO.sub.2j+1,q−1 and CO.sub.2j,q−1, respectively. In other words, the transpositions T.sub.αcj,q and T.sub.αsj,q are identical and no change of order of the bits is necessary. If the two parameters αc.sub.j,q and αs.sub.j,q are different, the comparator CO.sub.j,q permutes the positions of the blocks BCI.sub.2j+1,q and BCI.sub.2j,q before delivering them to the comparators CO.sub.2j+1,q−1 and CO.sub.2j,q−1, respectively. This replaces the transposition T.sub.αcj,q with the transposition T.sub.αsj,q. Proceeding thus by moving from the stage EO.sub.r−1 to the stage EO.sub.0, the code C.sub.rest−t is obtained at the outputs of the comparators CO.sub.j,0 of the stage EO.sub.0. In FIG. 11, the bits of the code C.sub.res−t-t computed by the circuit 130 are denoted by the references a.sub.7 to a.sub.0.

[0156] The current αc and desired as keys are obtained as follows, for example. The key α is divided into 2.sup.r blocks BK.sub.z,r of 2.sup.r bits each. Each block BK.sub.z,r contains only the parameters α.sub.j,r−1 to α.sub.j,0 of the transpositions to be applied, when the code C.sub.1 is calculated, to the bits placed within the respective block BD.sub.z,r of the data item D.sub.1. Within each block BK.sub.z,r, the parameters α.sub.j,r−1 to α.sub.j,0 are classified in a predetermined order. For example, here, they are first of all classified in descending order of stages and the various parameters α.sub.j,q of one and the same stage E.sub.q are also classified in descending order of subscript j. The desired key as is equal to the key a in which the parameters are classified as described above. Next, the various blocks BK.sub.z,r are permuted, for example, by a circuit identical to the permutator 131. The key containing the blocks BK.sub.z,r permuted in this way is equal to the current key αc. The parameters αc.sub.j,q and as.sub.j,q are the parameters that occupy the same position in the current key ac and the desired key as, respectively.

[0157] FIG. 12 shows the computation circuit 140 for computing the code C.sub.res−t from the code C.sub.1 when the arithmetic instruction executed by the unit 10 is a shift instruction for shifting the data item D.sub.1 a.sub.NbE−12.sup.NbE−1+ . . . +a.sub.q2.sup.q+ . . . +a.sub.02.sup.0 bits to the left. The coefficients a.sub.NbE−1 to a.sub.0 are coefficients whose Boolean values are determined and fixed in advance. The circuit 140 computes a code C.sub.res−t that is equal to the result D.sub.res−p if no execution fault occurs. Thus, in this embodiment, in step 100, the code C.sub.res−p is equal to the result D.sub.res−p.

[0158] For each stage E.sub.q of the function F.sub.α, the circuit 140 comprises a stage ET.sub.q. Each stage ET.sub.q has four inputs 142 to 145 and three outputs 146 to 148. The input 142 receives a code CP.sub.q to be permuted. Each code CP.sub.q comprises 2.sup.d−q blocks BCP.sub.j,q, of 2.sup.q bits each. These blocks BCP.sub.j,q do not overlap and are immediately consecutive. The subscript j is equal to the order number of the block BCP.sub.j,q counting from the block BCP.sub.0,q that contains the least significant bits.

[0159] Each input 142 is connected to the output 146 of the previous stage ET.sub.q+1, except the input 142 of the stage ET.sub.NbE−1 , which receives the code C.sub.1 at its input 142.

[0160] The input 143 receives the parameters α.sub.j,q of the stage E.sub.q of the function F.sub.α. Here, to this end, the input 143 of the stage ET.sub.q is connected to the output 147 of the previous stage ET.sub.q+1.

[0161] The input 144 receives a permutation key K.sub.ETq that contains only the parameters α.sub.j,q−1 to α.sub.j,0 that are required for implementing the transpositions of the stages E.sub.q−1 to E.sub.0 of the function F.sub.α. This key K.sub.ETq is divided into 2.sup.d−q blocks BK.sub.j,q of 2.sup.q bits each. Each block BK.sub.j,q contains only the parameters α.sub.j,q−1 to α.sub.j,0 of the transpositions to be applied to the bits placed within the block B.sub.j,q of the data item D.sub.1. Within each block BK.sub.j,q, the parameters α.sub.j,q−1 to α.sub.j,0 are classified in a predetermined order. For example, here, they are first of all classified in descending order of stages and the various parameters of one and the same stage E.sub.q−1 are also classified in descending order of subscript j. For example, let us suppose that q=3, the transpositions to be applied to the block B.sub.2,3 are, successively, the transpositions T.sub.α2,2, T.sub.α5,1, T.sub.α4,1, T.sub.α11,0, T.sub.α10,0, T.sub.α9,0 and T.sub.α8,0. This follows from the organization of the transpositions T.sub.αj,q in the function F.sub.α described with reference to FIG. 3. From then on, the block BK.sub.2,3 comprises the parameters α.sub.2,2, α.sub.5,1, α.sub.4,1, α.sub.11,0, α.sub.10,0, α.sub.9,0 and α.sub.8,0 and an additional 0 to reach the size of 2.sup.3 bits.

[0162] The input 145 receives the coefficient a.sub.q of the shift to be applied to the data item D.sub.1.

[0163] The stage ET.sub.q comprises two permutators 150 and 151, two shift registers 154 and 155 and two multiplexers 158 to 159.

[0164] The permutator 150 executes the transpositions of the stage E.sub.q on the data received at its input 142. In other words, the permutator 150 executes the following function: T.sub.αm,qo . . . oT.sub.αj,qo . . . oT.sub.α0,q(CP.sub.q), where m is equal to 2.sup.d−q−1.

[0165] To do this, the permutator 151 is connected to the input 142 in order to receive the code CP.sub.q to be permuted and to the input 143 in order to receive the parameters α.sub.m,q to α.sub.0,q.

[0166] The code permuted by the permutator 150 is transmitted directly to a first input of the multiplexer 158 and, in parallel, to an input of the register 154.

[0167] The register 154 performs a logic shift of 2.sup.q bits to the left on the bits received at its input in order to obtain a permuted and shifted code, which is delivered to a second input of the multiplexer 158.

[0168] The multiplexer 158 connects the first input directly to the output 146 if the coefficient α.sub.q received at the input 145 is equal to zero. If the coefficient a.sub.q received is equal to one, the multiplexer 158 connects its second input directly to the output 146.

[0169] The permutator 151 and the register 155 are identical to the permutator 150 and the register 154, respectively. They therefore perform the same operations as the permutator 150 and the register 154, respectively, but applied to the key K.sub.ETq, that is to say to the key received at the input 144.

[0170] The multiplexer 159 selects the permuted key delivered by the permutator 151 if the coefficient α.sub.q is equal to zero. Otherwise, it selects the permuted and shifted key delivered by the register 155. Moreover, using the key selected on the basis of the coefficient a.sub.q, the multiplexer 159 delivers to the output 147 the parameters α.sub.j,q−1 required for configuring the transpositions of the stage ET.sub.q−. It also delivers the key K.sub.ETq−1 to the output 148.

[0171] The operation of the circuit 140 is as follows: the permutator 150 of the stage ET.sub.q cancels the effect of the transpositions T.sub.j,q of the stage E.sub.q that is applied to the data item D.sub.1 when the code C.sub.1 is calculated. It should be remembered here that T.sub.j,q o T.sub.j,q is the identity function. Thus, in the permuted code delivered by the permutator 150, the blocks BCP.sub.j,q occupy the same position as the one that they had in the data item D.sub.1. However, within each block BCP.sub.j,q, the position of the bits corresponds to the result of application of the transpositions of the stages E.sub.j,q−1 to E.sub.j,0 to the bits placed within the block B.sub.j,q of the data item D.sub.1. Thus, the order of the bits within the blocks BCP.sub.j,q is not the same as the order of the bits within the block B.sub.j,q of the data item D.sub.1. However, this is not important for the application of a logic shift of 2.sup.q bits to the left, because such a shift shifts only blocks of 2.sup.q bits. Thus, applying the shift of 2.sup.q bits in the stage ET.sub.q allows the code C.sub.res−t to be computed without this requiring:

[0172] the data item D.sub.1 to be found from the code C.sub.1, then

[0173] the various logic shifts of 2.sup.q bits to be applied to this data item D.sub.1 that has been found.

[0174] In this embodiment, the parameters α.sub.j,q−1 to α.sub.j,0 required for configuring all of the transpositions T.sub.j,q−1 to T.sub.j,0 to be applied to the bits placed within a block BCP.sub.j,q received at the input 142 are placed within the block BK.sub.j,q of the same size and occupying the same position j in the key K.sub.ETq received at the input 144. At the output 148, this relationship between the position of the blocks BCP.sub.j,q−1 and the position of the blocks BK.sub.j,q−1 is preserved. In other words, in the key delivered at the output 148, the block BK.sub.j,q−1 contains all of the parameters α.sub.j,q−2 to α.sub.j,0 required for configuring the transpositions to be applied to the bits placed within the block BCP.sub.j,q−1 delivered at the output 146.

[0175] To preserve this relationship, the permutator 151 and the register 155 apply the same transpositions and the same shifts, respectively, as those applied to the code CP.sub.q, but this time to the key K.sub.ETq received. Next, the multiplexer 159 extracts from the selected key the parameters α.sub.j,q−1 to be delivered to the output 147. The multiplexer 159 also extracts the parameters α.sub.j,q−2 to α.sub.j,0 and generates the key K.sub.ETq−1 that is delivered to the output 148. Here, the multiplexer 159 identifies the parameters α.sub.j,q to be extracted on the basis of their position in the selected key.

[0176] The output 146 of the stage ET.sub.0 delivers the code C.sub.res−t to be compared with the code C.sub.res−p in order to check, in step 100, that the execution of the shift instruction has taken place without a fault.

[0177] FIG. 13 shows a computation circuit 149 for computing the code C.sub.res−t when the arithmetic instruction executed by the unit 10 is a rotation instruction for rotating the bits of the data item D.sub.1 one bit to the left. This rotation instruction is identical to the shift instruction for shifting one bit to the left, except that the most significant bit of the data item D.sub.1 is reinjected on the right and therefore becomes the least significant bit after this rotation has been executed.

[0178] For each stage E.sub.q of the function F.sub.α, the circuit 149 comprises a corresponding stage ER.sub.q. Each stage ER.sub.q comprises a component CC.sub.αj,q for each transposition T.sub.αj,q of the stage E.sub.q. More precisely, each component CC.sub.αj,q is associated with a respective corresponding transposition T.sub.αj,q.

[0179] For q less than NbE−2, each component CC.sub.αj,q is identical to the component CD.sub.αj,q of the circuit 120. The component CC.sub.α0,NbE−1 is shown in FIG. 13 in the particular case where NbE is equal to three. In FIG. 13, it is therefore denoted by the reference CR.sub.α0,2. The component CC.sub.α0,NbE−1 has two inputs 152 and 153 and two outputs 156 and 157. The inputs 152 and 153 are connected to the outputs 124 of the components CC.sub.α0,NbE−2 and CC.sub.α1,NbE−2 respectively. The outputs 156 and 157 are connected to the inputs 129 of the components CC.sub.α1,NbE−2 and CC.sub.α0,NbE−2, respectively.

[0180] The output 156 consistently delivers the same value as that received at the input 152. The output 157 consistently delivers the same value as that received at the input 153. In other words, the component CC.sub.α0,NbE−1 consistently reverses the position of the bits received at its inputs. This allows the most significant bit to be reinjected at the location intended to receive the least significant bit.

[0181] The operation of the circuit 149 is derived from the explanations given for the circuit 120.

[0182] FIG. 14 shows the computation circuit 160 for computing the code C.sub.res−t when the arithmetic instruction executed by the unit 10 is an addition instruction for adding the data D.sub.1 and D.sub.2. This time, the code C.sub.res−t is computed from the codes C.sub.1 and C.sub.2. The circuit 160 computes the code C.sub.res−t, which, in the absence of an execution fault, is equal to F.sub.α(D.sub.res−p).

[0183] FIG. 14 shows the circuit 160 in the particular case where the size of the codes C.sub.1 and C.sub.2 and of the code C.sub.res−t is equal to 8 bits. In this figure, the 8 bits of the codes C.sub.1 and C.sub.2 are denoted, in the order towards the most significant bit, α.sub.0 to α.sub.7 and b.sub.0 to b.sub.7, respectively. The 8 bits of the computed code C.sub.res−t are denoted, in the same order, s.sub.0 to s.sub.7.

[0184] The circuit 160 comprises a stage 162 of adders and a carry look-ahead unit 164.

[0185] The stage 162 comprises an adder AD.sub.p for each pair of bits a.sub.p, b.sub.p to be added. The subscript p denotes the position of the bits in the codes C.sub.1, C.sub.2 and C.sub.res−t. These adders AD.sub.p are structurally identical to one another and differ from one another only in the bits a.sub.p and b.sub.y that they add.

[0186] The adder AD.sub.p is shown in more detail in FIG. 15. The adder AD.sub.p has three inputs 170 to 172 and three outputs 174 to 176. The inputs 170 and 171 receive the bits a.sub.p and b.sub.p, respectively.

[0187] The input 172 receives a carry c.sub.p to be used in the addition of the bits a.sub.p and b.sub.p.

[0188] The output 174 delivers the result a.sub.p.b.sub.p. The output 175 delivers the result a.sub.p+b.sub.p. The output 176 delivers the bit s.sub.p. The bit s.sub.p is computed by the adder AD.sub.p using the following relationship: s.sub.p=a.sub.pXOR b.sub.pXOR c.sub.p.

[0189] The function of the unit 164 is to rapidly propagate the various carries c.sub.p to be used by the adders AD.sub.p. To that end, here, the unit 164 computes the carries c.sub.p from the information delivered at the outputs 174 and 175 of each adder AD.sub.p.

[0190] In this embodiment, the unit 164 comprises a stage EA.sub.q for each stage E.sub.q of the function F.sub.α. Each stage EA.sub.q comprises 2.sup.d−q−1 components CA.sub.αj,q, where the subscript j is the order number of the component CA.sub.αj,q in the stage EA.sub.q. Each component CA.sub.αj,q is associated with a respective transposition T.sub.αj,q of the function F.sub.α.

[0191] Here, the components CA.sub.αj,q are all structurally identical to one another and are distinguished only by their connection to the other components of the circuit 160.

[0192] The component CA.sub.αj,q is shown in more detail in FIG. 16. The component CA.sub.αj,q has six inputs 180 to 185 and four outputs 188 to 191. The output 188 delivers the result (G.sub.r+P.sub.r.G.sub.I).k+(G.sub.I+P.sub.I.G.sub.r).k′, where G.sub.r, P.sub.r, G.sub.I, P.sub.I and k are the values received at the inputs 180, 181, 182, 183 and 185, respectively.

[0193] The output 189 delivers the result P.sub.I.P.sub.r. The output 190 delivers the result c.sub.i.k′+(G.sub.I+P.sub.I.c.sub.i).k, where c.sub.i is the value received at the input 184. The output 191 delivers the result c.sub.i.k+(G.sub.r+P.sub.r.C.sub.1).k′.

[0194] The input 185 receives the parameter α.sub.j,q of the transposition T.sub.αj,q associated with this component CA.sub.αj,q.

[0195] The inputs 180 and 181 of each component CA.sub.αj,0 of the stage EA.sub.0 are connected to the outputs 174 and 175, respectively, of the adder AD.sub.2j. The inputs 182 and 183 of each component CA.sub.αj,0 of the stage EA.sub.0 are connected to the outputs 174 and 175, respectively, of the adder AD.sub.2j+1.

[0196] The outputs 190 and 191 of each component CA.sub.αj,0 of the stage EA.sub.0 are connected to the inputs 172 of the adders AD.sub.2j and AD.sub.2j+1 , respectively.

[0197] For q greater than zero:

[0198] the inputs 180 and 181 of each component CA.sub.αj,q of the stage EA.sub.q are connected to the outputs 188 and 189, respectively, of the component CA.sub.α2j,q−1 of the lower stage EA.sub.q−1,

[0199] the inputs 182 and 183 of each component CA.sub.αj,q are connected to the outputs 188 and 189 of the component CA.sub.α(2j+1).sub.,chi of the lower stage EA.sub.q−1,

[0200] the outputs 190 and 191 of each component CA.sub.αj,q are connected to the inputs 184 of the components CA.sub.α2j,q−1 and CA.sub.α(2j+1),q−1, respectively, of the stage ET.sub.q−1

[0201] The outputs 188 and 189 of the component CA.sub.α0,NbE−1 are not used. The input 184 of the component CA.sub.α0,NbE−1 allows the carry computed by another circuit, for example identical to the circuit 160, to be received. This allows multiple circuits 160 to be linked to one another, so as to perform additions on data of greater size.

[0202] The unit 164 functions as a conventional carry look-ahead computation unit. Here, however, this conventional unit is modified to take account of the transpositions T.sub.αj,q and therefore the parameters α.sub.j,q that are used for computing the code C.sub.res−t. In summary, the components CA.sub.αj,q propagate the carry to the right when the parameter α.sub.j,q is equal to zero and to the left when the parameter α.sub.j,q is equal to one.

Section IV—Variants

[0203] Variants of the Function Q.sub.α:

[0204] In the relationship Q.sub.a(D.sub.i)=P o F.sub.α(D.sub.i), the function P is not necessarily the identity function. For example, the function P is a compression function that constructs, from each of the bits of the result F.sub.α(D.sub.i), a code C.sub.1 whose size, in terms of the number of bits, is less than 2.sup.d. The reason is that when the function P is the identity function, the size of the code C.sub.i is equal to the size of the data item D.sub.i, that is to say equal to 2.sup.d. Now, in some contexts, it is desirable to reduce the size of the code C. For example, this is desirable in order to reduce the space that it can take up in the cache memory 27. By way of illustration, to this end, the function P is the 30 function that performs the following operations:

[0205] 1) the function P divides the result F.sub.α(D.sub.i) into two blocks P.sub.0 and p.sub.1 of bits of the same size, then,

[0206] 2) the function P performs an “EXCLUSIVE-OR” between the blocks P.sub.0 and p.sub.1. In this case, the size of the code C.sub.i is halved and is equal to 2.sup.d−1.

[0207] Many other compression functions P are possible. The function P can also be different from the identity function and from a compression function. For example, the function P is an encryption or other function.

[0208] When the function P is different from the identity function, each of the computation circuits described here is broken down into a first and a second subcircuit. The first subcircuit is identical to one of the computation circuits described earlier. This first subcircuit therefore delivers a code C.sub.res−int, which, in the absence of an execution fault, is consistently equal to the result F.sub.α(D.sub.res−p). The second subcircuit applies the predetermined function P to the code C.sub.res−int in order to obtain the code C.sub.res−t.

[0209] The various variants are described below in the particular case where the function P is equal to the identity function. However, these variants also apply to the case where the function P is different from the identity function.

[0210] As a variant, the transposition T.sub.αj,q permutes the blocks B.sub.2j+1,q and B.sub.2j,q when the parameter α.sub.j,q =0 and does not permute them when the parameter α.sub.j,q=1.

[0211] The function F.sub.α has been described in the particular case where the stages of transpositions first transpose the blocks of greater size and end by transposing the blocks of smaller size. However, as a variant, the stages E.sub.q of transpositions can be executed and classified in reverse order. In this case, the transpositions of smaller size are applied first, ending by applying the transposition T.sub.α0,NbE−1 of greater size. The order in which the various stages E.sub.q are classified does not modify the bit locality property described earlier. Thus, even when the order of the stages E.sub.q is reversed, it is possible to construct fast and simple computation circuits for computing the code C.sub.res−t for arithmetic instructions.

[0212] As a variant, one or more stages of the function F.sub.α are omitted.

[0213] Some of the transpositions T.sub.αj,q can be omitted. In this case, at least one of the stages comprises fewer than 2.sup.d−q−1 transpositions T.sub.αj,q.

[0214] Variants of the Computation Circuits for Computing the Code C.sub.res−t:

[0215] The teaching provided here in the case of a few arithmetic instructions, such as shifts, rotations and additions, can be applied to other arithmetic instructions. In particular, it is possible to take the teaching provided in these particular cases as a basis for developing computation circuits for computing a code C.sub.res−t for other arithmetic instructions. For example, the circuit 120 can be modified to compute the code C.sub.res−t corresponding to a logic shift instruction for shifting 1 bit to the right. In practice, it is sufficient, for this purpose, to retain the same circuit as the circuit 120, but to send the complement of the parameter α.sub.j,q, that is to say the parameter α.sub.j,q′, to the input 128 or 138 of each of the components CD.sub.αj,q.

[0216] Equally, it is possible to construct a computation circuit for computing the code C.sub.res−t for an arithmetic shift instruction for shifting one bit to the left or to the right. An arithmetic shift is distinguished from the logic shifts described earlier by the fact that the most significant bit remains unchanged and is therefore not shifted, unlike the other bits.

[0217] In the circuit 140, each 2.sup.q-bit shift register can be replaced by a register that performs a rotation of 2.sup.q bits. The circuit thus obtained computes the result C.sub.res−t, which corresponds to a rotation instruction for rotating the bits of the data item D.sub.1 a.sub.NbE−12.sup.NbE−1+ . . . +a.sub.q2.sup.q+ . . . +a.sub.0 bits to the left. By replacing these registers with registers that perform a shift to the right or a rotation to the right, the circuit obtained computes the code C.sub.res−t corresponding to a shift or rotation instruction for shifting or rotating a.sub.NbE−12.sup.NbE−1+ . . . +a.sub.q2.sup.q+ . . . +a.sub.0 bits to the right.

[0218] It is also possible to link multiple computation circuits in order to compute the code C.sub.res−t for an operation that corresponds to the composition of multiple suboperations for each of which there is already a computation circuit for computing the code C.sub.res−t. For example, if the executed operation is a logic shift instruction for shifting two bits to the left, the code C.sub.res−t is computed by applying the circuit 120 twice. To that end, the code C.sub.1 is first injected at the inputs of the circuit 120 and a first intermediate code CI.sub.cres−t is obtained. Next, the code CI.sub.cres−t is injected at the inputs of this same circuit 120 in order to obtain the desired code C.sub.res−t.

[0219] Similarly, the circuits 120 and 130 can be linked in order to compute the code C.sub.res−t for a logic shift to the left for any number of bits.

[0220] If the coefficients a.sub.q are consistently constant, as a variant, the inputs 145 of the circuit 140 are omitted. In this case, the coefficients α.sub.q are wired inside each stage ET.sub.q. For example, the multiplexer 158 is omitted. If the value of the coefficient a.sub.q is consistently equal to one, then the output of the register 154 is directly connected to the output 146. The multiplexer 159 is also simplified, since it consistently selects the output of the register 155. Conversely, if the coefficient a.sub.q is consistently equal to zero, then the output of the permutator 150 is directly connected to the output 146 and the register 154 is omitted. Equally, the register 155 is omitted.

[0221] As a variant, the component CA.sub.α0,NbE−1 of the circuit 160 is devoid of the outputs 188 and 189, which are not used.

[0222] As a variant, the output 175 of the component AD.sub.p delivers the result α.sub.p XOR b.sub.y rather than the result α.sub.p+b.sub.p.

[0223] In a simplified embodiment, only the execution of some arithmetic or logic instructions is secure. For example, only the execution of one of the following instructions is made secure by implementing the method described here: the bit shift instruction, the bit rotation instruction and the bit addition instruction. The execution of the other instructions, such as the logic instructions, is thus not secure. In this latter case, this means that, for these other instructions, no code .sub.res−t is calculated and step 100 is omitted.

[0224] Other Variants:

[0225] The module 28 is not necessarily a hardware module of a single block. As a variant, it is made up of multiple hardware submodules that each perform one of the specific functions of the module 28. These hardware submodules are thus preferably embedded as close as possible to the data that they process. For example, in this case, the hardware submodule that computes the code C.sub.i associated with each data item D.sub.1 is embedded in the cache memory 27. From then on, the code C.sub.i associated with each data item D.sub.i stored in the cache memory 27 is computed locally in this cache memory.

[0226] As a variant, each instruction of the machine code is also associated with an integrity code F.sub.α(I.sub.i) computed from the value of the loaded instruction I.sub.i. This code F.sub.α(I.sub.i) is verified just before the unit 10 executes the instruction I.sub.i. This allows the signalling of an execution fault to be triggered if the instruction I.sub.i is modified in the queue 22.

[0227] It is possible to associate the code C.sub.i with the data item D.sub.i in various ways. For example, instead of storing the code C.sub.i in the same register R.sub.i as the one that contains the data item D.sub.1, the code C.sub.i is stored in a register RC.sub.i associated with the register R.sub.i rather than in the register R.sub.i.

[0228] The secret key a can be modified, for example, at regular intervals.

[0229] Other embodiments of step 100 are possible. For example, the module 28 computes, as in the case of the circuit 140, a code C.sub.res−t that is equal to the result D.sub.res−p in the absence of an execution fault. In this case, the code C.sub.res−t is computed using the following relationship: C.sub.res−t=F.sub.a.sup.-1(C I.sub.res−t), where:

[0230] the function F.sub.α.sup.−1 is the inverse of the function F.sub.α, and

[0231] CI.sub.res−t is the code computed, for example, by the circuits 120, 130, 149 or 160.

[0232] The various computation circuits for computing the code C.sub.res−t that are described here can be implemented independently of one another.

Section V—Advantages of the Described Embodiments

[0233] Computing the code C; using a secret key α makes the method for executing the machine code more robust in the face of attempted attacks. The reason is that the attacker then has greater difficulty in falsifying the code C.sub.res−t so that it corresponds to an expected code when an execution fault has been deliberately introduced. Thus, the methods described earlier have the same advantages in terms of robustness as the one described in the article by DEMEYER2019. Moreover, the use of a function F.sub.α that has the locality property described earlier makes it possible to obtain computation circuits for computing the code C.sub.res−t that are simpler and faster than those required for implementing the method of the article DEMEYER2019.

[0234] The circuits 120, 130, 140, 149 and 160 each allow simple and fast computation of the code C.sub.res−t corresponding to a specific arithmetic instruction.

[0235] The circuit 110 also allows simple and fast computation of the code C.sub.rest−t for all Boolean operations.