RSA -- A public-key encryption algorithm

What is RSA ? and why named like that ?

RSA is an algorithm for public-key encryption. The RSA algorithm was invented in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman and was named after them.

How RSA works ?

Here's the relatively easy to understand math behind RSA public key encryption.

1. Find P and Q, two large (e.g., 1024-bit) prime numbers.

2. Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.

3. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.

4. The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.

5. The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.

Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful deterministic computers presently in existence can factor your modulus into P and Q.

An Example of the RSA Algorithm:

P = 61 <- first prime number

Q = 53 <- second prime number

PQ = 3233 <- modulus (give this to others)

E = 17 <- public exponent (give this to others)

D = 2753 <- private exponent (keep this secret!)

Your public key is (E,PQ).

Your private key is D.

The encryption function is:

encrypt(T) = (T^E) mod PQ = (T^17) mod 3233

The decryption function is:

decrypt(C) = (C^D) mod PQ = (C^2753) mod 3233

To encrypt the plaintext value 123, do this:

encrypt(123) = (123^17) mod 3233 = 337587917446653715596592958817679803 mod 3233 = 855

To decrypt the ciphertext value 855, do this:

decrypt(855) = (855^2753) mod 3233 = 123

Sources and more about RSA:

http://en.wikipedia.org/wiki/RSA

http://world.std.com/~franl/crypto/rsa-guts.html