Simple and effective public-key cryptosystem

• US 4,306,111 A
• Filed: 05/31/1979
• Issued: 12/15/1981
• Est. Priority Date: 05/31/1979
• Status: Expired due to Term

• Current Assignee: COMSAT Corporation (Reorganized ISA SA)
• Original Assignee: Communications Satellite Corporation (Reorganized ISA SA)
• Inventors: Lee, Lin-nan, Lu, Shyue-Ching
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US06/044,288
• Time in Patent Office: 929 Days
• Field of Search: 178/22, 375/2
• US Class Current: 380/30
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A public encryption key (c₁, c₂, r) in which r is the product of two relatively prime numbers, and in which c₁ and r, as well as c₂ 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.

Claims

1. 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₁ and m₂ where at least m₁ represents information and 0<

m₁ <

M₁ and 0<

m₂ <

M₂, where M₁ and M₂ are integers, said method comprising the steps of;

producing a cryptogram x from said original information signal and a public encryption key (c₁, c₂ r), where c₁, c₂ and r are all integers, r is the product of two relatively prime numbers p₁ and p₂, and c₁ and r are well as c₂ and r are relatively prime, said cryptogram x being defined by;

space="preserve" listing-type="equation">x=c.sub.1 m.sub.1 +c.sub.2 m.sub.2 (mod r)

where c₁ m₁ +c₂ m₂ (mod r) is defined as the remainder of (c₁ m₁ +c₂ m₂)/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₁ and m₂ of said original information signal.

2. The method according to claim 1, wherein said at least two simultaneous linear equations are:

space="preserve" listing-type="equation">x(mod p.sub.1)=a.sub.11 m.sub.1 +a.sub.12 m.sub.2

space="preserve" listing-type="equation">x(mod p.sub.2)=a.sub.21 m.sub.1 +a.sub.22 m.sub.2.

3. The method according to any one of claim 1 or 2, wherein only two integers m₁ and m₂ are used in the encryption algorithm.

4. 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₁₁, a₁₂, a₂₁, a₂₂, p₁, p₂) where a₁₁, a₁₂, a₂₁ and a₂₂ are integers.

5. 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₁ and p₂ ; and

selecting values of a₁₁, a₁₂, a₂₁ and a₂₂, such that

space="preserve" listing-type="equation">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₁₁, a₁₂, a₂₁, a₂₂, p₁ and p₂ comprising said description key.

6. 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₁ and b₂ satisfying the equation b₁ p₁ +b₂ p₂ =1;

calculating c₁ and c₂ according to;

##EQU8## calculating r=p₁ p₂, whereby said encryption key (c₁, c₂, r) is obtained.