Method for processing data involving modular exponentiation and related device
View Patent ↗A data processing method, whereby an element is subjected to a first operation with a given operand. The method includes a step of updating by a second operation a first variable (B; a 0 ; S′ p , S′ q ) or a second variable (A; a 1 ; S p , S q ), depending on whether a corresponding bit of the operand=0 or 1; and a step of testing a relationship between a first value (B; a 0 ; S′) derived from the first variable and a second value (A; a 1 ; S) derived from the second variable. A related device is also disclosed.
1. A data processing method, comprising:
subjecting, with a data processing device, an element to a first operation with a given operand, said first operation including updating by a second operation a first variable if a corresponding bit of the operand has a value 0 and a second variable if the corresponding bit of the operand has a value 1;
testing, with the data processing device a relationship between a first value derived from the first variable and a second value derived from the second variable; and
outputting the second value if said relationship is verified, otherwise outputting an error value.
2. The method according to claim 1 , wherein the first value is the value of the first variable and the second value is the value of the second variable.
3. The method according to claim 1 , wherein the test step is applied to the result of the first operation.
4. The method according to claim 1 , wherein the first value results from a first recombination in accordance with the Chinese Remainders Theorem involving the first variable and the second value results from a second recombination in accordance with the Chinese Remainders Theorem involving the second variable.
5. The method according to claim 1 , wherein the first operation is a multiplication on an elliptical curve and the second operation is an addition on the elliptical curve.
6. The method according to claim 1 , wherein the relationship is independent of the operand.
7. The method according to claim 2 , wherein the testing step is applied to the result of the first operation.
8. A data processing method, comprising:
subjecting, with a data processing device, an element to
a modular exponentiation with an exponent, including updating by a modular multiplication a first variable if a corresponding bit of an exponent has a value 0 and a second variable if the corresponding bit of the exponent has a value 1; and
testing, with the data processing device a relationship between a first value derived from the first variable and a second value derived from the second variable.
9. The method according to claim 8 , wherein the test step includes comparing the product of the first variable and the second variable to a third variable updated by calculating a square regardless of the corresponding bit of the operand.
10. The method according to claim 8 , wherein the testing step includes comparing the second variable to the product of the element and the first variable.
11. A device for processing data enabling a first operation on an element by means of an operand, comprising:
means for subjecting an element to a first operation with a given operand, said first operation including updating by a second operation of a first variable if a corresponding bit of the operand has a value 0 and a second variable if the corresponding bit of the operand has a value 1;
means for testing a relationship between a first value derived from the first variable and a second value derived from the second variable; and
means for outputting the second value if said relationship is verified, otherwise outputting an error value.
12. The device according to claim 11 , wherein the first value is the value of the first variable and the second value is the value of the second variable.
13. The device according to claim 11 , wherein the means for testing are applied to the result of the first operation.
14. The device according to claim 11 , further comprising means for obtaining the first value as the result of a first recombination in accordance with the Chinese Remainders Theorem involving the first variable and means for obtaining the second value as the result of a second recombination in accordance with the Chinese Remainders Theorem involving the second variable.
15. The device according to claim 11 , wherein the first operation is a modular exponentiation, the second operation is a modular multiplication, and the operand is an exponent.
16. The device according to claim 15 , wherein the means for testing include means for comparing the product of the first variable and the second variable to a third variable updated by calculating a square regardless of the corresponding bit of the operand.
17. The device according to claim 15 , wherein the means for testing include means for comparing the first variable to the product of the element and the second variable.
18. The device according to claim 11 , wherein the first operation is a multiplication on an elliptical curve and the second operation is an addition on the elliptical curve.
19. The device according to claim 11 , wherein the relationship is independent of the operand.
20. A microcircuit card comprising a device according to claim 11 .