Proof of correctness of RSA sufficient?

Question

In a lecture I am taking the following proof for the RSA cryptosystem is given: $m^{ed} \equiv m^{ee^{-1}} \equiv m^1 \equiv m \pmod N$

where $N = pq$; $p$,$q$ prime; $2 < e < \phi(N)$; $e$,$\phi(N)$ coprime; and $d$ is chosen so that $ed \equiv 1 \mod \phi(N)$, where $\phi$ is Euler's totient function.

The equation in the first line is the complete proof presented. Nothing else is given. In particular, $m$ is NOT required to be coprime to $N$. My question is: Is this a sufficient proof? The typical proofs for RSA are much longer and invoke either Euler's, Fermat's or the Chinese Remainder Theorem.

My analysis is that it is not obvious that we should be allowed to consider the exponent as a number $\mod {\phi(N)}$ unless that is separately proven to be valid. As far as I am aware, since $m$ and $N$ are not coprime, it's not necessarily true that $m^{\phi(N)} \equiv 1 \mod N$, thus we cannot simply take the exponent modulo $\phi$. Is there another way to see that this proof should be sufficient?

Answer 1

$m^{\phi(n)}\equiv1\bmod n$ requires $\gcd(m,n)=1$, but $m^{\phi(n)+1}\equiv m\bmod n$ doesn't.

Answer 2

wlog we need to prove: $m^{k \times \phi(N)+1} = m \mod N$.

If $m = \ell p q$ then the above is true since $0 = 0 \mod N$.

Hence wlog $m = p \ell$ where $(\ell,pq) = (\ell,N) = 1$.

Now by Fermat's little theorem,:

$$m^{k \times \phi(N)+1} = p^{k \times \phi(N)+1} \times \ell^{k \times \phi(N)+1} = p^{k \times \phi(N)+1} \times \ell \mod pq$$

Hence it suffices to prove $$p^{k \times \phi(N)+1} = p\mod pq$$

$$\implies p^{k \times \phi(N)+1}-p = (p^{k \times (p-1)(q-1)} - 1) \times p \mod pq$$

Again By Fermat's little theorem : $p^{k \times (p-1)(q-1)} - 1 = 0 \mod q \implies p^{k \times (p-1)(q-1)} - 1 \ is \ a \ multiple \ of \ q$.

Hence, $$(p^{k \times (p-1)(q-1)} - 1) \times p = 0 \mod pq$$

Hence, $$p^{k \times (p-1)(q-1)+1} = p \mod pq$$

Hence, $$p^{k \times \phi(N)+1} = p \mod pq$$