This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
A fault attack introduces an error during cryptographic calculations with the intent to obtain one or more bits of a cryptographic secret, such as a private decryption key. Practical ways to mount fault attacks are surveyed in “The Sorcerer's Apprentice Guide to Fault Attacks” by Nagai Bar-El, Hamid Choukri, David Naccache, Michael Tunstall, and Claire Whelan, Proceedings of the IEEE, 94(2):370-382, 2006 (Earlier version in Proc. of FDTC 2004) and in “A Survey On Fault Attacks” by Christophe Giraud and Hugues Thiebeauld, in J.-J. Quisquater, P. Paradinas, Y. Deswarte, and A. A. El Kalam, editors, Smart Card Research and Advanced Applications VI (CARDIS 2004), pages 159-176, Kluwer, 2004.
A RSA (Rivest-Shamir-Adleman) exponentiation consists in raising x to the power of d, on input x in Z/NZ and private exponent d, where Z/NZ is a ring of integers modulo N and N=pq is the product of two large primes. Adi Shamir provided an elegant countermeasure against fault attacks in “How to Check Modular Exponentiation”, presented at the rump session of EUROCRYPT'97, Konstanz, Germany, May 13, 1997. The countermeasure is:                1. Compute y′=xd mod rN for a (small) random integer r,        2. Compute z=xd mod r,        3. Check whether y′≡z (mod r), and                    if so, output y=y′ mod N;            if not, return “error”.                        
Typically, r is a 64-bit integer. The correctness of Shamir's method is an application of the Chinese remainder theorem (CRT). When the calculations are correct, it is obvious that y′≡y (mod N) and y′≡z (mod r). In the presence of faults, the probability that y′≡z (mod r) is about 1/r. When r is a 64-bit value, this means that a fault is undetected with probability of roughly 2−64. Larger values for r imply a higher detection probability at the expense of more demanding computations.
Shamir's method can be adapted to protect RSA exponentiations when evaluated in CRT mode; i.e, when y=xd mod N is evaluated from xd mod p and xd mod q. Further generalizations and extensions of Shamir's countermeasure are discussed in “Secure Evaluation of Modular Functions” by Marc Joye, Pascal Paillier, and Sung-Ming Yen, in R. J. Hwang and C. K. Wu, editors, 2001 International Workshop on Cryptology and Network Security, pages 227-229, Taipei, Taiwan, September 2001.
David Vigilant proposed an alternative solution in “RSA With CRT: A New Cost-Effective Solution to Thwart Fault Attacks”, in E. Oswald and P. Rohatgi, editors, Cryptographic Hardware and Embedded Systems—CHES 2008, volume 5154 of Lecture Notes in Computer Science, pages 230-145, Springer, 2008. This solution is to:                1. Form X=CRT(x (mod N), 1+r (mod r2)) for a (small) random integer r,        2. Compute y′=Xd mod r2N;        3. Check whether y′≡1+dr (mod r2), and                    if so, output y=y′ mod N;            if not, return “error”.                        
In step 1, CRT denotes an application of the Chinese remainder theorem; namely the so-obtained X satisfies X≡x (mod N) and X≡1+r (mod r2). Hence, we have y′≡xd (mod N) and y′≡(1+r)d (mod r2) when the computations are not faulty. The correctness of step 3 follows from the binomial theorem. We have
                    (                  1          +          r                )            d        =                  ∑                  0          ≤          k          ≤          d                    ⁢                        (                                                    d                                                                    k                                              )                ⁢                  1                      d            -            k                          ⁢                  r          k                      ,where
         (                            d                                      k                      )  denotes the binomial coefficient. Reducing this identity modulo r2 gives (1+r)d≡1+dr (mod r2) and thus y′≡1+dr (mod r2) when the computations are not faulty. The probability that a fault is undetected is expected to be about 1/r2. As a result, a 32-bit value for r in Vigilant's method should provide the same security level as a 64-bit value for r in Shamir's method.
Vigilant's method presents a couple of advantages over Shamir's method. In particular, it trades the exponentiation z=xd mod r against the multiplication 1+dr mod r2, which is much faster, although it will be appreciated that the evaluation of z in Shamir's method can be sped up as xd mod φ(r) mod r (where φ denotes Euler's totient function), provided that the value of φ(r) is known. In addition, Vigilant's method applies to RSA in CRT mode.
The description of Shamir's and Vigilant's countermeasures have been done with their application to RSA. However, it will be appreciated that elliptic curve cryptography (ECC) is an interesting alternative to RSA because the keys are much shorter for a same conjectured security level.
In ECC, given a point P on an elliptic curve E and an integer k, the basic operation consists in computing the scalar multiplication kP, that is, P+P+ . . . +P (k times) where + denotes the group operation on E. A goal of an attacker is to recover the value of k (or a part thereof) by inducing faults.
While Shamir's countermeasure generalizes to elliptic curve scalar multiplication (see, e.g. Johannes Blömer, Martin Otto, and Jean-Pierre Seifert: “Sign Change Fault Attacks on Elliptic Curve Cryptosystems”. In L. Breveglieri, I. Koren, D. Naccache, and J.-P. Seifert, editors, Fault Diagnosis and Tolerance in Cryptography—FDTC 2006, volume 4236 of Lecture Notes in Computer Science, pages 36-52. Springer-Verlag, 2006.), Vigilant's method does not readily lend itself to a generalization to elliptic curve scalar multiplication since there is no equivalent to the binomial theorem.
It can therefore be appreciated that there is a need for a solution that provides an alternative countermeasure against fault attacks on ECC. This invention provides such a solution.