RSA

RSA (named after Rivest – Shamir – Adleman) is a popularly used public key encryption system. Security of RSA is based on the fact that it is very difficult to factorize a very long integer into its prime factors.

Being public key crypto system, it involves the usage of public key and private key for encryption and decryption. Here the public key pair is made public to everyone and the private key is maintained in secrecy.

There are 3 simple steps to implement RSA

• Key Generation
  
• Encryption
• Decryption

Key generation

Lets consider 2 large primes p and q

Set modulus n = pq

As both p and q are prime their totient 𝜑(n) = (p-1)(q-1)

Select the public exponent e such that gcd(e,𝜑(n)) = 1 and 1<e<𝜑(n)

Now we got to determine our private key d such that ed = 1 mod 𝜑(n) i.e d = e^-1 mod 𝜑(n)

d is known as modular multiplicative inverse of e as e and 𝜑(n) are relatively prime and hence d can be calculated using Euclidean Extended Theorem. (e,n) are known as public key pair where as (d,n) are known as the private key pair

Encryption

Now we have our required keys generated and also the modulus required for encryption. We take a random message m such that m is less than the modulus n. We encrypt our message m as

c = m^e mod n

Decryption

Once we have the encrypted message c we can get the decrypted message using the generated private key

pt = c^d mod n

So,how can we say that both decrypted message and original message are the same? The only answer to this question is to prove it

Proof

pt = c^d mod n

pt = m^ed mod n but ed = 1 + k(𝜑(n))

pt = m^1+k(𝜑(n)) mod n by Euler’s theorem we know that m^𝜑(n) =1 mod n

pt = m(m^k(𝜑(n))) mod n

pt = m mod n

As we know that m < n we can say m = m mod n

so we proved that pt =m

So that’s all for this post. Please do correct me if you find any mistakes

 

Advertisement