Mathematician Project: RSA Encryption
by David Liu, 3/14/05
Cryptography literally means “secret writing”. It’s the process of encoding a message so that only the intended recipient can read it. Encrypting a message, or plaintext, makes it unreadable. On the other hand, decrypting the encrypted text, or cyphertext, turns it back into the plaintext.
Traditional cryptography depends on both parties knowing both the method of encryption and the secret key used. The same secret key is used to both encrypt and decrypt the message. The problem with this scheme, though, is that there is no easy way to communicate the secret key to both parties.
In 1976, a solution emerged: public key cryptography. This scheme involves two keys: a public key and a private key. As their names imply, the public key is freely distributed, and the private key is kept secret.
When one key is used to encrypt the message, only the other key will decrypt the message.
Let’s say Alice wants to send Bob a message. Alice looks up Bob’s public key, which is easily available, and uses it to encrypt her message, and sends off the result.
Now let’s say Eve has intercepted the encrypted message, and wants to read it. Bob’s public key cannot be used to decrypt the message. The only way Eve could read the message is if she had Bob’s private key, which is kept secret and never transmitted over the Internet.
This public key cryptography idea was powerful, but at the time there was no way to implement it. This was changed in 1978, when three men, Ronald Rivest, Adi Shamir, and Leonard Adleman, developed the RSA algorithm.
This algorithm is based upon the fact that it is extremely hard, using current technology, to factor large numbers.
Start by choosing two large primes, p and q. Multiply the primes together to get n. Notice that it is extremely hard to factor n back into p and q.
We can work through an example as I explain the algorithm. To keep things simple, we’ll choose primes p=3 and q=7.
This makes n=21.
Next, we must find a value e which is relatively prime to the value (p-1)(q-1).
(p-1)(q-1) is 12, so we can choose any number which is relatively prime to 12. Let’s make e=17.
Now we have both values necessary for the public key, n and e. These numbers may be distributed freely and anyone can use them to encrypt a message to us.
To determine our private key, we must find the modular inverse of e, (mod (p-1)(q-1)). We call this value d. To find the modular inverse, we’ll need something called the “Extended Euclidean Algorithm”. For more information on this, visit http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm. This site has a thorough explanation of the algorithm.
We need to find values x and y such that ex+(p-1)(q-1)y=1. Once we find this, x is the multiplicative inverse of e (mod (p-1)(q-1)).
The inverse of 17 (mod 12) is 5, as 17*5 mod 12 = 1. d=5.
Our private key is d.
To encrypt the plaintext w, we perform we mod n. This will result in the ciphertext, z. Remember that w is the plaintext in numerical form. There are many ways to convert words into numbers, but whatever the method, RSA can only operate on it if it is a number.
Let’s say our plaintext has been converted into the number 19. To encrypt it, we do 1917 mod 21. This equals: 5480386857784802185939 mod 21, which equals 10. Our ciphertext is 10.
To decrypt the ciphertext z, we perform zd mod n. This should bring us back to the original plaintext, z. Note that we are using the private key, d, to decrypt. Using the public exponent e would not decrypt the message.
To decrypt the ciphertext 10, we perform 105 mod 21. This is 100000 mod 21, which equals 19! We have successfully encrypted and decrypted a message.
In actual usage, remember that the primes p and q would be much, much larger. They need to be at least 150 or so digits long for reasonable security.
The sun would burn out before a product from such numbers could be factored
using current technology.
RSA encryption is often used in the real world to ensure privacy, security. Here are some common uses:
In conclusion, RSA is an extremely versatile algorithm which powers high security public key encryption. It is based on the fact that currently, it’s extremely difficult to factor large numbers.
Adam, Josh, Sam, and Paul. “Welcome to the world of RSA encryption!” June 12, 1996. http://personal.adamsutton.co.uk/websites/rsa/text/hiw.html
Francis Litterio . “The Mathematical Guts of RSA Encryption” 2001. http://world.std.com/~franl/crypto/rsa-guts.html
Wolfram Research, Inc. “RSA Encryption – From MathWorld” 2005. http://mathworld.wolfram.com/RSAEncryption.html
Wikipedia. “Extended Euclidean algorithm” February 23, 2005. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm