Method for certifying public keys in a digital signature scheme

• US 5,420,927 A
• Filed: 02/01/1994
• Issued: 05/30/1995
• Est. Priority Date: 02/01/1994
• Status: Expired due to Term

• Current Assignee: Assa Abloy AB
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/189,248
• Time in Patent Office: 483 Days
• Field of Search: 380/4, 380/23, 380/21, 380/28, 380/30
• US Class Current: 713/157
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

A method for certifying public keys of a digital signature scheme in a secure communications system is provided. The secure communications system in one in which there are authorities with previously-certified public verification keys. The method begins by having a user U present an authority a verification key PK_U. The authority then identifies the presenting user as U. Thereafter, the authority verifies that the presenting user knows the secret signing key associated with PK_U. If so, the authority computes a digital signature S relative to the authority'"'"'s own public key PK_A of its verification that PK_U is the public key of user U. The authority then issues a certificate that PK_U is the public key of user U, the certificate including both S and a certificate for PK_A.

Claims

1. A method for certifying pieces of data in a secure communications system with at least two levels of authorities, comprising the steps of:

presenting a piece of data requiring certification to a first-level authority for inspection of a given property;

if the piece of data passes the inspection of the first-level authority, having the first-level authority send to a higher authority a digital signature evidencing that the piece of data has passed the inspection of the first-level authority; and

if the digital signature of the first-level authority is correct, having the higher authority issue a certificate, which does not include a signature of the first level authority, that the piece of data possesses the given property.

2. The method of certifying as described in claim 1 wherein the piece of data presented is a verification key of a digital signature scheme.

3. The method of certifying as described in claim 2 wherein the given property of the presented verification key is that a given user has chosen the verification key to be the public key in the digital signature scheme.

4. The method of certifying as described in claim 3 wherein the first-level authority'"'"'s inspection also includes identifying the presenting user.

5. The method of certifying as described in claim 4 wherein the inspection of the presented verification key also includes checking the digital signature of a given message, signed and provided by the user, relative to said verification key.

6. The method of certifying as described in claim 5 wherein the inspection of the presented verification key also includes checking the digital signature of the given message, relative to said verification key, to determine the presenting user is the owner of the presented verification key.

7. The method of certifying as described in claim 3 wherein the first-level authority'"'"'s inspection includes verifying that the presenting user knows a secret signing key associated with the presented verification key.

8. The method of certifying as described in claim 3 wherein the first-level authority'"'"'s inspection includes checking the digital signature of a given message provided by the user relative to the presented verification key.

9. A method for certifying public keys of a digital signature scheme where there is at least one authority A with a certified public verification key PK_A, comprising the steps of:

having a user U present an authority B, having a verification key PK_B, a verification key PK_U together with a message correctly signed with respect to verification key PK_U ;

having authority B identify the presenting user as U;

having authority B verify that the presented digital signature of U is a correct digital signature of the message with respect to the presented verification key PK_U ;

having authority B compute a digital signature S relative to PK_B of the fact that PK_U is a legitimate public key of user U; and

having authority A issue a certificate that PK_U is the public key of user U, which can be verified without a separate certificate for PK_B, the certificate including a certificate for PK_A whenever PK_A is not certified by virtue of being universally known to users of the signature scheme.

10. A method for certifying public keys of a digital signature scheme in a secure communications system where there is at least one authority with a certified public verification key PK_A, comprising the steps of:

having a user U present an authority a verification key PK_U ;

having the authority identify the presenting user as U;

having the authority verify that the presenting user knows the secret signing key associated with PK_U ;

having the authority compute a digital signature S relative to PK_A of the fact that PK_U is the public key of user U; and

having the authority issue a certificate that PK_U is the public key of user U, the certificate including both S and a certificate for PK_A.

11. The method of certifying as described in claim 10 wherein the step of having the authority verify the secret signing key further includes the steps of:

having the user present a message signed with the digital signature of the user according to the private key of the user; and

having the authority verify the message using the public key of the user to verify user knowledge of the private key of the user.

12. The method of certifying as in claim 11 wherein the message comprises a message randomly selected by the authority.

13. The method of certifying as in claim 11 wherein the message comprises:

a first portion selected by the authority; and

a second portion selected by the user.

14. The method of certifying as in claim 11 wherein the message comprises a predetermined message having elements specific to the user.

15. A method for certifying public keys of a digital signature scheme where there are a plurality of authorities A₁, . . . , A_n, where each authority A_i has a secret signing key SK_i and a matching verification key PK_i known to A_i+1, and a verification key of A_n, PK_n, is already certified or universally known to users of a signature scheme, comprising the steps of:

having user U present A₁ a verification key PK_U ;

having authority A₁ verify, by means of a predetermined procedure, that PK_U possesses some properties out of a set of predetermined properties;

for i<

n, having authority A_i send authority A_i+1 at least a properly chosen digital signature, with respect to verification key PK_i, indicating that PK_U has been verified to possess some predetermined properties;

having A_n issue a certificate for PK_U which can be verified to be correct given a certificate for PK_n, which certificate for PK_U does not include at least one certificate for PK_i for some i<

n, but which may include a certificate for PK_n if PK_n is not universally known to the users of the signature scheme.

16. A method for certifying public keys in a digital signature scheme as in claim 15, wherein the predetermined properties include the time at which PK_U has been presented.

17. A method for certifying public keys in a digital signature scheme as in claim 15, wherein the certificate for PK_U includes additional information.

18. A method for certifying public keys in a digital signature scheme as in claim 15, wherein the certificate for the verification key PK_U produced by A_n includes a digital signature sent by authority A₁ to authority A₂.

19. A method for certifying public keys in a digital signature scheme as in claim 15, wherein the certificate for the verification key PK_U produced by A_n includes the digital signature sent by authority A_i to authority A_i+1 for i<

n.

20. A method for certifying public keys in a digital signature scheme as in claim 15, where, for i<

n, each authority A_i+1 stores the digital signatures received by authority A_i.

21. A method for certifying public keys in a digital signature scheme as in claim 15, where, for certifying a given verification key PK_U, whenever j<

i<

n, authority A_i also sends to authority A_i+1 the signature of authority A_j.

22. A method for certifying public keys of a digital signature scheme where there are a plurality of authorities A₁, . . . , A_n, where each i<

n authority A_i can send authority A_i+1 authenticated messages so that at least A_i+1 can be sure that these messages genuinely come from A_i, and authority A_n has a signing key SK_n and an associated public key PK_n, which is either certified or universally known to users of a signature scheme, comprising the steps of;

having a verification key PK_U presented to authority A₁ ;

having authority A₁ verify, by means of a predetermined procedure, that PK_U possesses some properties out of a set of predetermined properties;

for all i<

n, having authority A_i send authority A_i+1 an authenticated message indicating that PK_U has been verified to possess some predetermined properties;

having A_n issue a certificate for PK_U which can be verified valid if PK_n is known to be the public key of authority A_n, and which may include a certificate for PK_n if PK_n is not universally known to the users of the signature scheme, wherein the certificate for PK_U does not include any certificate relative to authority A_i for some i<

n.

23. A method for certifying public keys of a digital signature scheme where there is at least one authority with a certified public verification key PK_A, comprising the steps of:

having a user U present an authority a verification key PK_U together with a message correctly signed with respect to verification key PK_U and indicating that U is the owner of verification key PK_U ;

having the authority identify the presenting user as U;

having the authority verify that the presented digital signature of U is a correct digital signature of the message with respect to the presented verification key PK_U ;

having the authority compute a digital signature S relative to PK_U of the fact that PK_U is a legitimate public key of user U; and

having the authority issue a certificate that PK_U is the public key of user U, the certificate including both S and a certificate for PK_U.