Source: https://patents.google.com/patent/US20060153365A1/en
Timestamp: 2018-06-21 08:15:22
Document Index: 92941586

Matched Legal Cases: ['arty 202', 'arty 204', 'arty 204', 'arty 202', 'arty 204', 'arty 204', 'arty 302', 'arty 202', 'arty 202', 'arty 302', 'arty 302', 'arty 202', 'arty 302', 'arty 202', 'arty 302', 'arty 202', 'arty 302']

US20060153365A1 - Providing digital signature and public key based on shared knowledge - Google Patents
US20060153365A1
US20060153365A1 US11161556 US16155605A US2006153365A1 US 20060153365 A1 US20060153365 A1 US 20060153365A1 US 11161556 US11161556 US 11161556 US 16155605 A US16155605 A US 16155605A US 2006153365 A1 US2006153365 A1 US 2006153365A1
US11161556
US7593527B2 (en )
8. U.S. Patent Application “FACILITATING DIGITAL SIGNATURE BASED ON EPHEMERAL PRIVATE KEY” filed on Aug. 2005;
Symmetric cryptosystems have the following inherent problem: how does one transport the secret key from the send of a message to the recipient securely and in a tamperproof fashion? If someone could send the secret key securely, then in theory he or she would not need a cryptosystem in the first place - the secure channel could be simply used to send the message. Often, trusted couriers and digital certificates are used as a solution to this problem. Another method for communicating symmetric keys (as well as messages) is the well-known RSA asymmetric public key cryptosystem, which is used in the popular security tool Pretty Good Privacy (PGP).
Public key/private key cryptography has at least three principal applications. First is basic encryption-keeping the contents of messages secret. Second, digital signatures are implemented using public key/private key techniques. U.S. Pat. Nos. 6,851,054; 6,820,202; 6,820,199; 6,789,189; and others, the disclosures of which are incorporated by reference herein, are examples of digital signature type systems that utilize aspects of public key/private key cryptography. Third, electronic authentication systems that are not based strictly on conventional digital signature techniques may be implemented with public key/private key cryptography. Some of the foregoing incorporated and referenced patents describe certain aspects of such authentication systems.
In implementing ECC and, specifically, in generating an asymmetric public-private key pair for use in the Elliptic Curve Digital Signature Algorithm (ECDSA), an elliptic curve is defined by certain “domain” parameters, and a point is chosen along the elliptic curve that serves as a generator of a finite cyclic group, all the elements of which also lie along the elliptic curve. This generator is referred to as the “generating point” or “base point” (P). The domain parameters include: the field identification (or “Field ID”) identifying the underlying finite or Galois field, traditionally represented as “F2p” or “F2m”; the curve comprising two coefficients “a” and “b” of the elliptic curve equation y2=x3+ax+b mod p; a generating point (xp, yp); and the order of the generating point “n” comprising a prime number. Optionally, the domain parameters may include other specifications, such as, for example, a bit string seed of length 160 bits-if the elliptic curve is randomly generated in accordance with governmental standards, or a cofactor. The domain parameters further may include additional specifications, such as the appropriate bit length of a key.
In utilizing ECC-or any other cryptographic system, any cryptographic key used for encryption must be protected from compromise, especially during storage. Otherwise, the integrity of the cryptographic system is jeopardized. For example, if an insecure or network-accessible computer system and/or software is used in connection with a cryptographic operation, there is a risk that the keys stored in that computer system could be obtained and improperly utilized.
Safeguarding cryptographic keys, especially private keys in public-private key cryptographic systems, is important if adoption and use of cryptography by the general public in electronic communications is to become prevalent. The safeguarding of cryptographic keys is especially important in connection with the conduct of electronic transactions such as, for example, financial transactions. Facilitating the adoption and use of cryptography in such electronic communications-especially adoption and use of digital signatures-also is important, as demand for greater security, reliability, and accountability in such electronic communications is believed to be increasing.
More particularly described, certain aspects of the invention(s) relate to the use of the same private key in multiple public-private key pairs that are established for communicating with different parties. Moreover, as will become apparent from the detailed discussions below, the present invention particularly relates to-but is not limited to-elliptic curve cryptography (ECC) and the use of the Elliptic Curve Digital Signature Algorithm (ECDSA). Accordingly, many aspects and features of the present invention relate to, and are described in, the context of ECC, but the present invention is not thereby necessarily limited to such cryptography.
The step of transforming the initial generating point into a new generating point preferably includes the step of generating a transformer as a deterministic function of shared knowledge. In accordance with the invention, and as used herein, the phrase “as a deterministic function of means that which follows the phrase is an argument of the function. Moreover, the use of “deterministic” to modify function means that the function, given a specific argument or a specific set of arguments of the function (depending on whether the function includes one or more arguments), returns the same result time and time again. It should also be noted that a function could depend upon arguments in addition to that which follows “as a deterministic function of”, i.e., that which follows the phrase is not intended to be an exclusive list of all arguments of the function.
In any event, the deterministic function of the shared knowledge-whatever the shared knowledge may comprise-preferably outputs a large integer value constituting a transformer, and the step of transforming the initial generating point into the new generating point preferably includes the step of multiplying, through scalar multiplication, the initial generating point by the transformer to arrive at the new generating point.
Additionally, it is important to note that each term used herein refers to that which a person skilled in the art would understand such term to mean based on the contextual use of such term herein. To the extent that the meaning of a term used herein-as understood by a person skilled in the art based on the contextual use of such term-differs in any way from any particular dictionary definition of such term, it is intended that the meaning of the term as understood by a person skilled in the art should prevail.
In preferred system 200, the first party 202 obtains software from the second party 204. The software may be communicated 206 via the Internet 212 from a computer system of the second party 204 as shown in FIG. 2. The software preferably includes the ability to generate public and private keys of a public-private key pair in accordance with the aforementioned preferred methods of the invention, and includes the ability to generate digital signatures using the private key of the key pair, wherein the algorithm utilized to generate the digital signatures preferably is the ECDSA. Furthermore, the elliptic curve parameters-including the generating point-are communicated between the parties 202, 204 and, preferably, are included as predefined parameters contained within the software communicated to the first party 202 by the second party 204.
Upon receipt of the information from the second party 204 regarding the public key, the third party 302 may evaluate this information in gauging the risk that either the private key utilized to generate the digital signature was compromised and that the message was not, in fact, sent from the first party 202, or that the message was altered while in transit from the first party 202 to the third party 302. Indeed, a risk level can be assigned and taken under consideration in making a business judgment as to whether-and what-action to take, if any, in response by the third party 302 to receipt of a digitally signed message from the first party 202. The third party 302 further may request this information upon further receipt of digital signatures from the first party 202, or the third party 302 may itself record this information in association with the public key of the first party 202 in a database of the third party 302.
A preferred method of conveniently generating multiple digital signatures in accordance with the invention is illustrated in FIG. 4. This method includes first generating the private key as a function of UID in accordance with method 1400 of FIG. 1 4, discussed above. Accordingly, the UID is received in Step 402, the private key is generated as a deterministic function of the UID in Step 404, and the UID is then cleared in Step 406.
In a circle metaphor, these two pieces of information (a point on a circle 704, angle of the radius 706) can be utilized as a public/private key pair. The angle 706 may be utilized as a private key, while the (X, Y) point 704 may be utilized as the public key. If the hradius R 708 is known, the value of the center of the circle (A, B) 702 (which may be considered the data values encrypted) cannot be determined from merely knowing the point (X, Y)—the angle (e.g. 450) 706 must also be known in order to uniquely define a single point (A, B). Although this example using a circle as conceptually equivalent to an elliptic curve is contrived and computationally simple to break, it should now be understood that public key and private key for use in a cryptographic operation may be derived from a similar operation by using the mathematics of an elliptic curve, much in the same fashion as herein described in connection with the mathematics of a circle.
2. For every character in the input string (e.g. “PassWord”), look up the value corresponding to that character and add it to the value in the data variable ‘Passphrase Work Value’
3. When all of the input characters of the string are exhausted, divide the cumulative value in ‘Passphrase Work Value’by 360, and assign the remainder of this division (Modulo 360) to ‘PassphraseAngle’
4. The value or number of the variable ‘PassphraseAngle’is then utilized as a private key.
Assume that the input or passphrase is the string “PassWord” without the quotes. If we start with zero (0) in the ‘Passphrase Work Value’and take the first character (“P”) of the string and look it up in the above table we find the value 80. Add this value to the ‘Passphrase Work Value’ giving the value 80 for ‘Passphrase Work Value’ Move to the next character (“a”) in the string and perform the same lookup as before, which yields the value 65. Add the value 65 to the ‘Passphrase Work Value’, which cumulates to 145. Continue this process until there are no more characters in the input string. In this example, the cumulated values of the passphrase “PassWord” would yield the following computation:
The deterministic function of Step 1904 of method 1900 outputs a value using the UID as an argument of the function. This value represents the private key. The function is “deterministic” because each time the same UID is used as an argument of the function, the same output is received. In the preferred embodiment, the output of the deterministic function in step 1204 preferably is a large integer value. Furthermore, any function that can deterministically generate a suitably large number from an input value can be used as the deterministic function of step 1904 to generate the private key, as a private key for use in ECC is fundamentally any suitably large number. The deterministic function itself may include such algorithms as hashing the UID; hashing multiple times the UID; and hashing multiple times the UID while folding interim hashes together. Moreover, any hashing algorithm used preferably is a strong hash function. As will be appreciated by one having ordinary skill in the art, a strong hash function is a hashing algorithm that is considered secure because it: 1) it is computationally infeasible to find UID that corresponds to a given message digest; and, 2) it is computationally infeasible to find two UlDs that produce the same message digest. Using a strong hash function, any change to the UID will, with a very high probability, result in a different message digest.
The function for generating the digital signature preferably includes appending the indicator to that which is digitally signed such as, for example, an electronic message. The indicator may comprise, for example, either a “1” or “0” appended to the beginning or end of the electronic message. Of course, the indicator also should be communicated to the recipient of that which was digitally signed in order for the recipient to be able to verify the digital signature; however, the indicator need not be communicated if the recipient is aware of the possible values of the indicator and, therefore, can verify the digital signature by checking all possibilities. For example, the recipient of the electronic message and digital signature for the message-which in this case is the digital signature of both the message and the indicator appended thereto-can append the known different possible values of the indicator to the electronic message in verifying the digital signature. One of the different possibilities should result in verification of the digital signature, provided that the message was not changed in transit and that the true private key was used in generating the digital signature.
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 the steps of:
(b) transforming the initial generating point into a new generating point as a deterministic function; and
(c) generating within a 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 the step of clearing from the computer system the new generating point following said step of 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 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 the generated digital signature.
4. The method of claim 3, wherein the deterministic function of the shared knowledge outputs a large integer value.
5. The method of claim 3, wherein said step of transforming the initial generating point into a new generating point further includes the step of multiplying the initial generating point by the transformer to arrive at the new generating point.
6. The method of claim 3, wherein the shared knowledge comprises an account number for an account of the first party that is maintained with the second party.
7. The method of claim 3, further comprising the step of receiving user input into the computer system from the first party, the user input comprising the shared knowledge.
8. The method of claim 3, wherein the shared knowledge comprises information that is communicated between the first party and the second party.
9. The method of claim 3, wherein the shared knowledge comprises information that is communicated by a third party both to the first party and the second party.
10. The method of claim 3, wherein the shared knowledge comprises a unique identifier of the first party to the second party.
11. The method of claim 3, 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.
12. The method of claim 3, further comprising the step of exporting said generated digital signature from the computer system for communicating to the second party.
13. The method of claim 3, wherein said step of identifying the domain parameters of an elliptic curve comprises receiving an identification of the domain parameters from the second party.
14. The method of claim 3, wherein said step of identifying the domain parameters of an elliptic curve 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.
15. The method of claim 1, further comprising the step of determining the private key.
16. The method of claim 15, 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.
17. The method of claim 16, wherein the user input data represents a passphrase, password, or PIN.
18. The method of claim 16, wherein the user input data represents a biometric characteristic.
19. The method of claim 16, further comprising the step of 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).
20. The method of claim 16, further comprising the step of clearing the user input data from the computer system following said step 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.
21. The method of claim 15, wherein said step of determining the private key comprises retrieving the private key from a secure store of the computer system.
22. A computer-readable medium having computer-executable instructions for performing the steps comprising:
23. 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 a step of 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 the steps of,
(c) replacing the generating point of the domain parameters with the new generating point during said step of generating the digital signature as a function of the private key and the domain parameters.
24. 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 the steps of,
(ii) transforming in a deterministic function the initial generating point into a first new generating point, and
(iii) generating 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
(i) transforming in a deterministic function the initial generating point of the domain parameters into a second new generating point, and
(ii) generating 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.
25. The method of claim 24, 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 said step (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 said step (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.
said step (a)(ii) of transforming the initial generating point into a first 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; and
said step (b)(ii) of transforming the initial generating point into a second 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 third party different from the first party.
27. 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 the steps of:
(c) generating within a 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;
28. The method of claim 27, further comprising the step of 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.
30. 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 a step of 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,
(a) calculating 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,
(c) replacing the generating point of the domain parameters with the new generating point during said step of generating the public key as a deterministic function of the private key and the domain parameters.
US11161556 2005-01-07 2005-08-08 Providing digital signature and public key based on shared knowledge Active 2028-07-23 US7593527B2 (en)
US11161556 US7593527B2 (en) 2005-01-07 2005-08-08 Providing digital signature and public key based on shared knowledge
US20060153365A1 true true US20060153365A1 (en) 2006-07-13
US7593527B2 US7593527B2 (en) 2009-09-22
US11161556 Active 2028-07-23 US7593527B2 (en) 2005-01-07 2005-08-08 Providing digital signature and public key based on shared knowledge
CN103023648A (en) * 2012-11-27 2013-04-03 中国科学技术大学苏州研究院 Certificateless signature method based on elliptic curve discrete logarithm problem
US7593527B2 (en) 2009-09-22 grant
WO1997012460A1 (en) 1997-04-03 Document authentication system and method