US4306111A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simple and effective public-key cryptosystem
Assignee: Comsat Corp
•
Filing: 1979-05-31
•
Granted: 1981-12-15
•
Expires: 1999-05-31
Abstract
Abstract A public encryption key (c 1 , c 2 , r) in which r is the product of two relatively prime numbers, and in which c 1 and r, as well as c 2 and r, are relatively prime numbers, is used in an encryption algorithm x=c.sub.1 m.sub.1 +c.sub.2 m.sub.2 (mod r). The decryption algorithm will be equivalent to solving simultaneous linear equations derived from the encryption algorithm. Thus, both encrypting and decrypting are quite simplified while still maintaining a high degree of security.
Inventors
- 👤 Shyue-Ching Lu
- 👤 Lin-nan Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:03
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
257 words
A method of securely communicating over an insecure communication channel of the type wherein an original information signal is transformed into an encoded information signal according to an encryption algorithm, transmitted over said information channel between a transmitter and a receiver, received by said receiver and decoded to obtain said original information signal, said original information signal comprising at least two integers m 1 and m 2 where at least m 1 represents information and 0<m 1 <M 1 and 0<m 2 <M 2 , where M 1 and M 2 are integers, said method comprising the steps of: producing a cryptogram x from said original information signal and a public encryption key (c 1 , c 2 r), where c 1 , c 2 and r are all integers, r is the product of two relatively prime numbers p 1 and p 2 , and c 1 and r are well as c 2 and r are relatively prime, said cryptogram x being defined by: x=c.sub.1 m.sub.1 +c.sub.2 m.sub.2 (mod r) where c 1 m 1 +c 2 m 2 (mod r) is defined as the remainder of (c 1 m 1 +c 2 m 2 )/r; transmitting said cryptogram x as said encoded information signal from said transmitter to said receiver; receiving said encoded information signal at said receiver; generating two simultaneous linear equations from said encryption algorithm; and solving said two simultaneous linear equations using said received cryptogram x, to thereby obtain said integers m 1 and m 2 of said original information signal.
Claim 2
Independent Claim
257 words
A method of securely communicating over an insecure communication channel of the type wherein an original information signal is transformed into an encoded information signal according to an encryption algorithm, transmitted over said information channel between a transmitter and a receiver, received by said receiver and decoded to obtain said original information signal, said original information signal comprising at least two integers m 1 and m 2 where at least m 1 represents information and 0<m 1 <M 1 and 0<m 2 <M 2 , where M 1 and M 2 are integers, said method comprising the steps of: producing a cryptogram x from said original information signal and a public encryption key (c 1 , c 2 r), where c 1 , c 2 and r are all integers, r is the product of two relatively prime numbers p 1 and p 2 , and c 1 and r are well as c 2 and r are relatively prime, said cryptogram x being defined by: x=c.sub.1 m.sub.1 +c.sub.2 m.sub.2 (mod r) where c 1 m 1 +c 2 m 2 (mod r) is defined as the remainder of (c 1 m 1 +c 2 m 2 )/r; transmitting said cryptogram x as said encoded information signal from said transmitter to said receiver; receiving said encoded information signal at said receiver; generating two simultaneous linear equations from said encryption algorithm; and solving said two simultaneous linear equations using said received cryptogram x, to thereby obtain said integers m 1 and m 2 of said original information signal.
Claim 3
Dependent Claim
25 words
The method according to claim 1, wherein said at least two simultaneous linear equations are: x(mod p.sub.1)=a.sub.11 m.sub.1 +a.sub.12 m.sub.2 x(mod p.sub.2)=a.sub.21 m.sub.1 +a.sub.22 m.sub.2.
Claim 4
Dependent Claim
26 words
The method according to any one of claim 1 or 2, wherein only two integers m 1 and m 2 are used in the encryption algorithm.
Claim 5
Dependent Claim
58 words
The method as defined in claim 1, wherein said two simultaneous linear equations are generated in accordance with said encryption algorithm and a secret decryption key (a 11 , a 12 , a 21 , a 22 , p 1 , p 2 ) where a 11 , a 12 , a 21 and a 22 are integers.
Claim 6
Dependent Claim
99 words
The method as defined in either of claim 4 or 2, further comprising, prior to said producing step, the step of selecting said secret decryption key by: selecting two relatively prime numbers p 1 and p 2 ; and selecting values of a 11 , a 12 , a 21 and a 22 , such that a.sub.11 a.sub.22 -a.sub.12 a.sub.21 =0 and ##EQU7## where q=min and denotes the integer part of a real number u, said selected values a 11 , a 12 , a 21 , a 22 , p 1 and p 2 comprising said description key.
Claim 7
Dependent Claim
69 words
The method as defined in claim 5, further comprising, subsequent to said step of selecting said secret decryption key, the steps of: selecting integers b 1 and b 2 satisfying the equation b 1 p 1 +b 2 p 2 =1; calculating c 1 and c 2 according to: ##EQU8## calculating r=p 1 p 2 , whereby said encryption key (c 1 , c 2 , r) is obtained.
References Cited (Backward Citations)
US4200770A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1984-12-14 | 1985-06-15 | 1985-12-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1988-12-14 | 1989-06-15 | 1989-12-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1992-12-14 | 1993-06-15 | 1993-12-15 | $7700.00 | Window Closed / Lapsed |