System and method to improve efficiency in multiplicationladder-based cryptographic operations

Patent metadata

Field	Value
Publication number	US-2023254145-A1
Application number	US-202117916979-A
Country	US
Kind code	A1
Filing date	Apr 14, 2021
Priority date	Apr 14, 2020
Publication date	Aug 10, 2023
Grant date	—

Abstract

Aspects of the present disclosure involve a method to perform a cryptographic operation using a plurality of iterations, each of the plurality of iterations comprising: loading a first number corresponding to a difference between a first component of a first input working point on an elliptic curve and a first component of a second input working point on the elliptic curve, loading a second number corresponding to a difference between the first component of the first input working point and a first component of a third input working point on the elliptic curve, and determining a third number corresponding to a difference between a first component of a first output working point on the elliptic curve and the first component of the second input working point, wherein determining the third number comprises squaring a product of the first number and a first function of the second number.

First claim

What is claimed is:

1 . A method to perform a cryptographic operation, the method comprising:
performing, by a processing device, a plurality of iterations, wherein each of the plurality of iterations comprises: loading a first number corresponding to a difference between a first component of a first input working point on an elliptic curve and a first component of a second input working point on the elliptic curve; loading a second number corresponding to a difference between the first component of the first input working point and a first component of a third input working point on the elliptic curve; and determining a third number corresponding to a difference between a first component of a first output working point on the elliptic curve and the first component of the second input working point, wherein determining the third number comprises squaring a product of the first number and a first function of the second number.

2 . The method of claim 1 , wherein the first function of the second number is a square of the second number.

3 . The method of claim 1 , wherein determining the third number further comprises:
rescaling a second component of the second input working point by at least a second function of the second number; and adding the rescaled second component of the second input working point to the squared product of the first number and the first function of the second number.

4 . The method of claim 3 , wherein the second function is a cubic function of the second number.

5 . The method of claim 1 , further comprising:
determining a fourth number corresponding to a difference between a first component of a second output working point on the elliptic curve and the first component of the second input working point, wherein determining the fourth number comprises: determining a fifth number corresponding to a second component of the first input working point; computing a square of the fifth number; and multiplying the square of the fifth number by a function of the fifth number and the second number.

6 . The method of claim 5 , wherein determining the fifth number comprises using an input representation of a slope of a line passing through the second input working point and the third input working point.

7 . The method of claim 6 , further comprising:
determining a sixth number representing a rescaled value of a second component of the second input working point, by rescaling the second component of the second input working point by a cube of the fifth number and by a cube of the second number.

8 . The method of claim 7 , further comprising:
storing the third number in a first register; storing the fourth number in a second register; and storing the sixth number in a third register, wherein the first register, the second register, and the third register are input registers for a subsequent iteration of the plurality of iterations.

9 . The method of claim 6 , further comprising:
determining an output representation of a slope of a line passing through the second input working point and the second output working point; and storing the determined output representation in a register.

10 . The method of claim 1 , wherein, the first number is loaded from 1) a first register, if a cryptographic key bit corresponding to a respective iteration of the plurality of iterations has a first bit value, or 2) a second register, if the cryptographic key bit has a second bit value.

11 . The method of claim 1 , wherein the cryptographic operation is a multiplication operation to multiply a base point by a cryptographic key, and wherein the first input working point and the second input working point are selected based on a value of a cryptographic key bit corresponding to a respective iteration of the plurality of iterations.

12 . The method of claim 1 , further comprising:
determining a fourth number corresponding to a difference between the first component of the first output working point on the elliptic curve and a first component of a second output working point, wherein determining the fourth number comprises adding, to the third number, a rescaled second component of the third input working point.

13 . The method of claim 12 , wherein the rescaled second component of the third input working point is determined by multiplying the second component of the third input working point by a second function of a combination comprising the first number, a second component of the second input working point, and a representation of a slope of a line passing through the second input working point and the third input working point.

14 . The method of claim 13 , wherein the second function is a cubic function of the combination.

15 . A system to perform a cryptographic operation, the system comprising:
a memory device; and a processing device coupled to the memory device to perform a plurality of iterations, wherein each of the plurality of iterations comprises: loading a first number corresponding to a difference between a first component of a first input working point on an elliptic curve and a first component of a second input working point on the elliptic curve; loading a second number corresponding to a difference between the first component of the first input working point and a first component of a third input working point on the elliptic curve; and determining a third number corresponding to a difference between a first component of a first output working point on the elliptic curve and the first component of the second input working point, wherein to determine the third number the processing device is to square a product of the first number and a first function of the second number.

16 . The system of claim 15 , wherein the first function is a square of the second number.

17 . The system of claim 15 , wherein each of the plurality of iterations further comprises:
rescaling a second component of the second input working point by at least a second function of the second number; and adding the rescaled second component of the second input working point to the squared product of the first number and the first function of the second number.

18 . A computer-readable medium storing instructions thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation, cause the processing device to perform a plurality of iterations, wherein each of the plurality of iterations comprises:
loading a first number corresponding to a difference between a first component of a first input working point on an elliptic curve and a first component of a second input working point on the elliptic curve; loading a second number corresponding to a difference between the first component of the first input working point and a first component of a third input working point on the elliptic curve; and determining a third number corresponding to a difference between a first component of a first output working point on the elliptic curve and the first component of the second input working point, wherein determining the third number comprises squaring a product of the first number and a first function of the second number.

19 . The computer-readable medium of claim 18 , wherein the first function is a square of the second number.

20 . The computer-readable medium of claim 18 , wherein each of the plurality of iterations further comprises:
rescaling a second component of the second input working point by at least a second function of the second

Assignees

• Cryptography Res Inc

Inventors

• Hamburg Michael Alexander

Classifications

• H04L9/3066 Primary

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