Method for accelerating cryptographic operations on elliptic curves
OwnerRobert J. Lambert, Robert Gallant +1inventors
InventorsRobert J. Lambert, Robert Gallant, Scott A. Vanstone
Life of this patent
Estimating the term…
Abstract
This invention provides a method for accelerating multiplication of an elliptic curve point Q(x,y) by a scalar k, the method comprising the steps of selecting an elliptic curve over a finite field Fq where q is a prime power such that there exists an endomorphism ψ, where ψ (Q)=λ−Q for all points Q(x,y) on the elliptic curve; and using smaller representations ki of the scalar k in combination with the mapping ψ to compute the scalar multiple of the elliptic curve point Q.
Claims16
A method for multiplying an elliptic curve point Q(x,y) by a scalar to provide a point kQ, the method comprising the steps of:
- a) selecting an elliptic curve over a finite field F such that there exists an endomorphism ψ where ψ(Q)=λ·Q for all points Q(x,y) on the elliptic curve, and λ is an integer,
- b) establishing a representation of said scalar k as a combination of components ki and said integer λ
- c) combining said representation and said point Q to form a composite representation of a multiple corresponding to kQ and
- d) computing a value corresponding to said point kQ from said composite representation of kQ.
A method of generating in an elliptic curve cryptosystem a key pair having a integer k providing a private key and a public key kQ, where Q is a point on the curve,
- a) selecting an elliptic curve over a finite field F such that there exists an endomorphism ψ where ψ(Q)=λQ for all points Q (x,y) on the elliptic curve, λ is an integer,
- b) establishing a representation of said key k as a combination of components ki and said integer λ,
- c) combining said representation and said point Q to form a composite representation of a multiple corresponding to the public key kQ and
- d) computing a value corresponding to said key kQ from said composite representation of kQ.
A method of computing a coordinate of a point kP on an elliptic curve resulting from a point multiplication of an initial point P by a scalar k, said method comprising the steps of:
- a) decomposing said scalar k into a pair of components k0, k1 for point multiplication to obtain respective points on said curve which when combined provide said point kP;
- b) determining a signed representation in non-adjacent form of each of said first and second components;
- c) generating a table having a plurality of signed bit combinations contained in said representations and corresponding point multiples of said combinations to provide portions of said respective points;
- d) establishing for each of said representations a window having a width less then the length of each of said representations;
- e) initiating a sequential examination of said representations by said windows to obtain a position for one of said windows in one of said representations contaning a respective one of said combinations in said table;
- f) retrieving from said table the one of said point multiples corresponding to said respective one of said signed bit combinations in said table to obtain therefrom one of said portions;
- g) accumulating said portion and continuing examination of said representations with a doubling of said accumulator for each bit-wise shift of said windows to obtain a representation of said coordinate of said point kP in said accunulator.
Dependencies are inferred from the claim text.