Cryptographic protocol for secure communications

• US 5,241,599 A
• Filed: 10/02/1991
• Issued: 08/31/1993
• Est. Priority Date: 10/02/1991
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Merritt, Michael, Bellovin, Steven M.
• Primary Examiner(s): CAIN, DAVID C
• Application Number:
  US07/770,064
• Time in Patent Office: 699 Days
• Field of Search: 380/44, 380/21, 380/30, 380/28
• US Class Current: 713/171
• 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

Abstract

A cryptographic communication system. The system, which employs a novel combination of public and private key cryptography, allows two parties, who share only a relatively insecure password, to bootstrap a computationally secure cryptographic system over an insecure network. The system is secure against active and passive attacks, and has the property that the password is protected against offline "dictionary" attacks. If Alice and Bob are two parties who share the password P one embodiment of the system involves the following steps: (1) Alice generates a random public key E, encrypts it with P and sends P(E) to Bob; (2) Bob decrypts to get E, encrypts a random secret key R with E and sends E(R) to Alice; (3) Alice decrypts to get R, generates a random challenge C_A and sends R(C_A) to Bob; (4) Bob decrypts to get C_A, generates a random challenge C_B and sends R(C_A, C_B) to Alice; (5) Alice decrypts to get (C_A, C_B), compares the first against the challenge and sends R(C_B) to Bob if they are equal; (6) Bob decrypts and compares with the earlier challenge; and (7) Alice and Bob can use R as a shared secret key to protect the session.

Claims

1. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

forming an outgoing signal by encrypting at least a portion of an excitation signal with a second symmetric key cryptosystem using a key based on said authentication signal, said excitation signal being based on a first signal, R_A ;

transmitting said outgoing signal to one of said parties;

receiving a response signal, Q, in response to said outgoing signal; and

generating said cryptographic key based on said first signal and on said response signal.

2. The method of claim 1 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

3. The method of claim 1 wherein said step of forming an excitation signal comprises the step of setting said excitation signal to α

^R.sbsp.A moduloβ

, where α and

β

are numbers.

4. The method of claim 3 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to Q^R.sbsp.A moduloβ

.

5. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

forming an excitation signal based on a first signal, R_A ;

transmitting said excitation signal;

receiving an incoming signal from one of said parties in response to said excitation signal;

forming a response signal, Q, by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal; and

generating said cryptographic key based on said first signal and on said response signal.

6. The method of claim 5 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

7. The method of claim 5 wherein said step of forming an excitation signal comprises the step of setting said excitation signal to α

^R.sbsp.A moduloβ

, where α and

β

are numbers.

8. The method of claim 7 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to Q^R.sbsp.A moduloβ

.

9. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

forming an outgoing signal by encrypting at least a portion of an excitation signal with a second symmetric key cryptosystem using a key based on said authentication signal, said excitation signal being based on a first signal, R_A ;

transmitting said outgoing signal to one of said parties;

receiving an incoming signal from one of said parties in response to said outgoing signal;

forming a response signal, Q, by decrypting said incoming signal with a third symmetric key cryptosystem using a key based on said authentication signal; and

generating said cryptographic key based on said first signal and on said response signal.

10. The method of claim 9 wherein said first symmetric key cryptosystem, said second symmetric key cryptosystem and said third symmetric key cryptosystem are identical.

11. The method of claim 9 wherein said step of forming an excitation signal comprises the step of setting said excitation signal to α

^R.sbsp.A moduloβ

, where α and

β

are numbers.

12. The method of claim 11 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to Q^R.sbsp.A moduloβ

.

13. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving an incoming signal from one of said parties;

forming an excitation signal, S, by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal;

forming a response signal based on a first signal, R_B ;

transmitting said response signal; and

generating said cryptographic key based on said excitation signal and on said first signal.

14. The method of claim 13 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

15. The method of claim 13 wherein said step of forming a response signal comprises the step of setting said response signal to α

^R.sbsp.B moduloβ

, where α and

β

are numbers.

16. The method of claim 15 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to S^R.sbsp.B moduloβ

.

17. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving an excitation signal, S;

forming a response signal based on a first signal R_B ;

forming an outgoing signal by encrypting at least a portion of said response signal with a second symmetric key cryptosystem using a key based on said authentication signal;

transmitting said outgoing signal to one of said parties; and

generating said cryptographic key based on said excitation signal and on said first signal.

18. The method of claim 17 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

19. The method of claim 17 wherein said step of forming a response signal comprises the step of setting said response signal to α

^R.sbsp.B moduloβ

, where α and

β

are numbers.

20. The method of claim 19 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to S^R.sbsp.B moduloβ

.

21. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving an incoming signal from one of said parties;

forming a excitation signal, S, by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal;

forming a response signal based on a first signal R_B ;

forming an outgoing signal by encrypting at least a portion of said response signal with a third symmetric key cryptosystem using a key based on said authentication signal;

transmitting said outgoing signal to one of said parties; and

generating said cryptographic key based on said excitation signal and on said first signal.

22. The method of claim 21 wherein said first symmetric key cryptosystem, said second symmetric key cryptosystem and said third symmetric key cryptosystem are identical.

23. The method of claim 21 wherein said step of forming a response signal comprises the step of setting said response signal to α

^R.sbsp.B moduloβ

, where α and

β

are numbers.

24. The method of claim 23 wherein said step of generating said cryptographic key comprises the step of setting said cryptographic key to S^R.sbsp.B moduloβ

.

25. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

generating a public key and a private key to a public key cryptosystem;

forming an outgoing signal by encrypting at least a portion of said public key with a second symmetric key cryptosystem using a key based on said authentication signal;

transmitting said outgoing signal to one of said parties;

receiving a response signal in response to said outgoing signal; and

generating said cryptographic key based on said response signal and on said private key.

26. The method of claim 25 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

27. The method of claim 25 further comprising the step of validating said cryptographic key.

28. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

generating a public key and a private key to a public key cryptosystem;

transmitting said public key;

receiving an incoming signal from one of said parties in response to said public key;

forming a response signal by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal; and

generating said cryptographic key based on said response signal and on said private key.

29. The method of claim 28 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

30. The method of claim 28 further comprising the step of validating said cryptographic key.

31. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

generating a public key and a private key to a public key cryptosystem;

forming an outgoing signal by encrypting at least a portion of said public key with a second symmetric key cryptosystem using a key based on said authentication signal;

transmitting said outgoing signal to one of said parties;

receiving an incoming signal from one of said parties in response to said public key;

forming a response signal by decrypting said incoming signal with a third symmetric key cryptosystem using a key based on said authentication signal; and

generating said cryptographic key based on said response signal and on said private key.

32. The method of claim 31 wherein said first symmetric key cryptosystem, said second symmetric key cryptosystem, and said third symmetric key cryptosystem are identical.

33. The method of claim 31 further comprising the step of validating said cryptographic key.

34. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving an incoming signal from one of said parties;

forming a public key to a public key cryptosystem by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal;

generating said crytographic key;

forming a response signal by encrypting at least a portion of said cryptographic key with a public key cryptosystem using said public key; and

transmitting said response signal.

35. The method of claim 34 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

36. The method of claim 34 further comprising the step of validating said cryptographic key.

37. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving a public key to a public key cryptosystem;

generating said cryptographic key;

forming a response signal by encrypting at least a portion of said cryptographic key with a public key cryptosystem using said public key;

forming an outgoing signal by encrypting at least a portion of said response signal with a second symmetric key cryptosystem using a key based on said authentication signal; and

transmitting said outgoing signal to one of said parties.

38. The method of claim 37 wherein said first symmetric key cryptosystem and said second symmetric key cryptosystem are identical.

39. The method of claim 37 further comprising the step of validating said cryptographic key.

40. A method for generating a cryptographic key to a first symmetric key cryptosystem by using an authentication signal, said authentication signal being available to a plurality of parties, said method comprising the steps of:

receiving an incoming signal from one of said parties;

forming a public key to a public key cryptosystem by decrypting said incoming signal with a second symmetric key cryptosystem using a key based on said authentication signal;

generating said cryptographic key;

forming a response signal by encrypting at least a portion of said cryptographic key with a public key cryptosystem using said public key;

forming an outgoing signal by encrypting at least a portion of said response signal with a third symmetric key cryptosystem using a key based on said authentication signal; and

transmitting said outgoing signal to one of said parties.

41. The method of claim 40 wherein said first symmetric key cryptosystem, said second symmetric key cryptosystem, and said third symmetric key cryptosystem are identical.

42. The method of claim 40 further comprising the step of validating said cryptographic key.