# Prime numbers in RSA encryption [duplicate]

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 :)

• May 19, 2019 at 6:06
• May 19, 2019 at 23:58
• In particular, although the question How common are weak RSA keys? is phrased differently, it seems to be essentially the same question: Is the uniform random distribution on prime numbers of some size good enough, or do we need to impose additional criteria to avoid weak keys? May 20, 2019 at 15:40

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.