ISSUING IMPLICIT CERTIFICATES

• US 20120233457A1
• Filed: 03/08/2011
• Published: 09/13/2012
• Est. Priority Date: 03/08/2011
• Status: Abandoned Application

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Zaverucha, Gregory Marc
• Application Number:
  US13/043,311
• Publication Number:
  US 20120233457A1
• Time in Patent Office: Days
• US Class Current: 713/156
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• 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/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

Methods, systems, and computer programs for issuing an implicit certificate are disclosed. In some implementations, a certificate authority of an elliptic curve cryptography (ECC) system performs one or more operations for issuing the implicit certificate. A certificate request associated with a requester is received, and the certificate request includes a first element R_U in a group. In response to receiving the request, a second element P_U in the group is generated based on the first element R_U. An implicit certificate Cert_U is generated based on the second element P_U. Whether the public key Q_U of the requester corresponds to a trivial public key, such as an identity element of the group, can be determined. For example, the certificate authority can compute the public key Q_U of the requester based on the first element P_U, the implicit certificate Cert_U, and a public key Q_CA of the certificate authority.

Claims

1. A method for issuing an implicit certificate at a certificate authority of an elliptic curve cryptography system, the method comprising:

receiving a certificate request associated with a requester, the certificate request comprising a first point R_U in an elliptic curve group;

generating a second point P_U in the elliptic curve group in response to receiving the request and based on the first point R_U;

generating an implicit certificate Cert_U based on the second point P_U; and

determining whether a public key Q_U of the requester corresponds to an identity element of the elliptic curve group based on the second point P_U, the implicit certificate Cert_U, and a public key Q_CA of the certificate authority.

2. The method of claim 1, further comprising generating a hash value e based on the implicit certificate Cert_U, wherein determining whether the public key Q_U corresponds to the identity element comprises determining whether the public key Q_U corresponds to the identity element based on the second point P_U, the hash value e, and the public key Q_CA of the certificate authority.

3. The method of claim 2, wherein determining whether the public key Q_U corresponds to the identity element comprises:

generating the public key Q_U by computing eP_U+Q_CA; and

comparing the public key Q_U to the identity element.

4. The method of claim 2, further comprising:

receiving elliptic curve domain parameters that identify the elliptic curve group and a base point generator G in the elliptic curve group;

selecting a value k; and

generating a third point kG in the elliptic curve group, wherein generating the second point P_U comprises computing R_U+kG.

5. The method of claim 4, wherein when the public key Q_U corresponds to the identity element, the method further comprises:

selecting another value k′

;

generating a fourth point k′

G in the elliptic curve group;

generating a fifth point P_U′

in the elliptic curve group by computing R_U+k′

G;

generating a new implicit certificate Cert_U′

based on the fifth point P_U′

; and

determining whether a new public key Q_U′

of the requester corresponds to an identity element of the elliptic curve group based on the fifth point P_U′

, the new implicit certificate Cert_U′

, and the public key Q_CA of the certificate authority.

6. The method of claim 4, wherein when the public key Q_U does not correspond to the identity element, the method further comprises generating private key contribution data r based on the hash value e, the value k, and a private key of the certificate authority d_CA.

7. The method of claim 6, further comprising sending a response to the requester, the response comprising the implicit certificate Cert_U and the private key contribution data r.

8. The method of claim 1, further comprising determining whether the public key Q_U corresponds to a public key associated with another entity in the cryptography system.

9. The method of claim 1, further comprising publishing the implicit certificate Cert_U.

10. The method of claim 1, wherein the request further comprises an identification U associated with the requester, and generating the implicit certificate Cert_U comprises generating the implicit certificate Cert_U based on the second point P_U and the identification U.

11. The method of claim 10, further comprising obtaining certificate data I_U comprising the user identification U and additional information, wherein generating the implicit certificate Cert_U comprises generating the implicit certificate Cert_U based on the second point P_U and the certificate data I_U.

12. The method of claim 1, wherein generating the implicit certificate Cert_U comprises encoding the second point P_U in the implicit certificate Cert_U according to an implicit certificate encoding scheme.

13. A system comprising a certificate authority server, the certificate authority server comprising data processing apparatus operable to perform operations for issuing an implicit certificate, the operations comprising:

receiving a certificate request associated with a requester, the certificate request comprising a first point R_U in an elliptic curve group;

generating a second point P_U in the elliptic curve group in response to receiving the request and based on the first point R_U;

generating an implicit certificate Cert_U based on the second point P_U; and

determining whether a public key Q_U of the requester corresponds to an identity element of the elliptic curve group based on the second point P_U, the implicit certificate Cert_U, and a public key Q_CA of the certificate authority.

14. The system of claim 13, the operations further comprising generating a hash value e based on the implicit certificate Cert_U, wherein determining whether the public key Q_U corresponds to the identity element comprises determining whether the public key Q_U corresponds to the identity element based on the second point P_U, the hash value e, and the public key Q_CA of the certificate authority.

15. The system of claim 14, wherein determining whether the public key Q_U corresponds to the identity element comprises

generating the public key Q_U by computing eP_U+Q_CA;

and

comparing the public key Q_U to the identity element.

16. The system of claim 13, the operations further comprising:

receiving elliptic curve domain parameters that identify the elliptic curve group and a base point generator G in the elliptic curve group;

selecting a value k; and

generating a third point kG in the elliptic curve group, wherein generating the second point P_U comprises computing R_U+kG.

17. The system of claim 16, the operations further comprising:

generating private key contribution data r based on the hash value e, the value k, and a private key of the certificate authority d_CA; and

sending a response to the requester, the response comprising the implicit certificate Cert_U and the private key contribution data r.

18. The system of claim 17, further comprising a terminal associated with the requester, the terminal comprising data processing apparatus operable to perform operations comprising:

generating the certificate request; and

sending the certificate request to the certificate authority server.

19. The system of claim 18, the data processing apparatus of the terminal operable to perform operations further comprising receiving the response from the certificate authority server.

20. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations for issuing an implicit certificate, the operations comprising:

receiving a certificate request associated with a requester, the certificate request comprising a first point R_U in an elliptic curve group;

generating a second point P_U in the elliptic curve group in response to receiving the request and based on the first point R_U;

generating an implicit certificate Cert_U based on the second point P_U; and

determining whether a public key Q_U of the requester corresponds to an identity element of the elliptic curve group based on the second point P_U, the implicit certificate Cert_U, and a public key Q_CA of the certificate authority.

21. The computer-readable medium of claim 20, the operations further comprising generating a hash value e based on the implicit certificate Cert_U, wherein determining whether the public key Q_U corresponds to the identity element comprises determining whether the public key Q_U corresponds to the identity element based on the second point P_U, the hash value e, and the public key Q_CA of the certificate authority.

22. The computer-readable medium of claim 21, wherein determining whether the public key Q_U corresponds to the identity element comprises:

generating the public key Q_U by computing eP_U+Q_CA; and

comparing the public key Q_U to the identity element.

23. The computer-readable medium of claim 21, the operations further comprising:

receiving elliptic curve domain parameters that identify the elliptic curve group and a base point generator G in the elliptic curve group;

selecting a value k; and

generating a third point kG in the elliptic curve group, wherein generating the second point P_U comprises computing R_U+kG.

24. The computer-readable medium of claim 20, the operations further comprising determining whether the public key Q_U corresponds to a public key associated with another entity in the cryptography system.

25. The computer-readable medium of claim 20, the operations further comprising publishing the implicit certificate Cert_U.

26. The computer-readable medium of claim 20, wherein the certificate further comprises an identification U associated with the requester, and generating the implicit certificate Cert_U comprises generating the implicit certificate Cert_U based on the second point P_U and the identification U.