**RSA** (named after **R**ivest – **S**hamir โ **A**dleman) 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

**Ke****y 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

### Like this:

Like Loading...

## Published by 4lph4

Halo!! Ich heiฮฒe Sowmya. Ich bin studentin an der Amrita Universitat. Ich mache Kryptographie. Ich bin teil von Team Bi0s. Dieser Blog ist fรผr Crypto-Attacken erlernt und Herausforderungen gelรถst. Danke :)
View all posts by 4lph4