Providing digital signature and public key based on shared knowledge

• US 7,593,527 B2
• Filed: 08/08/2005
• Issued: 09/22/2009
• Est. Priority Date: 01/07/2005
• Status: Active Grant

• Current Assignee: First Data Corporation (Fiserv Incorporated)
• Original Assignee: First Data Corporation (Fiserv Incorporated)
• Inventors: Beeson, Curtis Linn
• Primary Examiner(s): Abrishamkar; Kaveh
• Application Number:
  US11/161,556
• Publication Number:
  US 20060153365A1
• Time in Patent Office: 1,506 Days
• Field of Search: None
• US Class Current: 380/30
• 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/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A public key and digital signature is provided using a private key of a public-private key pair in an elliptic curve digital signature algorithm (ECDSA) by: identifying domain parameters of an elliptic curve for use in elliptic curve cryptography, the domain parameters including an initial generating point; transforming the generating point into a new generating point as a deterministic function; generating the public key as a deterministic function of the private key and the domain parameters, in which the new generating point is substituted for the initial generating point; and generating the digital signature as a function of the private key and the domain parameters, in which the new generating point is substituted for the initial generating point.

Claims

1. A method of providing a digital signature of a first party using a private key of a public-private key pair in the elliptic curve digital signature algorithm (ECDSA), the method comprising:

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

(b) transforming within a computer system the initial generating point into a new generating point 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; and

(c) generating within the computer system a digital signature as a function of a private key and the domain parameters, in which the new generating point is substituted for the initial generating point.

2. The method of claim 1, further comprising clearing from the computer system the new generating point following said generating the digital signature so that the generating point is no longer available within the computer system for regenerating the digital signature.

3. The method of claim 1, wherein the deterministic function of the shared knowledge outputs a large integer value.

4. The method of claim 1, wherein transforming the initial generating point into a new generating point further includes multiplying the initial generating point by the transformer to arrive at the new generating point.

5. 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.

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

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

8. 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.

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

10. The method of claim 1, wherein the shared knowledge comprises a deterministic function of one or more predefined arguments, 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 the transformer.

11. The method of claim 1, further comprising exporting said generated digital signature from the computer system for communicating to the second party.

12. The method of claim 1, wherein identifying the domain parameters of an elliptic curve comprises receiving an identification of the domain parameters from the second party.

13. The method of claim 1, wherein identifying the domain parameters of an elliptic curve comprises selecting the domain parameters by the first party, and wherein the method further comprises communicating by the first party said selected domain parameters to the second party.

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

15. The method of claim 14, wherein 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.

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

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

18. The method of claim 15, further comprising clearing the private key from the computer system following said step of generating the digital signature so that the private key must be regenerated within the computer system in order to generate a digital signature within the computer system using the function of said step (c).

19. The method of claim 15, further comprising clearing the user input data from the computer system following 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.

20. The method of claim 14, wherein determining the private key comprises retrieving the private key from a secure store of the computer system.

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

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

(b) transforming within a computer system the initial generating point into a new generating point as a deterministic function of shared knowledge, wherein the shared knowledge is known to a first party and a second party different from the first party; and

(c) generating within the computer system a digital signature as a function of a private key and the domain parameters, in which the new generating point is substituted for the initial generating point.

22. In a method of providing a digital signature with a private key of a public-private key pair of a first party using the elliptic curve digital signature algorithm (ECDSA), the method including generating a digital signature as a function of the private key and domain parameters of an elliptic curve, the domain parameters including a generating point, an improvement to the method comprising,

(a) calculating a larger integer value as a deterministic function of shared knowledge that is known to the first party and a second party different from the first party,

(b) multiplying the generating point of the domain parameters by said calculated integer value to obtain a new generating point, and

(c) replacing the generating point of the domain parameters with the new generating point during generating the digital signature as a function of the private key and the domain parameters.

23. A method of providing two digital signatures in accordance with the elliptic curve digital signature algorithm (ECDSA), and using the same private key of a first party, which digital signatures can be verified with different respective public keys, the method comprising,

(a) with respect to the first digital signature,

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

(ii) transforming in a deterministic function of shared knowledge within a computer system the initial generating point into a first new generating point, wherein the shared knowledge is known to the first party and a second party different from the first party, and

(iii) generating within the computer system the first digital signature as a function of the private key and the domain parameters, in which the first new generating point is substituted for the initial generating point;

and

(b) with respect to the second digital signature,

(i) transforming in a deterministic function of shared knowledge within the computer system the initial generating point of the domain parameters into a second new generating point, wherein the shared knowledge is known to the first party and a third party different from the first party and

(ii) generating within the computer system the second digital signature as a function of the same private key and the domain parameters, in which the second new generating point is substituted for the initial generating point.

24. The method of claim 23, wherein the different respective public keys are provided by,

generating the first public key as a deterministic function of the private key and the domain parameters, in which the first new generating point of (a)(ii) is substituted for the initial generating point, said generated first public key thereby comprising, in conjunction with the private key, the first public-private key pair for use in elliptic curve cryptography;

and

generating the second public key as a deterministic function of the private key and the domain parameters, in which the second new generating of (b)(i) point is substituted for the initial generating point, said generated second public key thereby comprising, in conjunction with the private key, the second public-private key pair for use in elliptic curve cryptography.

25. A method of providing by a first party a public key of a public-private key pair for use in elliptic curve cryptography, the method comprising:

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

(b) transforming within a computer system the initial generating point into a new generating point as a deterministic function; and

(c) generating within computer system a public key as a deterministic function of a private key and the domain parameters, in which the new generating point is substituted for the initial generating point;

(d) wherein said generated public key comprises, in conjunction with the private key, a public-private key pair for use in elliptic curve cryptography.

26. The method of claim 25, further comprising clearing from the computer system the new generating point following said step of generating the public key so that the generating point is no longer available within the computer system for regenerating the public key.

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

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

(b) transforming within a computer system the initial generating point into a new generating point as a deterministic function; and

(c) generating within the computer system a public key as a deterministic function of a private key and the domain parameters, in which the new generating point is substituted for the initial generating point;

(d) wherein said generated public key comprises, in conjunction with the private key, a public-private key pair for use in elliptic curve cryptography.

28. In a method of providing a public key of a public-private key pair of a first party for use in elliptic curve cryptography, the method including generating a public key as a deterministic function of a private key and domain parameters of an elliptic curve for use in elliptic curve cryptography, the domain parameters including a 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, an improvement to the method comprising,

(a) calculating within a computer system a large integer value as a deterministic function of shared knowledge that is known to the first party and a second party different from the first party,

(b) multiplying the generating point of the domain parameters by said calculated integer value to obtain a new generating point, and

(c) replacing the generating point of the domain parameters with the new generating point during generating the public key as a deterministic function of the private key and the domain parameters.