I'm studying how the selection of prime numbers in RSA encryption may affect the security of the encryption in regards to the public key.
Essentially, are there any specific types of prime numbers that render the most secure public key? (meaning that someone cannot backtrack the public key and figure out the private key)
Or do the prime numbers just have to be 'sufficiently' large?
Thanks for helping out :)
As long as the two primes are large and random, and ideally approximately the same size, they will be suitable for a secure implementation of RSA. For an $n$-bit RSA key, it's generally safe to generate two $n/2$-bit random primes. As long as the two primes are generated randomly using a cryptographically-secure random number generator, they can be used securely. The difficulty comes in quickly and accurately determining whether or not an integer is prime, but luckily there are probabilistic algorithms like the Miller-Rabin primality test which are quite effective when run a sufficient number of times.
The most common method of generating random primes involves generating a large, random odd integer and checking if it is prime. If it is not, then it is incremented by two and checked again. This repeats until it is prime. Note that this method does not find perfectly-distributed primes. It is biased towards primes with large gaps between it and the previous prime. However, there are no known ways to exploit this bias and it is believed that none exist. The alternate, slightly slower method of finding primes is to generate a random odd integer and check it for primality. If it is not prime, then rather than adding two and checking again, a new independent integer is generated and checked for primality.
If you want to use a standard for prime generation, consider FIPS 186-4, which should be safe.
