Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

(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$. Hence we can write $ed = h(p-1)(q-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.

share|improve this answer
up vote 6 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$ | $ed = 1$ $mod$ $\phi(N)$,
  • Encryption of message $m$: $c = m^e$ $mod N$,
  • Decryption of crypto message $c$: $m = c^d$ $mod 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$ $mod$ $\phi(N)$

Thesis:

  • $ (m^e)^d = m$ $mod N$ $\forall 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 (mod N).$$

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

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

furthermore

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

and for Euler's Theorem

$$m*(m^{\phi(N)})^k = m (mod 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 (mod p) \wedge x = y (mod q) \Rightarrow x = y (mod pq)$$

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

  • $ (m^e)^d = m$ $mod p,$
  • $ (m^e)^d = m$ $mod 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 mod 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 (mod q).$$

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 mod q. \end{align} $$

which definitively proves the second statement and theorem.

share|improve this answer

Here is a blog post link: tominology

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

share|improve this answer
    
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. –  Samuel Judson Nov 18 at 2:00
    
Edited since I missed that you did cover the case where $p$ and $\phi(n)$ are not coprime. –  Samuel Judson Nov 18 at 2:02
    
Thanks for the criticism! I will try to do my best to improve –  Marco Nov 20 at 13:18
1  
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Gilles Dec 14 at 19:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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