Patent EP0316244A1 successfully refreshed from Google Patents.
US4424414A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Exponentiation cryptographic apparatus and method
Assignee: Leland Stanford Junior University
•
Filing: 1978-05-01
•
Granted: 1984-01-03
•
Expires: 1998-05-01
Abstract
Abstract A cryptographic system transmits a computationally secure cryptogram that is generated from a secret transformation of the message sent by the authorized transmitter; the cryptogram is again transformed by the authorized receiver using a secret reciprocal transformation to reproduce the message sent. The secret transformations use secret cipher keys that are known only by the authorized transmitter and receiver. The transformations are performed with nonsecret operations, exponentiation, that are easily performed but extremely difficult to invert. It is computationally infeasible for an eavesdropper either to solve known plaintext-ciphertext pairs for the secret cipher keys, or to invert the nonsecret operations that are used to generate the cryptogram.
Inventors
- 👤 Martin E. Hellman
- 👤 Stephen C. Pohlig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 20:16
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/3013; H04L9/3066
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
211 words
In a method of communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver by enciphering the message with a secret enciphering key at the transmitter, transmitting the enciphered message from the transmitter to the receiver, and deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by: generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key; generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key; deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, wherein the step of: generating the secret deciphering key is performed by generating a secret deciphering key D, such that D=K.sup.-1 (mod q-1) where 1≦D≦q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . q-2) which are relatively prime to q-1; generating the enciphered message is performed by generating an enciphered message C, such that C=P.sup.K (mod q) where P is the message; and deciphering the enciphered message is performed by generating the message P, where P=C.sup.D (mod q).
Claim 2
Dependent Claim
211 words
In a method of communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver by enciphering the message with a secret enciphering key at the transmitter, transmitting the enciphered message from the transmitter to the receiver, and deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by: generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key; generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key; deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, wherein the step of: generating the secret deciphering key is performed by generating a secret deciphering key D, such that D=K.sup.-1 (mod q-1) where 1≦D≦q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . q-2) which are relatively prime to q-1; generating the enciphered message is performed by generating an enciphered message C, such that C=P.sup.K (mod q) where P is the message; and deciphering the enciphered message is performed by generating the message P, where P=C.sup.D (mod q).
Claim 3
Dependent Claim
291 words
In an apparatus for communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver comprising means for enciphering the message with a secret enciphering key at the transmitter, means for transmitting the enciphered message from the transmitter to the receiver, and means for deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by: means for generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key; means for generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key, having an input connected to receive the secret enciphering key, having another input connected to receive the message, and having an output that generates the enciphered message, and means for deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, having an input connected to receive the secret deciphering key, having another input connected to receive the enciphered message, and having an output that generates the message, wherein said means for generating the secret deciphering key includes means for generating a secret deciphering key D, such that D=K.sup.-1 (mod q-1) where ≦D≦q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . , q-2) which are relatively prime to q-1; wherein said means, for generating the enciphered message by exponentiating, includes means for generating an enciphered message C, such that C=P.sup.K (mod q) where P is the message; and wherein said means, for deciphering the enciphered message by exponentiating, includes means for generating the message P, where, P=C.sup.D (mod q).
Claim 4
Dependent Claim
291 words
In an apparatus for communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver comprising means for enciphering the message with a secret enciphering key at the transmitter, means for transmitting the enciphered message from the transmitter to the receiver, and means for deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by: means for generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key; means for generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key, having an input connected to receive the secret enciphering key, having another input connected to receive the message, and having an output that generates the enciphered message, and means for deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, having an input connected to receive the secret deciphering key, having another input connected to receive the enciphered message, and having an output that generates the message, wherein said means for generating the secret deciphering key includes means for generating a secret deciphering key D, such that D=K.sup.-1 (mod q-1) where ≦D≦q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . , q-2) which are relatively prime to q-1; wherein said means, for generating the enciphered message by exponentiating, includes means for generating an enciphered message C, such that C=P.sup.K (mod q) where P is the message; and wherein said means, for deciphering the enciphered message by exponentiating, includes means for generating the message P, where, P=C.sup.D (mod q).
References Cited (Backward Citations)
US4079188A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-01-02 | 1987-07-04 | 1988-01-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-01-02 | 1991-07-04 | 1992-01-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-01-02 | 1995-07-04 | 1996-01-03 | $7700.00 | Window Closed / Lapsed |