Digital signatures on a Smartcard

• US 6,704,870 B2
• Filed: 08/29/2001
• Issued: 03/09/2004
• Est. Priority Date: 04/16/1996
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Menezes, Alfred J., Vanstone, Scott A.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/942,492
• Publication Number:
  US 20020095583A1
• Time in Patent Office: 923 Days
• Field of Search: 713/180, 713/200, 713/201, 380/285, 380/44, 380/30
• US Class Current: 713/180
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/082 Features insuring the integrity of the data on or in the card
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3247 involving digital signatures

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.

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.

2. A method according to claim 1 wherein said value derived from said message, m, is obtained by applying a hash function to said message.

3. A method according to claim 2 wherein said second signature component, s, is of the form s=k⁻

1{h(m)+ar} mod q, where q is a divisor of the order, e, of said elliptic curve and h(m) is said value derived by applying a hash function to said message.

4. A method according to claim 1 wherein said first signature component r is obtained by utilizing one coordinate of said point kP.

5. A method according to claim 4 wherein said one coordinate is the x coordinate of said point kP.

6. A method according to claim 5 wherein said x-coordinate is reduced mod q.

7. A method according to claim 6 wherein said signature consists of said first and second signature components.

8. A method according to claim 7 wherein said elliptic curve is an anomalous elliptic curve.

9. A method according to claim 8 wherein said anomalous curve is of the form y²=xy=x³+1.

10. A method according to claim 1 wherein an integer is derived from said representation of said point kP.

11. A method according to claim 10 wherein said integer is obtained by selecting one of said coordinates of said point kP, and reducing said coordinate mod q where q is a divisor of the order, e, of the elliptic curve.

12. A method according to claim 11 wherein said one coordinate is the x coordinate of said point kP.

13. A method according to claim 12 wherein said divisor q is preselected and publically known.

14. A method according to claim 12 wherein said value derived from said message, m, is obtained by applying a hash function to said message.

15. A method according to claim 14 wherein said value derived from said message is a q bit hash of said message.

16. A method according to claim 15 wherein said elliptic curve is an anomalous elliptic curve.

17. A method according to claim 16 wherein said elliptic curve is of the form y²+xy=x³+1.

18. A method according to claim 1 wherein said second signature component s has a value corresponding to k¹{h(m)+ar} mod q.

19. A method according to claim 18 wherein a value corresponding to said second signature component s is obtained by selecting an integer, c, and computing a value, u, which equals the product of c and k and computing s=c{h(m)+ar}, said signature components on said message m including r, s, and u.

20. A method according to claim 19 wherein a value corresponding to k¹{h(m)+ar} mod q is obtained by a recipient of said signature by computing the product of said second signature component, s, and an inverse of said value, u.

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 long-term 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.

22. A method according to claim 21 wherein said second signature component s has the form s=k¹{h(m)+ar} mod q, where h(m) is a hash of the message m.

23. A method according to claim 22 wherein said elliptic curve is an anomalous elliptic curve of the form y²+xy=x³+1.

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²+xy=x³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 Ø

ⁱ(kP);

ii) operating upon the integer k upon by a constant λ

where Ø

ⁱ(kP)=λ

ⁱ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²xy=x³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 Ø

ⁱ upon the point kP to obtain a point k′

P corresponding to Ø

ⁱ(kP);

ii) operating upon the integer k by a constant λ

where Ø

ⁱ(kp)=λ

ⁱp to obtain a value k′

corresponding to λ

ⁱk; and

utilizing the values k′ and

k′

P as a session key pair in a cryptographic operation.