Implicitly certified digital signatures

• US 10,110,386 B2
• Filed: 05/04/2012
• Issued: 10/23/2018
• Est. Priority Date: 06/10/2011
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Zaverucha, Gregory Marc, Kravitz, David William, Brown, Daniel Richard L.
• Primary Examiner(s): Henning, Matthew T
• Application Number:
  US13/464,007
• Publication Number:
  US 20120317412A1
• Time in Patent Office: 2,363 Days
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model

Abstract

Methods, systems, and computer programs for using an implicit certificate are disclosed. In some aspects, a message and an implicit certificate are accessed. The implicit certificate is associated with an entity. A modified message is generated by combining the message with a value based on the implicit certificate. A digital signature can be generated based on the modified message and transmitted to a recipient. In some aspects, a digital signature from an entity and a message to be verified based on the digital signature are accessed. An implicit certificate associated with the entity is accessed. A modified message is generated by combining the message with a value based on the implicit certificate. The message is verified based on the digital signature and the modified message.

Claims

1. A method of using an implicit certificate in a cryptography system, the method comprising:

receiving, by a first terminal, a first modified message and a digital signature from a second terminal over a data communication network;

obtaining, by the first terminal, an unmodified message associated with the first modified message;

obtaining, by the first terminal, an implicit certificate associated with the second terminal, wherein the implicit certificate includes a public key reconstruction value of the second terminal, the public key reconstruction value of the second terminal is different than a public key of the second terminal, and the public key of the second terminal is reconstructed using the public key reconstruction value of the second terminal and a public key of a certificate authority;

generating, by the first terminal, a hash value based on the implicit certificate;

generating, by the first terminal, a second modified message by combining the unmodified message with the hash value and the public key reconstruction value of the second terminal; and

verifying, by the first terminal, the unmodified message based on the digital signature and the second modified message.

2. The method of claim 1, wherein verifying the unmodified message comprises:

comparing the first modified message to the second modified message.

3. The method of claim 1, wherein obtaining the unmodified message comprises deriving the unmodified message from the first modified message.

4. The method of claim 1, wherein the second modified message is generated by combining the unmodified message with a value based on:

additional information included in the implicit certificate.

5. The method of claim 1, wherein obtaining the implicit certificate comprises accessing an implicit certificate issued by the certificate authority, and the second modified message is generated by combining the unmodified message with a value based on

the public key of the certificate authority.

6. The method of claim 1, wherein obtaining the implicit certificate comprises accessing an implicit certificate issued by a first certificate authority that is subordinate to a second certificate authority, and the second modified message is generated by combining the unmodified message with at least one of:

a public key of the first certificate authority;

a public key of the second certificate authority;

an implicit certificate of the first certificate authority;

or

an implicit certificate of the second certificate authority.

7. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:

accessing, by a first terminal, a first modified message to be verified based on a digital signature, wherein the first modified message and the digital signature are received over a data communication network from a second terminal;

obtaining, by the first terminal, an unmodified message associated with the first modified message;

obtaining, by the first terminal, an implicit certificate associated with the second terminal, wherein the implicit certificate includes a public key reconstruction value of the second terminal, the public key reconstruction value of the second terminal is different than a public key of the second terminal, and the public key of the second terminal is reconstructed using the public key reconstruction value of the second terminal and a public key of a certificate authority;

generating, by the first terminal, a hash value based on the implicit certificate;

generating, by the first terminal, a second modified message by combining the unmodified message with the hash value and the public key reconstruction value of the second terminal; and

verifying, by the first terminal, the unmodified message based on the digital signature and the second modified message.

8. The computer-readable medium of claim 7, wherein verifying the unmodified message comprises:

comparing the first modified message to the second modified message.

9. The computer-readable medium of claim 7, wherein obtaining the implicit certificate comprises accessing an implicit certificate issued by the certificate authority, and the second modified message is generated by combining the unmodified message with a value based on

the public key of the certificate authority.

10. The computer-readable medium of claim 7, wherein obtaining the implicit certificate comprises accessing an implicit certificate issued by a first certificate authority that is subordinate to a second certificate authority, and the second modified message is generated by combining the unmodified message with at least one of:

a public key of the first certificate authority;

a public key of the second certificate authority;

an implicit certificate of the first certificate authority;

or

an implicit certificate of the second certificate authority.