System and method for regenerating secret keys in diffie-hellman communication sessions

• US 6,151,395 A
• Filed: 12/04/1997
• Issued: 11/21/2000
• Est. Priority Date: 12/04/1997
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Harkins, Dan
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): DARROW, JUSTIN T
• Application Number:
  US08/984,863
• Time in Patent Office: 1,083 Days
• Field of Search: 380/28, 380/21, 380/30, 380/286
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

The present invention is directed to a system and method for regenerating secret keys by escrowing only one private value in a Diffie-Hellman exchange where a public number is exchanged between the two participants according to the equation:

Y=g.sup.X mod p,

where Y is the Diffie-Hellman public number, X is the Diffie-Hellman private number, g is the generator, and p is the prime. The public value for each communication session is controlled after the escrow of the private value, and the secret keys are regenerated from the escrowed private value and the controlled public values. The escrowed private value is transmitted to the escrow center with full proof of security and authenticity and, if desired, this private value can be changed and re-sent to the escrow center.

Claims

1. A method for regenerating for a third party L a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties J, comprising the steps of:

(1) providing a private value Xi of said first party I to said third party L;

(2) using a number n, the number n differing for each of said communication sessions, and said private value Xi, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions; and

(3) determining for said third party L a number m associated with said number n to regenerate said secret key Ks in a second modular exponentiation equation, whereby said third party is able to decipher each of said communication sessions.

2. The method of claim 1, wherein said step of escrowing comprises the steps of:

(a) selecting a party M to which to provide said private value Xi;

(b) adding identifications to said private value Xi to produce a certificate Xis; and

(c) transmitting said certificate Xis to said party M, using an encryption and signature technique.

3. The method of claim 1, wherein said number n is set to zero in a first of said communication sessions and is incremented by one for each one of successive sessions.

4. The method of claim 1 wherein said step (3) comprises the steps of:

acquiring a public value Yis and a public value Yjs, both of which are associated with said session S;

(ii) selecting a value for said number m;

(iii) calculating a number Y from the equation

space="preserve" listing-type="equation">Y=g.sup.(Xi+m) mod p

(iv) comparing said number Y to said public value Yis;

(v) if said number Y is not equal to said public value Yis, then selecting a different value for said number m and returning to said step (iii), else if said number Y is equal to said public value Yis, then continuing; and

(vi) calculating said secret key K from the equation

space="preserve" listing-type="equation">Ks=Yjs.sup.(Xi+m) mod p.

5. The method of claim 4, wherein said number m is set to zero in said step (ii) and is incremented by one in said step (v).

6. The method of claim 1, wherein said step (3) comprises the steps of:

(i) acquiring a public value Yjs associated with said session S;

(ii) selecting a value for said number m;

(iii) calculating said secret key Ks, using the equation

space="preserve" listing-type="equation">Ks=Yjs.sup.(Xi+m) mod p;

and

(iv) if said secret key Ks is not acceptable, then selecting a different value for said number m and returning to said step (iii), else if said secret key Ks is acceptable, then acquiring said secret key Ks.

7. The method of claim 6, wherein said number m is set to zero in said step (ii) and is incremented by one in said step (iv).

20. The method of claim 1 further comprising the step of escrowing said private value Xi to a fourth party.

21. The method of claim 1 wherein said step (3) comprises the steps of:

(i) acquiring a public value Yis and a public value Yjs, both of which are associated with said session S;

(ii) using said public value Yis and said public value Yjs to determine said number n; and

(iii) calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yjs.sup.(Xi+n) mod p.

22. The method of claim 21 further comprising the step of acquiring said private value Xi from an escrow center.

8. An apparatus for regenerating for a third party L a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties I, comprising:

means for providing a private value Xi of said first party I to said third party L;

means for using a number n, the number n differing for each of said communication sessions, and said private value Xi, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions; and

means for determining for said third party L a number m associated with said number n to regenerate said secret key Ks in a second modular exponentiation equation, whereby said third party is able to decipher each of said communication sessions.

9. The apparatus of claim 8, wherein said means for escrowing comprises:

(a) means for selecting a party M to which to provide said private value Xi;

(b) means for adding identifications to said private value Xi to produce a certificate Xis; and

(c) means for transmitting said certificate Xis to said party M, using an encryption and signature technique.

10. The apparatus of claim 8, wherein n is set to zero in a first of said communication sessions and is incremented by one for each one of successive sessions.

11. The apparatus of claim 8, wherein said means for determining comprises:

means for calculating a value of said number m from the equation

space="preserve" listing-type="equation">Y=g.sup.(Xi+m) mod p

in which Y is a number; and

means for calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yj.sup.(Xi+m) mod p.

12. The apparatus of claim 11, wherein said number m is set to zero for a first calculation of said number Y and is incremented by one in a successive calculation.

23. The apparatus of claim 8 further comprising means for escrowing said private value Xi to a fourth party.

24. The apparatus of claim 8 wherein said means for determining comprises:

means for acquiring a public value Yis and a public value Yjs, both of which are associated with said session S;

means for using said public value Yis and said public value Yjs to determine said number n; and

means for calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yjs.sup.(Xi+n) mod p.

25. The apparatus of claim 24 further comprising means for acquiring said private value Xi from an escrow center.

13. A computer-readable medium embodying instructions for causing a device to generate a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties J, by the steps of:

(1) providing a private value Xi of said first party I to a third party L;

(2) using a number n, the number n differing for each of said communication sessions, and said private value Xi, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions; and

(3) determining for said third party L a number m associated with said number n to regenerate said secret key Ks in a second modular exponentiation equation, whereby said third party L is able to decipher each of said communication sessions.

14. The computer-readable medium of claim 13, wherein said step of escrowing comprises the steps of:

(a) selecting a party M to which to provide said private value Xi;

(b) adding identifications to said private value Xi to produce a certificate Xis; and

(c) transmitting said certificate Xis to said party M using an encryption and signature technique.

15. The computer-readable medium of claim 13 wherein said number n is set to zero in a first of said communication sessions and is incremented by one for each one of successive sessions.

16. The computer-readable medium of claim 13, wherein said step (3) comprises the steps of:

(i) acquiring a public value Yis and a public value Yjs, both of which being associated with said session S;

(ii) selecting a value for said number m;

(iii) calculating a number Y from an equation

space="preserve" listing-type="equation">Y=g.sup.(Xi+m) mod p;

(iv) comparing said number Y to said public value Yis;

(v) selecting a different value for said number m if said number Y is not equal to said public value Yis and returning to said step (ii), else if said number Y is equal to said public value Y is, then continuing; and

(vi) calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yj.sup.(Xi+m) mod p.

17. The computer-readable medium of claim 16, wherein said number m is set to zero in said step (ii) and is incremented by one in said step (v).

18. The computer-readable medium of claim 13, wherein said step (3) comprises the steps of:

(i) acquiring a public value Yjs associated with said session S;

(ii) selecting a value for said number m;

(iii) calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yj.sup.(Xi+m) mod p;

and

(iv) if said secret Ks is not acceptable, then selecting a different value for said number m and returning to said step (ii), else if said secret key Ks is acceptable, then acquiring said secret key Ks.

19. The computer-readable medium of claim 18, wherein said number m is set to zero in said step (ii) and is incremented by one in said step (iv).

26. The computer-readable medium of claim 13 further comprising the step of escrowing said private value Xi to a fourth party.

27. The computer-readable medium of claim 13 wherein said step (3) comprises the steps of:

(i) acquiring a public value Yis and a public value Yjs, both of which are associated with said session S;

(ii) using said public value Yis and said public value Yjs to determine said number n; and

(iii) calculating said secret key Ks from the equation

space="preserve" listing-type="equation">Ks=Yjs.sup.(Xi+n) mod p.

28. The computer-readable medium of claim 27 further comprising the step of acquiring said private value Xi from an escrow center.

29. A method for regenerating for a third party L a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties J, comprising the step of:

using a number n at node A, the number n differing for each of said communication sessions, and a private value Xi of said first party I, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions;

whereby a number m associated with said number n is determinable for a third party L to regenerate said secret key Ks in a second modular exponentiation equation and decipher each of said communication sessions.

30. An apparatus for regenerating for a third party L a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties J, comprising:

means for using a number n, the number n differing for each of said communication sessions, and a private value Xi of said first party I, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions;

whereby a number m associated with said number n is determinable for a third party L to regenerate said secret key Ks in a second modular exponentiation equation and decipher each of said communication sessions.

31. A computer-readable medium embodying instructions for causing a device to generate a secret key Ks used in a Diffie-Hellman communication session S among a plurality of sessions communicated between a first party I and one or more second parties J, by the steps of:

using a number n, the number n differing for each of said communication sessions, and a private value Xi of said first party I, in a first modular exponentiation equation

space="preserve" listing-type="equation">Yi=g.sup.(Xi+n) mod p,

wherein g represents a generator number and p represents a prime number, to generate a plurality of public values Yi of said first party I;

each of said public values Yi being associated with one public value Yj of said party J for each of said communication sessions;

whereby a number m associated with said number n is determinable for a third party L to regenerate said secret key Ks in a second modular exponentiation equation and decipher each of said communication sessions.