RSA Algorithm in Cryptography with example

RSA Algorithm in Cryptography

Rivest Shamir and Adelman (RSA) technique is a public key cryptography system. It facilitates the generation of public and private keys by choosing two large prime numbers p and q and making N = p.q. Next, a random positive integer e is chosen such that it is relatively prime to (p-1)(q-1), where e is called the encryption constant. Then the decryption constant d is derived such that e.d = 1 mod (p-1)(q-1). The public key is (N, e) and the private key is d.

It should be mentioned that although N is revealed to all, the factors p and q of N are kept secret. Obviously, if an intruding party can factor N to find p and q, then it can use the e of the public key to derive the private key d from the expression

e.d = 1 mod (p-1)(q-1)

RSA Algorithm Steps

The steps of the RSA algorithm are as follows:

Step-1: Generate two large prime numbers, p and q and let n = p.q.

Step-2: Let Φ = (p-1)(q-1)

Step-3: Choose another number e which is relatively prime to Φ, two numbers a and b that have no common factors other than 1. That is called co-prime or relatively prime.

Step-4: Select e, 1 < e< Φ such that gcd(e, Φ) = 1. GCD (greatest common divisor) of two integers a and b is the largest integer that divides both numbers.

Step-5: Find d, such that d.e ≡ 1 mod Φ. The notation “a ≡ b (mod n)” means a is congruent to b, that is a and b have the same remainder when divided by n.

Step-6: Encryption: Compute c = m^e mod n, where m is the message block represented as a number 0 < m < n-1 and c is the encrypted message.

Step-7: Decryption: Compute m = c⁴mod n.