### What is the
Significance of Factoring in Cryptography?

Factoring is the underlying, presumably
hard problem upon which several public-key cryptosystems are
based, including RSA. Factoring an RSA modulus (see Question 8) would allow an attacker to figure out the
private key; thus, anyone who can factor the modulus can
decrypt messages and forge signatures. The security of RSA
depends on the factoring problem being difficult and the
presence of no other types of attack. Unfortunately, it has
not been proven that factoring must be difficult, and there
remains a possibility that a quick and easy factoring method
might be discovered (see Question 49),
although factoring researchers consider this possibility
remote.

Factoring large numbers takes more time
than factoring smaller numbers. This is why the size of the
modulus in RSA determines how secure an actual use of RSA is;
the larger the modulus, the longer it would take an attacker
to factor, and thus the more resistant to attack the RSA
modulus is.