Hashing prefix-free values in a signature scheme
Methods, systems, and computer programs for producing hash values are disclosed. A prefix-free value is obtained based on input data. The prefix-free value can be based on an implicit certificate, a message to be signed, a message to be verified, or other suitable information. A hash value is obtained by applying a hash function to the prefix-free value. The hash value is used in a cryptographic scheme. In some instances, a public key or a private key is generated based on the hash value. In some instances, a digital signature is generated based on the hash value, or a digital signature is verified based on the hash value, as appropriate.
1. A computer-implemented method for generating a digital signature to improve security of a message, comprising:
accessing an input message comprising a first message part N and a second message part V;
generating, by data processing apparatus, an encoded message part C based on the input message, wherein generating the encoded message part C comprises:
computing an elliptic curve point Q=zG, where G is an elliptic curve point that represents a base point generator, and z is an integer;
using a key derivation function to derive a key K based on the elliptic curve point Q; and
using an encoding function to compute the encoded message part C based on the key K and the input message;
converting a value C∥V to a prefix-free value, where C∥V represents the encoded message part C concatenated with the second message part V;
obtaining a hash value by applying a hash function to the prefix-free value;
generating a signature based on the hash value and a signer's private key; and
transmitting, over a network, the signature to a recipient.
2. The method of claim 1 , wherein generating the signature comprises computing s=z−d A e(mod n), where s is an integer that represents the signature, e is an integer that represents the hash value, n is an integer that represents the order of G, and d A is an integer that represents the signer's private key.
3. The method of claim 1 , wherein sending the signature comprises sending the signature with the encoded message part C and the second message part V.
4. The method of claim 1 , wherein converting the value C∥V to a prefix-free value comprises:
generating a first value that indicates a length of the value C∥V; and
producing the prefix-free value by prepending the first value to the value C∥V.
5. The method of claim 4 , further comprising dividing the value C∥V into a plurality of blocks, wherein the first value indicates a length of the value C∥V in units of blocks.
6. The method of claim 4 , wherein the first value indicates a length of the value C∥V in units of bytes.
7. The method of claim 1 , wherein converting the value C∥V to a prefix-free value comprises:
dividing the value C∥V into a plurality of blocks, the plurality of blocks including a first plurality of blocks and a last block;
appending a zero bit to each of the first plurality of blocks; and
appending a one bit to the last block.
8. The method of claim 1 , wherein converting the value C∥V to a prefix-free value comprises converting the value C∥V to a format in which the value C∥V has a predetermined length.
9. A computing system for generating a digital signature to improve security of a message, comprising:
memory; and
data processing apparatus operable to:
access an input message comprising a first message part N and a second message part V;
generate an encoded message part C based on the input message, wherein generating the encoded message part C comprises:
computing an elliptic curve point Q=zG, where G is an elliptic curve point that represents a base point generator, and z is an integer;
using a key derivation function to derive a key K based on the elliptic curve point Q; and
using an encoding function to compute the encoded message part C based on the key K and the input message;
convert a value C∥V to a prefix-free value, where C∥V represents the encoded message part C concatenated with the second message part V;
obtain a hash value by applying a hash function to the prefix-free value;
generate a signature based on the hash value and a signer's private key; and
transmit, over a network, the signature to a recipient.
10. The computing system of claim 9 , wherein generating the signature comprises computing s=z−d A e(mod n), where s is an integer that represents the signature, e is an integer that represents the hash value, n is an integer that represents the order of G, and d A is an integer that represents the signer's private key.
11. The computing system of claim 9 , wherein converting the value C∥V to a prefix-free value comprises:
generating a first value that indicates a length of the value C∥V; and
producing the prefix-free value by prepending the first value to the value C∥V.
12. The computing system of claim 9 , wherein converting the value C∥V to a prefix-free value comprises:
dividing the value C∥V into a plurality of blocks, the plurality of blocks including a first plurality of blocks and a last block;
appending a zero bit to each of the first plurality of blocks; and
appending a one bit to the last block.
13. The computing system of claim 9 , wherein converting the value C∥V to a prefix-free value comprises converting the value C∥V to a format in which the value C∥V has a predetermined length.
14. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations for generating a digital signature to improve security of a message, comprising:
accessing an input message comprising a first message part N and a second message part V;
generating an encoded message part C based on the input message, wherein generating the encoded message part C comprises:
computing an elliptic curve point Q=zG, where G is an elliptic curve point that represents a base point generator, and z is an integer;
using a key derivation function to derive a key K based on the elliptic curve point Q; and
using an encoding function to compute the encoded message part C based on the key K and the input message;
converting a value C∥V to a prefix-free value, where C∥V represents the encoded message part C concatenated with the second message part V;
obtaining a hash value by applying a hash function to the prefix-free value;
generating a signature based on the hash value and a signer's private key; and
transmitting, over a network, the signature to a recipient.
15. The computer-readable medium of claim 14 , wherein generating the signature comprises computing s=z−d A e(mod n), where s is an integer that represents the signature, e is an integer that represents the hash value, n is an integer that represents the order of G, and d A is an integer that represents the signer's private key.
16. The computer-readable medium of claim 14 , wherein converting the value C∥V to a prefix-free value comprises:
generating a first value that indicates a length of the value C∥V; and
producing the prefix-free value by prepending the first value to the value C∥V.
17. The computer-readable medium of claim 14 , wherein converting the value C∥V to a prefix-free value comprises:
dividing the value C∥V into a plurality of blocks, the plurality of blocks including a first plurality of blocks and a last block;
appending a zero bit to each of the first plurality of blocks; and
appending a one bit to the last block.
18. The computer-readable medium of claim 14 , wherein converting the value C∥V to a prefix-free value comprises converting the value C∥V to a format in which the value C∥V has a predetermined length.