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 = me 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 = c4mod n.