US 8,284,930 B2Granted

Simultaneous scalar multiplication method

AssigneeCerticom Corp.

InventorsAdrian Antipa, Yuri Poeluev

Life of this patent

Estimating the term…

Loading patent…

Abstract

In computing point multiples in elliptic curve schemes (e.g. kP and sQ) separately using, for example, Montgomery's method for the purpose of combining kP+sQ, several operations are repeated in computing kP and sQ individually, that could be executed at the same time. A simultaneous scalar multiplication method is provided that reduces the overall number of doubling and addition operations thereby providing an efficient method for multiple scalar multiplication. The elements in the pairs for P and Q method are combined into a single pair, and the bits in k and s are evaluated at each step as bit pairs. When the bits in k and s are equal, only one doubling operation and one addition operation are needed to compute the current pair, and when the bits in k and s are not equal, only one doubling operation is needed and two addition operations.

Claims27

Dependent claims

A method of operating a cryptographic unit to perform a cryptographic operation in a cryptographic communication system by simultaneously performing a first multiplication of a first scalar k by a first point P on an elliptic curve E, and a second multiplication of a second scalar s by a second point Q on said elliptic curve E, wherein said first scalar k comprises one or more binary bits ki and said second scalar s comprises one or more binary bits si, wherein i represents a common bit position in said first scalar k and said second scalar s, said cryptographic operation comprising:

generating an initial computation pair comprising a first term and a second term by:
adding respective first terms from Montgomery forms of the first multiplication and the second multiplication;
and
adding respective second terms from the Montgomery forms for the first multiplication and the second multiplication;
and
beginning with the initial computation pair, for each bit pair (ki, si), computing a next computation pair using a previous computation pair by:
if the bit pair is (0,0) generating the next computation pair by:
doubling the first term of the previous computation pair to obtain the first term of the next computation pair;
and
adding the first term and the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (1,1), generating the next computation pair by:
adding the first term and the second term of the previous computation pair to obtain the first term of the next computation pair;
and
doubling the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (0,1), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the second point Q to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair;
and
if the bit pair is (1,0), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the first point P to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair.

20 more elements

A cryptographic unit configured to perform a cryptographic operation in a cryptographic communication system by simultaneously performing a first multiplication of a first scalar k by a first point P on an elliptic curve E, and a second multiplication of a second scalar s by a second point Q on said elliptic curve E, wherein said first scalar k comprises one or more binary bits ki and said second scalar s comprises one or more binary bits si, wherein i represents a common bit position in said first scalar k and said second scalar s, said cryptographic unit comprising:

a cryptographic module configured to generate an initial computation pair comprising a first term and a second term by:
adding respective first terms from Montgomery forms of the first multiplication and the second multiplication;
and
adding respective second terms from the Montgomery forms for the first multiplication and the second multiplication;
and
beginning with the initial computation pair, for each bit pair (ki, si), the cryptographic module configured to compute a next computation pair using a previous computation pair by:
if the bit pair is (0,0) generating the next computation pair by:
doubling the first term of the previous computation pair to obtain the first term of the next computation pair;
and
adding the first term and the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (1,1), generating the next computation pair by:
adding the first term and the second term of the previous computation pair to obtain the first term of the next computation pair;
and
doubling the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (0,1), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the second point Q to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair;
and
if the bit pair is (1,0), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the first point P to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair.

20 more elements

A non-transitory computer readable medium having stored thereon computer readable instructions for configuring a cryptographic unit to perform a cryptographic operation in a cryptographic communication system by simultaneously performing a first multiplication of a first scalar k by a first point P on an elliptic curve E, and a second multiplication of a second scalar s by a second point Q on said elliptic curve E, wherein said first scalar k comprises one or more binary bits ki and said second scalar s comprises one or more binary bits si, wherein i represents a common bit position in said first scalar k and said second scalar s, said cryptographic operation comprising:

generating an initial computation pair comprising a first term and a second term by:
adding respective first terms from Montgomery forms of the first multiplication and the second multiplication;
and
adding respective second terms from the Montgomery forms for the first multiplication and the second multiplication;
and
beginning with the initial computation pair, for each bit pair (ki, si), computing a next computation pair using a previous computation pair by:
if the bit pair is (0,0) generating the next computation pair by:
doubling the first term of the previous computation pair to obtain the first term of the next computation pair;
and
adding the first term and the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (1,1), generating the next computation pair by:
adding the first term and the second term of the previous computation pair to obtain the first term of the next computation pair;
and
doubling the second term of the previous computation pair to obtain the second term of the next computation pair;
if the bit pair is (0,1), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the second point Q to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair;
and
if the bit pair is (1,0), generating the next computation pair by:
doubling the first term of the previous computation pair and adding the first point P to obtain the first term of the next computation pair;
and
adding the first point P and the second point Q to the first term of the next computation pair.

20 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/177,286Filed 6 Jul 2011 · continuation
Priority: 3 Nov 2005
Published: US 2011/0261956 A127 Oct 2011
Granted: 9 Oct 2012
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 7/725
Finite field arithmetic: over elliptic curves
H04L 9/3066
Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy: involving…
H04L 2209/20
Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication…
G06F
Computing and data processing

Family

Application60/732,715Us provisional application · filed 3 Nov 2005
Application11/556,531Parent of this continuation · filed 3 Nov 2006
US 2011/0261956 A1Pre-grant publication · published 27 Oct 2011
US 8,045,705 B2Parent of this continuation
US 2007/0098154 A1Published application
US 8,284,930 B2This patent

From the US filing history. Foreign family members aren’t listed.