Minimizing information leakage during modular exponentiation and elliptic curve point multiplication

Abstract

Minimizing information leakage during modular exponentiation using random masks is disclosed Minimizing information leakage during elliptic curve point multiplication is disclosed with windowing by using point randomization is disclosed. Elliptic curve point multiplication with windowing calculates and stores multiple points based on the point being multiplied and then processes multiple bits of the multiplier at a time is also disclosed.

1 . A method for minimizing information leakage during modular exponentiation using random masks where b is the base, e is the exponent, and m is the modulus, the method comprising:
 generating at least four random numbers for masking, where the random numbers are r1, r2, r3, and r4, wherein the at least four random numbers are of any bit width and r2 is non-zero;   computing a randomized base (br), where br=b+m*r3;   computing a randomized modulus (mr), where mr=m*r2;   computing a first randomized exponent (e1), where e1=e+m*r1−r4;   computing a second randomized exponent (e2), where e2=r4−r1;   determining a first modular exponentiation, y1, with the randomized base, the randomized modulus, and the first randomized exponent, y1=br{circumflex over ( )}e1 mod mr;   determining a second modular exponentiation, y2 with the randomized base, randomized modulus, and the second randomized exponent, y2=br{circumflex over ( )}e2 mod mr; and   wherein the modulus is prime.   
     
     
         2 . The method of  claim 1 , wherein the results of the two modular exponentiations are used as a modular multiplicative masked share for the modular exponentiation result. 
     
     
         3 . The method of  claim 1 , wherein the results of the two modular exponentiations are combined by computing the modular multiplication of the two results modulo m to obtain the unmasked modular exponentiation result, y=y1*y2 mod m. 
     
     
         4 . A method for minimizing information leakage during elliptic curve point multiplication, the method comprising:
 combining elliptic curve multiplier order randomization and multiplier splitting,   generating at least two random numbers of any bit width (r1 and r2) and used for making;   storing a first random multiplier (d1) as d+n*r1−r2;   storing a first intermediate result point (Y1) as a resulting point from an elliptic curve point multiply with multiplier (d1) and point X;   storing a second intermediate result point (Y2) as a resulting point from an elliptic curve point multiply with multiplier (r2) and point X; and   storing a resulting point Y as the point addition of Y1 and Y2 where Y=Y1+Y2=dX.   
     
     
         5 . A method of performing elliptic curve point randomization on all or a random selection of the window points after any windowed point is used. 
     
     
         6 . The method of  claim 5 , wherein the windowed elliptic curve points are represented in projective form and projective point randomization. 
     
     
         7 . The method of  claim 5 , wherein the windowed elliptic curve points are represented in Jacobian form and Jacobian point randomization is used.