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.