Hashing prefix-free values in a certificate scheme

Patent metadata

Field	Value
Publication number	US-9049022-B2
Application number	US-201213458382-A
Country	US
Kind code	B2
Filing date	Apr 27, 2012
Priority date	Apr 27, 2012
Publication date	Jun 2, 2015
Grant date	Jun 2, 2015

Abstract

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.

First claim

What is claimed is:

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

Assignees

• Zaverucha Gregory Marc
• Kravitz David William
• Certicom Corp

Inventors

• Zaverucha Gregory Marc
• Kravitz David William

Classifications

• H04L9/3066 Primary

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title