Two-way public key authentication and key agreement for low-cost terminals

• US 5,299,263 A
• Filed: 03/04/1993
• Issued: 03/29/1994
• Est. Priority Date: 03/04/1993
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Beller, Michael J., Yacobi, Yacov
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/026,673
• Time in Patent Office: 390 Days
• Field of Search: 380/23, 380/25, 380/30, 380/49, 380/21, 380/24, 380/43, 380/29, 340/825.31, 340/825.34, 235/380, 379/95
• US Class Current: 380/30
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: H04L 63/0869 for achieving mutual authentication cryptographic mechanisms or cryptographic arrangements for mutual authentication H04L9/3273
• 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/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A method for achieving mutual authentication and session key agreement between a first party 12 which has minimal computational resources and a second party 18 which has substantial computational resources utilizes a modular square root operation for certificate authentication and key distribution and an ElGamal, NIST DSS, or other efficient signature operation for obtaining the signature of a message. These operations are highly advantageous in a system with asymmetric resources because the computation power required to perform these operations is far less than the computation power required to invert these operations. The entire mutual authentication and session key agreement method can be carried out using only three modular multiplications on the weak computational side.

Claims

1. A method for achieving mutual identification and session key agreement between a terminal and a server at the start of communication session comprising the steps of

(a) transmitting from the server to the terminal an identity j of the server, public key N_j of the server and a certificate C_j of the server which certificate C_j, if valid, is congruent to √

h(j, N_j)mod N_u where N_j is a public key of the server, N_u is a public key of a central authority, and h() signifies a one-way hashing function,

(b) at the terminal, verifying that said transmitted certificate C_j received at the terminal satisfies h(j, N_j)≡

c_j² mod N_u,

(c) at the terminal, choosing a random number x≡

(x_L x_R) and obtaining y≡

x² mod N_j and transmitting y to said server,

(d) at said server, performing the modular square root operation to obtain x=(x_L, x_R)≡

√

y mod N by using secret keys of the server p_j,qj, such that N_j =p_j q_j, and transmitting x_L back to the terminal,

(e) transmitting, from the terminal to the server, an identity i of the terminal, a public key P_i of the terminal, and a certificate c_i of the terminal which certificate c_i, if valid, is congruent to √

h(i,P_i) mod N_u, wherein the identity i, the public key P_i and the certificate c_i are encrypted using x_R as a session key,

(f) at the server, verifying that the received certificate c_i satisfies h(i,P_i)≡

C_i² mod N_u,

(g) computing at the terminal a signature S(m) based on a challenge message m sent by the server by applying an asymmetric signature operation to said challenge message m, and transmitting the signature to the server in encrypted form using x_R as a session key, and

(h) verifying the signature at the server.

2. The method of claim 1 wherein said signature s(m) is given by the ordered pair (v,w) for which:

space="preserve" listing-type="equation">P.sub.i.sup.v v.sup.w ≡

α

.sup.m mod N.sub.s

where

P_i is said public key of the terminal,

N_s is a signature modulus which is a prime number or the product of two prime numbers,

α

is a generator in the maximal cyclic subgroup of the multiplicative group of integers modulo N_s /Z*_ns.

3. The method of claim 2 wherein said step of evaluating a signature s(m) on a message m comprises

performing the real time operation

4. The method of claim 3 wherein the value of r is chosen randomly each time the terminal evaluates a signature

5. The method of claim 3 wherein a terminal i has a separate signature modulus N_iS and wherein the certificate of the terminal i is of the form c_i =√

h(i,p_i, N_iS) mod N_u.

6. The method of claim 1 wherein said signature operation is an ElGamal signature operation.

7. The method of claim 1 wherein said signature S(m) is computed according to the National Institute of Standards and Technology Digital Signature Standard Algorithm.

8. The method of claim 1 wherein said communication session is aborted if the certificate c_j received at said terminal does not satisfy c_j² mod N_u =h(j,N_j).

9. The method of claim 1 wherein said communication session is aborted if the certificate c_j received at the server does not satisfy c_i² mod N_u =h(i,P_i).

10. The method of claim 1 wherein said terminal is a terminal of a portable communications system and said server is a port control unit of said portable communication system.

11. The method of claim 10 wherein said terminal is a portable telephone.

12. The method of claim 1 wherein the terminal is a smart card and the server is a smart card base unit.

13. The method of claim 1 wherein the terminal is an Analog Display Service Interface (ADSI) terminal and said server is an ADSI network cryptoserver.

14. The method of claim 1 wherein said terminal is computationally weaker than said server.

15. The method of claim 13 wherein said initialization step further comprises selecting said secret key s_i and generating the corresponding public key p_i, forming the certificate c_i at the central authority and transmitting the certificate c_i to the terminal, and transmitting the public key N_u of the central authority to the terminal.

16. The method of claim 1 wherein prior to any communication session said server is initialized by selecting for the server its secret key p_j q_j, and its public key N_j =p_j q_j transmitting the public key N_j to the central authority, forming the certificate c_j at the central authority and transmitting the certificate c_j to the server, and transmitting said public key N_u from said central authority to said server and storing the key N_u at said server.

17. The method of claim 1 further comprising the step of, at the server, identifying the proper root when computing √

y mod N_j by providing said random number with color.

18. A method for achieving mutual authentication and session key agreement between a server and a terminal comprising the steps of

(a) transmitting a certificate of said server from said server to said terminal,

(b) verifying the authenticity of said certificate of said server at said terminal,

(c) distributing a session key to said terminal and server by selecting a random number x at said terminal, encrypting sad umber x at said terminal by performing at said terminal an asymmetric public key operation which can only be inverted with the knowledge of a secret key of said server,

(d) transmitting said number x in encrypted form from said terminal to said server and inverting said operation suing said secret key of said server to obtain x at said server,

(e) transmitting a certificate of said terminal from said terminal to said server encrypted using a session key, wherein said session key is based on said number x,

(f) verifying the authenticity of said terminal certificate at said server,

(g) evaluating a signature S(m) of a message m at said terminal using an asymmetric signature operation, and

(h) transmitting the signature to said server in encrypted form using said session key and inverting the signature operation at said server.

19. The method of claim 18 wherein said step (a) comprises transmitting from said server to said terminal an identity j of said server, a public key N_j of said server and a certificate c_j which if valid is of the form c_j ≡

√

h(j,N_j) mod N_u where N_u is a public key of a central authority.

20. The method of claim 19 wherein said step (b) comprises determining if h(j,N_j)≡

c_j² mod N_u.

21. The method of claim 18 wherein said asymmetric public key operation is y≡

c_j² mod N_j, where N_j is a public key of the server.

22. The method of claim 21 wherein s=(x_L, x_R), wherein x_R is said session key, and wherein x is provided with color which is used at said server to identify the proper root of x² mod N_j.

23. The method of claim 18 wherein said step (e) comprises transmitting an identity i of said terminal, a public key P_i of said terminal and a certificate c_i of said terminal which if valid is of the form c_i ≡

√

h(i,P_i) mod N_u.

24. The method of claim 23 wherein said step (f) comprises determining if h(i,P_i)≡

c_i² mod N_u.

25. The method of claim 18 wherein said signature operation is an ElGamal signature operation.

26. A method for achieving mutual authentication and session key agreement between a first party and a second party at the start of a communication session comprising the steps of

(a) distributing a session key between said parties by selecting a random number at said first party, encrypting said random number using an asymmetric public key encryption operation, transmitting the encrypted random number to the second party, and inverting said encryption operation at said second party to obtain said random number, and

(b) at said first party, performing an asymmetric signature operation on a message m to obtain a signature S(m), encrypting said signature S(m) using an encipherment function and a session key which is based on said random number, and transmitting the encrypted signature S(m) to said second party, and at said second party, decrypting said signature S(m) and inverting said signature operation.

27. The method of claim 26 wherein said public key encryption operation comprises squaring said random number utilizing only a single modular multiplication at said first party.

28. The method of claim 26 wherein said signature operation is an ElGamal signature operation which utilizes only a single real time modular multiplication at said first party.

29. The method of claim 26 further comprising the step of authenticating a certificate of said second party at said first party by performing only a single modular multiplication at said first party.

30. The method of claim 26 further comprising the step of authenticating a certificate of said first party at said second party.

31. The method of claim 26 wherein said second party has more computational resources than said first party.

32. The method of claim 31 wherein the terminal is an Analog Display Server Interface (ADSI) and the server is an ADSI network crypto server.

33. The method of claim 26 wherein said first party is a terminal of a portable communication system and the second party is a port control unit of the portable communication system.

34. The method of claim 26 wherein the first party is a terminal and the second party is a server.

35. The method of claim 34 wherein said terminal is a smart card and said server is a smart card base unit.

36. The method of claim 26 wherein the first party is a server and the second party is a terminal or workstation.

37. A method for achieving mutual authentication and session key agreement between first and second parties communicating via a communication medium comprising:

(a) transmitting a certificate of said second party for said second party to said first party,

(b) verifying the authenticity of said certificate of said second party at said first party,

(c) distributing a session key to said first and second parties by selecting a random number x at said first party, encrypting said number x at said first party by performing at said first party an asymmetric public key operation which can only be inverted with the knowledge of a secret key of said second party,

(d) transmitting said number x in encrypted from said first party to said second party and inverting said operation using said secret key of said second party,

(e) transmitting a certificate of said first party from said first party to said second party encrypted using a session key based on said number x,

(f) verifying the authenticity of said certificate of said first party at said second party,

(g) evaluating a signature S(m) of a message m at said first party using an asymmetric signature operation,

(h) transmitting the signature to said second party in encrypted form using said session key and inverting the signature operation at the second party.