1
$\begingroup$

To show that $m^{ed} \equiv m \pmod{pq}$ with $de \equiv 1 \pmod{\phi(pq)}$ and $p\neq{q}$,

Choose $e$ coprime to $\phi(pq)$ so that $\gcd(e,\phi(pq)) = 1$ and

$$m^{\gcd(e,\phi(pq))} \equiv m \pmod{pq}$$

Using Bézout's identity we expand the gcd thus

$$m^{\gcd(e,\phi(pq))} = m^{ed + \phi(pq)k} \pmod{pq}$$

where $d$ appears as the multiplicative inverse of $e$ and we expand the exponent

$$m^{ed + \phi(pq)k} = m^{ed} (m^{\phi(pq)})^{k} \pmod{pq}$$

By Fermat's little theorem this is reduced to

$$m^{ed} 1^{k} = m^{ed} \equiv m \pmod{pq}$$

which is the original claim.


Please review this simple proof and help me fix it, if it is not correct.

$\endgroup$
  • 1
    $\begingroup$ Maybe this question fits better on math.stackexchange.com then here... $\endgroup$ – Hilder Vitor Lima Pereira Sep 3 '17 at 12:09
  • 2
    $\begingroup$ Anyway, your proof doesn't seem to be right, because at the end, you basically says $m^{ed}$ is equal to $m$ (which is what you wanna prove) without doing any justification. You have to use the fact that $e$ is the inverse of $d$ modulo $\phi(n)$... $\endgroup$ – Hilder Vitor Lima Pereira Sep 3 '17 at 12:14
1
$\begingroup$

Update: there is a serious gap in the reasoning after applying Bézout's identity, which concludes that there exists $d$ and $k$ with $ed+\phi(pq)k=1$. The fragment "where $d$ appears as the multiplicative inverse of $e$" attempts to link the $d$ thus exhibited to the $d$ used in RSA. But why would these $d$ share more than their name, especially since the $d$ and $k$ exhibited by Bézout's identity are not unique, and (at least the usual form of) Bézout's identity does not state a relation between these multiple solutions?

We want either a different statement of Bézout's identity, or getting rid of it altogether. That's easy: start from the definition of $d$ in RSA (whatever that is), and prove that a suitable $k$ must exist, using fact 3 below.


It is thought to prove that in RSA, decryption consistently reverses encryption. But hypothesis at time of starting this answer where insufficient for that, as they did not insure that $$\;p\ne q\;\text{ or }\;\gcd(m,pq)=1\;$$ This is required in RSA (illustration: try $p=q=5$, $\phi(pq)=20$, $e=3$, $d=7$; encryption of $m=10$ followed by decryption yields $0$ rather than $10$ ).

Now $p\ne q$ is made explicit, satisfying said requirement. But it is not apparent where this is used.

Not coincidentally, the proof still has a serious gap at the point where $1^k$ appears, which implicitly uses that $m^{\phi(pq)}\equiv1\pmod{pq}$, because:

  • This proposition is wrong for some $m$, including $m=2q$ .
  • Fermat's little theorem is invoked as a justification, but an hypothesis in FLT is that the modulus is prime, while $pq$ is not.
  • FLT makes no mention of $\phi$ , and the definition of $\phi$ is not invoked in the proof.

Useful standard facts (for all variables in $\mathbb Z$ unless otherwise noted):

  1. If $p$ and $q$ are coprime, then $pq$ divides $x$ if and only if both $p$ and $q$ divide $x$ .
  2. If $p$ and $q$ are distinct primes, then $p$ and $q$ are coprime.
  3. The definition of $u\equiv v\pmod w$ is that $w$ divide $v-u$ ; or equivalently that there exists $k$ such that $u+kw=v$.
  4. For $w>0$, the definition of $u=v\bmod w$ used in RSA encryption and decryption is that $u\equiv v\pmod w$ and $0\le u<w$ .
  5. FLT: if $p$ is prime, then $y^p\equiv y\pmod p$ .

That allows deriving the helpful:

  • if $p$ and $q$ are distinct primes, and both $p-1$ and $q-1$ divide $j-1$, and $j>1$, then $y^j\equiv y\pmod{pq}$ .

Proof hint: use fact 1 with $x=y^j-y$ , and other above facts.


Independently: it is used, but not stated, that the definition of RSA considered uses $d$ such that $ed\equiv1\pmod{\phi(pq)}$ . Another popular definition uses $ed\equiv1\pmod{\lambda(pq)}$ , where $\lambda$ is the Carmichael function. This definition is used in PKCS#1 and FIPS 186-4. It is mathematically satisfying, for it is necessary and sufficient, when $ed\equiv1\pmod{\phi(pq)}$ is merely sufficient.

Also, the proof would be clearer if it was restated:

  • $p$ and $q$ are primes;
  • the definition of $d$ used in RSA, and the definition of $\phi$ or $\lambda$ if they appear (in which case those are bound to be used in a correct proof!)
  • $N=pq$ ;
  • whatever hypothesis on $m$ (commonly, that is $0\le m<N$, with further restriction to $\gcd(m,N)=1$ if the condition $p\ne q$ is not used);
  • use of textbook RSA encryption $m\to c=m^e\bmod N$ ;
  • use of textbook RSA decryption $c\to m'=c^d\bmod N$ (with a distinct notation for the original message and deciphered messages);
  • what's to be demonstrated (this answer assumes that it is $m'=m$ for all $m$ satisfying the hypothesis made on $m$ ).

Also: there's a missing bit of reasoning, going from $m'\equiv m\pmod N$ to $m'=m$ .

Finally: textbook RSA is not a secure encryption algorithm (assume encryption of the name of someone in the class roll, which will be interrogated tomorrow; one can easily determine from the ciphertext and public key if that's her/him, or even who this is if the class roll is public).

| improve this answer | |
$\endgroup$
  • $\begingroup$ I corrected the proof to include $p\neq{q}$ $\endgroup$ – conchild Sep 3 '17 at 19:01
  • 1
    $\begingroup$ @conchild: I accordingly modified the rebuttal; it now includes useful facts. $\endgroup$ – fgrieu Sep 3 '17 at 21:09
  • $\begingroup$ Actually, $\text{gcd}(m, pq) = 1$ is not required by RSA; it may be required by his proof strategy, but there are proofs that do not assume that. $\endgroup$ – poncho Sep 5 '17 at 17:43
  • $\begingroup$ @fgrieu I will work on this in the long term and try to fix the issue with the use of FLT $\endgroup$ – conchild Sep 5 '17 at 22:18
  • 1
    $\begingroup$ @poncho: the answer never stated that $\gcd(m, pq) = 1$ must hold in RSA. Rather, it consistently stated $p\ne q\;\text{ or }\;\gcd(m,pq)=1$. Modern proofs and definitions of RSA use the left side of the or, but the original RSA article explicitly uses the other (and the question initially used none). Both options are valid. It is asked a proof review, thus I find essential to question what the exact hypotheses are, and where they are used! $\endgroup$ – fgrieu Sep 6 '17 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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