Method and apparatus for protecting public key schemes from timing and fault attacks

• US 5,991,415 A
• Filed: 05/12/1997
• Issued: 11/23/1999
• Est. Priority Date: 05/12/1997
• Status: Expired due to Term

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Shamir, Adi
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/854,464
• Time in Patent Office: 925 Days
• Field of Search: 380/9, 380/30, 380/49, 380/50, 380/59, 380/28, 380/1, 380/2
• US Class Current: 380/30
• CPC Class Codes: G06F 2207/7247 Modulo masking, e.g. A**e mod (n*r)
• CPC Class Codes: G06F 2207/7257 Random modification not requiring correction
• CPC Class Codes: G06F 2207/7271 Fault verification, e.g. comparing two values which should be the same, unless a computational fault occurred
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/004 for fault attacks
• CPC Class Codes: H04L 9/005 for timing attacks
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

Improved methods and apparatus are provided for protecting public key schemes based on modular exponentiation (including RSA and Diffie-Hellman) from indirect cryptanalytic techniques such as timing and fault attacks. Known methods for making the implementation of number-theoretic schemes resistant to such attacks typically double their running time, whereas the novel methods and apparatus described in this patent add only negligible overhead. This improvement is particularly significant in smart card and software-based implementations, in which the modular exponentiation operation is quite slow, and doubling its time may be an unacceptable solution.

Claims

1. In a method of implementing public key schemes containing the non-CRT form of the modular exponentiation operation x d (mod n), the improvement comprising the steps of:

computing or storing the computed value of t=phi(n), where phi is Euler'"'"'s totient function of the modulus n;

selecting some secret integer i; and

replacing the computation of x d (mod n) by the computation of x (d+i*t) (mod n);

thereby increasing public key scheme resistance to timing attacks without a twofold slowdown in computation time.

2. In the method of claim 1, the further improvement where i is chosen as a random number in the range for some k.

3. In the method of claim 2, the further improvement where k=32.

4. In a method of implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=p*q, the improvement comprising the steps of:

selecting some secret integer j;

computing v_-- 1=x (mod j*p), v_-- 2=x (mod j*q), d_-- 1=d (mod phi(j*p)), d_-- 2=d (mod phi(j*q)), w_-- 1=v_-- 1 d_-- 1 (mod j*p), and w_-- 2=v_-- 2 d_-- 2 (mod j*q);

aborting the computation if w_-- 1 and w_-- 2 are not equal modulo j; and

otherwise, computing y_-- 1=w_-- 1 (mod p), y_-- 2=w_-- 2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n);

thereby increasing public key scheme resistance to timing and fault attacks without a twofold slowdown in computation time.

5. In the method of claim 4, the further improvement where j is chosen as a prime number.

6. In the method of claim 5, the further improvement where k=32.

7. In the method of claim 4, the further improvement where j is chosen as a random number in the range for some k.

8. In a method of implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=p*q, the improvement comprising the steps of:

selecting two secret integers j_-- 1 and j_-- 2;

computing v_-- 1=x (mod j_-- 1*p), v_-- 2=x (mod j_-- 2*q), d_-- 1=d (mod phi(j_-- 1*p)), d_-- 2=d (mod phi(j_-- 2*q)), w_-- 1=v_-- 1 d_-- 1 (mod j_-- 1*p), and w_-- 2=v_-- 2 d_-- 2 (mod j_-- 2*q);

computing v_-- 3=x (mod j_--

     1), v_-- 4=x (mod j_--

     2), d_-- 3=d (mod j_--

     1), d_-- 4=d (mod j_--

     2), w_-- 3=v_-- 3 d_-- 3 (mod j_--

     1), and w_-- 4=v_-- 4 d_-- 4 (mod j_--

     2);

aborting the computation if w_-- 3 is not equal to w_-- 1 modulo j_-- 1, or if w_-- 4 is not equal to w_-- 2 modulo j_-- 2; and

otherwise, computing y_-- 1=w_-- 1 (mod p), y_-- 2=w_-- 2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n);

thereby increasing public key scheme resistance to timing and fault attacks without a twofold slowdown in computation time.

9. In the method of claim 8, the further improvement where j_-- 1 and j_-- 2 are prime numbers.

10. In the method of claim 8, the further improvement where j_-- 1 and j_-- 2 are chosen as random numbers in the range for some k.

11. In the method of claim 10, the further improvement where k=32.

12. In an apparatus for implementing public key schemes containing the non-CRT form of the modular exponentiation operation x d (mod n), the improvement comprising:

means for computing or storing the computed value of t=phi(n), where phi is Euler'"'"'s totient function of the modulus n;

means for selecting some secret integer i; and

means for replacing the computation of x d (mod n) by the computation of x (d+i*t) (mod n);

thereby increasing public key scheme resistance to timing attacks without a twofold slowdown in computation time.

13. In the apparatus according to claim 12, the improvement where i is chosen as a random number in the range for some k.

14. In the apparatus according to claim 13, the further improvement where k=32.

15. In an apparatus for implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=p*q, the improvement comprising:

means for selecting some secret integer j;

means for computing v_-- 1=x (mod j*p), v_-- 2=x (mod j*q), d_-- 1=d (mod phi(j*p)), d_-- 2=d (mod phi(j*q)), w_-- 1=v_-- 1 d_-- 1 (mod j*p), and w_-- 2=v_-- 2 d_-- 2 (mod j*q);

means for aborting the computation if w_-- 1 and w_-- 2 are not equal modulo j; and

otherwise, means for computing y_-- 1=w_-- 1 (mod p), y_-- 2=w_-- 2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n);

thereby increasing public key scheme resistance to timing and fault attacks without a twofold slowdown in computation time.

16. In the apparatus according to claim 15, the further improvement where j is chosen as a prime number.

17. In the apparatus according to claim 16, the further improvement where k=32.

18. In the apparatus according to claim 15, the further improvement where j is chosen as a random number in the range for some k.

19. In an apparatus for implementing public key schemes containing the CRT form of the modular exponentiation operation x d (mod n) where n=p*q, the improvement comprising:

means for selecting two secret integers j_-- 1 and j_-- 2;

means for computing v_-- 1=x (mod j_-- 1*p), v_-- 2=x (mod j_-- 2*q), d_-- 1=d (mod phi(j_-- 1*p)), d_-- 2=d (mod phi(j_-- 2*q)), w_-- 1=v_-- 1 d_-- 1 (mod j_-- 1*p), and w_-- 2=v_-- 2 d_-- 2 (mod j_-- 2*q);

means for computing v_-- 3=x (mod j_--

     1), v_-- 4=x (mod j_--

     2), d_-- 3=d (mod j_--

     1), d_-- 4=d (mod j_--

     2), w_-- 3=v_-- 3 d_-- 3 (mod j_--

     1), and w_-- 4=v_-- 4 d_-- 4 (mod j_--

     2);

means for aborting the computation if w_-- 3 is not equal to w_-- 1 modulo j_-- 1, or if w_-- 4 is not equal to w_-- 2 modulo j_-- 2; and

otherwise, means for computing y_-- 1=w_-- 1 (mod p), y_-- 2=w_-- 2 (mod q), and combining them by the Chinese Remainder Theorem to obtain the result of x d (mod n);

thereby increasing public key scheme resistance to timing and fault attacks without a twofold slowdown in computation time.

20. In the apparatus according to claim 19, the further improvement where j_-- 1 and j_-- 2 are prime numbers.

21. In the apparatus according to claim 19, the further improvement where j_-- 1 and j_-- 2 are chosen as random numbers in the range for some k.

22. In the apparatus according to claim 21, the further improvement where k=32.