System and method for one-time Chinese-Remainder-Theorem exponentiation for cryptographic algorythms
A system, method and computer-readable storage medium with instructions for protecting an electronic device against fault attack. The technology includes operating the electronic device to determine two half-size exponents, dp and dq, from the exponent d; to split the base m into two sub-bases mp and mq determined from the base m; and to iteratively compute a decryption result S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration I′. Other systems and methods are disclosed.
1. A method for operating a cryptography apparatus to perform a decryption operation having an exponentiation operation X, the method protecting the apparatus from revealing information in regard to the exponentiation operation X when the operation is exposed to a fault attack while being executed on the cryptography apparatus, the method comprising producing a result equivalent to the exponentiation by:
receiving, on the cryptography apparatus, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=m d mod n;
determining two half-size exponents dp and dq from the exponent d;
splitting the base m into two sub-bases mp and mq determined from the base m;
iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i;
returning as the value S the final value of the accumulator A; and completing the cryptographic operation using the value S obtained from the operation.
2. The method of claim 1 wherein the two half-sized exponents dp and dq are determined from dp=d mod (p−1)and dq=d mod (q−1) where p and q are prime numbers such that n=pq.
3. The method of claim 1 wherein:
mp= 1+ q*iq *( m− 1)mod n ; and
mq= 1+(1− q*iq )*( m− 1)mod n wherein
iq=q −1 mod p.
4. The method of claim 1 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1&& dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
5. The method of claim 2 wherein:
mp= 1+ q*iq *( m− 1)mod n ; and
mq= 1+(1− q*iq )*( m− 1)mod n wherein
iq=q −1 mod p.
6. The method of claim 2 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
7. The method of claim 3 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
8. The method of claim 5 wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
9. An electronic device protected from fault attack and comprising:
a central processing unit, memory, and an instruction storage wherein the instruction storage contains instructions to cause the central processing unit to perform:
receiving, on by the central processing unit of the electronic device, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=m d mod n;
determining two half-size exponents dp and dq from the exponent d;
splitting the base m into two sub-bases mp and mq determined from the base m;
iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i;
returning as the value S the final value of the accumulator A; and completing the cryptographic operation using the value S obtained from the operation.
10. The electronic device protected from fault attack of claim 9 , wherein the two half-sized exponents dp and dq are determined from dp=d mod (p−1) and dq=d mod (q−1) where p and q are prime numbers such that n=pq.
11. The electronic device protected from fault attack of claim 9 , wherein:
mp= 1+ q*iq *( m− 1)mod n ; and
mq= 1+(1− q*iq )*( m− 1)mod n wherein
iq=q −1 mod p.
12. The electronic device protected from fault attack of claim 10 , wherein:
mp= 1+ q*iq *( m− 1)mod n ; and
mq= 1+(1− q*iq )*( m− 1)mod n wherein
iq=q −1 mod p.
13. The electronic device protected from fault attack of claim 9 , wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
14. The electronic device protected from fault attack of claim 10 , wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
15. The electronic device protected from fault attack of claim 11 , wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.
16. The electronic device protected from fault attack of claim 12 , wherein dp and dq have bits indexed from 0 to k and the iteration is an iteration from 0 to k performing the calculations:
A=A*A mod n
IF (dp i =0 && dq i 0)
A=A* 1 mod n
IF (dp i =1 && dq i 0)
A=A*mp mod n
IF (dp i =0 && dq i 1)
A=A*mq mod n
IF (dp i =1 && dq i 1)
A=A*m mod n.