3
$\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.

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Sep 21, 2016 at 11:10

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Many thanks for your response made it a lot clearer. $\endgroup$
    – Joseph Howarth
    Commented Sep 20, 2016 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
    Commented Sep 20, 2016 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
    Commented Sep 20, 2016 at 12:12
  • 2
    $\begingroup$ In my experience RSA 2048 is the typical current recommendation. $\endgroup$
    – CodesInChaos
    Commented Sep 20, 2016 at 15:02
  • $\begingroup$ Updated to reflect comments by tylo and CodesinChaos. $\endgroup$
    – Stephen Touset
    Commented Sep 20, 2016 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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