Why does RSA use semiprime numbers? Why not just use any big number ??
What is the advantage of the two original numbers being prime?

Because factoring any big number will be difficult

  • $\begingroup$ crypto.stackexchange.com/questions/10590/… $\endgroup$ Dec 7 '13 at 10:23
  • $\begingroup$ Factoring a big number which has less than two big factors is much easier. $\endgroup$ Dec 7 '13 at 10:28
  • $\begingroup$ @user16...: Example: Try and factor $2^{1337}$. That's a very big number, but its definitely not hard to factor! $\endgroup$ Dec 7 '13 at 10:31
  • 1
    $\begingroup$ Note: RSA has been extended to moduli with more than 2 factors (eg. 3), although that's not as common. $\endgroup$
    – Aleph
    Dec 7 '13 at 13:17

A Semiprime is the product of two prime numbers. Such numbers, i.e. semi primes, if enough large, as used in RSA, are very difficult to factorize. Since there is not enough computational power or a mathematical solution to factorize large prime numbers, the strength of the RSA stands. Currently, 2048-bit numbers are used in RSA for generating these keys, and with all the computational power in universe, it is impossible to factorize the semiprimes into their individual factors p and q. Now, knowing p and q would help you crack the RSA security by figuring out d (the private key). For large semiprimes, its impossible given the current computational power. Semiprimes are special than just any numbers because they are difficult to factorize, that's why the RSA algorithm utilizes them. It's mathematical beauty.


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