# RSA

Suppose Eve, an eavesdropper, intercepts the public key *N* and *e*, and the ciphertext *c*. However, she is unable to directly obtain *d*, which Alice keeps secret. The most obvious way for Eve to deduce *n* from *c* is
to factor *N* into *p* and *q*, in order to compute (*p*-1)(*q*-1) which allows the determination of *d* from *e*. No polynomial-time method for factoring large integers
on a classical computer has yet been found, but it has not been proven that none exists. See integer factorization for a discussion of this problem.

It has not been proven that factoring *N* is the only way of deducing *n* from *c*, but no easier method has been discovered (at least to public knowledge.)

Therefore, it is generally presumed that Eve is defeated in practice if *N* is sufficiently large.

If *N* is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If *N* is 512 bits or shorter, it can be factored by several hundred computers as of 1999.
It is currently recommended that *N* be at least 1024 bits long.

In 1993, Peter Shor showed that a quantum computer could in principle perform the factorization in polynomial time. If (or when) quantum computers become a practical technology, Shor's algorithm will make RSA and related algorithms obsolete.

Should an efficient classical factorization code be discovered or a practical quantum computer constructed, using still larger key lengths would provide a stopgap measure. However, any such security break in RSA would obviously be *retroactive*.
An eavesdropper who had recorded a public key and any ciphertext produced with it (easily found by just recording traffic to that public key's owner), could simply wait until such a breakthrough. And then decipher that ciphertext into the plaintext
message. Therefore, it is inherently unsafe to exchange long-term secrets with RSA or any cipher with similar vulnerabilities.