Key agreement and transport protocol with implicit signatures

• US 5,761,305 A
• Filed: 05/17/1995
• Issued: 06/02/1998
• Est. Priority Date: 04/21/1995
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Qu, Minghua, Menezes, Alfred John, Vanstone, Scott
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/442,833
• Time in Patent Office: 1,112 Days
• Field of Search: 380/21, 380/23, 380/25, 380/30, 380/49, 380/50
• US Class Current: 713/171
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A key establishment protocol between a pair of correspondents includes the generation by each correspondent of respective signatures. The signatures are derived from information that is private to the correspondent and information that is public. After exchange of signatures, the integrity of exchange messages can be verified by extracting the public information contained in the signature and comparing it with information used to generate the signature. A common session key may then be generated from the public and private information of respective ones of the correspondents.

Claims

1. A method of establishing a session key between a pair of correspondents A,B in a public key data communication system to permit exchange of information therebetween over a communication channel, each of said correspondents having a respective private key a,b and a public key p_A, p_B derived from a generator α

and respective ones of said private keys a,b, said method including the steps of;

i) a first of said correspondents A selecting a first random integer x and exponentiating a first function f(α

) including said generator to a power g(x) to provide a first exponentiated function f(α

)^g(x) ;

ii) said first correspondent A generating a first signature s_A from said random integer x said exponentiated function f(α

)^g(x) and said private key a to bind said integer x and said private key a;

iii) said first correspondent A forwarding to a second correspondent B a message including said first exponentiated function f(α

)^g(x) ;

iv) said correspondent B selecting a second random integer y and exponentiating a second function f(α

) including said generator to a power g(y) to provide a second exponentiated function f(α

)^g(y) and generating a signature s_B obtained from said second integer y said second exponentiated function f(α

)^g(y) and said private key b to bind said integer y and said private key b;

v) said second correspondent B forwarding a message to said first correspondent A including said second exponentiated function f(α

)^g(y) ; and

vi) each of said correspondents constructing a session key K by exponentiating information made public by the other correspondent with information that is private to themselves whereby subsequent decryption of information confirms establishment of a common key and thereby the identity of said correspondents.

2. A method of claim 1 wherein said message forwarded by said first correspondent includes an identification of the first correspondent.

3. A method according to claim 1 wherein said message forwarded by said second correspondent includes an identification of said second correspondent.

4. A method according to claim 3 wherein said message forwarded by said first correspondent includes an identification of the first correspondent.

5. A method according to claim 1 wherein said first function f(α

) including said generator is said generator itself.

6. A method according to claim 1 wherein said second function f(α

) including said generator is said generator itself.

7. A method according to claim 6 wherein said first function f(α

) including said generator is said generator itself.

8. A method according to claim 1 wherein said first function f(α

) including said generator includes the public key p_B of said second correspondent.

9. A method according to claim 1 wherein said second function f(α

) including said generator includes the public key p_A of said first correspondent.

10. A method according to claim 1 wherein said signature generated by a respective one of the correspondents combine the random integer, exponentiated function and private key of that one correspondent.

11. A method according to claim 10 wherein said signature S_A of correspondent A is of the form x-r_A aα

^a mod (p-1).

12. A method according to claim 11 wherein said correspondent A selects a second integer x₁ and forwards r_A.sbsb.1 to correspondent B where r_A.sbsb.1 =α

.spsp.x¹ and said correspondent B selects a second random integer y₁ and sends r_B.sbsb.1 to correspondent A, where r_B.sbsb.1 =α

.spsp.y¹ each of said correspondents computing a pair of keys k₁,k₂ equivalent to α

^xy and α

.spsp.x¹.spsp.y¹ respectively, said session key K being generated by XORing k₁ and k₂.

13. A method according to claim 10 wherein said signature S_A of correspondent A is of the form x+aα

^a (p_B)^x mod (p-1).

14. A method according to claim 10 wherein said signature S_A of correspondent A is of the form xr_x.sbsb.1 -(r_a).spsp.r.sbsp.x¹ a mod (p-1) where x₁ is a second random integer selected by A and r_x.sbsb.1 =α

.spsp.x¹.

15. A method according to claim 10 wherein said signature S_B of correspondent B is of the form y_B -r_B bα

^b mod (p-1).

16. A method according to claim 10 wherein said signature S_B of correspondent B is of the form y+bα

^b (p_A)^y mod (p-1).

17. A method according to claim 10 wherein said signature S_B of correspondent B is of the form yr_y.sbsb.1 -(r_B).spsp.r.sbsp.y¹ b mod (p-1) where y₁ is a second integer selected by correspondent B and r_y.sbsb.1 =α

.spsp.y¹.