Efficient squaring with loop equalization in arithmetic logic units

Patent metadata

Field	Value
Publication number	US-2022076594-A1
Application number	US-202017309933-A
Country	US
Kind code	A1
Filing date	Jan 6, 2020
Priority date	Jan 7, 2019
Publication date	Mar 10, 2022
Grant date	—

Abstract

Aspects of the present disclosure describe a method and a system to support execution of the method to perform a cryptographic operation involving identifying an N-word number, X=XN−1 . . . X1Xo, to be squared, performing a first loop comprising M first loop iterations, wherein M is a largest integer not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product Xa*Xb of a word Xa and a word Xb, wherein a+b=2j+m, j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations.

First claim

What is claimed is:

1 . A method to perform a cryptographic operation involving squaring an N-word number, X=X N−1 . . . X 1 X 0 , the method comprising:
performing, by a processing device, a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product X a *X b of a word X a and a word X b , wherein a+b=2j+m, j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations.

2 . The method of claim 1 , wherein the iteration m of the second loop that is within the iteration j of the first loop further comprises:
multiplying the product X a *X b by f wherein f=1 if a is equal to b and f=2 if a is not equal to b, adding a carry value stored during the iteration m−1 of the second loop; adding an accumulator value A a+b stored during the iteration j−1 of the first loop; storing a high word of a resulting number as a new carry; and storing a low word of the resulting number as the accumulator A a+b .

3 . The method of claim 2 , further comprising:
determining that the iteration m of the second loop is a final iteration of the second loop; and storing the new carry value as an accumulator value A a+b+1 .

4 . The method of claim 3 , wherein the word X a is retrieved from a first memory device and the accumulator value A a+b is stored in a second memory device.

5 . The method of claim 3 , wherein the carry value is stored in a flip-flop memory.

6 . The method of claim 3 , further comprising, at the completion of the first loop, reading the stored accumulator value A l as a word l of X 2 :
X 2 =( X N−1 . . . X 1 X 0 )*( X N−1 . . . X 1 X 0 )= A 2N−1 . . . A 1 A 0 ;

7 . The method of claim 1 , wherein the number of second loop iterations is N, if N is odd, and N+1, if N is even.

8 . The method of claim 1 , further comprising performing at least one Montgomery reduction on results of each first loop iteration.

9 . The method of claim 1 , further comprising performing at least one Montgomery reduction on results of each second loop iteration.

10 . A system to perform a cryptographic operation involving squaring an N-word number, X=X N−1 . . . X 1 X 0 , the system comprising:
a first memory device to store the N-word number X; and an arithmetic logic unit (ALU) coupled to the first memory device to receive words of the N-word number X, the ALU to perform a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein during an iteration m of the second loop that is within an iteration j of the first loop the ALU is to compute a product X a *X b of a word X b , and a word X b , wherein a+b=2j+m, wherein j>0 and m>0, and wherein all second loops have an equal number of second loop iterations.

11 . The system of claim 10 , further comprising a second memory device coupled to the ALU and a third memory device coupled to the ALU, and wherein during the iteration m of the second loop that is within the iteration j of the first loop the ALU is further to:
retrieve, from the second memory device, an accumulator value Act-kb stored therein during the iteration j−1 of the first loop; retrieve, from the third memory device, a carry value stored therein during the iteration m−1 of the second loop; multiply the product X a *X b by f wherein f=1 if a is equal to b and f=2 if a is not equal to b, add the carry value; add the accumulator value A a+b ; determine a low word and a high word of a resulting number; store, in the second memory device, the low word of the resulting number as an updated accumulator value A a+b ; and store, in the third memory device, the high word of the resulting number as a new carry value.

12 . The system of claim 11 , wherein the second memory device is a scratchpad memory device and the third memory device is a flip-flop memory device.

13 . A computer-readable medium storing instruction thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation, cause the processing device to square an N-word number, X=X N−1 . . . X 1 X 0 , by causing the processing device to:
perform a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product X a *X b of a word X a and a word X b , wherein a+b=2j+m, wherein j>0 and m>0, and wherein all second loops have an equal number of second loop iterations.

14 . The computer-readable medium of claim 13 , wherein the iteration m of the second loop that is within the iteration j of the first loop further comprises:
multiplying the product X a *X b by f, wherein f=1 if a is equal to b and f=2 if a is not equal to b, adding a carry value stored during the iteration m−1 of the second loop; adding an accumulator value A a+b stored during the iteration j−1 of the first loop; storing a high word of a resulting number as a new carry value; and storing a low word of the resulting number as a new accumulator value A a+b .

15 . The computer-readable medium of claim 14 , further comprising:
determining that the iteration m of the second loop is a final iteration of the second loop; and storing the new carry value as an accumulator value A a+b+1 .

16 . The computer-readable medium of claim 15 , wherein the word X a is retrieved from a first memory device and the accumulator value A a+b is stored in a second memory device.

17 . The computer-readable medium of claim 15 , wherein the carry value is stored in a flip-flop memory.

18 . The computer-readable medium of claim 15 , further comprising, at the completion of the first loop, reading the stored accumulator value A l as a word l of X 2 :
X 2 =( X N−1 . . . X 1 X 0 )*( X N−1 . . . X 1 X 0 )= A 2N−1 . . . A 1 A 0 ;

19 . The computer-readable medium of claim 13 , wherein the number of second loop iterations is N, if N is odd, and N+1, if N is even.

20 . The computer-readable medium of claim 13 , further comprising performing at least one Montgomery reduction on results of each first loop iteration or performing at least one Montgomery reduction on results of each second loop iteration.

Assignees

• Cryptography Res Inc

Inventors

• Hamburg Michael Alexander

Classifications

• G06F7/728

  using Montgomery reduction · CPC title

• G06F7/723

  Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title

• H04L9/3013 Primary

  involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems · CPC title

• H04L9/302

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title