## RSA

RSA is an asymmetric algorithm and is attributed to three people but reading this article will explain who developed the algorithm years earlier. When reading this article, try to understand the section on key generation, encrypting messages, decrypting messages, and signing messages. Most importantly, note the speed of RSA in comparison to DES that was discussed in the section on symmetric key encryption. Also note how attacks such as man-in-the-middle and RSA blinding attacks can be avoided.

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.