Protection against side channel attacks

1. A cryptographic mechanism involving a secret D which can be represented as an n-bit number {d 0 , d 1 , . . . d n−1 } 2 , the cryptographic mechanism being arranged to calculate an output element OUT equal to X D , X being an element of a monoid {M, *}, the cryptographic mechanism comprising a first variable VAR 0 , a second variable VAR 1 , and computer program instructions to cause a processor of a cryptographic device to perform the steps of:

a. generating a random element MSK_INPUT (R);

b. creating a masked element MASKED_X (VAR 1 ) by using the element X and the random element MSK_INPUT and initializing a masked output element to the random element MSK_INPUT (R);

c. calculating the masked output element MASKED_OUT (VAR 0 ) using the masked element MASKED_X (VAR 1 ), the calculation of the masked output element MASKED_OUT thereby accumulating the random element MSK_INPUT (R) into intermediate results for MASKED_X and MASKED_OUT, the calculation comprising:

for i=n−1 down to 0:

performing a step MULi: VAR 1−di →VAR 1−di *VAR di ;

performing a step SQi: VAR di →VAR di * VAR di ;

d. calculating an output mask MSK_OUTPUT (MSK 0 ) from the random element MSK_INPUT, MSK_OUTPUT (MSK 0 ) being an inverse of the accumulation of the random element MSK_INPUT in masked output element MASKED_OUT during the step of calculating the masked output element in step c, without involving the secret D;

e. calculating the output element OUT using the masked output element MASKED_OUT and the output mask MSK_OUTPUT; and

wherein the step d occurs at any time between step a and step e, and wherein the steps a, b, c and e are consecutive.

2. The cryptographic mechanism according to claim 1 , wherein the random element MSK_INPUT (R) has an inverse element (R −1 ) for the operation * of the monoid {M, *}, the inverse element being usable to compute the output mask MSK_OUTPUT.

3. The cryptographic mechanism according to claim 2 wherein the calculation of the output mask MSK_OUTPUT comprises n steps {R_SQ i } i=n−1 . . . 0 , such that during each step R_SQ i , the cryptographic device calculates MSK i *MSK i , MSK i being an element of the monoid {M, *}, the initial value MSK n being obtained from the inverse element (R −1 ) of the random element MSK_INPUT, the last value MSK 0 being the output mask MSK_OUTPUT used to unmask the value of the masked output MASKED_OUT.

4. The cryptographic mechanism according to claim 3 , wherein MSK i is equal to MSK i+1 *MSK i+1 for i equal to n−1 down to 0.

5. The cryptographic mechanism according to claim 4 , wherein the masked element MASKED_X is equal to X*R and wherein the output element OUT is equal to MASKED_OUT*MSK 0 , MSK n being equal to the inverse of R, the initial value of the first variable VAR 0 being set to the value (R) of the random element, the initial value of the second variable VAR 1 being set to the value of the masked element MASKED_X, each step MUL i consisting in calculating VAR 1−di *VAR di and storing the result in VAR 1−di , each step SQ i consisting in calculating VAR di *VAR di and storing the result in VAR di .

6. A cryptographic device having a processor, a memory storing a secret D which can be represented as an n-bit number {d 0 , d 1 , . . . d n−1 } 2 , and a cryptographic mechanism being arranged to calculate an output element OUT equal to X D , X being an element of a monoid {M, *}, the cryptographic mechanism comprising a first variable VAR 0 and a second variable VAR 1 , and the cryptographic mechanism causing the processor of the cryptographic device to execute the steps of:

a. generating a random element MSK_INPUT (R);

b. creating a masked element MASKED_X (VAR 1 ) by using the element X and the random element MSK_INPUT and initializing a masked output element to the random element MSK_INPUT (R);

c. calculating the masked output element MASKED_OUT (VAR 0 ) using the masked element MASKED_X, the calculation of the masked output element MASKED_OUT thereby accumulating the random element MSK_INPUT (R) into intermediate results for MASKED_X and MASKED_OUT, the calculation comprising:

for i=n−1 down to 0:

performing a step MULi: VAR 1−di →VAR 1−di *VAR di ;

performing a step SQi: VAR di →VAR di *VAR di ;

d. calculating an output mask MSK_OUTPUT (MSK 0 ) from the random element MSK_INPUT, MSK_OUTPUT (MSK 0 ) being an inverse of the accumulation of the random element MSK_INPUT in masked output element MASKED_OUT during the step of calculating the masked output element in step c, without involving the secret D;

e. calculating the output element OUT using the masked output element MASKED_OUT and the output mask MSK_OUTPUT; and

wherein the step d occurs at any time between step a and step e, and wherein the steps a, b, c and e are consecutive.

7. A smart card having a processor, a memory storing a secret D which can be represented as an n-bit number {d 0 , d 1 , . . . d n−1 } 2 , and a cryptographic mechanism being arranged to calculate an output element OUT equal to X D , X being an element of a monoid {M, *}, the cryptographic mechanism comprising a first variable VAR 0 , a second variable VAR 1 , and instructions to cause the processor of the smart card to execute the steps of:

a. generating a random element MSK_INPUT (R);

b. creating a masked element MASKED_X (VAR 1 ) by using the element X and the random element MSK_INPUT and initializing a masked output element to the random element MSK_INPUT (R);

c. calculating the masked output element MASKED_OUT (VAR 0 ) using the masked element MASKED_X, the calculation of the masked output element MASKED_OUT thereby accumulating the random element MSK_INPUT (R) into intermediate results for MASKED_X and MASKED_OUT, the calculation comprising:

for i=n−1 down to 0:

performing a step MULi: VAR 1−di →VAR 1−di *VAR di ;

performing a step SQi: VAR di →VAR di *VAR di ;

d. calculating an output mask MSK_OUTPUT (MSK 0 ) from the random element MSK_INPUT, MSK_OUTPUT (MSK 0 ) being an inverse of the accumulation of the random element MSK_INPUT in masked output element MASKED_OUT during the step of calculating the masked output element in step c, without involving the secret D;

e. calculating the output element OUT using the masked output element MASKED_OUT and the output mask MSK_OUTPUT; and

wherein the step d occurs at any time between step a and step e, and

wherein the steps a, b, c and e are consecutive.

8. The cryptographic device of claim 6 wherein the cryptographic mechanism further comprises the random element MSK_INPUT (R) has an inverse element (R −1 ) for the operation * of the monoid {M, *}, the inverse element being usable to compute the output mask MSK_OUTPUT.

9. The cryptographic device of claim 8 wherein the cryptographic mechanism further comprises the calculation of the output mask MSK_OUTPUT comprising n steps {R_SQ i } i=−1 . . . 0 , such that during each step R_SQ i , the cryptographic device calculates MSK i *MSK i , MSK i being an element of the monoid {M, *}, the initial value MSK n being obtained from the inverse element (R −1 ) of the random element MSK_INPUT, the last value MSK 0 being the output mask MSK_OUTPUT used to unmask the value of the masked output MASKED_OUT.

10. The cryptographic device of claim 9 wherein the MSK i is equal to MSK i+1 *MSK i+1 for i equal to n−1 down to 0.

11. The cryptographic device of claim 10 wherein the masked element MASKED_X is equal to X*R and wherein the output element OUT is equal to MASKED_OUT*MSK 0 , MSK n being equal to the inverse of R, the initial value of the first variable VAR 0 being set to the value (R) of the random element, the initial value of the second variable VAR 1 being set to the value of the masked element MASKED_X, each step MUL i consisting in calculating VAR 1−di *VAR di and storing the result in VAR 1−di , each step SQ i consisting in calculating VAR di *VAR di and storing the result in VAR di .

12. The smart card of claim 7 wherein the random element MSK_INPUT (R) has an inverse element (R −1 ) for the operation * of the monoid {M, *}, the inverse element being usable to compute the output mask MSK_OUTPUT.

13. The smart card of claim 12 , wherein the calculation of the output mask MSK_OUTPUT comprises n steps {R_SQ i } i=n−1 . . . 0 , such that during each step R_SQ i , the cryptographic device calculates MSK i *MSK i , MSK i being an element of the monoid {M, *}, the initial value MSK n being obtained from the inverse element (R −1 ) of the random element MSK_INPUT, the last value MSK 0 being the output mask MSK_OUTPUT used to unmask the value of the masked output MASKED_OUT.

14. The smart card of claim 13 , wherein MSK i is equal to MSK i+1 *MSK i+1 for i equal to n−1 down to 0.

15. The smart card of claim 14 , wherein the masked element MASKED_X is equal to X*R and wherein the output element OUT is equal to MASKED_OUT*MSK 0 , MSK n being equal to the inverse of R, the initial value of the first variable VAR 0 being set to the value (R) of the random element, the initial value of the second variable VAR 1 being set to the value of the masked element MASKED_X, each step MUL i consisting in calculating VAR 1−di *VAR di and storing the result in VAR 1−di , each step SQ i consisting in calculating VAR di *VAR di and storing the result in VAR di .

16. A cryptographic mechanism for masking a cryptographic operation to calculate a final result as a function of a value X and a multi-bit secret D composed of n bits d i , such that the cryptographic operation is masked in a manner to reduce risk of side-channel attack on the cryptographic operation, the cryptographic mechanism comprising instructions to cause a processor of a cryptographic device to perform the steps of:

iterating over the bits d i , and for each iteration:

computing a zeroth intermediate result corresponding to the contribution to the final result of the i-th bit of D;

computing a first intermediate result that may be used to calculate the zeroth intermediate result of a subsequent iteration;

accumulating an evolving mask in the zeroth and first intermediate results; and

whereby the accumulated evolved mask is a function of the number of bits in D;

calculating an inverse of the accumulation of the mask; and

recovering the value final result by applying the calculated inverse of the accumulation of the mask to the zeroth intermediate result.

17. The cryptographic mechanism of claim 16 wherein the cryptographic operation is an exponentiation of a value X by the value D thereby computing the final result X D .

18. The cryptographic mechanism of claim 16 further comprising instructions to cause the processor to perform the steps of

initializing the zeroth intermediate result to a random value R;

initializing the first intermediate result to a function of the random value R and the value X;

initializing an inverse mask to the inverse of the random value R;

wherein the step of iterating over the bits d i operates from i=n−1 down to 0, and each iteration comprises:

if d i is 0:

setting the first intermediate result to the first intermediate result times the zeroth intermediate result;

setting the zeroth intermediate result to the zeroth intermediate result squared

if d i is 1:

setting the zeroth intermediate result to the first intermediate result times the zeroth intermediate result;

setting the first intermediate result to the first intermediate result squared; and

setting the inverse mask to the inverse mask squared thereby iteratively calculating the inverse of the accumulation of the mask; and

wherein the step of recovering the final result X D comprises multiplying the zeroth intermediate result and the inverse mask.

19. The cryptographic mechanism of claim 17 further comprising instructions to cause the processor to perform the steps of

initializing the zeroth intermediate result to a random value R;

initializing the first intermediate result to a function of the random value R and the value X;

initializing an inverse mask to the inverse of the random value R;

wherein the step of iterating over the bits d i operates from i=n−1 down to 0, and each iteration comprises:

if d i is 0:

setting the first intermediate result to the first intermediate result times the zeroth intermediate result;

setting the zeroth intermediate result to the zeroth intermediate result squared

if d i is 1:

setting the zeroth intermediate result to the first intermediate result times the zeroth intermediate result;

setting the first intermediate result to the first intermediate result squared; and

setting the inverse mask to the inverse mask squared thereby iteratively calculating the inverse of the accumulation of the mask; and

wherein the step of recovering the final result X D comprises multiplying the zeroth intermediate result and the inverse mask.