RSA Algorithm Illustrated

neotam Avatar

RSA Algorithm Illustrated

RSA is asymmetric key encryption algorithm which was first presented by three MIT researchers Ron Rivest, Adi Shamir and Leonard Adleman in the year 1977. This algorithm uses trapdoor function based on the fact that it is easy to compute product of two primes but not prime factorization of given large number. RSA is named after three initials of inventors Rivest, Shamir and Adleman (RSA)

RSA algorithm is also called as public key algorithm. RSA is widely used in secure data communication, digital signature and key distribution

Trapdoor function is a mathematical function which is easy to compute in one direction but difficult or time taking to compute in opposite direction

RSA algorithm uses prime factorization as trapdoor function. For example take following scenario

Given two prime numbers 193 and 71 it is easy to compute product 193 * 71 = 13703
But, it way difficult to compute prime factors of product 13703 assuming that prime numbers are not know before

RSA Algorithm

Let’s assume

M as message or plain text
C as cipher text or encrypted message
n as integer
p and q are prime factors of n

RSA algorithm take two prime numbers p & q and plain text M
Give output, cipher text C and possible d and e values

RSA is asymmetric key or public key algorithm. It involves key generation, generated keys are used in encryption and decryption

Key generation portion gives the output of public and private keys by taking in put of two prime numbers p and q where p ≠ q

Key Generation

Key generation algorithm is the critical part. It take two prime numbers p & q as an input and produces possible values of d & e which are used to make private and public keys respectively

Input: p, q where p ≠ q
output: possible d, e where public key Ku = {e, n} and private key Kr = {d, n}

Follow steps describe key generation algorithm

z is also referred as Euler totient of n. There relation ship between e,d and z is expressed as

→ select p, q where p ≠ q and prime numbers
→ calculate n = p x q
→ calculate z = (p-1)(q-1) where z is a co-prime of n
→ calculate e such that gcd(z, e)=1; 1 < e < z; e is co-prime of z or e is relatively prime to z
→ calculate d such that de mod z = 1
→ Private key Kr = {d, n}
→ public key Ku = {e, n}
ed mod z = 1

Choose p and q and calculate n that is product of p and q. Where n is modulus for encryption and decryption

There are two types of ciphers based on how they work on plain text, that are block cipher and stream cipher. RSA is block cipher, where both plaintext and ciphertext are integers with in range of 0 and n-1 for n.

Encryption

Encryption logic using public key

→ C = Me mod n

Where, M < n

Decryption

Decryption using private key

→ M = Cd mod n

For RSA to work for all M, M < n

This RSA algorithm works on the principle that determining d is not feasible given e and n

Example

Let’s select two prime numbers p and q and p not equal to q

p = 5 and q = 11
such that, n = p x q
=>  n = 5 x 11 = 55

Calculate z or ϕ(n)

z = (p-1)(q-1)
=> z = (5-1)(11-1)
=> z = 40

Choose e such that 1 < e < z; gcd(z, e)=1

In this case there are different possible value of e those are: 19, 23, 27, 33, 37

Let’s choose the value e = 23

Calculate the value of d. Where de mod z = 1

if e=23, d will will be 7  where (7x23)mod40 = 1

Hence

n=55, p=5, q=11, z=40, e=23 and d=7
Public key Ku = {e, n} = {23, 55}
Private key Kr = {d, n} = {7, 55}

Encryption

Let’s consider message M =22

Cipher Text C = Me mod n

C =  (22 ^ 23) mod 55
=> C = 33

Ciphertext C or encrypted message is 33 .

Decryption

→ M = Cd mod n

M = (33 ^ 7) mod 55
M = 22

Original message or plaintext M or decrypted message from given ciphertext 33 is 22 .

Leave a Reply

Your email address will not be published. Required fields are marked *