4

i know that public key cryptography uses prime numbers, also know that two large(e.g. 100 digit) prime numbers (P, Q) are used as the private key, the product is a public key N = P * Q, and using prime numbers is because the factorization of N to obtain P , Q is sooo difficult and takes much time, i'm ok with that, but i'm puzzled why not just use any ordinary large non-prime numbers for P , Q and so the factorization of N will be still difficult because there would because now , there are not only 2 factors possible, but even more.

thanks....

user452799
  • 73
  • 6
  • You can approach your question let's say for decryption purposes or efficient hashing. Anyways you want to minimize collisions (repeated outputs) and prime characteristics a good (not perfect) for that. You can take a very large non-prime, but once the computer knows it becomes relatively small compared with all the nums. that are bigger than it. – Eric Fortis Dec 19 '10 at 02:42

3 Answers3

2

I am not a crypto expert.

why not just use any ordinary large non-prime numbers for P , Q

Because there would be more factors. Integer factorization is an attack against public private key encryption. This attack exploits this very relation.

One could more easily find the relation and possible values with more common factors. It boils down to algebra.

N = P * Q

if P and Q are both Prime then N has 4 factors {N P Q 1}

However! if P and Q both share a factor of 2

N / 4 = P / 2 * Q / 2

If N could have been 0..2^4096 it is now 0..2^4094 and since 2 was a factor another large number was also a factor.

This means that I could find a scalar multiple, P', Q' of P,Q S.T. P',Q' < P,Q

I don't fully understand the concept myself but I believe this shows where i'm going with this.

You have to search a smaller space until you brute force the key.

EnabrenTane
  • 7,428
  • 2
  • 26
  • 44
2

It is perfectly possible to use RSA with a modulus N that is composed of more than two prime factors P and Q, but two things have to be noted:

  1. You must know the exact value of all of these factors, or else you will be unable to derive the private key from the public key upon key generation. The equation for two-prime RSA is 1 = D*E (mod LCM(P-1,Q-1)). If you do know these prime factors, you can perform the calculation. If you don't know the prime factors you can't perform this calculation, which BTW is why it is safe to make the public key E,N public - you can't derive the private key D if you only have the information that is easily derived from the public key, unless you are able to factor N.

  2. The security of RSA is effectively bounded by the magnitude of the second largest prime factor of the RSA modulus N. Finding small prime factors that are less than 2^32 can be done in a fraction of a second on a modern computer, simply by trying to divide the modulus N by each such prime and check if the residue is zero (meaning N is divisible by that number) or not (meaning that number is not a factor of N). If N is composed of only such small prime factors times a single large prime factor Q, it would be trivial to find that Q as well, simply by dividing N by all small factors to get N' and test N' for primality. If N' is a prime, it is the last prime factor Q.

Henrick Hellström
  • 2,556
  • 16
  • 18
0

I'm not really expert in cryptology (so if I'm wrong just tell me in a comment, and I'll promptly delete this answer), but I think it's because if you just use random large numbers you may get easily factorisable ones (i.e. you don't have to get up to really large prime numbers to get their prime factors). So just really big, guaranteed-prime numbers are used.

Matteo Italia
  • 123,740
  • 17
  • 206
  • 299