Efficient squaring with loop equalization in arithmetic logic units

Patent metadata

Field	Value
Publication number	US-11961420-B2
Application number	US-202017309933-A
Country	US
Kind code	B2
Filing date	Jan 6, 2020
Priority date	Jan 7, 2019
Publication date	Apr 16, 2024
Grant date	Apr 16, 2024

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, the method comprising:
receiving an input data associated with one or more messages communicated between two or more nodes associated with a common cryptography system;
identifying an N-word number, X=X N−1 . . . X 1 X 0 , associated with the input data;
computing, by a processing device, a square of the N-word number X, by performing 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; and
obtaining, using the computed square of the N-word number X, an output data; and
performing the cryptographic operation comprising at least one of:
obtaining, using the output data, a cryptographic key, and processing, using the cryptographic key to obtain at least one of: (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
or
obtaining, using the output data, a digital signature authentication of the one or more messages.

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 comprising:
a first memory device to store an N-word number X=X N−1 . . . X 1 X 0 , associated with an input data, wherein the input data is associated with one or more messages communicated between two or more nodes associated with a common cryptography system; and
an arithmetic logic unit (ALU) communicatively coupled to the first memory device, wherein the ALU is to:
receive words of the N-word number X,
compute a square of the N-word number X by performing 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 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;
obtain, using the computed square of the N-word number X, an output data; and
perform the cryptographic operation comprising at least one of:
obtain, using the output data, a cryptographic key, and process, using the cryptographic key to obtain at least one of: (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
or
obtain, using the output data, a digital signature authentication of the one or more messages.

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 non-transitory computer-readable medium storing instruction thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation, cause the processing device to:
receive an input data associated with one or more messages communicated between two or more nodes associated with a common cryptography system;
identify an N-word number, X=X N−1 . . . X 1 X 0 , associated with the input data;
compute a square of the N-word number X by performing 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; and
obtain, using the computed square of the N-word number X, an output data, and;
perform the cryptographic operation comprising at least one of:
obtain, using the output data, a cryptographic key, and process, using the cryptographic key to obtain at least one of: (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
or
obtain, using the output data, a digital signature authentication of the one or more messages.

14. The non-transitory 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 non-transitory comput

Assignees

• Cryptography Res Inc

Inventors

• Hamburg Michael Alexander

Classifications

• G09C1/00 Primary

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• G06F7/57

  Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)} · CPC title

• G06F7/728

  using Montgomery reduction · 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