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 ≡ Be (mod n)
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 ≡ Cd (mod n).
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)
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. Pomerance editor, Cryptology and computational number theory--an introduction, Proc. Symp. Appl. Math. Vol, 42, Amer. Math. Soc., Providence, RI, 1990. 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. Simmons editor, Contemporary cryptology -- the science of information integrity, IEEE Press, 1992. pp. xvi+640, MR 93k:94009