Basic encryption/RSA prime number concept? [beginner] [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

so I understand that for RSA encryption, you multiply two large primes to get a very large composite number, which is your public key. The two large primes are your private key, so you want to keep both of those primes secret, and you can do so because it is impossible for the computer to guess them, because you would have to increment your guess by 1 each time for a long time, because each prime number is so large.

However my question is: why won't composite numbers work as well for this? If one of the large primes in your private key was a large composite, wouldn't you still have to guess it by incrementing by 2,3,5,7,11, etc? I know incrementing like this wouldn't take as long as incrementing by 1, but it would still take a long time because you don't know whether to increment by 2,3,5,7, etc.

Although if incrementing by 2 doesn't work, you can be sure private key < publickey/2, if incrementing by 3 doesnt work you can be sure that private key < publickey/3, and so on.

But anyways, can someone tell me why composite numbers aren't as good for encryption? How would you guess a large composite?

Answer 1

The use of prime numbers isn't about the difficulty of factoring - the most efficient method for factoring large composite numbers like the modulus of an RSA key is the General Number Field Sieve, which is much more efficient than simply trying to divide by successive numbers.

In fact, your statement that it doesn't work with composite numbers isn't really true - whilst RSA is generally performed using two primes, it still works more than two distinct primes, and since every composite number is a product of primes, you could choose two composite numbers (providing they are the product of distinct primes, and have no common factors) and the algorithm will still work.

For example, if we choose two composite numbers with distinct prime factors and no common factors:

a = 15 (= 3 * 5)
b = 77 (= 7 * 11)

This is equivalent to 4-prime RSA:

p = 3
q = 5
r = 7
s = 11

So far, so good however you go on to say that the "primes are your private key", which isn't really true either - the private key is actually the combination of the modulus n = p * q (which is also part of the public key), and the private exponent, which is the number d such that e * d = 1 mod phi(n) where e is the public exponent (which is often just 65537), and phi is Euler's totient function. Once d is calculated, the original primes can be discarded.

The problem is that calculating phi(n) requires knowing the prime factors of n. In ordinary RSA where n = p * q we already know the prime factors of n, but if we instead chose two composite numbers (like the a and b above) and use n = a * b we need to factor these numbers in order to calculate phi(n). Since the security of RSA itself relies on the difficulty of factoring large composite numbers, it is infeasible to calculate the private exponent if we haven't constructed the modulus directly from its prime factors, which is the real reason that you have to use primes rather than composite numbers.

Answer 2

because, like you said, with a prime number you have to increment by one. So if I have the number 13, it would take me 13 steps to get to the number 13 since it's prime so I'd be incrementing by one. But, if I have the number 14, it would only take me 7 steps to get there because i could go by twos. And the larger you scale the numbers the bigger the difference in them is. And I will admit you don't know what you need to increment by, but even incrementing by 2 is still faster than by one