Back to results
US 8,027,467 B2Granted
Method for elliptic curve point multiplication
AssigneeWired Connections LLC
InventorsBodo Möller, Tsuyoshi Takagi
Life of this patent
Estimating the term…
Abstract
An elliptic curve multiplication method comprises three stages. In the first stage, randomly selected point representations are stored in variables. In the second stage, a right-to-left loop is executed that modifies the variable values in dependency of a multiplier. In the last stage, the result is calculated from the modified variable values.
Claims20
A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables Ab and b are stored on the cryptographic processing device, the method comprising:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2Wi P over those indexes i for which bi=b holds is added to each variable and Ab;
- and
- calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of the variables Ab, wherein B is a set of integers, and wherein the values of variables Ab and b were previously determined during an initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- e
- =
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- is the point at infinity.
35 more elements
A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
- a reader configured to read values of variables Ab and b stored on the cryptographic processing device, and
- a processor configured to complete the elliptic curve point multiplication by:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds is added to each variable Ab, and
- calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of the variables Ab, wherein B is a set or integers, and wherein the values of variables Ab and b were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- e
- =
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- is the point at infinity.
36 more elements
A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
- modifying values of variables Ab in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds is added to each variable Ab, wherein the variables Ab and b are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve;
- and
- calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of the variables Ab, wherein B is a set of integers, wherein the values of variables Ab and b were previously determined during an initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- e
- =
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- is the point at infinity.
35 more elements
A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables Ab, b and Q are stored on the cryptographic processing device, the method comprising:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds is added to each variable Ab;
- and
- calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of Ab, and subtracting from it the variable Q stored on the cryptographic processing device, wherein B is a set of integers, and wherein the values of variables Ab, b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- by using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab, for each b=B, such that none of the selected point representations is a point at infinity;
- and
- computing the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in the variable Q.
33 more elements
A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
- a reader configured to read values of variables Ab, b and Q stored on the cryptographic processing device;
- and
- a processor configured to complete the elliptic curve point multiplication by:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds is added to each variable Ab, and calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of Ab and subtracting from it the variable Q stored on the cryptographic processing device, wherein B is a set of integers, and wherein the values of variables Ab b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- by using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for each bi εB, such that none of the selected point representations is a point at infinity;
- and
- computing the
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in the variable Q.
34 more elements
A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
- modifying válues of variables Ab in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds is added to each variable Ab;
- and
- calculating the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- by using the modified values of Ab, and subtracting from it a variable Q stored on the cryptographic processing device, wherein B is a set of integers, wherein the variables Ab, b and Q are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve, and wherein the values of variables Ab, b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- by using digits bi εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for each b εB, such that none of the selected point representations is a point at infinity;
- and
- comprising the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in the variable Q.
33 more elements
A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables Ab and b are stored on the cryptographic processing device, the method comprising:
- modifying the values of the variables Ab, stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB′, wherein B is a set of integers and B′ denotes, the set of absolute values of the integers in set B;
- and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the modified values of the variables Ab, wherein the values of variables Ab and b were previously determined during an initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits b εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB′, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- is the point at infinity.
35 more elements
A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
- a reader configured to read values of variables Ab and b stored on the cryptographic processing device;
- and
- a processor configured to complete the elliptic curve point multiplication by:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB′;
- wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B, and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the modified values of the variables Ab, wherein the values of variables Ab and b were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits b εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB′, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- is the point at infinity,
38 more elements
A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
- modifying values of variables Ab in dependency of digits bi such that the sure of the points 2wi P over those indexes i for which bi=b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers inset B, wherein variables Ab and b are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve;
- and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the modified values of the variables Ab, wherein the values of variables Ab and b were previously determined during an initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- using digits b εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for at least one but not all b εB′, such that none of the selected point representations is a point at infinity;
- and
- assigning point representations to variables Ab for all values of b for which randomly selected point representations were not assigned so that the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- is the point at infinity.
35 more elements
A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables Ab, b and Q are stored on the cryptographic processing device, the method comprising:
- modifying the values of the variables Ab stored on the cryptographic processing device in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B;
- and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the modified values of Ab, and subtracting from it the variable Q stored on the cryptographic processing device, wherein the values of variables Ab, b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- by using digits bi, εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for each b εB′, such that none of the selected point representations is a point at infinity;
- and
- computing the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in a variable Q.
34 more elements
A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
- a reader configured to read values of variables Ab, b and Q stored on the cryptographic processing device;
- and
- a processor configured to complete the elliptic curve point multiplication by:
- modifying the values of the variables Ab in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B, and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the moainea values of Ab and subtracting from it the variable Q stored on the cryptographic processing device, wherein the values of variables Ab, b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- wi
- by using digits bi, εb where w and l are integers;
- assigning randomly selected point representations to variables Ab for each b εB′, such that none of the selected point representations is a point at infinity;
- and
- computing the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in a variable Q.
36 more elements
A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
- modifying values of variables Ab in dependency of digits bi such that the sum of the points 2wi P over those indexes i for which bi=−b holds minus the sum of the points 2wi P over those negative indexes i for which bi=−b holds is added to each variable Ab with b εB ′, wherein B is a set of integers and B ′ denotes the set of absolute values of the integers in set B;
- and
- calculating the sum
- ∑
- b
- ∈
- B
- ′
-
- bA
- b
- by using the modified values of Ab, and subtracting from it a variable Q stored on the cryptographic processing device, wherein the variables Ab, b, and Q are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve, and wherein the values of variables Ab, b and Q were previously determined during the initialization of the cryptographic processing device by:
- representing the multiplier e in the form
- ∑
- 0
- ≤
- i
- ≤
- l
-
- b
- i
-
- 2
- w
-
-
- i
- by using digits bi, εB where w and l are integers;
- assigning randomly selected point representations to variables Ab for each b εB′, such that none of the selected point representations is a point at infinity;
- and
- computing the sum
- ∑
- b
- ∈
- B
-
- bA
- b
- and storing it in a variable Q.
37 more elements
Dependencies are inferred from the claim text.