Minimizing information leakage during modular exponentiation and elliptic curve point multiplication

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:

providing a processor,

wherein the processor is configured to:

generate at least four random numbers for masking, where the random numbers are r 1 , r 2 , r 3 , and r 4 ,

wherein the at least four random numbers are of any bit width and r 2 is non-zero;

compute a randomized base (br), where br=b+m*r 3 ;

compute a randomized modulus (mr), where mr=m*r 2 ;

compute a first randomized exponent (e 1 ), where e 1 =e+m*r 1 −r 4 ;

compute a second randomized exponent (e 2 ), where e 2 =r 4 −r 1 ;

determine a first modular exponentiation, y 1 , with the randomized base, the randomized modulus and the first randomized exponent y 1 =br^e 1 mod mr;

determine a second modular exponentiation, y 2 with the randomized base, randomized modulus, and the second randomized exponent, y 2 =br^e 2 mod mr; and

wherein the modulus is prime;

generating the at least four random numbers for masking, where the random numbers are r 1 , r 2 , r 3 , and r 4 , wherein the at least four random numbers are of any bit width and r 2 is non-zero;

computing the randomized base (br), where br=b+m*r 3 ;

computing the randomized modulus (mr), where mr=m*r 2 ;

computing the first randomized exponent (e 1 ), where e 1 =e+m*r 1 −r 4 ;

computing the second randomized exponent (e 2 ), where e 2 =r 4 −r 1 ;

determining the first modular exponentiation, y 1 , with the randomized base, the randomized modulus, and the first randomized exponent, y 1 =br^e 1 mod mr;

determining the second modular exponentiation, y 2 with the randomized base, randomized modulus, and the second randomized exponent, y 2 =br^e 2 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=y 1 *y 2 mod m.

4. A method for minimizing information leakage during elliptic curve point multiplication, the method comprising:

providing a processor,

wherein the processor is configured to:

combine elliptic curve multiplier order randomization and multiplier splitting,

generate at least two random numbers of any bit width (r 1 and r 2 ) and used for making;

store a first random multiplier (d 1 ) as d+n*r 1 −r 2 ;

store a first intermediate result point (Y 1 ) as a resulting point from an elliptic curve point multiply with multiplier (d 1 ) and point X;

store a second intermediate result point (Y 2 ) as a resulting point from an elliptic curve point multiply with multiplier (r 2 ) and point X; and

store a resulting point Y as a point addition of Y 1 and Y 2 where Y=Y 1 +Y 2 =dX;

combining elliptic curve multiplier order randomization and multiplier splitting,

generating the at least two random numbers of any bit width (r 1 and r 2 ) and used for making;

storing the first random multiplier (d 1 ) as d+n*r 1 −r 2 ;

storing the first intermediate result point (Y 1 ) as the resulting point from the elliptic curve point multiply with multiplier (d 1 ) and point X;

storing the second intermediate result point (Y 2 ) as the resulting point from the elliptic curve point multiply with multiplier (r 2 ) and point X; and

storing the resulting point Y as the point addition of Y 1 and Y 2 where Y=Y 1 +Y 2 =dX.