|
RSA cryptosystem (another Prime Pages' Glossary entries) |
|
|
Glossary:
Prime Pages:
Top 5000:
|
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. CJohn 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 Now for each encrypted block C we just calculate BSee 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:
Chris Caldwell © 1999-2010 (all rights reserved)
|
Be (