Method and apparatus for verifiable generation of public keys
View Patent ↗The invention provides a method of verifiable generation of public keys. According to the method, a self-signed signature is first generated and then used as input to the generation of a pair of private and public keys. Verification of the signature proves that the keys are generated from a key generation process utilizing the signature. A certification authority can validate and verify a public key generated from a verifiable key generation process.
1. A computer implemented method of generating a private key of a computing device in a communication system, the computing device having a cryptographic unit, the method comprising:
the cryptographic unit generating a pair of signature components, one of the pair of signature components generated from an ephemeral private key, the pair of signature components representing a digital signature of a self-signed signature message to bind the computing device to the self-signed signature message;
the computing device obtaining message data;
the cryptographic unit generating the self-signed signature message based upon the message data and the digital signature;
the cryptographic unit computing the private key based upon the self-signed signature message; and
the cryptographic unit computing a public key based upon the private key such that verification of the self-signed signature message proves that the public key and private key were generated from a key generation process utilizing the self-signed signature message.
2. The method of claim 1 , further comprising the computing device receiving at least a portion of the message data from a trusted authority.
3. The method of claim 2 , wherein the portion of the message data contains randomness.
4. The method of claim 3 , further comprising:
the computing device sending a request message to a certification authority; and
the computing device receiving at least the portion of the message data from the certification authority over a secure channel;
wherein at least the portion of the message data is generated by the certification authority from the request message and signed with a private key of the certification authority.
5. The method of claim 1 , wherein the pair of signature components, the private key, and the public key are generated based upon a Digital Signature Algorithm (DSA).
6. The method of claim 1 , wherein the pair of signature components, the private key, and the corresponding public key are generated based upon an Elliptic Curve Digital Signature Algorithm.
7. The method of claim 1 , wherein the pair of signature components includes an integer.
8. The method of claim 1 , wherein generating the pair of signature components comprises:
the cryptographic unit generating an ephemeral public key;
the cryptographic unit obtaining a salt value; and
the cryptographic unit computing a hash value of a pre-determined number of repetitions of a concatenation of the salt value and the ephemeral public key.
9. The method claim 1 , wherein the pair of signature components includes an integer, and generating the pair of signature components comprises:
the cryptographic unit selecting the ephemeral private key, the ephemeral private key being a value selected at random;
the cryptographic unit computing an ephemeral public key from the ephemeral private key, the ephemeral public key being a product of the ephemeral private key and an elliptic curve point; and
the cryptographic unit assigning to the integer an integer value corresponding to the ephemeral public key.
10. The method of claim 1 , wherein generating a self-signed signature message based upon the message data and the digital signature comprises concatenating the message data and the pair of signature components into the self-signed signature message, and wherein the computing the private key comprises:
the cryptographic unit computing a message digest from an integer hash value of the self-signed signature message; and
the cryptographic unit computing the private key from the digital signature and the message digest.
11. The method of claim 1 , wherein the pair of signature components comprises a first integer r and a second integer s and wherein generating the pair of signature components comprises:
the cryptographic unit selecting the ephemeral private key k, the ephemeral private key k being a non-negative integer smaller than a prime number n;
the cryptographic unit computing an ephemeral public key from the ephemeral private key k, the ephemeral public key being a product of the ephemeral private key and an elliptic curve point G having the prime number as its order;
the cryptographic unit assigning an integer value corresponding to the ephemeral public key to the first integer r; and
the cryptographic unit selecting the second integer s, the second integer being a non-negative integer smaller than the prime number n, the first integer r and the second integer s forming the digital signature.
12. The method of claim 11 , wherein computing the private key comprises:
the cryptographic unit computing a message digest e from an integer hash value of the self-signed signature message; and
the cryptographic unit computing the private key d using a formula d=(s k−e)/r mod n.
13. The method of claim 12 , wherein the cryptographic unit computes the public key Q using a formula Q=d G.
14. The method of claim 12 , wherein the cryptographic unit computes the public key Q using a formula Q=(1/r mod n)(sR−eG).
15. The method of claim 11 , wherein the cryptographic unit assigning the integer value comprises:
providing a salt value;
computing a hash value for a pre-determined number of repetitions of a concatenation of the salt value and the ephemeral public key; and
assigning an integer value of the hash value to the first integer r.
16. A non-transitory computer readable medium for generating a private key of a computing device in a communication system, the computing device having a cryptographic unit, the non-transitory computer readable medium having stored thereon computer executable instructions for:
the cryptographic unit generating a pair of signature components, one of the pair of signature components generated from an ephemeral private key, the pair of signature components representing a digital signature of a self-signed signature message to bind the computing device to the self-signed signature message;
the computing device obtaining message data;
the cryptographic unit generating the self-signed signature message based upon the message data and the digital signature;
the cryptographic unit computing the private key based upon the self-signed signature message; and
the cryptographic unit computing a public key based upon the private key such that verification of the self-signed signature message proves that the public key and private key were generated from a key generation process utilizing the self-signed signature message.
17. A computing device comprising a cryptographic unit, the computing device configured to perform a method comprising:
the cryptographic unit generating a pair of signature components, one of the pair of signature components generated from an ephemeral private key, the pair of signature components representing a digital signature of a self-signed signature message to bind the computing device to the self-signed signature message;
the computing device obtaining message data;
the cryptographic unit generating the self-signed signature message based upon the message data and the digital signature;
the cryptographic unit computing the private key based upon the self-signed signature message; and
the cryptographic unit computing a public key based upon the private key such that verification of the self-signed signature message proves that the public key and private key were generated from a key generation process utilizing the self-signed signature message.
18. The computing device of claim 17 , wherein generating the pair of signature components comprises:
the cryptographic unit generating an ephemeral public key;
the cryptographic unit obtaining a salt value; and
the cryptographic unit computing a hash value of a pre-determined number of repetitions of a concatenation of the salt value and the ephemeral public key.
19. The computing device of claim 17 , wherein generating a self-signed signature message based upon the message data and the digital signature comprises concatenating the message data and the pair of signature components into the self-signed signature message, and wherein the computing the private key comprises:
the cryptographic unit computing a message digest from an integer hash value of the self-signed signature message; and
the cryptographic unit computing the private key from the digital signature and the message digest.