US5953420A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for establishing an authenticated shared secret value between a pair of users
Assignee: International Business Machines Corp
•
Filing: 1996-10-25
•
Granted: 1999-09-14
•
Expires: 2016-10-25
Abstract
Abstract A method and apparatus for generating authenticated Diffie-Hellman keys. Each user first generates an authenticated first shared secret value from a first nonshared persistent secret value generated by that user and an authenticated first transformed value received from the other user over a trusted communications channel. Each user then dynamically generates a second shared secret value from a second nonshared secret value dynamically generated by that user and a dynamically generated second transformed value received from the other user. Each user thereafter generates one or more keys by concatenating the first and second shared secret values together with a count to form a concatenated value and passing the concatenated value through a one-way hash function to generate a hash value from which the keys are extracted. Since only the legitimate users possess the information necessary to construct the first shared secret value, a spoofer interacting with a user to generate a second shared secret value cannot generate the same key. Incrementing the count for successive hashes allows a multiplicity of keys to be generated from a given pair of shared secret values.
Inventors
- 👤 Stephen Michael Matyas, Jr.
- 👤 Donald Byron Johnson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 16:29
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/08; H04L9/0816; H04L9/0838; H04L9/0841; H04L9/0844
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
244 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of: generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users; generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and generating said new shared secret value as a function of said first shared secret value and said second shared secret value.
Claim 2
Dependent Claim
244 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of: generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users; generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and generating said new shared secret value as a function of said first shared secret value and said second shared secret value.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein said users are located at nodes coupled by a communications channel.
Claim 4
Dependent Claim
13 words
The method of claim 1 wherein each of said users performs said steps.
Claim 5
Dependent Claim
115 words
The method of claim 1 wherein each of said steps of generating a shared secret value comprises the steps of: generating a transformed value by transforming in a manner infeasible to invert, using said common transformation a nonshared secret value generated by said one of said users; transmitting said transformed value to the other of said users; receiving a transformed value generated by the other of said users using said common transformation; and generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the transformed values exchanged between said users.
Claim 6
Dependent Claim
62 words
The method of claim 4 wherein said transformed value is generated by said one of said users as Y=g.sup.X mod p where X is the nonshared secret value generated by said one of said users, Y is the transformed value generated by said one of said users, p is a prime modulus, and g is a generator over the Galois field GF(p).
Claim 7
Dependent Claim
60 words
The method of claim 5 wherein said shared secret value is generated by said one of said users as Z=Y.sup.X mod p where X is the nonshared secret value generated by said one of said users, Y is the transformed value received from said other of said users, p is said prime modulus, and Z is said shared secret value.
Claim 8
Dependent Claim
47 words
The method of claim 1 wherein said step of generating said new shared secret value comprises the steps of: combining said first and second shared secret values to generate a combined value; and generating said new shared secret value as a one-way function of said combined value.
Claim 9
Dependent Claim
22 words
The method of claim 7 wherein said first and second values are also combined with a count to generate said combined value.
Claim 10
Dependent Claim
27 words
The method of claim 1 wherein said first shared secret value is a relatively long-term value and said second shared secret value is a relatively short-term value.
Claim 11
Dependent Claim
23 words
The method of claim 1 wherein said first transformed value is received from said other of said users over a trusted communications channel.
Claim 12
Dependent Claim
226 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of: generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value; generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value; concatenating said first and second shared secret values to generate a concatenated value; and generating said new authenticated shared secret value as a one-way function of said concatenated value.
Claim 13
Dependent Claim
226 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, a method of establishing for one of said users a new shared secret value with the other of said users, comprising the steps of: generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value; generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value; concatenating said first and second shared secret values to generate a concatenated value; and generating said new authenticated shared secret value as a one-way function of said concatenated value.
Claim 14
Independent Claim
170 words
A method of establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising the steps of: generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value; transmitting said transformed value to the other of said users; receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation; generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users; concatenating said shared secret value and a value available to the other user to generate a concatenation value; and generating said key as a one-way function of said concatenation value.
Claim 15
Independent Claim
170 words
A method of establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising the steps of: generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value; transmitting said transformed value to the other of said users; receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation; generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users; concatenating said shared secret value and a value available to the other user to generate a concatenation value; and generating said key as a one-way function of said concatenation value.
Claim 16
Dependent Claim
31 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 1, claim 11 or claim 12.
Claim 17
Dependent Claim
19 words
The method of claim 12 in which said value available to the other user is a successively incremented count.
Claim 18
Dependent Claim
47 words
The method of claim 12 wherein said step of generating said key comprises the step of generating each of a plurality of different keys as a one-way function of said shared secret value and a value available to the other user that is unique to that key.
Claim 19
Dependent Claim
17 words
The method of claim 12 wherein said users are located at nodes coupled by a communications channel.
Claim 20
Dependent Claim
13 words
The method of claim 12 wherein each of said users performs said steps.
Claim 21
Dependent Claim
247 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising: means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users; means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and means for generating said new authenticated shared secret value as a function of said first shared secret value and said second shared secret value.
Claim 22
Dependent Claim
247 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising: means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value and being authenticated as having originated from said other of said users; means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value and not being authenticated as having originated from said other of said users; and means for generating said new authenticated shared secret value as a function of said first shared secret value and said second shared secret value.
Claim 23
Dependent Claim
120 words
The apparatus of claim 18 wherein each of said means for generating a shared secret value comprises: means for generating a transformed value by transforming in a manner infeasible to invert, using said common transformation, a nonshared secret value generated by said one of said users; means for transmitting said transformed value to the other of said users; means for receiving a transformed value generated by the other of said users using said common transformation; and means for generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the transformed values exchanged between said users.
Claim 24
Dependent Claim
48 words
The apparatus of claim 18 wherein said means for generating said new shared secret value comprises: means for combining said first and second shared secret values to generate a combined value; and means for generating said new shared secret value as a one-way function of said combined value.
Claim 25
Dependent Claim
230 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising: means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value; means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value; means for concatenating said first and second shared secret values to generate a concatenated value; and means for generating said new authenticated shared secret value as a one-way function of said concatenated value.
Claim 26
Dependent Claim
230 words
In a system in which each of a pair of users has its own nonshared secret value and establishes a shared secret value with the other user by transforming its own nonshared secret value using a common transformation to generate a transformed value, exchanging the transformed value with the other user, and generating the shared secret value from the user's own nonshared secret value and the transformed value received from the other user, apparatus for establishing for one of said users a new shared secret value with the other of said users, comprising: means for generating a first shared secret value from a first nonshared secret value generated by said one of said users and a first transformed value received from the other of said users, said first transformed value being generated by said other of said users from its own first nonshared secret value; means for generating a second shared secret value from a second nonshared secret value generated by said one of said users and a second transformed value received from the other of said users, said second transformed value being generated by said other of said users from its own second nonshared secret value; means for concatenating said first and second shared secret values to generate a concatenated value; and means for generating said new authenticated shared secret value as a one-way function of said concatenated value.
Claim 27
Dependent Claim
178 words
Apparatus for establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising: means for generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value; means for transmitting said transformed value to the other of said users; means for receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation; means for generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users; means for concatenating said shared secret value and a value available to the other user to generate a concatenation value; and means for generating said key as a one-way function of said concatenation value.
Claim 28
Dependent Claim
178 words
Apparatus for establishing for one of a pair of users a cryptographic key that is shared with the other of said pair of users, comprising: means for generating a transformed value by transforming in a manner infeasible to invert, using a common transformation, a nonshared secret value generated by said one of said users, each of said users having its own nonshared secret value; means for transmitting said transformed value to the other of said users; means for receiving a transformed value generated by the other of said users from its own nonshared secret value using said common transformation; means for generating, from said nonshared secret value generated by said one of said users and said transformed value received from said other of said users, a shared secret value that is infeasible to generate solely from the first transformed values exchanged between said users; means for concatenating said shared secret value and a value available to the other user to generate a concatenation value; and means for generating said key as a one-way function of said concatenation value.
Claim 29
Dependent Claim
19 words
The apparatus of claim 22 in which said value available to the other user is a successively incremented count.
Claim 30
Dependent Claim
43 words
The apparatus of claim 22, wherein said means for generating said key generates each of a plurality of different keys as a one-way function of said shared secret value and a value available to the other user that is unique to that key.
References Cited (Backward Citations)
US4200770A
Cited
US4424414A
Cited
JPH02246640A
Cited
JPH02246639A
Cited
US4956863A
Cited
US5199070A
Cited
US5115467A
Cited
US5345506A
Cited
US5299263A
Cited
US5406628A
Cited
WO1995004416A1
Cited
WO1995008232A1
Cited
US5515439A
Cited
EP0658021A1
Cited
US5668877A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-13 | 2003-03-15 | 2003-09-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-13 | 2007-03-15 | 2007-09-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-13 | 2011-03-15 | 2011-09-14 | $7700.00 | Window Closed / Lapsed |