Behind the Scenes of RSA

I had specified in the "Writing Strong Crypto Algo" post that a computationally unsolvable problem (NP complete problem) is usually coupled with a Cryptographic algorithm to make it really hard to break. The NP Complete problem associated with RSA algorithm is Factorization Problem

What is Factorization problem ?
Factorization problem is problem of finding two large prime factors that make the product if only the product is known.

RSA Algorithm :
1. Take any two very large prime numbers P and Q. N which is the product of PQ is referred to as the modulus.

2. Take any number E which is less than PQ and does not have a common prime factor with (P-1)(Q-1).

3. Now we need to pick a private key. The private key D can be any number such that DE- 1 is divisible by (P-1)(Q-1).

4. Next step is the encoding the message. Encoding is done using the formula C = T E mod N
where T is the value of the text to be encoded. and C is the encoded result / Cypher text

5. Decoding the cypher can be done using the private key and the modulus N using the formula T = C D mod N

The public key consists of
n, the modulus, and
e, the public exponent (sometimes encryption exponent).

The private key consists of
d, the private exponent (sometimes decryption exponent), which must be kept secret.

A working example :
Here is an example of RSA encryption and decryption. The parameters used here are artificially small

p = 61 — first prime number (to be kept secret or deleted securely)
q = 53 — second prime number (to be kept secret or deleted securely)
n = pq = 3233 — modulus (to be made public)
e = 17 — public exponent (to be made public)
d = 2753 — private exponent (to be kept secret)

The public key is (e, n). The private key is d.
The encryption function is: encrypt(m) = me mod n = m17 mod 3233
where m is the plaintext.

The decryption function is: decrypt(c) = cd mod n = c2753 mod 3233
where c is the ciphertext.

To encrypt the plaintext value 123, we calculate
encrypt(123) = 12317 mod 3233 = 855

To decrypt the ciphertext value 855, we calculate
decrypt(855) = 8552753 mod 3233 = 123


How to break RSA ?
If someone can get the value of D (the private key) they can decipher the cypher text C. We know that D is chosen in such a way that DE - 1 is divisible by (P-1) (Q-1). So if we know P and Q, we can compute D.

Here comes the Factorization problem. Though we know the product of PQ which is N, we cannot compute the value of P and Q from N. This is how the NP complete problem gets associated with RSA algo to make it strong.