How RSA Algorithm Works

The RSA algorithm is used for public key encryption and digital signature. In this algorithm data (input) is encrypted using a public key and decrypted using private key. The public key is exposed to the sender and the receiver will keep the private key. Most people knows this ability of RSA algorithm. But they don’t know how it is possible.

Here is the mathematical explanation of RSA algorithm

1. Let’s assume that p and q are two large prime numbers.
2. Now calculate n = p*q and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1
4. Find the secret exponent d, 1 < d < phi, such that
   (e*d) % phi = 1
5. The public key is (n, e) and the private key is (n, d).
6. The values of p, q, and phi should also be kept secret.
7. Encryption : C=(I^e)%n
8. Decryption: I=(C^d)%n

• n is known as the modulus.
• e is known as the public exponent or encryption exponent.
• d is known as the secret exponent or decryption exponent.

Let us examine the algorithm step by step

1. Let p=7 and q=17
2. n=pq=7*17=119
3. phi=(p-1)*(q-1)=(7–1)*(17–1)*17=96
4. Let e=5. So, gcd(5,96)=1
5. Calculated d=77 as (5*77)%96=1
6. So our private key is (119,77) and the public key is (119,5)

Now we can examine encrypt and decrypt method.
Let our input I is 7. So, C=(7^5)%119=16807%119=28
So, 28 is the encrypted number. We cannot find 7 from the encrypted number 28 and public key (119,5).

Let us use our private key (119,77) to decrypt 28.
I=(28^77)%119=2.6987857810871449487269638198368e+111%119=7. So, 7 is the decrypted number.