Cryptographic method for key agreement and user authentication

• US 5,222,140 A
• Filed: 11/08/1991
• Issued: 06/22/1993
• Est. Priority Date: 11/08/1991
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Chang, Li Fung, Yacobi, Yacov, Beller, Michael J.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US07/789,700
• Time in Patent Office: 592 Days
• Field of Search: 380/9, 380/21, 380/30, 380/43, 380/49, 380/50, 380/23, 379/61, 379/62, 379/95, 340/825.31, 340/825.34
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• 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/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

Protocols for session key agreement and authentication in a communication system such as a portable communication system make use of public key cryptographic techniques. The protocols of the present invention are especially suited for use in a portable communication system because portable telephones are required by the inventive protocols to perform only a minimal amount of processing, while assigning the heavier computations to the network. The inventive protocols also authenticate the weaker (i.e. portable) side. The protocols also ensure that a third party cannot trace the location of a user by eavesdropping on a radio signal transmitted by a portable telephone.

Claims

1. A method for enabling a user terminal i and a network access unit j in a communication system to choose a session key for a communication session comprising the steps of:

at the start of a communication session, transmitting a public key from the network access unit to the user terminal via a communication channel,

at the user terminal, utilizing an electronic device to select a number x and to perform a public operation on the number x utilizing the public key received from the network access unit,

transmitting via said communication channel the result of said public operation from said user terminal to said network access unit, and

at said network access unit, performing a secret operation on said result utilizing a secret key of the network access unit to invert said public operation to compute the number x.

2. The method of claim 1 wherein the number x is said session key.

3. The method of claim 1 wherein said public key of said network access unit includes a modulus N:

and said secret key of said network access unit includes the prime numbers p_j and q_j, where N_j =p_j q_j.

4. The method of claim 3 wherein said public operation is e₁ =x² mod N_j where e₁ is said result, and said secret operation is x=√

e₁ mod N_j.

6. The method of claim 1 Wherein said method further comprises the step of authenticating said user terminal at said network access unit.

7. The method of claim 6 wherein said step of authenticating said user terminal comprises

transmitting from said user terminal to said network access unit a linkage including public identification information of the user terminal and an authentication certificate, which if legitimate, is the result of utilizing a secret certification key to perform a secret certification operation on a function of said linkage, and

at said network access unit, utilizing a public certification key to perform a public certification operation to invert said secret certification operation and determining if the result of said inversion is identical to said function of said linkage.

8. The method of claim 1 wherein said method further comprises the step of authenticating said network access unit to said user terminal.

9. The method of claim 8 wherein said authenticating step comprises

transmitting from said network access unit to said user terminal a linkage including public identification information of the network access unit, and an authentication certificate which is the result of utilizing a secret certification key to perform a secret certification operation on a function of said linkage, and

at said terminal, utilizing a public certification key to perform a public certification operation to invert said secret certification operation and determining if the result of the inversion is identical to said function of said linkage.

10. The method of claim 1 wherein said user terminal is a portable telephone of a portable communication system, said communication channel is a radio link, and said network access unit is a port control unit of said portable communication system.

11. The method of claim 1 wherein said public operation is a one-way trapdoor function.

5. The method of claim I wherein said user terminal has a secret key S_i and a public key P_i and wherein said network access unit has a further secret key S_j and a further public key P_j such that P_j^Si ≡

P_i^Sj mod N, where N is a modulus and wherein said method further comprises the steps of

transmitting P_j to said user terminal,

transmitting P_i to said network access unit,

evaluating at said user terminal η

≡

P_j^Si mod N and determining a session key sk=f(x,η

) where f is an encipherment function,

evaluating at said network access unit η

≡

P_i^Sj mod N and determining said session key sk=f(x,η

) whereby both said network access unit and said user terminal are in possession of said session key sk.

12. A method for enabling a user terminal and a network access unit in a communication system to choose a session key for a communication session comprising the steps of

at the start of a communication session, transmitting via a communication channel from a network access unit to a user terminal a modulus N_j, N_j =p_j Q_j, where p_j and q_j are large prime numbers known only to the network access unit j,

utilizing an electronic device at the user terminal to select a number x and to evaluate a quantity e₁ =y(x) mod N_j, where y(x) is a function which is hard to invert without knowledge of the factors p_j and q_j,

transmitting via said communication channel the quantity e₁ from said user terminal to said network access unit,

at said network access unit, determining x=y^-1 (e₁) mod N_j, whereby the number x is now known to said user terminal and said network access unit, and

utilizing said number x as a session key to send encrypted messages between said user terminal and said network access unit.

13. The method of claim 12 wherein said method further comprises the steps of

utilizing an electronic processor comprising part of said user terminal to generate a plain text message m which includes i and c_i where i is an identification number of said user terminal and c_i is a certificate of said user terminal,

encrypting said plain text message m at said user terminal utilizing an encipherment function f to obtain an encrypted message e₂ =f(x,m),

transmitting said encrypted message e₂ via said communication channel from said user terminal to said network access unit, and

authenticating that the user terminal is a legitimate user of said communication system by decrypting said message e₂ and determining if c_i² mod N_u equals g(i), where N_u is a certification modulus and g(i) is a one way function which expands its argument to the size of the modulus N .

14. The method of claim 12 wherein said method includes authenticating said network access unit to said user terminal by the steps of

at the start of said communication session, transmitting from said network access unit to said user terminal, in addition to said modulus N_j, a certificate c_j of said network access unit and the identification number j of the network access unit, and

authenticating said network access unit at said user terminal by utilizing an electronic processor comprising part of said user terminal to determine if h(j,N_j) equals c_j² mod N_u, where h is a hashing function.

15. The method of claim 12 wherein y(x) mod N_j equals x² mod N_j and y^-1 (e₁) mod N_j equal √

e₁ mod N_j.

16. The method of claim 15 wherein said number x is utilized by said user terminal and said network access unit to determine a session key for said communication system.

17. The method of claim 12 wherein said communication system is a portable communication system, said user terminal is a portable telephone, said communication channel is a radio link, and said network access unit is a port control unit.

18. A method for enabling a user terminal and a network access unit in a communication system to choose a session key for a communication session comprising the steps of:

at the start of a communication session, transmitting via a communication channel from the network access unit to the user terminal a public key of said network access unit,

at said user terminal, utilizing an electronic processor to select a number x and to generate a quantity e₁ =y(x) where y(x) is a function that is evaluated utilizing said public key and that is hard to invert without knowledge of a secret key known only to said network access unit,

transmitting via said communication channel said quantity e₁ from said user terminal to said network access unit, and

at said network access unit, determining x=y^-1 (e₁) utilizing said secret key, whereby said number x is now known to said user terminal and said network access unit.

19. The method of claim 18 wherein said number x is utilized as a session key by said user terminal and said network access unit.

20. The method of claim 18 wherein said method includes the step of authenticating the identity of said user terminal to said network access unit.

21. The method of claim 18 wherein said method includes the step of authenticating the identity of said network access unit to said user terminal.

22. The method of claim 18 wherein y(x) equals x² mod N, N=p.q, where N is said public key, and p and q are large prime numbers which form said secret key.

23. The method of claim 18 wherein said communication system is a portable communication system, said communication channel is a radio link, said network access unit is a port control unit and a user terminal is a portable telephone.