Note 4/20/17: Due to circumstances I have had to move my web pages here.
Click here for a faster version using a Java applet
How RSA works
Start by Generating a pair of primes, p and q.
Choose an encryption exponent e relatively prime to (p-1)*(q-1).
Then generate a decryption exponent d such that
e * d == 1 (modulo (p-1)*(q-1) ). Then calculate n = p * q.
To encrypt a message, convert your message into a large integer m.
Then calculate c = me (modulo n).
Decrypting the message is simple: calculate cd (modulo n),
although a faster approach uses knowledge of p and q
with the Chinese Remainder Theorem.
Generating Primes
Generating primes are key to the RSA algorithm. The approach used here (in an invisible
Java applet for speed) involves two tests for primality.
First a random odd number of the appropriate size is generated, using a cryptographically
secure random number generator. Second, the number is tested by dividing it by
3, 5, 7, 11, 13, 17 and 19 to eliminate many non-prime numbers.
This approach can be continued for small numbers, but isn't feasible for large
(20 or more digits), so another test.
This second primality test is based on Fermat's little theorem, which says (in one
variant), that if a number p is prime, then for any 2 ≤ a < p, then
ap-1 == 1 (modulo p).
For composite numbers, this test usually (but not always) fails. So this test is often
repeated until a desired level of confidence is reached (balancing speed and confidence).
A number that passes all the tests is declared prime.
Note that ideally the two primes should not be quite the same size, since some factoring
algorithms can quickly find two similar-sized factors of a number.
Generating Encryption and Decryption Exponents
To calculate the exponents, we must find two values: First an encryption exponent e
relatively prime to (p-1)*(q-1) , and then the
decryption exponent d such that
e * d ≡ 1 (modulo (p-1)*(q-1) ).
These can be done simultaneously using a variation on Euclid's algorithm:
- Set x[0] = (p-1)*(q-1)
- Set y[0] = 0
- Set x[1] = e
- Set y[1] = 1
- Then while x[i] > 0 calulate:
- x[i] = x[i-2] modulo x[i-1]
- y[i] = y[i-2] - floor( x[i-2] / x[i-1] ) * y[i-1]
- You can show by induction that x[i] ≡ e * y[i] (modulo (p-1)*(q-1) ),
so if x[i] = 1 we know both that e is relatively
prime to (p-1)*(q-1),
and that y[i] (modulo (p-1)*(q-1) ) is the corresponding value for
d
Encryption/Decryption
The encryption equation me (modulo n) is simple, but very time
consuming, especially when you realize that n may be 1000 or more bits long, even before
we start raising it to the power e.
Two things make this reasonable: First is the standard power rule
xy+z = xy * xz. So we can calculate
me by repeatedly squaring m and multiplying the appropriate
powers together.
The other equation that helps is a * b (modulo n) ≡
(a (modulo n)) * (b modulo n)) (modulo n), so we can
take the value modulo n as often as we want, usually after every multiplication.
Decrypting using the Chinese Remainder Theorem
The above process is still slow, but we can make it much faster,
by exploiting our knowledge of p and q when we decrypt a message.
We end up doing two
modular exponentiations, but since the numbers (and exponents) are smaller, we end
up as much as four times faster overall.
Often this is combined with a small e such as 3, 17, or 65537 to keep the
encryption time reasonable.
When we calculate the keys, we calculate four additional values:
- d1 = d (modulo p-1)
- d2 = d (modulo q-1)
- p-1 (modulo q) - Use the same algorithm
we used to calculate the decryption exponent d above
- q-1 (modulo p)
To decrypt a message m, calculate:
- Mp = md1 (modulo p)
- Mq = md2 (modulo q)
Then the decrypted message is
(Mp * ( q-1 (modulo p) ) * q
+ Mq * ( p-1 (modulo q) ) * q) (modulo n).
Return to my home page
Send Mail