RSA Public-key data encryption system having large random prime number generating microprocessor or the like

• US 4,351,982 A
• Filed: 12/15/1980
• Issued: 09/28/1982
• Est. Priority Date: 12/15/1980
• Status: Expired due to Term

• Current Assignee: Racal-Guardata Limited
• Original Assignee: Racal-Milgo Incorporated
• Inventors: Miller, William J., Trbovich, Nick G.
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US06/216,435
• Time in Patent Office: 652 Days
• Field of Search: 178/22.10, 178/22.11
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

A public-key data encryption system employing RSA public-key data encryption including a message encrypter capable of encrypting messages using a non-secret encryption key, a transmitter-receiver coupled to the message encrypter which transmits or receives an encrypted message to or from a remote location, the transmitter-receiver also being coupled to a decrypter capable of decrypting a received encrypted message using a decryption key which is a secret input to the decrypter, and an encryption-decryption key generator, including a microprocessor or other large-scale integrated circuit or circuits formed to generate a sequence of prime numbers beginning with a selected known prime number having a length relatively short with respect to the desired length of the last in the sequence of prime numbers, and which is constructed to form the sequence of prime numbers in the form hP+1 where P is the preceding prime number in the sequence, and to test hP+1 for primality by first determining if hP+1 has a GCD of 1 with x, wherein x is a composite number consisting of the product of all known prime numbers less than or equal to a pre-selected known prime number and if the GCD is not equal to 1, incrementing h to form a new hP+1 to be tested for a GCD equal to 1, and when a GCD is found to be 1, performing the primality tests to determine whether 2^hP ≡1 [mod (hP+1)] and 2^h ≢1 [mod (hP+1)], and if either 2^hP ≢1 [mod (hP+1)] or 2^h ≡1 [mod (hP+1)] further incrementing h and so on until a prime is found in this manner and then determining if the length of the prime number is of or greater than the desired length. If the hP+1 which has been determined to be prime is not of the desired length, hP+1 is placed in the sequence of prime numbers and a new h selected to be used to find the next prime number in the sequence in accordance with the above described procedure by forming a new hP+1 in which P is the previously determined prime number in the sequence of prime numbers. When a prime number in the sequence of prime numbers is found which is of the desired length it is input into the encryption-decryption key generator for generating the RSA public-key encryption and decryption keys.

Claims

1. In a public-key data encryption/decryption system having a plurality of terminals, a terminal comprising:

a transmitter-receiver capable of receiving an encrypted message encrypted using a non-secret encryption key specific to the terminal;

an encrypter/decrypter, coupled to the transmitter-receiver, adapted to decrypt the encrypted message using a secret decryption key;

an encryption/decryption key generator coupled to the encrypter/decrypter and adapted to generate the non-secret and secret keys by use of a pair of large randomly selected prime numbers;

a large random prime number generator, including a large-scale integrated circuit, coupled to the key generator and adapted to provide the key-generator with the pair of random large prime numbers having a desired length, the large-scale integrated circuit being constructed to perform the following operations in selecting each of the pair of large random prime numbers;

starting with a P, which is a known prime number having a length which is relatively short in comparison to the desired length, forming a sequence of prime numbers in the form hP+1, wherein P is the current prime number in the sequence of prime numbers, by selecting at random an h and forming hP+1 and testing hP+1 for primality by determining first if the greatest common divisor (GCD) of (hP+1), (x) is one, wherein x is a composite number consisting of the product of all known prime numbers less than or equal to a selected known prime number, and if the GCD is equal or one, determining if both 2^hP ≡

1 [mod (hp+1)] and 2^h ≢

1 [mod (hP+1)], and, if GCD is not equal to one, incrementing h to form a new hP+1, and if GCD is equal to one, but either 2^hP ≢

1 [mod (hP+1)] or 2^h ≡

1 [mod (hP+1)], incrementing h to form a new hP+1, but if both 2^hP |[mod (hP+1)] and 2^h ≢

1 [mod (hP+1)], determining if the length of hP+1 is greater than or equal to the desired length, and if greater than or equal to the desired length then setting hP+1 as an output as a large random prime number to the encryption/decryption key generator, and if not greater than or equal to the desired length, then placing hP+1 in the sequence of prime numbers and repeating the above steps using hP+1 as the new P and commencing by selecting a new h as above set forth.

2. The public-key data encryption system of claim 1 wherein the large-scale integrated circuit is constructed to select the initial h, for the formation of each succeeding prime number in the sequence of prime numbers, to have a length of about one-half that of the current prime number in the sequence of prime numbers.

3. The public-key data encryption system of claim 1 wherein the large-scale integrated circuit is constructed to further determine if the length of hP+1 is within a pre-selected length of the desired length, if not greater than or equal to the desired length, and if within the pre-selected length and not greater than or equal to the desired length, to select the next initial h with a selected length less than about one-half of the length of the current prime number in the sequence of prime numbers, but of a length sufficient to make the next prime number in the sequence of prime numbers greater than or equal to the desired length.

4. The public-key data encryption system of claim 3 wherein the desired length is 23 bytes each of eight bits.

5. The public-key data encryption system of claim 4 wherein the pre-selected length is 4 bytes each of eight bits.

6. The public-key data encryption system of claim 5 wherein the selected length is 4 bytes.

7. The public-key data encryption system of claim 1 wherein:

the non-secret key is (e, n) such that the encrypted form of a message M is M^e (mod n);

the secret key is d, such that the decrypted form of the encrypted form of the message M is (M^e (mod n))^d (mod n);

n is the product of two large random prime numbers p and q, each having a desired length, such that n has a suitable cryptoanalytically secure length to make n cryptoanalytically secure for a desired cryptoanalytic computational time;

e is an integer selected to have a GCD of [(e), (p-1) (q-1)]equal to 1; and

e*d≡

1 [mod (p-1) (q-1)].

8. The public-key data encryption system of claim 7 wherein the desired cryptoanalytic computational is approximately 1,000 years.

9. The public-key data encryption system of claim 8 wherein p and q are at least 23 bytes in length and n is at least 46 bytes in length.

19. The public-key data encryption system of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 or 18 wherein P is initially randomly selected from the known prime numbers having a length relatively short in comparison to the desired length.

20. The public-key data encryption system of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 or 18 wherein the selected known prime number is 139.

10. In a public-key data encryption system having a plurality of terminals, a terminal comprising:

a transmitter-receiver means for receiving encrypted messages, encrypted using a non-secret encryption key specific to the terminal;

an encrypter/decrypter means, for decrypting the encrypted message using a secret decryption key;

an encryption/decryption key generating means, coupled to the encrypter/decrypter means, for generating the non-secret and secret keys by use of a pair of large randomly selected prime numbers;

a large random prime number generating means, including a large-scale integrated circuit means, coupled to the encryption/decryption key generating means, for generating separately each of the pair of large randomly selected prime numbers, each having a desired length, the large-scale integrated circuit means including;

a random prime number selecting means for selecting a prime number P from the known prime numbers having a length relatively short in comparison to the desired length;

a prime number sequence generating means for generating a sequence of prime numbers starting with the prime number P selected by the prime number selecting means, the prime number sequence generating means including;

a selecting means for selecting a random h and forming the quantity hP+1, wherein P is the current prime in the computed sequence of prime numbers and is initially the P selected by the prime number selecting means;

a greatest common divisor (GCD) testing means for testing whether the GCD of (x), (hP+1) is equal to 1, wherein x is a composite number formed from the product of known prime numbers less than or equal to a selected known prime number;

a primality testing means, responsive to the determination by the GCD testing means that the GCD is equal to 1, for determining if both 2^hP ≡

1 [mod (hP+1)] and 2^h ≡

1 [mod (hP+1)];

an incrementing means, responsive to either the determination by the GCD testing means that the GCD is not equal to 1 or the determination by the primality testing means that either 2^hP ≢

1 [mod (hP+1)] or 2^h ≡

1 [mod (hP+1)], for incrementing h and forming a new hP+1 and initiating the determination by the GCD testing means with respect to the new hP+1;

a length determining means, responsive to the determination by the primality testing means that both 2^hP ≡

1 [mod (hP+1)] and 2^h ≢

1 [mod (hP+1)], for determining whether the length of hP+1 is greater than or equal to the desired length; and

,

a sequence placement means, responsive to the determination by the length determining means, that the length of hP+1 is not greater than or equal to the desired length, for placing hP+1 in the sequence of prime numbers and for initiating the selection by the selecting means of a new h to form a new hP+1, wherein P is the hP+1 previously determined to be prime but not greater than or equal to the desired length; and

,

an output means, coupled to the prime number sequence generating means and responsive to the determination by the length determining means that a respective hP+1 is greater than or equal to the desired length, for selecting the respective hP+1 as the output to the encryption/decryption key generating means as one of the necessary large randomly selected prime numbers having the desired length.

11. The public-key data encryption system of claim 10 wherein:

the selecting means includes a means for selecting each initial h which is even and which has a length of about one-half of the length of the current prime number in the sequence of prime numbers.

12. The public-key data encryption system of claim 10 wherein:

the length determining means includes a means for determining if the respective hP+1 is within a pre-selected length of the desired length, if not greater than or equal to the desired length, and if within the pre-selected length but not greater than or equal to the desired length, for initiating the selection by the selecting means of new initial h having a length less than approximately one-half of the length of the current prime number in the sequence of prime numbers, but sufficient to make the next prime number in the sequence of prime numbers greater than or equal to the desired length.

13. The public-key data encryption system of claim 12 wherein the desired length is 23 bytes.

14. The public-key data encryption system of claim 13 wherein the pre-selected length is 4 bytes.

15. The public-key data encryption system of claim 14 wherein the selected length is 4 bytes.

16. The public-key data encryption system of claim 10 wherein:

the non-secret encryption key is (e, n) such that the encrypted form of a message M is M^e (mod n);

the secret decryption key is d, such that the decrypted form of the encrypted form of the message M is (M^e (mod n))^d (mod n);

n is the product of two large randomly selected prime numbers p and q, each having a desired length, such that n has a suitable cryptoanalytically secure length to make n cryptoanalytically secure for a desired cryptoanalytic computational time;

e is an integer selected to have a GCD of [(e), (p-1) (q-1)] equal to 1; and

e*d≡

1 [mod (p-1) (q-1)].

17. The public-key data encryption system of claim 16 wherein the desired cryptoanalytic computational time is approximately 1,000 years.

18. The public-key data encryption system of claim 17 wherein p and q are at least 23 bytes in length and n is at least 46 bytes in length.

21. In a public-key data encryption system employing RSA public-key data encryption, a large random prime number generating means for generating large randomly selected prime numbers necessary for RSA public-key data encryption, each having a desired length, the random prime number generating means including a large-scale integrated circuit means for performing the following operations in selecting each of the necessary large random prime numbers:

starting with a P, which is a known prime number having a length which is relatively short in comparison to the desired length, forming a sequence of prime numbers in the form hP+1, wherein P is the current prime number in the computed sequence of prime numbers, by selecting at random an h and forming hP+1 and testing hP+1 for primality by determining first if the greatest common divisor (GCD) of [(hP+1), (x)] is one, wherein x is a composite number consisting of the product of known prime numbers less than or equal to a selected known prime, and if the GCD is equal to 1, determining if both 2^hP ≡

1 [mod (hP+1)] and 2^h ≢

1 [mod (hP+1)], and if the GCD is not equal to 1, or if the GCD is equal to 1, but either 2^hP ≢

1 [mod (hP+1)] or 2^h ≡

1 [mod (hP+1)], incrementing h to form a new hP+1, but if both 2^hP ≡

1 [mod (hP+1)] and 2^h ≢

1 [mod (hP+1)], determining if hP+1 is greater than or equal to the desired length, and if greater than or equal to the desired length, then setting hP+1 as one of the necessary large randomly selected prime numbers, and if not greater than or equal to the desired length, then placing hP+1 in the sequence of prime numbers and repeating the above steps using hP+1 as the new P and commencing by selecting a new h as above set forth.

22. In a public-key data encryption system employing RSA public-key data encryption, a large random prime number generating means for generating large randomly selected prime numbers necessary for RSA public-key data encryption, each having a desired length, the random prime number generating means including a large-scale integrated circuit means for generating the random prime numbers, the large-scale integrated circuit means having:

a random prime number selecting means for selecting a prime number P from the known prime numbers having a length relatively short in comparison to the desired length;

a prime number sequence generating means for generating a sequence of prime numbers starting with the prime number P selected by the prime number selecting means, the prime number sequence generating means including;

a selecting means for selecting a random h and forming the quantity hP+1, wherein P is the current prime number in the sequence of prime numbers and is initially the P selected by the prime number selecting means;

a greatest common divisor (GCD) testing means for testing whether the GCD [(x), (hP+1)] is equal to 1, wherein x is a composite number formed from the product of all known prime numbers less than or equal to a selected known prime number;

a primality testing means, responsive to the determination by the GCD testing means that the GCD is equal to 1, for determining if both 2^hP ≡

1 [mod (hP+1) and 2^h ≢

1 [mod (hP+1)];

an incrementing means, responsive to either the determination by the GCD testing means that the GCD is not equal to 1, or the determination by the primality testing means that either 2^hP ≢

1 [mod (hP+1)] or 2^h ≡

1 [mod (hP+1)], for incrementing h and forming a new hP+1, and initiating the determination by the GCD testing means with respect to the new hP+1;

a length determining means, responsive to the determination by the primality testing means that both 2^hP ≡

1 [mod (hP+1)] and 2^h ≢

1 [mod (hP+1)], for determining whether the length of hP+1 is greater than or equal to the desired length;

sequence placement means, responsive to the determination by the length determining means, that the length of hP+1 is not greater than or equal to the desired length, for placing hP+1 in the sequence of prime numbers and for initiating the selection by the selecting means of a new h to form a new hP+1 wherein P is the hP+1 previously determined to be prime but not greater than or equal to the desired length; and

,

an output means, responsive to the determination by the length determining means that a respective hP+1 is greater than or equal to the desired length, for selecting the respective hP+1 as one of the large randomly selected prime numbers necessary for the RSA public-key data encryption.