Verification protocol

• US 6,446,207 B1
• Filed: 01/29/1998
• Issued: 09/03/2002
• Est. Priority Date: 01/31/1997
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A., Johnson, Donald B.
• Primary Examiner(s): HAYES, GAIL O
• Assistant Examiner(s): Lathan, Bryan
• Application Number:
  US09/015,338
• Time in Patent Office: 1,678 Days
• Field of Search: 380/30, 713/180
• US Class Current: 713/180
• CPC Class Codes: G06F 7/725 over elliptic curves
• 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 verification protocol utilises a pair of signature components incorporating a pair of private keys, one of which is a long term key and the other of which is a short term key.

The long term key is applied to one of the signature components to reveal the short term key.

The short term key is then used to compute a value of a signature component contained in the signature. If the computed value and received values agree then authenticity is verified.

Claims

1. A method of verifying at a recipient a digital signature generated by a signor in a data communication system, said signature having a pair of signature components, one of said components incorporating first and second private keys with said first private key known to said recipient and signor and the other of said components having a value equivalent to a function associated with said second private key, said method of verifying comprising the steps of applying at said recipient said first of said private keys to said signature components to recover a value equivalent to said function associated with said second of said private keys and comparing said recovered value wit said other signature component to determine the authenticity of said signature.

2. A method according to claim 1 wherein said recovered value is used to compute a value of one of said signature components and said computed value and said signature component are compared to verify said signature.

3. A method according to claim 1 wherein the structure of said recovered value is compared with predetermined parameters to verify said signature.

4. A method according to claim 1 wherein one of said keys is a long term key and the other of said keys is a short term key generated for each signature.

5. A method according to claim 4 wherein said recovered value corresponds to said short term key.

6. A method according to claim 5 wherein said recovered value is used to compute a short term public key derived from said private key and included in said signature components.

7. A method according to claim 5 wherein at least a portion of said recovered value is hashed by a cryptographic hash function and a resultant hash value is compared to one of said signature components for verification.

8. A method of verifying a digital signature generated by a signor in a computer system, said signor having a private key d and a public key y, derived from an element g and said private key d said signature being generated by signing a message m in said computer system by:

a) generating a first signature component by combining at least said element g and a value k used by said signor as a short signature parameter according to a first mathematical function; and

b) generating a second signature component by mathematically combing said first signature component with said private key d;

said message m and said signature parameter k;

said method of verifying said digital signature comprising the steps of;

c) recovering a value k′

from said signature without using said public key y, and;

d) utilizing said recovered value k′

in said first mathematical function to derive a value r′

to verify said signature parameter k and k ′

are equivalent.

9. A method as defined in claim 8, wherein g is an element of order q in a field F*_p.

10. A method as defined in claim 8, wherein g is a point of prime order n in E(F_q), such that E is an elliptic curve defined over the field F_q.

11. A method as defined in claim 8, wherein said element g is a point on an elliptic curve over a finite field F_qⁿ.

12. A method as defined in claim 8, said signature parameter k being a randomly selected integer in the interval [1, q−

1], and said first signature component having a form defined by by r=g^k mod p mod q, wherein p and q are primes such that q divides p−

1.

13. A method as defined in claim 12, including calculating a value e=h(m) wherein h is a hash function, and wherein said second signature component s=k⁻

1(e+dr) mod q.

14. A method as defined in claim 13, said step of recovering said value k′

including;

(a) calculating a value z=(h(m)+dr)mod q;

(b) calculating z<sup>−

1</sup> inverting z mod q;

(c) calculating k′

<sup>−

1</sup>=s(z<sup>−

1</sup>) mod q; and

(d) calculating k′

by inverting k<sup>−

1</sup> mod q.

15. A method as defined in claim 14, said step of verifying that said signature parameter k and said value k′

are equivalent including tie steps of calculating r′

=g^k′

mod p mod q and comparing r′

ro r in order to verify k=k′

.

16. A method as defined in claim 14 including utilizing precomputed tables in said calculations.

17. A method as defined in claim 10, said signature parameter k being a statistically unique and unpredictable integer k selected in an interval {2, n−

2} and said fist signature component having a form defined by r=x, mod n wherein x is a co-ordinate of a private key.

18. A method as defined in claim 17, including calculating a value e=h(m) wherein h is a hash function and said second signature component is given by s=k⁻

1(e+dr) mod n.

19. A method as defined in claim 18, wherein said step of recovering said value k′

includes;

a) calculating a value z=(h(m)+dr) mod n;

b) calculating z<sup>−

1</sup> by inverting z mod n;

c) calculating k′

<sup>−

1</sup>=s(z<sup>−

1</sup>) mod n, and

d) calculating k′

by invert k<sup>−

1</sup> mod n.

20. A method as defined in claim 19, wherein said step of verifying that said signature parameter k and said k′

are equivalent including the steps of calculating r′

=g^k′

mod n and comparing r′

to r in order to verify k=k′

.

21. A method as defined in claim 19, wherein said signature parameter k is a randomly selected integer in an interval, and said first signature component has a form defined by e=h(m r′

);

wherein r=g^k mod p, h is a hash function and denotes concatenation.

22. A method as defined in claim 21, wherein said second signature component is defined by s=(de+k) mod p.

23. A method as defined in claim 22, wherein said step of recovering said value k′

includes;

a) calculating a value k′

=(s−

de) mod p;

b) calculating a value r′

=g^k mod p;

c) calculating a value e′

=h(m r′

); and

d) comparing said value e′

to e in order to verify k′

=k.

24. A method of verifying the authenticity of a certificate issued by a certifying authority in an electronic data communication system, said method including the steps of said certifying authority including in said certificate a pair of signature components derived from a pair of private keys, said certifying authority retaining one of said private keys, said certifying authority receiving said certificate and applying said private key to said signature components to derive therefrom a value corresponding to a function of the other of said private keys and comparing said derived value with said function to determine the authenticity of said certificate.

25. A method according to claim 24 wherein said derived value is compared with predetermined parameters to determine the authenticity of said certificate.

26. A method according to claim 24 wherein said derived value corresponds to said other key.

27. A method according to claim 26 wherein said one key is a long term private key used in a plurality of signatures and said other key is a short term key derived for each signature.

28. A method according to claim 26 wherein said signature components include a public key derived from said other key and said method includes the step of deriving a corresponding public key from said derived value and comparing said public key in said signature components with said corresponding public key.

29. A data communication system having a pair of correspondents connected by a data communication link, each of said correspondents having a cryptographic function to implement a public key cryptographic scheme utilising a pair of private keys, one of said private keys being utilised for multiple communications between said correspondents and the other of said private keys being generated by one of said correspondents at each communication, said one private key being shared by said correspondents to permit the other of said private keys to be recovered by said other correspondent from a digital signature generated by said one correspondent and compared to a signature component of said digital to verify the authenticity of said one correspondent.

30. A data communication system according to claim 29 wherein said cryptographic functions implement an elliptic curve cryptosystem.