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\;)\text{ and }(\;p\text{ and }q\text{ are primes}\;)$$ which happens to be a necessary condition in RSA (illustration: try $p=q=5$, $e=3$, $m=10$; encryption followed by decryption yields $0$ rather than $10$ ).
Arguably $p$ and $q$ primes is an implicit hypothesis; and now $p\ne q$ is made explicit. But it is not apparent where these hypothesis are 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=p$
- 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$.
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. That definition is used in PKCS#1 et 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 a number of other things:
- $p$ and $q$ are primes;
- $N=pq$ ;
- hypothesis on $m$ (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 (that is $m'=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 public class roll, which will be interrogated tomorrow, and how one can easily determine if that's her/him).