초록 ▼

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 lo

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 2hP≡1 [mod (hP+1)]and 2h≠1 [mod (hP+1)], and if either 2hP≠1 [mod (hP+1)]or 2h≡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.

대표청구항 ▼

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 incl

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 2hP≡1 [mod (hP+1)]and 2h≠1 [mod (hP+1)], and if the GCD is not equal to 1, or if the GCD is equal to 1, but either 2hP≠1 [mod (hP+1)]or 2h≡1 [mod (hP+ 1)], incrementing h to form a new hP+1, but if both 2hP≡1 [mod (hP+1)]and 2h≠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.