RSA Algorithm

RSA stands for Rivest-Shamir-Adleman (Name of the Creators of the algorithm)

Key Generation

(e, n) = Public Key
(d, n) = Private Key

e: RSA Exponent
n: RSA Modulus

Choose two prime numbers

p = 7
q = 11

Compute n

$n=p\times q=7\times 11=77$

Compute ɸ(n)

Eulers Totient Function

$\varphi (n)=\varphi (p\times q)=\varphi (p)\times \varphi (q)$
$=(p-1)\times (q-1)=(7-1)\times (11-1)=60$

Choose e

e should lie between $1\le e<\varphi (n)$ and be co-prime to $\varphi (n)$

e = 13
(e, n) = Public Key = (13, 60)

Determine d

$e\times d=1\mathrm{mod}\varphi (n)$
e and ɸ(n) here are coprime (Found in above step)

Then we can say d is an multiplicative inverse of e.
The above equation can also be represented as : $d=e^{-1}\mathrm{mod}\varphi (n)$

Calculating $e^{-1}$ without the knowledge of d (Private Key) is quite challenging
Hence without knowing the private key it is practically impossible to decrypt the message

$d=\frac{((\varphi (n)\times i)+1)}{e}$

We have to keep incrementing the value of i until we get an integer as the result

$d=\frac{((60\times 8)+1)}{13}=37$

(d, n) = Private Key = (37, 60)

Encryption and Decryption

Modular Exponentiation

Encryption	Decryption
(e, n) = (13, 143) = Public Key P = 13 = Plain Text	(d, n) = (37, 143) = Private Key C = 52 = Cipher Text
C = $P^e\mathrm{mod}n$, P < n C = $13^{13}\mathrm{mod}143$	P = $C^d\mathrm{mod}n$ P = $52^{37}mod143$
$C=[(13\mathrm{mod}143)\times (13^4\mathrm{mod}143)\times (13^8\mathrm{mod}143)]\mathrm{mod}143$ C = 52 (Cipher Text)	$P=[(52\mathrm{mod}143)\times (52^4\mathrm{mod}143)\times (52^{32}\mathrm{mod}143)]\mathrm{mod}143$ P = 13

The Plain Text that is specified is the algorithm is the ASCII code of the character to be encoded