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

  • Could you try to explain exactly what you do understand and what you don't understand? Do you understand Fermat's little theorem? What about the Chinese remainder theorem? – Thomas Jun 13 '12 at 16:16
  • @Thomas - I do understand the case when GCD(m,N) = 1, (It's a straightforward application of Euler theorem). What I don't understand is when GCD(m,N) = p or = q how the proof is taken forward. However I thought that a full explanation could be useful also for other users (such as a site wiki).. – Matteo Jun 13 '12 at 16:42
  • Can anyone express their opinion on the three answers?some expert opinion would be the best to understand! – Matteo Jun 14 '12 at 10:00
  • One such proof is here. – fgrieu Mar 20 at 8:27
up vote 19 down vote accepted

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 > 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 &= 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.

  • 2
    you wrote "e ∈ Zn"; but e should be chosen with this criteria gcd(ϕ(N),e)=1 ; in other words e should be coprime with ϕ(N). See here crypto.stackexchange.com/questions/12255/… – Jako Jun 12 '16 at 16:38
  • With $p$ and $q$ prime, $\gcd(p,q)=1$ is the same as $p≠q$. It is unclear if the proof hypothesize $p$ and $q$ prime. If it does not, it is incorrect in the fragment "Because $\gcd(m, N) \neq 1$ one between $\gcd(m, N) = p$, and $\gcd(m, N) = q$ must stand true". Further, there's a notation problem: $m\cdot(m^{\phi(N)})^k=m \bmod N$ is simply wrong when we take $\bmod\;$ to be the operator "remainder of the Euclidean division". We have $m\cdot(m^{\phi(N)})^k\equiv m\pmod N$, or $m=m \cdot(m^{\phi(N)})^k\bmod N$. – fgrieu Mar 20 at 21:30

(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.

  • 2
    $ϕ(n)=(p−1)(q−1)$ divides $ed-1$, not $ed$. – Mehran Torki Apr 8 '16 at 7:14
  • When it is written "$c = m^e$ $($mod $n)$", the parenthesis immediately before "mod" tends to mean that the equality holds modulo $n$ as in $c\equiv m^e\pmod n$, rather than mean that the left side is reduced modulo $n$. A correct notation is $c=m^e\bmod n$ ($c=m^e\bmod n$), which means that $c\equiv m^e\pmod n$ ($c\equiv m^e\pmod n$) and $0\le c<n$. The distinction is critical, because e.g. $c'$ computed as $m^e$ also matches $c'\equiv m^e\pmod n$ but allows to recover $m$ without knowing the private key; and we can define other $c'$ the size of $n$ that slowly leak the private key. – fgrieu Oct 23 at 5:16
  • The proof is nice, however the Chinese Remainder Theorem is invoked rather cavalierly, to the point that the overall conclusion reached is incorrect (we can exhibit a numerical counterexample). An hypothesis is missing: $p$ and $q$ need to be distinct! As pointed to me in this related comment, there is a milder and better known form of the CRT that also allows to conclude: if $u$ and $v$ are coprime (including prime and distinct) and both divide $w$, then $u\,v$ divides $w$. – fgrieu Oct 23 at 5:40

Here is a blog post link: tominology

For a sketch of proof using Fermat's little theorem and a simplified JavaScript implementation

  • How is this in anyway useful? You've posted a new answer to a question that was asked and answered (with a fair number of upvotes) two years ago. As the question had been firmly answered the only logical reason for answering would be that you had a statement of intuition you wanted to share, yet you simply linked to a blog post (itself a no-no) with a reiteration of previous answers and Javascript code, the latter not being relevant to answers on this site. – sju Nov 18 '14 at 2:00
  • Edited since I missed that you did cover the case where $p$ and $\phi(n)$ are not coprime. – sju Nov 18 '14 at 2:02
  • Thanks for the criticism! I will try to do my best to improve – Marco Nov 20 '14 at 13:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.