RSA Proof of Correctness Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm?

And why is it needed?

I can't say that this or this helped me much, I'd like a more detailed and newbie like explanation, if you don't mind too much... ;)
After a couple of hours of detailed study I've come to an answer.

As we all know the RSA algorithm works as follows:


Choose two prime numbers $p$ and $q$,
Compute the modulus in which the arithmetic will be done: $N = pq$,
Pick a public encryption key $e \in Z_n$,
Compute the private decryption key as $d$ such that $ed = 1 \bmod{\phi(N)}$,
Encryption of message $m$: $c = m^e \bmod{N}$,
Decryption of crypto message $c$: $m = c^d \bmod{N}$.


While these statements and equations can stand true for some fixed values of $p$, $q$, $m$, $e$, $d$ in order to define the RSA as a general cryptographic algorithm we must prove their generality for any message $m$ we wish to encrypt. 

This is therefore the reason why the proof of the correctness of the RSA algorithm is needed.

Getting to the proof we can formalise it as follows:

Hypothesis:


$\gcd(p,q) = 1$
$N = pq$
$ed = 1 \bmod{\phi(N)}$


Thesis:


$ (m^e)^d = m \bmod{N}$, for all $m \in Z_n$



  NOTE:The important part is ^^^^^^^^^ the for all part...


Proof:

Being $m \in Z_n$ there are only two possible cases to analyse:


  1) $\gcd(m, N) = 1$


In this case Euler's Theorem stands true, assessing that
$$ m^{\phi(N)} = 1 \bmod{N}\text{.}$$

As for the Thesis to prove, because of Hypothesis number 3, we can write:

$$(m^e)^d = m^{ed} = m^{1 + k\phi(N)}\text{,}$$

furthermore

$$ m^{1 + k\phi(N)} = m\cdot m^{k\phi(N)} = m \cdot (m^{\phi(N)})^k,$$

and for Euler's Theorem

$$m \cdot (m^{\phi(N)})^k = m \bmod{N}$$ 

Proving that the thesis stands in this case.


  2) $\gcd(m, N) \neq 1$


In this case Euler's Theorem does not stand true any more.

For a result of the Chinese Remainder Theorem (check this SO question - Chinese Remainder Theorem and RSA - or just wiki it) it is true that if $\gcd(p,q) = 1$ then:

$$ x = y \pmod{p} \land x = y \pmod{q} \Rightarrow x = y \pmod{pq}$$

So by proving the following two statements we would have finished:


$ (m^e)^d = m \bmod{p}$
$ (m^e)^d = m \bmod{q}$


Because $\gcd(m, N) \neq 1$ one between $\gcd(m, N) = p$, and $\gcd(m, N) = q$ must stand true. I will demonstrate that both the above statements stand true in the case $\gcd(m, N) = p$, being it absolutely identical (by switching letters) to prove it for $\gcd(m, N) = q$ as well.

So let it be $\gcd(m, N) = p$, this implies that $m = kp$ for some $k &gt; 0$ which means that $m \bmod{p} = 0$. By concerning the first statement we also have

$$ (m^e)^d = ((kp)^e)^d$$

which therefore results to be a multiple of $p$, and so it is equal to zero. 

So the first statement becomes $0 = 0$ and is proven to be satisfied.

Concerning the second statement we have that Euler's Theorem results to be proved in $Z_q$, since $\gcd(m,q) = 1$, so:

$$ m^{\phi(q)} = 1 \bmod{q}\text{.}$$

This implies that we can write:

$$\begin{align}
 (m^{e})^d &amp;= m^{ed} \\
&amp;= m^{ed - 1}m\\
&amp;= m^{h(p-1)(q-1)}m\\
&amp;= (m^{q-1})^{h(p-1)}m\\
&amp;= 1^{h(p-1)}m = m \bmod{q}.
\end{align}
$$

which definitively proves the second statement and theorem.