RSA Cryptography ... Simple and Elegant

RSA is named after it's inventors (R. Rivest, A. Shamir and L.Adleman ) and it's the most widely used public key cryptosystem. it's very strong way of encryption and it uses the idea of public private key encryption mechanism.

RSA is very powerful because it takes advantage of the mathematical problem of the intractability of prime number factorization and it's exponential.

Let's see together the typical encryption and decryption process of the RSA :

we have to generate two pair of keys public key and private key and we generate them as follows :

first we choose two distinct prime numbers P and Q .

then we compute the N and Φ

N = P * Q ----"1"

Φ = (P - 1) (Q - 1)----"2"

then we select the encryption exponent E which is a prime number that must fulfill the following characteristics :

integer and 1 < E < Φ , such that great common divisor gcd(E,Φ)=1 (we will explain it more on the example).

then we finally calculate the decryption exponent D which is multiplicative inverse of E

the equation for D = E^-1 mod Φ

The equation for encrypting massage M = M^E mod N ----"3"

The equation for decrypting massage C = C^D mod N ----"4"

let's see numerical example to make this process more understandable :

ex : let's suppose that we have a massage M = 7 and send it to from Alice to Bob and then let Bob decrypt it and get the massage back.

we choose our prime numbers to be

P = 11 Q = 17 E = 11

sol

first of all we have to calculate N and Φ

equation "1" and "2"

N = P * Q = 11 * 17 = 187

Φ = (P-1)(Q-1) = 10 * 16 = 160

then we calculate the gcd(E, Φ) to find if it is really equal to 1 and after that we will calculate the D which is the inverse multiplecitive of E

so to find the gcd (11, 160) using The Euclidean algorithm

160 = 11 (14) + 6 (this is actually 160/11 and the remaining )

11 = 6 (1) + 5

6 = 5 (1) + 1 ---"*"

5 = 1(5) + 0

we will ignore the plus Zero phase and our gcd is actually 1 and this is what we hope for.

Now we will calculate the D

D = E ^ -1 mod Φ

D = 11 ^ -1 mod 160 "***"

here we will use the Extended Euclidean algorithm

160 = 11 (14) + 6 (this is actually 160/11 and the remaining )

11 = 6 (1) + 5

6 = 5 (1) + 1 ---"*"

5 = 1(5) + 0

(now we will ignore the zero and work our way back up to complete the Extended Euclidean algrorithm)

1 = 6 - 5

5 = 11 - 6 (1)

6 = 160 - 11 (14)

we will substitute the 5 in the first equation with it's equivalence

1 = 6 - (11 - 6(1))

we simplify it to 1 = 2*6 - 11

then we substitute the 6 in the first equation with it's equivalence

1 = 2(160 - 11(14)) - 11

we simplify it to 1 = 2*160 - 28*11 - 11

1 = 2*160 - 29*11

since our modular is 160 in the equation "***" everything multiplied by the modular the remaining will be zero

1 = 0 - 29*11

so 11^-1 mod 160 ≡ -29 but as the rule stated the number should be between 1 and 160

D = 160 -29 = 131

Now we have all the component let's encrypt the massage M = 7 and send it to Bob

C = M^E mod N = 7^11 mod 187 = 150

we send the encrypted massage C to Bob .

Bob receive the massage and to read it he have to decrypt it

to get the massage Bob has to do the following

M = C^D mod N = 150^131 mod 187 = 7

and here it's we decrypt the massage with different key it seem like magic isn't it.

actually the attacker can't actually decrypt the massage without knowing the P and Q we choose them earlier because without them you can't find N and Φ and that means surely he can't find D.

In this example I used two small numbers for P and Q and it will be very easy to guess by computer but in reality we use a very large numbers.

Our public key actually contain E and N but RSA rely on the factorization problem because it will take time to guess the two prime number that are making N specially if we have very large encryption numbers which is usually the case because RSA uses 1024 or 2048 or 4096 bit and you can see even with the most powerful computer it will take years and maybe decades to find the two prime numbers.

It's always fascinating to see How simple and yet how Powerful the RSA is .