Granted Patent B2

US 11,468,797 · App. 16/911,342 · Granted Oct 11, 2022

Inventors: Ishai Ilani (Dolev, IL); Noam Weber (Moshav Salit, IL)

Assignee: Western Digital Technologies, Inc.

G09C1/00G06F7/523G06F7/721G06F7/722G06F7/724G06F7/728

Abstract

Claims (57)

1. A method for calculating a cryptographic component R 2 mod n for a cryptographic function, where n is a modulo number and R is a constant greater than n, the method comprising:

iteratively performing Montgomery multiplication of a first operand with a second operand to produce an intermediate result, wherein the first operand and the second operand are set to the intermediate result after each iteration;

responsive to a termination condition being met, determining an adjustment parameter indicative of a difference between the intermediate result and the cryptographic component; and

performing Montgomery multiplication of the intermediate result with the adjustment parameter, to calculate the cryptographic component for the cryptographic function.

2. The method of claim 1 , wherein:

the cryptographic component is an integer equal to R 2 mod n;

R is of the form 2 l ;

l is an integer;

n is an integer which is less than R; and

R is coprime with n.

3. The method of claim 1 , wherein the intermediate result, when the termination condition is met, exceeds the cryptographic component.

4. The method of claim 1 , wherein determining the adjustment parameter comprises determining an excess parameter, the excess parameter being indicative of a difference between the intermediate result and the cryptographic component.

5. The method of claim 4 , wherein the adjustment parameter is a function of an inverse of the excess parameter.

6. The method of claim 4 , wherein determining the excess parameter comprises:

determining an integer c for which 2 2 k −c is equal to R; and

setting the excess parameter to be equal to 2 c .

7. The method of claim 4 , wherein the adjustment parameter is equal to the inverse of the excess parameter multiplied by R mod n.

8. The method of claim 4 , wherein determining the excess parameter comprises:

determining an integer c for which 2 2 l b−c is equal to R; and

setting the excess parameter to be equal to 2 c .

9. The method of claim 4 , wherein the adjustment parameter is equal to the inverse of the excess parameter multiplied by R.

10. The method of claim 1 , further comprising determining a base value.

11. The method of claim 10 , wherein the base value is equal to 2R mod n.

12. The method of claim 10 , wherein:

the base value is equal to 2 b R;

b is an integer greater than or equal to 1;

b is less than (2 k −l); and

k is a first integer for which 2 2 k is greater than or equal to R.

13. The method of claim 10 , further comprising:

determining an integer b, where b is greater than or equal to 1, and b is less than (2 k −l);

responsive to b being equal to 1, setting the base value to an integer equal to 2R mod n; and

responsive to b exceeding 1, setting the base value to an integer equal to 2 b R.

14. The method of claim 1 , wherein:

the termination condition is met when the intermediate result is in the form yR mod n; and

y exceeds R.

15. The method of claim 1 , wherein:

the termination condition is the completion of k Montgomery multiplication iterations; and

k is a first integer for which 2 2 k is greater than or equal to R.

16. The method of claim 1 , wherein:

the termination condition is the completion of i Montgomery multiplication iterations; and

i is a first integer for which 2 2 i b is greater than or equal to R.

17. The method of claim 16 , further comprising:

responsive to b being equal to 1, setting the termination condition to be the completion of k Montgomery multiplication iterations, where k is a first integer for which 2 2 k is greater than or equal to R; and

responsive to b exceeding 1, setting the termination condition to be the completion of i Montgomery multiplication iterations, where i is a first integer for which 2 2 i b is greater than or equal to R.

18. An apparatus for calculating a cryptographic component R 2 mod n for a cryptographic function, where n is a modulo number and R is a constant greater than n, the apparatus comprising an arithmetic logic unit configured to:

iteratively perform Montgomery multiplication of a first operand with a second operand to produce an intermediate result, wherein the first operand and the second operand are set to the intermediate result after each iteration;

responsive to a termination condition being met, determine an adjustment parameter indicative of a difference between the intermediate result and the cryptographic component; and

perform Montgomery multiplication of the intermediate result with the adjustment parameter, to calculate the cryptographic component for the cryptographic function.

19. The apparatus of claim 18 , wherein the arithmetic logic unit comprises:

a Montgomery multiplication unit having a first and a second input for receiving a first and a second operand, respectively, and having an output for supplying an intermediate result, the Montgomery multiplication unit configured to perform a Montgomery multiplication function on the first and the second operands to produce the intermediate result; and

a controller for controlling the values of the first input and the second input, the controller configured to perform the steps of,

iteratively setting the first and the second input to the intermediate multiplication result, until a termination condition is met; and

responsive to the termination condition being met, setting the first input to the intermediate result and setting the second input to an adjustment parameter.

20. An apparatus for calculating a cryptographic component R 2 mod n for a cryptographic function, where n is a modulo number and R is a constant greater than n, the apparatus comprising:

means for iteratively performing Montgomery multiplication of a first operand with a second operand to produce an intermediate result, wherein the first operand and the second operand are set to the intermediate result after each iteration;

means for determining, responsive to a termination condition being met, an adjustment parameter indicative of a difference between the intermediate result and the cryptographic component; and

means for performing Montgomery multiplication of the intermediate result with the adjustment parameter, to calculate the cryptographic component for the cryptographic function.

Assignments (10)