2
$\begingroup$

I have recently been reading about encryption and the importance of prime numbers and I have some questions that I would really appreciate some answers to, if possible:

  1. Is it correct that when creating encryption keys you take one large prime number, and then multiply it by another prime number to leave you with an even larger prime number?
  2. If 1 is correct, then is it correct to say "the reason for the large prime number calculation is it is very difficult and time consuming to work out what the initial prime numbers were used in the original calculation"?
  3. What constitutes as a large prime number?

The reason for this question is I have been doing some reading about encryption as stated above, and assuming the above statements are correct I think I have a really simple formula for working out what the original prime numbers used were. I have tested this prime numbers all the way up to $299993$. And I must be doing this wrong because it can not be this simple, I assume someone will point out where I am going wrong.

$\endgroup$
  • $\begingroup$ In the context of cryptography based on integer factorization, 299993 (which is 20-bit) is a small prime, and has been so since at least the 1960s. In the present century, large never started before 250 bits, and ECM has been used to pull factors of about that size. $\endgroup$ – fgrieu Sep 21 '16 at 11:10
6
$\begingroup$

Is it correct that when creating encryption keys you take one large prime number multiple it by another prime number to leave you with a even larger prime number?

Any number that is a multiple of two primes is by definition not prime. This creates a semiprime: a number that has only two prime factors.

This approach is only used in a few cryptosystems, the most common of which is RSA. Many other cryptosystems exist that do not rely on integer factorization. Some of these systems (e.g., AES, ChaCha20) are symmetric algorithms unlike RSA, and some (e.g., ECC) are asymmetric like RSA. RSA is gradually being phased out in favor of modern systems based on elliptic curves.

If 1 is correct, then is it correct to say "the reason for the large prime number calculation is it is very difficult and time consuming to work out what the initial prime numbers were used in the original calculation"?

Yes. As far as we know, integer factorization is a hard problem.

What constitutes as a large prime number?

2048-bit RSA is a typical current recommendation. In this case, the modulus (e.g., the semiprime) is the part that is 2048 bits, so each prime is roughly 1024 bits long. For scale, a 1024-bit prime will be over 150 decimal digits long, so they are quite large.

$\endgroup$
  • $\begingroup$ Many thanks for your response made it a lot clearer. $\endgroup$ – Joseph Howarth Sep 20 '16 at 9:49
  • 1
    $\begingroup$ There are other cryptosystems based on the factorization being hard, e.g. Paillier and Rabin. Maybe put an actual 4096 bit number in the answer, to show how far a tiny number like $299993$ is from what is considered a number large enough. (Although I would say recommendations differ quite a bit, and 4096 is mentioned not that often - 2048 or 3072 are more common) $\endgroup$ – tylo Sep 20 '16 at 12:03
  • $\begingroup$ @JosephHowarth, it looks like you may have accidentally created two accounts. If you are the same person as "Joe" who posted the question. If that is the case, follow this guidance for how to merge your accounts. $\endgroup$ – mikeazo Sep 20 '16 at 12:12
  • 2
    $\begingroup$ In my experience RSA 2048 is the typical current recommendation. $\endgroup$ – CodesInChaos Sep 20 '16 at 15:02
  • $\begingroup$ Updated to reflect comments by tylo and CodesinChaos. $\endgroup$ – Stephen Touset Sep 20 '16 at 19:06

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.