Next: 3.4.5 Has factoring been
Up: 3.4 Factoring and Discrete
Previous: 3.4.3 What is the
Factoring is the underlying, presumably hard problem upon which several
public-key cryptosystems are based, including RSA. Factoring an RSA modulus
(see Question 3.2.1) 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 therefore depends on the
factoring problem being difficult. 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
3.4.7), 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
implementation is.
Denis Arnaud
12/19/1997