Simple RSA proof of correctness using Bézout's identity 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.
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):


If $p$ and $q$ are coprime, then $pq$ divides $x$ if and only if both $p$ and $q$ divide $x$ .
If $p$ and $q$ are distinct primes, then $p$ and $q$ are coprime.
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$.
For $w&gt;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&lt;w$ .
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&gt;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&lt;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).