RSA procedure
- choose two primes, $p$ and $q$
- calculate $N = p\times q$
- calculate $r = \varphi(N)= \varphi(p\times q)=(p-1)(q-1)$
- $\varphi$ is the Eular function, $\varphi(n)$ represents the number of integers prime with $n$
- if $n$ is a prime, then obviously $\varphi(n)=n-1$
- $\varphi(mn)=\varphi(m)\varphi(n)$
- choose $e$ no more than $N$ and prime with $r$
- calculate $d$ such that $ed \equiv1 \mod r$
- then $(e, N)$ is public key and $(d, N)$ is private key
- don’t forget to destroy $p$ and $q$
Now Alice wants to send some message to Bob.
She needs to transform the message string into a integer $m$ no more then $N$.
- ciphertext $c = m^e \bmod N$
When Bob receive the ciphertext, he needs to decrypt it.
- plaintext $m = c^d \bmod N$
Rightness
How to show that Bob can get right raw message?
Just to show that $c^d \equiv m \mod N$
$$
\begin{align}
c^d &\equiv (m^e)^d \mod N \\
&\equiv m^{ed} \mod N \\
&\equiv m^{tr+1} \mod N \\
&\equiv m\cdot m^{tr} \mod N \\
&\equiv m\cdot (m^{\varphi(N)})^t \mod N \\
&\equiv m\cdot 1^t \mod N \\
&\equiv m \mod N
\end{align}
$$
The key point is $m^{\varphi(N)}\equiv1 \mod N$ when $\gcd(m, N)=1$
More
In fact, we can choose more than two primes at beginning.
For example, choose $n$ primes $p_1, p_2, \cdots,p_n$
calculate $N = p_1\times p_2\times\cdots\times p_n$
and calculate $r = \varphi(N) = (p_1-1)(p_2-1)\cdots(p_n-1)$
then everything is the same.
The difficulty to crack RSA decides to the difficulty to factoring a big intger.
The big intger is just $N$ and if we can factor it into some primes, then we can calculate $r$, and get $d$.