Digital signatures on a smartcard
OwnerScott Vanstone, Alfred Menezesinventors
Life of this patent
Estimating the term…
Abstract
A digital signature scheme for a “smart” card utilizes a set of prestored signing elements and combines pairs of the elements to produce a new session pair. The combination of the elements is performed partly on the card and partly on the associated transaction device so that the exchange of information between card and device does not disclose the identity of the signing elements. The signing elements are selected in a deterministic but unpredictable manner so that each pair of elements is used once. Further signing pairs are generated by implementing the signing over an anomalous elliptic curve encryption scheme and applying a Frobenius Operator to the normal basis representation of one of the elements.
Claims20
A method of generating a signature implemented over an elliptic curve public key encryption scheme utilizing information maintained secret in one computing device comprising the steps of:
- i) initiating the computation of a coordinate a point on the elliptic curve from a pair of other points on said curve by performing on said one device an initial set of sufficient steps in the computation to inhibit recognition of information pertaining to the identity of said other points;
- ii) transferring to another computing device remote from the one device the results of said steps;
- iii) performing at least such additional steps in said computation at said other device to permit the completion of said computation at said one device;
- and
- iv) transferring the result of said additional steps to said one device for incorporation in said signature.
A method of deriving a coordinate of a point on an anomalous elliptic curve over the field GF2m for utilization in a public key encryption scheme implemented on said curve, said method comprising the steps of:
- i) storing a normal basis representation of each of a set of coordinates of points on said curve;
- ii) retrieving said normal basis representation of a coordinate of one of said points;
- iii) performing an i-fold cyclic shift on said retrieved normal basis representation of said one coordinate;
- and
- iv) utilizing the resultant representation as a coordinate of a further point on the curve resulting from an i-fold application of the Frobenius Operation to said one point.
A method of generating a session pair k, kP for use in a digital signature performed on an anomalous elliptic curve in the filed GF2m where kP is a point on said curve resulting from the k fold addition of a starting point P where k is an integer, said method comprising the steps of:
- i) storing a set of initial values of k and kP, as a normal basis representation in the field GF2m;
- ii) selecting a coordinate of one of said points kP in said set of initial values;
- iii) performing an i-fold cyclic shift on said coordinate to obtain a normal basis representation of the coordinate after an i-fold application of a Frobenius Operation;
- iv) selecting the integer k associated with said one of said points;
- v) computing an integer value λik where λ defines the relationship between the start point P and a point ØP and Ø indicates a Frobenius Operation;
- vi) utilizing the resultant representation of the coordinate and the value λik as a session pair in a digital signature r,s where r is derived from the representation of a coordinate of a point on the curve and s is derived form the integer value associated with such point, the message to be signed and r.
A method of generating signature components for use in a digital signature scheme, said signature components including private information and a public key derived from said private information, said method comprising the steps of storing private information and related public key as an element in a set of such elements, cycling in a deterministic but unpredictable manner through said set to select at least one element of said set without repetition and utilizing said one element to derive a signature component in said digital signature scheme.
Dependencies are inferred from the claim text.