Granted Patent B2

US 11,508,263 · App. 16/911,356 · Granted Nov 22, 2022

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

Assignee: Western Digital Technologies, Inc.

G09C1/00G06F7/722G06F7/728

Abstract

Claims (55)

1. A method for calculating, using a processor, 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:

setting a start value to be equal to R mod n;

performing b iterations of a shift and subtract operation on the start value to produce a base value, wherein the start value is set to be equal to the base value after each iteration;

setting a multiplication operand to be equal to the base value; and

performing k iterations of a Montgomery modular multiplication of the multiplication operand with the multiplication operand to produce an intermediate result, wherein the multiplication operand is set to be equal to the intermediate result after each iteration;

wherein the shift and subtract operation comprises determining a shifted start value which is equivalent to the start value multiplied by two, and subtracting n from the shifted start value if the shifted start value is greater than or equal to n.

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 determining a shifted start value which is equivalent to the start value multiplied by two comprises performing a single bit left shift of the start value.

4. The method of claim 1 , further comprising setting the value of b based on the value of R.

5. The method of claim 1 , further comprising setting the value of b to be equal to the lowest integer value for which a single iteration of the Montgomery multiplication consumes less processing time than b iterations of the shift and subtract operation.

6. The method of claim 1 , further comprising setting the value of k based on the value of b.

7. The method of claim 6 , wherein the value of k is set based on the value of b to satisfy the relationship 2 2 k b−1 <R<2 2 k b+1 .

8. The method of claim 6 , wherein the value of k is set based on the value of b to satisfy the equation R=2 2 k b .

9. The method of claim 1 , further comprising setting the value of b based on a calculation of the power consumed to calculate the cryptographic component, or based on the time taken to calculate the cryptographic component.

10. The method of claim 1 , further comprising:

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.

11. The method of claim 10 , 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.

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

13. The method of claim 10 , wherein determining the excess parameter comprises:

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

setting the excess parameter to be equal to 2 c .

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

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

16. 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 a processor configured to:

set a start value to be equal to R mod n;

perform b iterations of a shift and subtract operation on the start value to produce a base value, wherein the start value is set to be equal to the base value after each iteration;

set a multiplication operand to be equal to the base value; and

perform k iterations of a Montgomery modular multiplication of the multiplication operand with the multiplication operand to produce an intermediate result, wherein the multiplication operand is set to be equal to the intermediate result after each iteration;

wherein the shift and subtract operation comprises determining a shifted start value which is equivalent to the start value multiplied by two, and subtracting n from the shifted start value if the shifted start value is greater than or equal to n.

17. The apparatus of claim 16 , wherein the processor is further configured to:

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.

18. The apparatus of claim 17 , wherein the processor comprises:

a shift and subtract unit having a first input, a second input, and an output;

a Montgomery multiplication unit having a first input and a second input for receiving a first operand and a second operand, respectively, and having an output for supplying an intermediate result, the Montgomery multiplication unit configured to perform a Montgomery multiplication of the first operand with the second operand 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,

setting the input to the shift and subtract unit to be equal to a start value,

iteratively setting the input to the shift and subtract unit to be equal to the output of the shift and subtract unit, for b shift and subtract operation iterations,

setting the first input and the second input of the Montgomery multiplication unit to be equal to the output of the shift and subtract unit, and

iteratively setting the first input and the second input to the intermediate multiplication result, for k Montgomery multiplication iterations.

19. The apparatus of claim 18 , wherein the controller is further configured to perform the steps of:

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.

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 setting a start value to be equal to R mod n;

means for performing b iterations of a shift and subtract operation on the start value to produce a base value, wherein the start value is set to be equal to the base value after each iteration;

means for setting a multiplication operand to be equal to the base value; and

means for performing k iterations of Montgomery modular multiplication of the multiplication operand with the multiplication operand to produce an intermediate result, wherein the multiplication operand is set to be equal to the intermediate result after each iteration;

wherein the shift and subtract operation comprises determining a shifted start value which is equivalent to the start value multiplied by two, and subtracting n from the shifted start value if the shifted start value is greater than or equal to n.

Assignments (10)