Elliptic curve encryption systems
AssigneeCerticom Corp.
InventorsScott A. Vanstone, Ronald C. Mullin, Gordon B. Agnew
Life of this patent
Estimating the term…
Abstract
An elliptic curve encryption system represents coordinates of a point on the curve as a vector of binary digits in a normal basis representation in F2m. A key is generated from multiple additions of one or more points in a finite field. Inverses of values are computed using a finite field multiplier and successive exponentiations. A key is represented as the coordinates of a point on the curve and key transfer may be accomplished with the transmission of only one coordinate and identifying information of the second. An encryption protocol using one of the coordinates and a further function of that coordinate is also described.
Claims58
A method of computing an inverse of a number x with a finite field multiplier operating in the finite field GF(2M) and having elements A2i (o≦i<i that constitute a normal basis, said multiplier having a pair of m celled recirculating shift registers connected to a m celled recirculating accumulating register to generate in each of said accumulating register a respective grouped term of the normal basis representation of the product of a pair of elements located in respective ones of said recirculating shift registers, said method comprising the steps of
- a) representing the number x as a vector of binary digits xi where xi is the coefficient of A2i in the normal basis representation of x,
- b) loading in to each of said shift registers the vector of binary digits xi representing the normal basis representation of x2,
- c) cyclically shifting the binary digits of a first of said registers one cell to provide in said first register a vector representing x4,
- d) rotating said vectors in said shift registers and cojointly rotating said accumulating register with a m fold cyclic shift to generate in the cells of said accumulating register the m grouped terms representing the vector of the product of x2 and x4,
- e) loading the vector from the accumulating register to a second of said shift registers,
- f) repeating the steps of (c), (d), and (e) (g−2) times where g is a factor of m−1 to provide in said accumulating register a vector γ which is the normal basis representation of the exponentiation of x ∑ j = 0 g - 1 2 j ,
- g) loading the vector representing the normal basis representation of γ in each of said shift registers,
- h) performing a g-fold cyclic shift the binary digits of the vector in one of said shift registers where g is a factor of m−1 and g.h=m−1 to provide a vector representing y2e in said one register,
- i) rotating said bit elements in said shift registers and said accumulating register to generate grouped terms of the vector representing the product of γ and y2e,
- j) loading the vector from the accumulating register to the other of said shift registers,
- k) repeating steps h), i), and j) a total of g(h−1)-1 times to provide in said accumulating cell a vector of binary digits of the coefficients of the normal basis representation of the inverse of x.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said second coordinates having values differing in at least one but not all bit positions, said method comprising the steps of:
- a) said first correspondent selecting an identifying bit of said second coordinates, said second coordinates differing at the bit position of said identifying bit;
- b) said first correspondent using said identifying bit to generate identifying information of one of said second coordinates corresponding to said public key;
- c) said first correspondent forwarding to said second correspondent said first coordinate of said public key and said identifying information;
- d) said second correspondent computing said second coordinates from said first coordinate and said elliptic curve;
- e) said second correspondent using said identifying information to determine the appropriate value of said one of said second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said first correspondent forwarding to said second correspondent said first coordinate of said public key;
- b) said first correspondent identifying to said second correspondent a subset containing one of said second coordinates corresponding to said public key, and excluding the other of said second coordinates;
- c) said second correspondent computing said second coordinates from said first coordinate and said curve;
- d) said second correspondent determining which of said second coordinates is contained in the identified subset to thereby determine the value of said one of said second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosysyem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve defined over a field Fp, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said first correspondent forwarding to said second correspondent said first coordinate of said public key, together with identifying information of one of said second coordinates corresponding to said public key, said identifying information indicating the Legendre symbol associated with said one of said second coordinates;
- b) said second correspondent computing said second coordinates from said first coordinate and said elliptic curve;
- and
- c) said second correspondent using said identifying information to determine the appropriate value of said one of second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosysytem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said second coordinates having values differing in at least one but not all bit positions, said method comprising the steps of:
- a) said first correspondent selecting an identifying bit of said second coordinates, said second coordinates differing at the bit position of said identifying bit;
- b) said first correspondent using said identifying bit to generate identifying information of one of said second coordinates corresponding to said public key;
- c) said first correspondent forwarding to said second correspondent said first coordinate of said point and said identifying information;
- whereby said second correspondent may compute said second coordinates from said first coordinate and said parameters of said elliptic curve and use said identifying information to determine the appropriate value of said one of said second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said second coordinates having values differing in at least one but not all bit positions, said method comprising the steps of:
- a) said second correspondent receiving said first coordinate of said public key and identifying information of one of said second coordinates corresponding to said public key, said identifying information being computed from an identifying bit of said second coordinate, said second coordinates differing at the bit position of said identifying bit;
- b) said second correspondent computing said second coordinates from said first coordinate and said elliptic curve;
- c) said second correspondent using said identifying information to determine the appropriate value of said one of said second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said first correspondent forwarding to said second correspondent said first coordinate of said public key;
- b) said first correspondent identifying to said second correspondent a subset containing one of said second coordinates corresponding to said public key, and excluding the other of said second coordinates;
- whereby said second correspondent may compute said second coordinates from said first coordinate and said curve and determine which of said second coordinates is contained in the identified subset to thereby determine the value of said one of second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said second correspondent receiving from said first correspondent said first coordinate of said public key;
- b) said second correspondent receiving from said first correspondent an identification of a subset one of said second coordinates corresponding to said point, and excluding the other of said second coordinates;
- c) said second correspondent computing said second coordinates from said first coordinate and said curve;
- d) said second correspondent determining which of said second coordinates is contained in the identified subset to thereby determine the value of said one of said second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve defined over a field Fp, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said first correspondent forwarding to said second correspondent said first coordinate of said public key, together with identifying information of one of said second coordinates corresponding to said public key, said identifying information indicating the Legendre symbol associated with said one of said second coordinates,
- whereby said second correspondent may compute said second coordinates from said coordinate and said elliptic curve, and use said identifying information to determine the appropriate value of said one of second coordinates corresponding to said public key.
A method of transferring coordinates of a public key in an elliptic curve cryptosystem from a first correspondent to a second correspondent connected to said first correspondent by a data communications link and having the parameters of the curve, said public key being a point on a non-supersingular elliptic curve defined over a field Fp, said coordinates including a first coordinate determining two possible points on the curve, each of said possible points having a respective second coordinate, said method comprising the steps of:
- a) said second correspondent receiving from said first correspondent said first coordinate of said public key together with identifying information of one of said second coordinates corresponding to said public key, said identifying information indicating the Legendre symbol associated with said one of said second coordinates;
- b) said second correspondent computing said second coordinates from said first coordinate and said elliptic curve;
- and
- c) said second correspondent using said identifying information to determine the appropriate value of said one of said second coordinates a corresponding to said public key.
Dependencies are inferred from the claim text.