RSA

Intro §

RSA is an encryption algo used to send a message from one person to another. Each person has a private and public key.

Procedure §

The variables used will be

$$p,q,z,n,s$$

$p$ and $q$ are 2 long primes, but for the demonstration we will use

$$\begin{array}{rl}p& =2\\ q& =11\\ z=pq& =22\end{array}$$

Now we calculate $\varphi$ using Euler’s totient function

$${\varphi }_z=(p-1)(q-1)=10$$

The receiver chooses a number

$$n:\text{gcd}(n,\varphi )=1$$

This is useful for finding

$$s:s\in (0,\varphi )\wedge ns\equiv 1\mathrm{mod}\varphi$$

$n$ is often prime. In our case, we set $n$ to 7 and $s$ to 3.

$$\begin{array}{rl}n& =7\\ s& =3\end{array}$$

$n,z$ are broadcast by the receiver as public keys. The send broadcasts the message encrypted using the formula

$$c=a^n\mathrm{mod}z$$

For example, if the sender encrypts and sends the message $5,13,8$, they would send $3,7,2$.

Now, the receiver uses his private key $s$ to decode the message.

$$\begin{array}{rl}{3}^3& \equiv 5\mathrm{mod}22\\ 7^3& \equiv 13\mathrm{mod}22\\ 2^3& \equiv 8\mathrm{mod}22\end{array}$$