Note 4/20/17: Due to circumstances I have had to move my web pages here.

Click here for a JavaScript-based version (slower, but no Java applet needed)

## 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.

Note: This page relies on a Java applet to do the actual calculations.

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) 3 4 5 6 7 8 9 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 90 100 150 200 Size of the Second Prime (p) 3 4 5 6 7 8 9 10 15 20 25 30 35 40 45 50 60 70 80 90 100 150 200 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:
• Set x = (p-1)*(q-1)
• Set y = 0
• Set x = e
• Set y = 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).

Send Mail