Digital signatures on a Smartcard
First Claim
1. A method of generating a signature on a message m in an elliptic curve cryptographic system having a seed point P on an elliptic curve of order e over a finite field, said method comprising the steps of:
 i) selecting as a session key an integer k and computing representation of a corresponding point kP;
ii) deriving from said representation a first signature component, r, independent of said message,m;
iii) combining said first signature component, r, with a private key, a, a value derived from said message, m, and said session key, k, to obtain a second 10 signature component, s, containing said private key, a, and said session key, k, such that extraction of either is inhibited even when said signature components, r,s, are made public; and
iv) utilizing said signature components r,s, in the signature of the message, m.
2 Assignments
Litigations
0 Petitions
Accused Products
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.
43 Citations
25 Claims

1. A method of generating a signature on a message m in an elliptic curve cryptographic system having a seed point P on an elliptic curve of order e over a finite field, said method comprising the steps of:

i) selecting as a session key an integer k and computing representation of a corresponding point kP;
ii) deriving from said representation a first signature component, r, independent of said message,m;
iii) combining said first signature component, r, with a private key, a, a value derived from said message, m, and said session key, k, to obtain a second 10 signature component, s, containing said private key, a, and said session key, k, such that extraction of either is inhibited even when said signature components, r,s, are made public; and
iv) utilizing said signature components r,s, in the signature of the message, m.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)


21. A method of generating a digital signature r, s, of a message m using an elliptic curve cryptosystem employing an elliptic curve of order e, said method comprising the steps of:

i) selecting an integer k and determining a corresponding point kP where P is point on the curve;
ii) selecting a coordinate (x) of the point kP;
iii) reducing the coordinate mod q where q is a known divisor of e, to obtain a first component r; and
iv) combining said first component, r, with a longterm private key a and 10 said integer k to obtain a second signature component s, such that extraction of either said long term private key a or said integer k is inhibited even when said signature r,s, are made public.  View Dependent Claims (22, 23)


24. A method of generating a signature r,s, of a message m performed on an elliptic curve cryptosystem implemented over an anomalous elliptic curve of the form said y^{2}+xy=x^{3}1, method comprising the steps of:

i) performing a Frobenius operation 0 upon at least one coordinate, x, of a point kP, where k is an integer and kP is a point on the curve obtained from a k fold 6 composition of a point P on the curve, to obtain a corresponding coordinate x′
of a point k′
P corresponding to Ø
^{i}(kP);
ii) operating upon the integer k upon by a constant λ
where Ø
^{i}(kP)=λ
^{i}P to obtain a value k′
;
iii) utilizing the coordinate x′
to obtain a first signature component r; and
iv) combining said first signature component r with the value k′
to obtain said second signature component s.


25. A method of generating a session key pair from an initial key pair k, kP for use in a public key encryption elliptic scheme implemented over an anomalous curve of the form y^{2}xy=x^{3}1 where k is an integer and kP is a point on the curve obtained from a k fold composition of a point P on the curve, said method comprising the steps of:

i) performing a Frobenius operation Ø
^{i }upon the point kP to obtain a point k′
P corresponding to Ø
^{i}(kP);
ii) operating upon the integer k by a constant λ
where Ø
^{i}(kp)=λ
^{i}p to obtain a value k′
corresponding to λ
^{i}k; and
utilizing the values k′ and
k′
P as a session key pair in a cryptographic operation.

1 Specification