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.


10/27/06: I have decided to make many of these boxes read-only to reduce the chance of this page being used to solve homework problems
Prime Generation
Size of the First Prime (p)
Size of the Second Prime (p)
First Prime (p)
Second Prime (q)

Key Generation
Encryption Exponent (e)
Modulus (n)
Decryption Exponent (d)

Message to encrypt/decrypt
ASCII Hexadecimal Decimal
Output message
ASCII Hexadecimal Decimal

Details:

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:

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:

To decrypt a message m, calculate: Then the decrypted message is (Mp * ( p-1 (modulo q) ) * q + Mq * ( q-1 (modulo p) ) * q) (modulo n).


Return to my
home page
Go to the EKU CS Department page