Fault-resistant calculcations on elliptic curves
View Patent ↗Means for checking the correctness of a cryptographic operation on an elliptic curve E(Z/pZ), including fault-resistant computation of Q=kP on elliptic curve E(Z/pZ). Elliptic curve E^(Z/pr 2 Z)≡E(Z/pZ)×E(Z/r 2 Z) is given by Chinese remaindering and where r is an integer. A point P^=CRT(P (mod p), R (mod r 2 )) is formed in E^(Z/pr 2 Z); P^ reduces to P in E(Z/pZ), and to R in E 1 (Z/r 2 Z). Q^=kP^ in E^(Z/pr 2 Z) is computed ( 130 ). It is then verified whether Q^≡kR (mod r 2 ) in E 1 (Z/r 2 Z), and if so, Q=Q^ mod p is output, whereas “error” is returned if this is not the case. Also provided are an apparatus and a computer program product.
1. A method for checking the correctness of a cryptographic operation on a first elliptic curve E(Z/pZ), the method being resistant against fault attacks and comprising the steps of:
obtaining, by a processor, a third elliptic curve E^(Z/pr 2 Z)≡E(Z/pZ)×E(Z/r 2 Z) given by Chinese remaindering from the first elliptic curve E(Z/pZ) and a second elliptic curve E(Z/r 2 Z), where r is an integer;
performing the cryptographic operation on E^(Z/pr 2 Z) to obtain a first result;
performing the cryptographic operation on E 1 (Z/r 2 Z), where E 1 (Z/r 2 Z) denotes the subset of points in E(Z/r 2 Z) that reduce modulo r to the identity element on E(Z/rZ), to obtain a second result;
verifying that the first result and the second result are equal in E 1 (Z/r 2 Z); and if this is the case;
outputting the first result of the operation in E^(Z/pr 2 Z) reduced modulo p.
2. A method according to claim 1 , wherein the cryptographic operation is a scalar multiplication in E(Z/pZ), for fault-resistant computation of Q=kP on elliptic curve E(Z/pZ), the method comprising the steps of:
forming a point P^=CRT(P (mod p), R (mod r 2 )) in E^(Z/pr 2 Z) such that P^ reduces to P in E(Z/pZ), and to R in E 1 (Z/r 2 Z), where CRT denotes the Chinese remaindering method;
computing Q^=kP^ in E^(Z/pr 2 Z);
verifying whether Q^≡kR (mod r 2 ) in E 1 (Z/r 2 Z) and outputting Q=Q^ mod p only if this the case.
3. The method of claim 1 , wherein the integer r is chosen randomly.
4. The method of claim 1 , wherein the integer r has a predetermined value.
5. The method of claim 3 , wherein the integer r is a prime.
6. The method of claim 2 , wherein the point R in E 1 (Z/r 2 Z) is chosen randomly.
7. The method of claim 1 , wherein the elliptic curve is represented as an Edwards curve or as a Jacobi curve.
8. An apparatus for checking the correctness of a cryptographic operation on a first elliptic curve E(Z/pZ), the apparatus being resistant against fault attacks and comprising a processor with an associated non-transitory storage medium and configured to:
obtain a third elliptic curve E^(Z/pr 2 Z)≡E(Z/pZ)×E(Z/r 2 Z) given by Chinese remaindering from the first elliptic curve E(Z/pZ) and a second elliptic curve E(Z/r 2 Z), where r is an integer;
perform the cryptographic operation on E^(Z/pr 2 Z) to obtain a first result;
perform the cryptographic operation on E 1 (Z/r 2 Z), where E 1 (Z/r 2 Z) denotes the subset of points in E(Z/r 2 Z) that reduce modulo r to the identity element on E(Z/rZ), to obtain a second result;
verify that the first result and the second result are equal in E 1 (Z/r 2 Z); and if this is the case;
output the first result of the operation in E^(Z/pr 2 Z) reduced modulo p.
9. The apparatus according to claim 8 , wherein the cryptographic operation is a scalar multiplication in E(Z/pZ), for fault-resistant computation of Q=kP on an elliptic curve E(Z/pZ), the processor further being configured to:
form a point P^=CRT(P (mod p), R (mod r 2 )) in E^(Z/pr 2 Z) such that P^ reduces to P in E(Z/pZ), and to R in E 1 (Z/r 2 Z), where CRT denotes the Chinese remaindering method;
compute Q^=kP^ in E^(Z/pr 2 Z); and
verify whether Q^≡kR (mod r 2 ) in E 1 (Z/r 2 Z) and outputting Q=Q^ mod p only if this the case.
10. A computer program product stored on a non-transitory computer readable storage medium embodying instructions that, when executed by a processor, performs the method of claim 1 .