5
$\begingroup$

I was talking to a friend of mine yesterday about encryption. I was explaining RSA and how prime numbers are used - the product $N = pq$ is known to the public and used to encrypt, but to decrypt you need to know the primes $p$ and $q$ which you keep to yourself. The factorization of $N$ is the hard part, and that's why RSA is safe.

Then I was asked: Who actually calculates these primes, and how? They're huge, so can you do it on just a normal computer (in reasonable time)? And if not, and encryption software gets the primes from somewhere else, this third party would have a list of primes (however large) to try to factor $N$ with. Using it would be considerably easier than just brute forcing, trying to divide with every prime number up to $\sqrt{N}$. If they (or someone else) has the list, encryption isn't really safe.

So, how is it actually done?

$\endgroup$
  • 2
    $\begingroup$ The primes are generated locally, on your (or whoever's) computer. Finding large primes and testing that they really are prime can be done in reasonable time by normal computers nowadays (although the test might be probabilistic, but with an error probability below the probability of a hardware fault). $\endgroup$ – Daniel Fischer Feb 26 '14 at 21:34
  • 1
    $\begingroup$ This question was raised and answered well over at Crypto SE. $\endgroup$ – anon Feb 27 '14 at 21:15
  • $\begingroup$ If somebody else generates it, you have to worry about who else they tell. $\endgroup$ – Ross Millikan Feb 27 '14 at 21:30
4
$\begingroup$

They are generated on the machine doing the encryption. Generating primes of a given size is fairly easy, and verifying that they are prime can be done much faster than trial division.

1024-bit RSA requires two 512-bit primes. On my (old) machine it takes about 34 milliseconds to generate a 512-bit prime (so generating the whole key would take about 0.07 seconds). That's about 10 milliseconds to find the prime and 25 to verify it to high certainty. If I was willing to live with 'only' one mistake in $10^{100}$ I could verify a prime in a third the time. If I wanted to instead prove that it was a prime, it would take about 1.6 seconds... but that's overkill for reasonable purposes. (Better to move to a higher bit level with less certainty.)

$\endgroup$
2
$\begingroup$

Cryptography libraries like PGP, GPG, Openssl generate the primes used for RSA encryption. They generally won't store the primes directly but compute N and Phi then forget them.

Openssl can generate a 2048 bit RSA key quite fast in just a few seconds on my laptop. On a Linux machine or Mac OS X you can run the command

openssl genrsa and inspect the output.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.