Method for the application of implicit signature schemes

• US 8,069,347 B2
• Filed: 12/11/2008
• Issued: 11/29/2011
• Est. Priority Date: 06/09/2000
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A.
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): TRUVAN, LEYNNA THANH
• Application Number:
  US12/333,135
• Publication Number:
  US 20090086968A1
• Time in Patent Office: 1,083 Days
• Field of Search: 726 2- 4, 726 17- 19, 726/21, 726 27- 30, 726/263, 713/150, 713/153, 713155-157, 713/161, 713/168, 713175-176, 713/171, 713/180, 380228-229, 380/232, 380/255, 380277-279, 380282-286, 380 44- 47, 380 28- 30, 705/50, 705/53, 705/67, 705/71, 705 75- 76, 705/78, 707/10
• US Class Current: 713/156
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/64 Self-signed certificates
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

A method of verifying a transaction over a data communication system between a first and second correspondent through the use of a certifying authority. The certifying authority has control of a certificate'"'"'s validity, which is used by at least the first correspondent. The method comprises the following steps. One of the first and second correspondents advising the certifying authority that the certificate is to be validated. The certifying authority verifies the validity of the certificate attributed to the first correspondent. The certifying authority generates implicit signature components including specific authorization information. At least one of the implicit signature components is forwarded to the first correspondent for permitting the first correspondent to generate an ephemeral private key. At least one of the implicit signature components is forwarded to the second correspondent for permitting recovery of an ephemeral public key corresponding to the ephemeral private key. The first correspondent signs a message with the ephemeral private key and forwards the message to the second correspondent. The second correspondent attempts to verify the signature using the ephemeral public key and proceeds with the transaction upon verification.

Claims

1. A method for recertifying a correspondent in a computer implemented data communication system through the use of a certifying authority, said certifying authority including a cryptographic unit, said method comprising the steps of:

a) said certifying authority generating a first random number having a value using said cryptographic unit;

b) said certifying authority generating implicit certificate components using said cryptographic unit, said implicit certificate components including a first component generated using said first random number, and a second component generated using said first component and a private key of said certifying authority;

c) said certifying authority publishing a public key of said certifying authority; and

d) said certifying authority making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority;

wherein said certifying authority recertifies said correspondent'"'"'s certificate by changing said value of said first random number using said cryptographic unit.

2. A method as defined in claim 1, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=h(γ

_A∥

ID_A∥

cP)c_i+c_i(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, h indicates a secure hash function, c_i is one of said long term private key of said certifying authority and said first random number, and c_i is the other of said long term private key of said certifying authority and said first random number.

3. The method as defined in claim 2, wherein said second component s_A=h(γ

_A∥

ID_A∥

cP)c+c_A(mod n).

4. The method as defined in claim 2, wherein said second component s_A=h(γ

_A∥

ID_A∥

cP)c_A+c(mod n).

5. A method as defined in claim 1, wherein said correspondent is recertified by forwarding new implicit certificate components with said first random number having said changed value from said certifying authority to said correspondent.

6. A method as defined in claim 1, wherein said first random number has said value for one certification period, said value being changed for others of said certification periods.

7. The method as defined in claim 1, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_A±

ch(ID_A∥

γ

_A)(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

8. The method as defined in claim 1, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_Ah(ID_A∥

γ

_A)±

c(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

9. A certifying authority for recertifying a correspondent in a computer implemented data communication system, said certifying authority including a cryptographic unit for:

a) generating a first random number having a value;

b) generating implicit certificate components including a first component generated using said first random number, and a second component generated using said first component and a private key of said certifying authority;

c) publishing a public key of said certifying authority;

d) making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority; and

e) recertifying said correspondent'"'"'s certificate by changing said value of said first random number.

10. A certifying authority as defined in claim 9, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=h(γ

_A∥

ID_A∥

cP)c_i(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, h indicates a secure hash function, c_i is one of said long term private key of said certifying authority and said first random number, and c_i is the other of said long term private key of said certifying authority and said first random number.

11. The certifying authority as defined in claim 10, wherein said second component S_A=h(γ

_A∥

ID_A∥

cP)c+c_A(mod n).

12. The certifying authority as defined in claim 10, wherein said second component s_A=h(γ

_A∥

ID_A∥

cP)c_A+c(mod n).

13. A certifying authority as defined in claim 9, wherein said correspondent is recertified by forwarding new implicit certificate components with said first random number having said changed value from said certifying authority to said correspondent.

14. A certifying authority as defined in claim 9, wherein said first random number has said value for one certification period, said value being changed for others of said certification periods.

15. The certifying authority as defined in claim 9, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_A+ch(ID_A∥

γ

_A)(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

16. The certifying authority as defined in claim 9, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_Ah(ID_A∥

γ

_A)±

c(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

17. A non-transitory computer-readable medium having stored thereon computer-executable instructions for performing a method for recertifying a correspondent in a computer implemented data communication system through the use of a certifying authority, said certifying authority including a cryptographic unit, said computer-executable instructions comprising instructions to perform the steps of:

a) said certifying authority generating a first random number having a value using said cryptographic unit;

b) said certifying authority generating implicit certificate components using said cryptographic unit, said implicit certificate components including a first component generated using said first random number, and a second component generated using said first component and a private key of said certifying authority;

c) said certifying authority publishing a public key of said certifying authority; and

d) said certifying authority making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority;

wherein said computer-executable instructions further comprise instructions for recertifying said correspondent'"'"'s certificate by changing said value of said first random number using said cryptographic unit.

18. A non-transitory computer-readable medium as defined in claim 17, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=h(γ

_A∥

ID_A∥

cP)c_i (mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent. h indicates a secure hash function, c_i is one of said long term private key of said certifying authority and said first random number, and c_i is the other of said long term private key of said certifying authority and said first random number.

19. The non-transitory computer-readable medium as defined in claim 18, wherein said second component s_A=h(γ

_A∥

ID_A∥

cP)c+c_A(mod n).

20. The non-transitory computer-readable medium as defined in claim 18, wherein said second component s_A=h(γ

_A∥

ID_A∥

cP)c_A+c(mod n).

21. A non-transitory computer-readable medium as defined in claim 17, wherein said correspondent is recertified by forwarding new implicit certificate components with said first random number having said changed value from said certifying authority to said correspondent.

22. A non-transitory computer-readable medium as defined in claim 17, wherein said first random number has said value for one certification period, said value being changed for others of said certification periods.

23. The non-transitory computer-readable medium as defined in claim 17, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_A±

ch(ID_A∥

γ

_A(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

24. The non-transitory computer-readable medium as defined in claim 17, wherein c_A is said first random number generated by said certifying authority and:

a) said first component is γ

_A, where γ

_A=aP+c_AP, and where aP is a long term public key of said correspondent and P is a point on a curve; and

b) said second component is s_A, where s_A=c_Ah(ID_A∥

γ

_A)±

c(mod n), and where c is a long term private key of said certifying authority, n is a large prime number, ID_A is an identifier of said correspondent and includes at least one distinguishing feature of said correspondent, and h indicates a secure hash function.

25. A method for recertifying a correspondent in a computer implemented data communication system through the use of a certifying authority, said certifying authority including a cryptographic unit, said method comprising the steps of:

a) said certifying authority generating a first random number using said cryptographic unit;

b) said certifying authority generating implicit certificate components using said cryptographic unit, said implicit certificate components including a first component generated using said first random number, and a second component generated using said first component, a private key of said certifying authority, and a second random number;

c) said certifying authority publishing a public key of said certifying authority; and

d) said certifying authority making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority;

wherein said certifying authority recertifies said correspondent'"'"'s certificate by changing said second random number using said cryptographic unit.

26. A method as defined in claim 25, wherein k_i is said second random number generated by said certifying authority for an ith certification period and said second component is s_Ai=r_ic+k_i+c_A(mod n), where n is a large prime number, c is a long term private key of said certifying authority, c_A is said first random number, and r_i=h(γ

_A∥

ID_A∥

cP∥

k_iP∥

i), where ID_A includes at least one distinguishing feature of said correspondent, P is a point on a curve, and h indicates a secure hash function; and

wherein said first component is γ

_A=aP+c_AP, where aP is a long term public key of said correspondent.

27. A method as defined in claim 25, wherein said correspondent is recertified by forwarding from said certifying authority to said correspondent a new second component with said second random number having said changed value.

28. A certifying authority for recertifying a correspondent in a computer implemented data communication system, said certifying authority including a cryptographic unit for:

a) generating a first random number;

b) generating implicit certificate components including a first component generated using said first random number, and a second component generated using said first component, a private key of said certifying authority, and a second random number;

c) publishing a public key of said certifying authority;

d) making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority; and

e) recertifying said correspondent'"'"'s certificate by changing said second random number.

29. A certifying authority as defined in claim 28, wherein k_i is said second random number generated by said certifying authority for an ith certification period and said second component is s_Aj=r_ic+k_i+c_A(mod n), where n is a large prime number, c is a long term private key of said certifying authority, c_A is said first random number, and r_ih(γ

_A∥

ID_A∥

cP∥

k_iP∥

i), where ID_A includes at least one distinguishing feature of said correspondent, P is a point on a curve, and h indicates a secure hash function; and

wherein said first component is γ

_A=aP+c_AP, where aP is a long term public key of said correspondent.

30. A certifying authority as defined in claim 28, wherein said correspondent is recertified by forwarding from said certifying authority to said correspondent a new second component with said second random number having said changed value.

31. A non-transitory computer-readable medium having stored thereon computer-executable instructions for recertifying a correspondent in a computer implemented data communication system through the use of a certifying authority, said certifying authority including a cryptographic unit, said computer-executable instructions comprising instructions for performing the steps of:

a) said certifying authority generating a first random number using said cryptographic unit;

b) said certifying authority generating implicit certificate components using said cryptographic unit, said implicit certificate components including a first component generated using said first random number, and a second component generated using said first component, a private key of said certifying authority, and a second random number;

c) said certifying authority publishing a public key of said certifying authority; and

d) said certifying authority making available said implicit certificate components to enable said correspondent to generate a new private key using said second component and to enable the construction of a new public key using said first component and said public key of said certifying authority;

wherein said computer-executable instructions further comprise instructions for recertifying said correspondent'"'"'s certificate by changing said second random number using said cryptographic unit.

32. A non-transitory computer-readable medium as defined in claim 31, wherein k_i is said second random number generated by said certifying authority for an ith certification period and said second component is s_Ai=r_ic+k_i+c_A(mod n), where n is a large prime number, c is a long term private key of said certifying authority, c_A is said first random number, and r_i=h(γ

_A∥

ID_A∥

cP∥

k_iP∥

i), where ID_A includes at least one distinguishing feature of said correspondent, P is a point on a curve, and h indicates a secure hash function; and

wherein said first component is γ

_A=aP+c_AP, where aP is a long term public key of said correspondent.

33. A non-transitory computer-readable medium as defined in claim 31, wherein said correspondent is recertified by forwarding from said certifying authority to said correspondent a new second component with said second random number having said changed value.