US5987131A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cryptographic key exchange using pre-computation
Assignee: Polycom LLC
•
Filing: 1997-08-18
•
Granted: 1999-11-16
•
Expires: 2017-08-18
Abstract
Abstract A public-key method of cryptographic key exchange using modular exponentiation in which memory, for storing pre-computed results, can be flexibly traded off against the computational complexity of key-exchange. In a typical embodiment, the invention performs key exchange by the method of Diffie-Hellman but with exponents having a constrained form such that by use of a small table of pre-computed powers of a user's public key, any possible shared secret key within the allowed set can be computed with many fewer modular multiplications than the number of bits of effective key-length thereby obtained. The table of pre-computed powers is transmitted as part of the key exchange protocol. The party in receipt of the table uses the pre-computed powers of the sender's public key to replace calculations that would otherwise need to be done at key-exchange time. The method allows a flexible trade-off between computation and table size. The method of accelerating modular exponentiation can also be applied to other cryptographic operations in which the number to be raised to a power is fixed or known in advance and where the exponent is allowed to be of the specified form.
Inventors
- 👤 Craig S. K. Clapp
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 11:23
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/08; H04L9/0816; H04L9/0838; H04L9/0841; H04L9/32; H04L9/321
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
105 words
A method of cryptographic key exchange, comprising the steps of: selecting a modulus; selecting a generator; selecting an ordered plurality of exponents; populating entries of a power table with the generator raised to the power of each one of the plurality of exponents, modulo the modulus; producing a first result by performing calculations defined by a calculation sequence known to a first party and not known to a second party on entries of the power table; and populating entries of a pre-computed table of powers with results of raising the first result to the power of each of the plurality of exponents, modulo the modulus.
Claim 2
Independent Claim
105 words
A method of cryptographic key exchange, comprising the steps of: selecting a modulus; selecting a generator; selecting an ordered plurality of exponents; populating entries of a power table with the generator raised to the power of each one of the plurality of exponents, modulo the modulus; producing a first result by performing calculations defined by a calculation sequence known to a first party and not known to a second party on entries of the power table; and populating entries of a pre-computed table of powers with results of raising the first result to the power of each of the plurality of exponents, modulo the modulus.
Claim 3
Dependent Claim
20 words
The method of claim 1, further comprising the step of: transmitting the pre-computed table of powers to the first party.
Claim 4
Dependent Claim
30 words
The method of claim 2, further comprising the step of: generating a signed secure certificate attesting to the authenticity of one or more subsets of the pre-computed table of powers.
Claim 5
Dependent Claim
21 words
The method of claim 3, wherein: the signed secure certificate contains a certified secure hash of the pre-computed table of powers.
Claim 6
Dependent Claim
25 words
The method of claim 3, wherein: the generating step is performed by a trusted authority trusted by the first party and by the second party.
Claim 7
Dependent Claim
19 words
The method of claim 5, further comprising the step of: transmitting the signed secure certificate to the first party.
Claim 8
Dependent Claim
23 words
The method of claim 6, further comprising the step of: transmitting the secret calculation sequence of the first party to the first party.
Claim 9
Dependent Claim
83 words
The method of claim 7, further comprising: transmitting the signed secure certificate to the second party; performing signature verification on the signed secure certificate to produce a first certified secure hash of the pre-computed table of powers; transmitting the pre-computed table of powers to the second party; applying a hash function to the pre-computed table of powers to produce a second certified secure hash of the pre-computed table of powers; and comparing the first certified secure hash with the second certified secure hash.
Claim 10
Dependent Claim
27 words
The method of claim 8, further comprising: producing a shared key by applying a secret calculation seqence of the second party to the pre-computed table of powers.
Claim 11
Dependent Claim
15 words
The method of claim 8, wherein calculations in the sequence of calculations comprise Montgomery calculations.
Claim 12
Dependent Claim
24 words
The method of claim 10, further comprising the step of selecting a Montgomery reduction factor, and wherein the generator is stored in Montgomery form.
Claim 13
Dependent Claim
26 words
The method of claim 3, wherein the generating step further comprises: generating the secure certificate using an RSA signature method with a public exponent of 3.
Claim 14
Dependent Claim
20 words
The method of claim 3, wherein the generating step further comprises: generating the signed secure certificate using a modified-Rabin scheme.
Claim 15
Dependent Claim
24 words
The method of claim 3, wherein the signed secure certificate comprises secure hashes of a plurality of subsets of entries of the power table.
Claim 16
Dependent Claim
22 words
The method of claim 1, wherein the secret calculation sequence defines a sequence of calculations applicable to entries of the power table.
Claim 17
Dependent Claim
59 words
The method of claim 15, wherein the sequence of calculations defined by the secret calculation sequence comprises; a multiplication of a first sub-set of entries of the power table to produce a product; a squaring of the product to produce an intermediary result; a multiplication of the intermediary result by a second sub-set of entries of the power table.
Claim 18
Dependent Claim
16 words
The method of claim 16, wherein each entry in the first sub-set of entries is distinct.
Claim 19
Dependent Claim
11 words
The method of claim 16, wherein the first subset is empty.
Claim 20
Dependent Claim
18 words
The method of claim 16, wherein the first subset comprises all of the entries of the power table.
Claim 21
Dependent Claim
17 words
The method of claim 1, wherein the ordered plurality of exponents comprise successive integral powers of 2.
Claim 22
Dependent Claim
39 words
The method of claim 1, wherein: the modulus is a prime number p; (p-1)/2 is a prime number; and the generator is a number g such that g is a generator of the prime order sub-group of order (p-1)/2.
Claim 23
Dependent Claim
21 words
The method of claim 1, wherein: the modulus is a prime number p; and (p-1) has a large prime factor q.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |