CODEWITHSUNDEEP
primespublic-key-encryptionprime-factoring
Euthenia
Euthenia

Reputation: 111

The product of two large prime numbers in encryption

Ok, so I understand the importance of using the product of two large primes, but why not use the product of three large primes instead?

Would this make the encryption weaker in some way?

If the answer is not a simple one, then I would appreciate a technical answer if possible.

Upvotes: 1

Views: 2171

Answers (3)

user448810
user448810

Reputation: 17866

Say you have a 1024-bit key. With two primes, each is about 512 bits; with three primes, each is about 341 bits. Current factorization methods require exponential time, so each additional bit requires about double the time to find the factor. Thus, two primes are substantially stronger than three primes.

To be specific, a 768-bit key has been factored, and reported in the mathematical literature, which means that a 341-bit factor can be found (the 768-bit factorization took about 2000 PC-years, so it's not easy, but possible). No one has yet reported factorization of a 1024-bit key (although there are doubtless people working on it).

Upvotes: 1

user2736738
user2736738

Reputation: 30926

The public and the private key-generation algorithm is the most complex part of RSA cryptography. Two large prime numbers, p and q, are generated using the Rabin-Miller primality test algorithm. A modulus n is calculated by multiplying p and q. This number is used by both the public and private keys and provides the link between them.

Between sender and receiver you need 2 keys public and private. But for that you can use any number of primes but generally 2 is used.

  • But till now the performance of the algorithm doesn't improve due to any further increase in the strength of the algorithm.
  • Also it doesn't make any hard for the attackers.
  • The processing time for encryption and decryption will be much more higher. You can check some books on cryptanalysis.

Upvotes: 0

John Coleman
John Coleman

Reputation: 52008

The answer is simple, really. For numbers of a given size (e.g. 1024 bits) the toughest factoring problem is when the number factors into two primes (assuming that they are not too close to the square root of the overall number). Intuitively, it is easier to fish in oceans that contain more fish. It is easier to find one of three primes than one of two.

Upvotes: 0

Related Questions