US5299263A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Two-way public key authentication and key agreement for low-cost terminals
Assignee: Nytell Software LLC
•
Filing: 1993-03-04
•
Granted: 1994-03-29
•
Expires: 2013-03-04
Abstract
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.
Inventors
- 👤 Michael J. Beller
- 👤 Yacov Yacobi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 18:58
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/08; H04L63/0869; G; G06; G06Q; G06Q20/00; G06Q20/30; G06Q20/36; G06Q20/367; G06Q20/3674; H04L9/00; H04L9/08; H04L9/0816; H04L9/0838; H04L9/0841; H04L9/0844; H04L9/32; H04L9/3247; H04L9/3249
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
342 words
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 2 mod N u , (c) at the terminal, choosing a random number x≡(x L x R ) and obtaining y≡x 2 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 2 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.
Claim 2
Independent Claim
342 words
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 2 mod N u , (c) at the terminal, choosing a random number x≡(x L x R ) and obtaining y≡x 2 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 2 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.
Claim 3
Dependent Claim
72 words
The method of claim 1 wherein said signature s(m) is given by the ordered pair (v,w) for which: 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 .
Claim 4
Dependent Claim
46 words
The method of claim 2 wherein said step of evaluating a signature s(m) on a message m comprises performing the real time operation w=(m-S.sub.i v)*r.sup.-1 mod φ(N.sub.s) where r is a predetermined number,v≡α r mod N s , φ(N) is the Euler totient function, and gcd(r,φ(N))=1.
Claim 5
Dependent Claim
20 words
The method of claim 3 wherein the value of r is chosen randomly each time the terminal evaluates a signature
Claim 6
Dependent Claim
40 words
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 .
Claim 7
Dependent Claim
14 words
The method of claim 1 wherein said signature operation is an ElGamal signature operation.
Claim 8
Dependent Claim
24 words
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.
Claim 9
Dependent Claim
32 words
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 2 mod N u =h(j,N j ).
Claim 10
Dependent Claim
32 words
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 2 mod N u =h(i,P i ).
Claim 11
Dependent Claim
29 words
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.
Claim 12
Dependent Claim
12 words
The method of claim 10 wherein said terminal is a portable telephone.
Claim 13
Dependent Claim
21 words
The method of claim 1 wherein the terminal is a smart card and the server is a smart card base unit.
Claim 14
Dependent Claim
24 words
The method of claim 1 wherein the terminal is an Analog Display Service Interface (ADSI) terminal and said server is an ADSI network cryptoserver.
Claim 15
Dependent Claim
14 words
The method of claim 1 wherein said terminal is computationally weaker than said server.
Claim 16
Dependent Claim
58 words
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.
Claim 17
Dependent Claim
89 words
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.
Claim 18
Dependent Claim
30 words
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.
Claim 19
Independent Claim
207 words
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.
Claim 20
Independent Claim
207 words
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.
Claim 21
Dependent Claim
62 words
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.
Claim 22
Dependent Claim
21 words
The method of claim 19 wherein said step (b) comprises determining if h(j,N j )≡c j 2 mod N u .
Claim 23
Dependent Claim
29 words
The method of claim 18 wherein said asymmetric public key operation is y≡c j 2 mod N j , where N j is a public key of the server.
Claim 24
Dependent Claim
44 words
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 2 mod N j .
Claim 25
Dependent Claim
49 words
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 .
Claim 26
Dependent Claim
21 words
The method of claim 23 wherein said step (f) comprises determining if h(i,P i )≡c i 2 mod N u .
Claim 27
Dependent Claim
14 words
The method of claim 18 wherein said signature operation is an ElGamal signature operation.
Claim 28
Independent Claim
143 words
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.
Claim 29
Independent Claim
143 words
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.
Claim 30
Dependent Claim
26 words
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.
Claim 31
Dependent Claim
27 words
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.
Claim 32
Dependent Claim
32 words
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.
Claim 33
Dependent Claim
21 words
The method of claim 26 further comprising the step of authenticating a certificate of said first party at said second party.
Claim 34
Dependent Claim
17 words
The method of claim 26 wherein said second party has more computational resources than said first party.
Claim 35
Dependent Claim
24 words
The method of claim 31 wherein the terminal is an Analog Display Server Interface (ADSI) and the server is an ADSI network crypto server.
Claim 36
Dependent Claim
31 words
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.
Claim 37
Dependent Claim
19 words
The method of claim 26 wherein the first party is a terminal and the second party is a server.
Claim 38
Dependent Claim
21 words
The method of claim 34 wherein said terminal is a smart card and said server is a smart card base unit.
Claim 39
Dependent Claim
21 words
The method of claim 26 wherein the first party is a server and the second party is a terminal or workstation.
Claim 40
Independent Claim
218 words
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.
Claim 41
Independent Claim
218 words
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.
References Cited (Backward Citations)
US4453074A
Cited
US4723284A
Cited
US4799258A
Cited
US4876716A
Cited
US4935962A
Cited
US4969189A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-03-28 | 1997-09-27 | 1998-03-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-03-28 | 2001-09-27 | 2002-03-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-03-28 | 2005-09-27 | 2006-03-29 | $7700.00 | Window Closed / Lapsed |