Hashing prefix-free values in a certificate 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 comprising:
accessing an implicit certificate associated with an entity;
converting the implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, wherein the converting comprises:
generating a first value that indicates a length of the implicit certificate;
dividing the implicit certificate into a plurality of blocks, wherein the first value indicates a length of the implicit certificate in units of blocks; and
producing the prefix-free value by prepending the first value to the implicit certificate;
obtaining a hash value by applying a hash function to the prefix-free value;
generating, by data processing apparatus, a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U , and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.
2. The method of claim 1 , wherein the first value indicates a length of the implicit certificates in units of bytes.
3. The method of claim 1 , wherein converting the implicit certificate to a prefix-free value comprises converting the implicit certificate to a format in which the implicit certificate has a predetermined length.
4. The method of claim 1 , wherein using the public key for cryptographic correspondence comprises using the public key to encrypt a message to the entity.
5. The method of claim 1 , wherein using the public key for cryptographic correspondence comprises using the public key to authenticate a message from the entity.
6. The method of claim 1 , wherein the method is performed by data processing apparatus associated with the entity.
7. The method of claim 1 , wherein the method is performed by data processing apparatus associated with a certificate authority that issued the implicit certificate.
8. The method of claim 1 , wherein the method is performed by data processing apparatus associated with a correspondent, other than the entity, that validates the public key based on the implicit certificate.
9. A computer-implemented method comprising:
accessing an implicit certificate associated with an entity;
converting the implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, wherein converting the implicit certificate to the prefix-free value comprises:
dividing the implicit certificate 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; and
obtaining a hash value by applying a hash function to the prefix-free value;
generating, by data processing apparatus, a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.
10. A computing system comprising:
a hash module comprising computer-readable instructions on a computing device operable to:
convert an implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, and the implicit certificate is associated with an entity, wherein the hash module is operable to convert the implicit certificate to the prefix-free value by:
generating a first value that indicates a length of the implicit certificate;
dividing the implicit certificate into a plurality of blocks, wherein the first value indicates a length of the implicit certificate in units of blocks; and
producing the prefix-free value by prepending the first value to the implicit certificate; and
obtain a hash value by applying a hash function to the prefix-free value; and
a key generation module operable to generate a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U , and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.
11. The computing system of claim 10 , wherein the hash module is operable to convert the implicit certificate to a prefix-free value by converting the implicit certificate to a format in which the implicit certificate has a predetermined length.
12. A computing system comprising:
a hash module comprising computer-readable instructions on a computing device operable to:
convert an implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, and the implicit certificate is associated with an entity, wherein the hash module is operable to convert the implicit certificate to a prefix-free value by:
dividing the implicit certificate 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; and
obtain a hash value by applying a hash function to the prefix-free value; and
a key generation module operable to generate a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U , and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.
13. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:
converting an implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, and the implicit certificate is associated with an entity, wherein the converting comprises:
generating a first value that indicates a length of the implicit certificate;
dividing the implicit certificate into a plurality of blocks, wherein the first value indicates a length of the implicit certificate in units of blocks; and
producing the prefix-free value by prepending the first value to the implicit certificate;
obtaining a hash value by applying a hash function to the prefix-free value;
generating a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U , and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.
14. The computer-readable medium of claim 13 , wherein converting the implicit certificate to a prefix-free value comprises converting the implicit certificate to a format in which the implicit certificate has a predetermined length.
15. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:
converting an implicit certificate to a prefix-free value in a prefix-free set, wherein none of the values in the prefix-free set is a prefix of any other value in the prefix-free set, and the implicit certificate is associated with an entity, wherein converting the implicit certificate to the prefix-free value comprises:
dividing the implicit certificate 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;
obtaining a hash value by applying a hash function to the prefix-free value;
generating a public key associated with the entity based on the hash value, wherein the public key is an elliptic curve point Q U , and generating the public key includes:
extracting from the implicit certificate an elliptic curve point P U that represents a public key reconstruction value;
accessing an elliptic curve point Q CA that represents a public key of a certificate authority that issued the implicit certificate;
computing the elliptic curve point Q U =eP U +Q CA , where e is the hash value; and
using the public key for cryptographic correspondence.