Return to Answer

Update: the most fundamental hole in the reasoning is after applying Bézout's identity, which implies existence of $d$ and $k$ with $ed+\phi(pq)k=1$. Then, the sentence 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 more precise 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 as they stood at time of starting this answer where insufficient for that, for 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$ ).

• 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$ .

• $p$ and $q$ are primes;
• the definition of $d$ used in RSA, and the definition of $\phi$ or $\lambda$ if they appear (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$ ).

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

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

• $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$ ).

The proof as it stood at time of starting this answer attempted to prove something that did not hold with the hypothesis that it then stated, which did not include $$\;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$ ).

It is thought to prove that in RSA, decryption consistently reverses encryption. But hypothesis as they stood at time of starting this answer where insufficient for that, for 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$ ).

Also, the proof would be clearer if it was restated a number of other things:

• $p$ and $q$ are primes;
• $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, 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 (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$ ).