 Solution

In RSA, choose $N=pq$ with distinct large primes, an exponent $e$ coprime to $\phi (N)$, and $d$ satisfying $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep $d$ secret. Encrypt a residue $m$ as $c=m^e\mathrm{mod}N$ and decrypt by $c^d\mathrm{mod}N$. Fermat's little theorem on each prime and the Chinese remainder theorem prove decryption, including messages not coprime to $N$.

A customer knows a nonzero multiple $M=ed-1$ of $\phi (N)$. Write $M=2^{s}t$ with $t$ odd. Choose a base $a$ at random. A nontrivial $\gcd (a,N)$ already factors $N$. Otherwise compute $a^t,a^{2t},\dots ,a^{2^{s}t}$ modulo $N$. The last entry is $1$. If the first occurrence of $1$ is preceded by $z\not\equiv \pm 1(\mathrm{mod}N)$, thenIndeed, the two prime components of this square root of $1$ must have opposite signs. This procedure succeeds for some bases: by the Chinese remainder theorem, choose a base whose component modulo $p$ has order $2$ and whose component modulo $q$ has order $1$. Its odd $t$-th power is already a nontrivial square root of $1$. Trying bases therefore gives an explicit factoring algorithm, and repeated random choices give the usual efficient attack. More precisely, if the two components' orders have different powers of $2$, the procedure succeeds. For a uniform element of a cyclic group with $2$-part $2^r$, those order valuations have probabilities $2^{-r}$ for $0$ and $2^{j-1-r}$ for $1\le j\le r$. Independence of the two prime components shows that equal valuations have probability at most $1/2$. Thus a random unit succeeds with probability at least $1/2$. Once $N$ is factored, every customer's private exponent is computable. The exceptional $ed=1$ is an identity cipher and is already insecure.

For the outsider's RSA common-modulus attack, find integers $a,b$ with $a{e}_1+b{e}_2=1$ by Bézout's identity. For a unit message,using modular inverses for negative powers. If a ciphertext is a nonzero nonunit, its greatest common divisor with $N$ factors $N$ instead; zero ciphertext corresponds to the zero message for a squarefree modulus. The common message is recoverable without a private key. For a generic unit message this alone does not supply the factorization or all private keys, so it does not demonstrate a complete break for unrelated messages. The nonunit case does give that stronger break.