Minimizing information leakage during modular exponentiation and elliptic curve point multiplication
AssigneeThe Athena Group, Inc.
InventorSTUART AUDLEY
Life of this patent
Estimating the term…
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.
Claims7
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.
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.
A method of performing elliptic curve point randomization on all or a random selection of the window points after any windowed point is used.
Dependencies are inferred from the claim text.