RSA Proof of Correctness

Question

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... ;)

Answer 1

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 \mathbb{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 \mathbb{Z}_n$

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

Proof:

Being $m \in \mathbb{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 > 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 $\mathbb{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 &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{q-1})^{h(p-1)}m\\ &= 1^{h(p-1)}m = m \bmod{q}. \end{align} $$

which definitively proves the second statement and theorem.

Answer 2

(Being new to cryptography, I hope the following makes sense).

I will try to follow the Wikipedia article. What I write is pretty much just taken from there. If some of the steps are unclear you might want to look up for example the Chinese Reminder theorem or simply check out a book on basic modular arithmetic.

So you have

• two primes $p$ and $q$.
• $n = pq$
• $1 < e < \phi(n)$ such that $\gcd(\phi(n), e) = 1$, $\phi(n) = (p-1)(q-1)$.
• $d$ such that $de \equiv 1$ $($mod $\phi(n))$.

So the

• public key is $(n, e)$,
• secret key is $(n, d)$.

And so you

• encrypt $m$ by computing $c = m^e$ $($mod $n)$,
• decrypt $c$ by somputing $m = c^d$ $($mod $n)$.

The question that I think you are asking is why is $$ (m^e)^d \equiv m\;(\text{mod }n)$$. (A: Why do we need to check this? A: because you want to make sure that when you first encrypt and then decrypt you recover the original plaintext).

(1) First note that (by the Chinese Remainder Theorem) it is enough to check that

$$ (m^e)^d \equiv m\;(\text{mod }p)$$.

So, we have that $de \equiv 1$ $($mod $\phi(n))$. This means that $\phi(n) = (p-1)(q-1)$ divides $ed - 1$. Hence we can write $ed = h(p-1)(q-1) + 1$ for some (non negative) integer $h$.

(2) Now if $p$ divides $m$, then we are done... so assume that $m$ is not divisible by $p$.

(3) So we compute ($\equiv_p$ is taking mod $p$)

$$\begin{align} (m^{e})^d &= m^{ed} \\ &= m^{ed - 1}m\\ &= m^{h(p-1)(q-1)}m\\ &= (m^{p-1})^{h(q-1)}m. \end{align} $$ Now we use the fact from Fermat's Little Theorem that $m^{p-1}\equiv_p 1$. So we get

$$\begin{align} (m^{e})^d &= ... \\ &\equiv_p 1^{h(q-1)}m \\ &= m. \end{align} $$ Then you do the same for $q$ instead of $p$, and you are done.