DIGITAL SIGNATURE SYSTEM BASED ON SHARED KNOWLEDGE

• US 20060153367A1
• Filed: 08/08/2005
• Published: 07/13/2006
• Est. Priority Date: 01/07/2005
• Status: Abandoned Application

• Current Assignee: First Data Corporation (Fiserv Incorporated)
• Original Assignee: First Data Corporation (Fiserv Incorporated)
• Inventors: Beeson, Curtis Linn
• Application Number:
  US11/161,559
• Publication Number:
  US 20060153367A1
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A method in a digital signature system includes providing a public key of a first party to a second party for later verification of a digital signature. The method includes: identifying domain parameters of an elliptic curve, including a generating point; transforming the generating point into a second generating point as a deterministic function of shared knowledge; and generating the public key as a deterministic function of a private key and the domain parameters, in which the second generating point is substituted for the identified generating point. The public key and private key constitute a public-private key pair of elliptic curve cryptography. A digital signature is generated as a function of the private key and the domain parameters, in which the second generating point again is substituted for the initial generating point identified. The shared knowledge is known to and shared between the first party and the second party.

Claims

1. In a digital signature system, a method comprising the steps of:

(a) first, providing a public key of a first party to a second party for the later verification of a digital signature generated using an elliptic curve digital signature algorithm, by performing the steps of,

(i) identifying domain parameters of an elliptic curve for use in elliptic curve cryptography, including identifying a generating point,

(ii) transforming said identified generating point into a second generating point as a deterministic function of shared knowledge,

(iii) generating within a computer system of the first party the public key as a deterministic function of a private key and the domain parameters, in which the second generating point is substituted for said identified generating point, wherein said generated public key comprises, in conjunction with the private key, a public-private key pair for use in elliptic curve cryptography, and

(iv) communicating said generated public key to the second party; and

(b) thereafter, providing a digital signature to the second party for verification, by performing the steps of,

(i) generating within the computer system of the first party the digital signature as a function of the private key and the domain parameters identified in said step (a)(i), in which the second generating point of said step (a)(ii) is substituted for said identified generating point of said step (a)(i), and

(ii) communicating said generated digital signature to the second party, wherein the shared knowledge is known to the first party and the second party.

2. The method of claim 1, wherein the deterministic function of the shared knowledge of said step (a)(ii) outputs a large integer value.

3. The method of claim 1, wherein said step (a)(ii) of transforming the generating point into the second generating point comprises multiplying the generating point by a large integer value to arrive at the second generating point.

4. The method of claim 1, wherein the shared knowledge comprises an account number for an account of the first party that is maintained with the second party.

5. The method of claim 1, further comprising the step of receiving user input into the computer system of the first party, the user input comprising the shared knowledge.

6. The method of claim 1, wherein the shared knowledge comprises information that is communicated between the first party and the second party.

7. The method of claim 1, wherein the shared knowledge comprises information that is communicated by a third party both to the first party and the second party.

8. The method of claim 1, wherein the shared knowledge comprises a unique identifier of the first party to the second party.

9. The method of claim 1, wherein the shared knowledge comprises a deterministic function of one or more predefined arguments, and wherein the deterministic function and predefined arguments are known both to the first party and the second party, whereby both the first party and the second party may independently calculate the shared knowledge for use in generating a transformer of the identified generating point of said step (a)(i).

10. The method of claim 1, wherein said step of identifying the domain parameters of said step (a)(i) comprises receiving an identification of the domain parameters from the second party.

11. The method of claim 1, wherein said step (a)(i) of identifying the domain parameters comprises selecting the domain parameters by the first party, and wherein the method further comprises the step of communicating by the first party said selected domain parameters to the second party.

12. The method of claim 1, further comprising the step of determining the private key.

13. The method of claim 12, wherein said step of determining the private key comprises generating the private key as a deterministic function of user input data that is received within the computer system from the first party.

14. The method of claim 13, wherein the user input data represents a passphrase, password, or PIN.

15. The method of claim 13, wherein the user input data represents a biometric characteristic.

16. The method of claim 13, further comprising the step of clearing the private key from the computer system following said step (a)(iii) of generating the public key so that the private key must be regenerated within the computer system of the first party in order to generate the digital signature within the computer system in said step (b)(i).

17. The method of claim 13, further comprising the step of clearing the user input data from the computer system following said step (a)(iii) of generating the private key so that the user input data must be received again within the computer system in order to regenerate the private key within the computer system of the first party.

18. The method of claim 12, wherein said step of determining the private key comprises retrieving the private key from a secure store of the computer system of the first party.

19. The method of claim 1, further comprising steps performed by the second party, including,

(d) receiving said generated public key from the first party,

(e) receiving said generated digital signature, the digital signature being for an electronic message,

(f) identifying the same domain parameters that were identified by the first party in said step (a)(i), including identifying the same generating point that was identified by the first party in said step (a)(i),

(g) transforming said identified generating point of said step (f) into the second generating point of said step (a)(ii) as a deterministic function of the shared knowledge, and

(h) verifying said received digital signature as a function of said received public key, the electronic message, and said identified domain parameters of said step (f), in which the second generating point of said step (g) is substituted for said identified generating point of said step (f).

20. The method of claim 1, further comprising additional steps performed by the first party, including,

(d) first, providing a second public key of the first party to a third party for the later verification of a digital signature, by performing the steps of,

(i) identifying domain parameters of an elliptic curve for use in elliptic curve cryptography, including identifying a generating point,

(ii) transforming said identified generating point of said step (d)(i) into a second generating point as a deterministic function of additional shared knowledge,

(iii) generating within the computer system of the first party the second public key as a deterministic function of the private key and the domain parameters identified in said step (d)(i), in which the second generating point of said step (d)(ii) is substituted for the generating point identified in said step (d)(i), wherein said generated second public key comprises, in conjunction with the private key, a second public-private key pair for use in elliptic curve cryptography, which key pair is different from the public-private key pair of said step (a)(iii), and

(iv) communicating said generated second public key to the third party;

and

(e) thereafter, providing a digital signature to the third party for verification, by performing the steps of,

(i) generating within the computer system of the first party the digital signature as a function of the private key and the domain parameters identified in said step (d)(i), in which the second generating point of said step (d)(ii) is substituted for the generating point identified in said step (d)(i), and

(ii) communicating said generated digital signature to the third party;

(f) wherein the additional shared knowledge is known to the first party and the third party.

21. The method of claim 20, further comprising steps performed by the third party, including,

(g) receiving said generated second public key from the first party,

(h) receiving said generated digital signature of said step (e)(i), the digital signature being for an electronic message,

(i) identifying the same domain parameters that were identified by the first party in said step (d)(i), including identifying the same generating point that was identified by the first party in said step (d)(i),

(j) transforming, as a deterministic function of the additional shared knowledge, said identified generating point in said step (i) into the second generating point of said step (d)(ii), and

(k) verifying said received digital signature as a function of said received second public key, the electronic message, and said identified domain parameters of said step (i), in which the second generating point of said step (i) is substituted for said identified generating point of said step (i).

22. A computer-readable medium having computer-executable instructions for performing the steps comprising:

(a) first, providing a public key of a first party to a second party for the later verification of a digital signature generated using an elliptic curve digital signature algorithm, by performing the steps of,

(i) identifying domain parameters of an elliptic curve for use in elliptic curve cryptography, including identifying a generating point,

(ii) transforming said identified generating point into a second generating point as a deterministic function of shared knowledge,

(iii) generating within a computer system of the first party the public key as a deterministic function of a private key and the domain parameters, in which the second generating point is substituted for said identified generating point, wherein said generated public key comprises, in conjunction with the private key, a public-private key pair for use in elliptic curve cryptography, and

(iv) communicating said generated public key to the second party; and

(b) thereafter, providing a digital signature to the second party for verification, by performing the steps of,

(i) generating within the computer system of the first party the digital signature as a function of the private key and the domain parameters identified in said step (a)(i), in which the second generating point of said step (a)(ii) is substituted for said identified generating point of said step (a)(i), and

(ii) communicating said generated digital signature to the second party,

wherein the shared knowledge is known to the first party and the second party.

23. An invention comprising a method of generating digital signatures with an Elliptic Curve Digital Signature Algorithm utilizing a private key of a public-private key pair used in elliptic curve cryptography, the method comprising the steps of:

(a) receiving into a computer system of the first party user input data;

(b) generating within the computer system a private key as a deterministic function of said received data of said step (a);

(c) maintaining an indicator to indicate whether a digital signature has yet been generated using said generated private key of said step (b) following said step of receiving the user input data;

(d) identifying domain parameters of an elliptic curve for use in elliptic curve cryptography, the domain parameters including an initial generating point;

(e) transforming the initial generating point into a new generating point as a deterministic function;

(f) generating within the computer system a digital signature as a deterministic function of said generated private key of said step (b), said maintained indicator of said step (f), and the domain parameters, in which the new generating point is substituted for the initial generating point; and

(g) following said step (f) of generating the digital signature, clearing from the computer system said generated private key of said step (b) and said new generating point of said step (e) so that neither the private key nor the new generating point is available within the computer system for generating a digital signature.

24. The invention of claim 23, further comprising clearing from the computer system said received data of said step (a) following said step (b) of generating the private key so that said received data is no longer available within the computer system for regenerating the private key, whereupon the user input data received in step (a) must be received again within the computer system in order to regenerate the private key within the computer system using the deterministic function of said step (b).

25. The invention of claim 23, wherein said step (f) comprises appending or pre-pending a value of said maintained indicator to an electronic message prior to digitally signing the electronic message in generating the digital signature.

26. The invention of claim 23, further comprising, prior to said step (g) of clearing, repeating said step (f) to thereby generate additional digital signatures within the computer system.

27. The invention of claim 23, wherein said step (c) of maintaining the indicator is performed prior to each respective performance of said step (f) of generating a digital signature.

28. The invention of claim 23, wherein said step (g) of clearing occurs immediately upon expiration of a predetermined period of time.

29. The invention of claim 23, further comprising a computer-readable medium having computer-executable instructions for performing the method.

30. The invention of claim 23, wherein said step of transforming the initial generating point into a new generating point includes the step of generating a transformer as a deterministic function of shared knowledge, wherein the shared knowledge is known to the first party and a second party different from the first party, wherein the second party receives said generated digital signature.