RSA

"A New Kind of Cipher that Would Take Millions of Years to Break." - Martin Gardner.

Although Diffie and Hellmen came up with a unique way to exchange keys securely over a public medium, the search was still on for a truly asymmetric cipher. At MIT, the trio Ronald Rivest, Adi Shamir and Leonard Adleman came up with RSA, namely the acronym for their last names in 1978. RSA uses a one-way function and makes use of very large primes.

RSA Process

1. Select two very large prime numbers P and Q such that P * Q = N and the plaintext M < N.

2. Find any number E such that E is relatively prime to Φ(N) = (P – 1) * (Q – 1). Then the public key is {E, N}.

3. Find another number D such that (D * E) ≡ 1 mod Φ(N), where E and D are multiplicative inverses of each other mod Φ(N). Then the private key is {D, N}.

Note that E, D Î Z^*_Φ(N), where E * D ≡ 1 mod Φ(N), such that the message M = M^ED mod N

Encryption

A chunk of plaintext M, that is smaller than N, is raised to the E power mod N to produce ciphertext C:

C = M^E mod(N) such that 0 < C < N

Decryption

C is raised to the private key D power mod N:

M = C^D mod(N)

Example

1. Suppose that we choose P = 7 and Q = 13, which yields N = 91 and Φ(91) = (7 – 1) * (13 – 1) = 72.

2. Next, find an E that is relatively prime to 72 so we choose E = 5, yielding a public key of {5, 91}.

3. We then find D from (D * 5) ≡ 1 mod 72, which is [(D * 5) mod 72] = [1 mod 72] = 1. So, D = 101, because (101 * 5) mod 72 = 505 mod 72 = 1, yielding a private key of {101, 91}.

Encryption

Now let us encrypt a message that has a numeric value of 3, for example. We will use the public key, {5, 91} of the recipient. Now, 3 becomes encrypted as 61. 61 is sent to the recipient.

C = 3⁵ mod 91 = 61

Decryption

The receiver raises 61 to his own private number mod 91, such that the decryption process yields the original letter:

M = 61¹⁰¹ mod 91 = 3

Security

RSA's security is based on the RSA problem that is when given N, E and the C find D. Moreover, the RSA strength is based on factorization and the discrete logarithm problem. RSA can be subjected to a chosen ciphertext attack where the attacker can force feed the decryption process with various encrypted values to be able to deduce plaintext values. Furthermore, there are two more general types of possible attacks: (1) Mathematical manipulation and (2) Timing attacks. Mathematically there are a few approaches to attacking RSA. The most significant approach is to try to break N down into its 2 prime factors. Ideally and currently, you would probably want an N size greater than 10³⁰⁰. Until mathematicians find a fast and easy way to factor very large numbers, which by the way is RSA's only known weakness, RSA is very secure. Another attack that has a slight tint of potential is a timing attack. A private key can possibly be determined by tracking the amount of times it takes to decipher ciphertext. However, one can easily thwart off this kind of attack by always keeping this time frame constant or multiply a random number by the ciphertext before exponentiation.

Links

http://www.rsasecurity.com/rsalabs/faq/index.html
http://www.rsasecurity.com/rsalabs/pkcs/index.html
http://csrc.nist.gov/encryption/aes/rijndael/
http://theory.lcs.mit.edu/~rivest/publications.html