Method and apparatus for performing validation of elliptic curve public keys
AssigneeCerticom Corp.
InventorsDaniel R. L. Brown, Atsushi Yamada
Life of this patent
Estimating the term…
Abstract
A method of validating a public key comprising the steps of receiving a public key, computing a function of the public key, the function having a predefined value for all points of a given order, and comparing the result of the function to predetermined information to indicate the validity of the public key.
Claims17
A method of validating a public key in an elliptic curve cryptosystem using an elliptic curve over a finite field, the public key comprising two coordinates (x,y) where x and y are elements of said finite field, said elliptic curve having cofactor h and said finite field being a binary field, said method comprising the steps of:
- a) receiving the public key;
- b) applying a function to the public key to obtain a result, the function being an algebraic expression and having for each order of the elliptic curve a predefined value for points on the elliptic curve of that order, whereby a characteristic of the public key is verifiable based on the order of the result;
- c) comparing the result of the function to predetermined information to determine the acceptability of the order of the result in order to determine the validity of the public key;
- and
- d) partially validating said public key if the order of the result is acceptable.
A method of validating a point on an elliptic curve with a known cofactor, comprising the steps of:
- a) determining factors of said cofactor;
- b) determining the possibility of scalar division of said point by each of said factors;
- and
- c) rejecting said point if any of said scalar divisions is not possible.
A method of nearly fully validating a point on an elliptic curve with a given cofactor comprising the steps of:
- a) partially validating said point;
- b) finding the scalar multiple of said point to said cofactor;
- and
- c) accepting said point if said point is partially valid and said scalar multiple is the zero element of said elliptic curve.
A method of nearly fully validating a point on an elliptic curve with a known cofactor comprising the steps of:
- a) partially validating said point;
- and
- b) confirming that said point does not equal each member of a set of predetermined points.
A method of validating a point on an elliptic curve defined over a finite field and with order an odd prime times a power of two comprising the steps of:
- a) partially validating said point;
- b) attempting to halve said point repeatedly until
- i. no half is found, or
- ii. the number of times said point is halved is the exponent of two in said power of two;
- and
- c) accepting said point if said point is partially valid and said number of times is equal to said exponent.
Dependencies are inferred from the claim text.