# RSA cryptosystem

The **RSA algorithm**, perhaps the most famous of all
public key cryptosystems, was announced in 1977 by Ronald
Rivest, Adi Shamir, and Leonard Adleman at MIT. RSA relies
on the relative ease of finding large primes and the
comparative difficulty of factoring integers for its
security.

To use this system we first find two large primes
*p* and *q* and form their product *n* =
*pq*. Next we choose a random integer *e* which
is relatively prime to (*p*-1)( *q*-1) (this is
phi(*n*)). The pair (*n*,*e*) is made
public (it is the public key), but the prime factors
*p* and *q* are kept secret. Using this public
key anyone can encrypt a message to send to us, a message
which presumably only we can decrypt.

Suppose John wishes to send us an encrypted message.
John would convert his message to numbers (using, for
example, a=01, b=02, . . . , z = 26, blank=27) and break
this message into blocks smaller than the number *n*.
For each block *B* John computes an encrypted block
*C* as follows.

C≡B^{e}(modn)

John then can send the blocks *C* to us.

We can decrypt this message using Euler’s theorem. To
decrypt any message we first calculate an integer *d*
such that *ed* ≡ 1 (mod (*p*-1)( *q*-1)).
(This is easily done using the extended Euclidean
algorithm.) The pair (*n*,*d*) is the private
key, and once it is found all records of the prime factors
*p* and *q* of *n* should be destroyed.

Now for each encrypted block *C* we just calculate

B≡C^{d}(modn).

See the example below.

There is no known way to break the break the RSA
system without finding its prime factorization. So we must
be careful to ensure our number *n* is difficult to
factor! For example, to avoid a factorization by Pollard’s
*p*-1 method we must make sure *p*-1 and *q*-1 both
have at least one large prime factor.

As factorization methods continue to improve and computer power continues to increase, the key sizes used in RSA encryption must also be increased. In 1977 Rivest, Shamir and Adleman published a challenge (a message encrypted) using 129 digit integers. They expected this to remain unbroken for a long time.

But it was broken in 1994 using about the same amount of computer operations used to animate the movie Toy Story (about 5000 MIPS years). So when choosing a key size consider how long you want the encryption to last!

**See Also:** RSAExample

**Related pages** (outside of this work)

- The PGP Attack FAQ Part 2 is breaking the RSA cipher in PGP
- RSA Laboratories' Frequently Asked Questions About Today's Cryptography
- Electronic Frontier Foundation

**References:**

- Bernstein2001
D. Bernstein, "Circuits for integer factorization: a proposal," (2001) Available from http://cr.yp.to/factorization.html. (Abstract available)- Odlyzko94
A. M. Odlyzko, "Public key cryptology,"AT\&T Tech. J.,73:5 (Sept-Oct 1994) 17-23.- Pomerance94a
C. Pomeranceeditor,Cryptology and computational number theory--an introduction, Proc. Symp. Appl. Math. Vol, 42, Amer. Math. Soc., 1990. Providence, RI, pp. 1--12,MR 92e:94023- Schneier96
B. Schneier,Applied cryptography, 2nd edition, John Wiley \& Sons, 1996. New York, NY, [A comprehensive pragmatic survey of modern cryptology--perhaps the best introduction for those actually wishing to understand the details of the usual implementations.]- Simmons91
G. Simmonseditor,Contemporary cryptology -- the science of information integrity, IEEE Press, 1992. pp. xvi+640,MR 93k:94009