Patent US5159632A successfully refreshed from Google Patents.
US5159632A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for public key exchange in a cryptographic system
Assignee: Next Software Inc
•
Filing: 1991-09-17
•
Granted: 1992-10-27
•
Expires: 2011-09-17
Abstract
Abstract The present invention is an elliptic curve cryptosystem that uses elliptic curves defined over finite fields comprised of special classes of numbers. Special fast classes of numbers are used to optimize the modulo arithmetic required in the enciphering and deciphering process. The class of numbers used in the present invention is generally described by the form 2q-C where C is an odd number and is relatively small, for example, no longer than the length of a computer word (16-32 bits). When a number is of this form, modulo arithmetic can be accomplished using shifts and adds only, eliminating the need for costly divisions. One subset of this fast class of numbers is known as "Mersenne" primes, and are of the form 2q-1. Another class of numbers that can be used with the present invention are known as "Fermat" numbers of the form 2q+1. The present invention provides a system whose level of security is tunable. q acts as an encryption bit depth parameter, such that larger values of q provide increased security. Inversion operations normally require an elliptic curve algebra can be avoided by selecting an inversionless parameterization of the elliptic curve. Fast Fourier transform for an FFT multiply mod operations optimized for efficient Mersenne arithmetic, allow the calculations of very large q to proceed more quickly than with other schemes.
Inventors
- 👤 Richard E. Crandall
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 15:12
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3066; G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; G06F7/727
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
207 words
A key generator for electronically generating a secure key comprising: a first private key source for providing a first private key; a second private key source for providing a second private key; a public key source for providing at least first and second public keys, said first public key generated by performing an elliptic multiplication of said first private key and a point on an elliptic curve, and said second public key generated by performing an elliptic multiplication of said second private key and said point, said point on an elliptic curve over a finite field F p k, where p is one of a class of numbers such that mod p arithmetic is performed in a processor using only shift and add operations; first elliptic multiplying means coupled to said first private key source and said public key source, said first elliptic multiplying means for generating an enciphering key by performing an elliptic multiplication of said first private key and said second public key; a second elliptic multiplying means coupled to said second private key source and said public key source, said second elliptic multiplying means for generating a deciphering key by performing an elliptic multiplication of said second private key and said first public key.
Claim 2
Dependent Claim
207 words
A key generator for electronically generating a secure key comprising: a first private key source for providing a first private key; a second private key source for providing a second private key; a public key source for providing at least first and second public keys, said first public key generated by performing an elliptic multiplication of said first private key and a point on an elliptic curve, and said second public key generated by performing an elliptic multiplication of said second private key and said point, said point on an elliptic curve over a finite field F p k, where p is one of a class of numbers such that mod p arithmetic is performed in a processor using only shift and add operations; first elliptic multiplying means coupled to said first private key source and said public key source, said first elliptic multiplying means for generating an enciphering key by performing an elliptic multiplication of said first private key and said second public key; a second elliptic multiplying means coupled to said second private key source and said public key source, said second elliptic multiplying means for generating a deciphering key by performing an elliptic multiplication of said second private key and said first public key.
Claim 3
Dependent Claim
28 words
The key generator of claim 1 wherein p is given by 2 q -C, where C is a binary number having a length no greater than 32 bits.
Claim 4
Dependent Claim
17 words
The key generator of claim 1 wherein p is a Mersenne prime given by 2 q -1.
Claim 5
Dependent Claim
25 words
The key generator of claim 1 wherein p is a Fermat number given by 2 q +1 and q is given by 2 m .
Claim 6
Dependent Claim
21 words
The key generator of claim 1 wherein said initial point on said elliptic curve is (X 1 , Y 1 ).
Claim 7
Dependent Claim
46 words
The key generator of claim 1 wherein said initial point on said elliptic curve is (X 1 /Z 1 , Y) where Z 1 =1 and n o (X m /Z m ) is an elliptic multiplication and denotes the coordinate (X n+m /Z n+m ).
Claim 8
Dependent Claim
17 words
The key generator of claim 6 wherein Fast Fourier Transforms are used to compute X n+m .
Claim 9
Dependent Claim
64 words
The key generator of claim 7 where X denotes the Fourier transform of the digits of X, and, X n , X m , Z n , Z m , and Z n-m denote the Fourier transforms of the digits of X n , X m , Z n , Z m , and Z n-m respectively and; X.sub.n+m =Z.sub.n-m (X.sub.n X.sub.m -Z.sub.n Z.sub.m).sup.2
Claim 10
Dependent Claim
37 words
The key generator of claim 1 further including encrypting means coupled to said elliptic multiplying means and receiving a plaintext message from a message source, said encrypting means for generating a ciphertext message using said enciphering key.
Claim 11
Dependent Claim
37 words
The key generator of claim 9 further including decrypting means coupled said encrypting means and said second elliptic multiplying means, said decrypting means for receiving said ciphertext message and decoding said plaintext message using said deciphering key.
Claim 12
Dependent Claim
50 words
The key generator of claim 1 wherein said first public key is given by (first private key).sup.o (X.sub.1,Y.sub.1)=first public key where o is an elliptic multiplication, (X 1 , Y 1 ) is a point on an elliptic curve over a finite field F p k, and p=2 q -C.
Claim 13
Dependent Claim
20 words
The key generator of claim 11 wherein said second public key is given by: (second private key).sup.o (X.sub.1,Y.sub.1)=second public key
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) | 1995-10-27 | 1996-04-27 | 1996-10-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-10-27 | 2000-04-27 | 2000-10-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-10-27 | 2004-04-27 | 2004-10-27 | $7700.00 | Window Closed / Lapsed |