Why in RSA, the public exponent $e$ must be coprime with $\phi (n)$

Question

I'm trying to understand the RSA cryptosystem, and that's what I know so far:

If we think about some number $m$ as the message, then we are searching a $e$ and $d$ such that

$$m^{ed} \equiv m \ \ (\mbox{mod} \ n)$$

So someone can encrypt the message by doing $$m^e \ \ (\mbox{mod} \ n)$$ And the person that holds $d$ can decrypt it by doing

$$(m^e \ \ (\mbox{mod} \ n))^d (\mbox{mod}\ n) = m$$ *(not the best notation but you guys get the idea)

$d$ can be calculated by using Euler's theorem, which states that:

$$m^{\phi(n)}\equiv 1 \ (\mbox{mod} \ n) \tag{2}$$

where $m$ coprime with $n$

Then, by some modular arithmetic properties, we can do this in $(2)$:

Raise both sides by $k$, so we get:

$$m^{k\phi(n)}\equiv 1 \ (\mbox{mod} \ n)$$ *because $1^k$ is $1$

Then multiply both sides by $m$:

$$m^{k\phi(n)+1}\equiv m \ (\mbox{mod} \ n)$$

By comparing this congruency with the one we've been searching:

$$m^{k\phi(n)+1}\equiv m \ (\mbox{mod} \ n)$$

$$m^{ed} \equiv m \ \ (\mbox{mod} \ n)$$

We just need to solve for $d$ by doing:

$$ed = k\phi(n)+1\implies d = \frac{k\phi(n)+1}{e}$$

So $d$ can be easely calculated if you know the factorization of $n$, because for a number $n$, $\phi(n)$ is $\phi(p)\phi(q)$ where $n = pq$ (in other words, $p$ and $q$ are the prime factors of $n$). So since we think (for centuries) that factorization of large numbers is a difficult problem, we assume that no one will be able to find $d$ in a reasonable amount of time, unless they know wich prime numbers form $n$.

My questions are:

I don't know if I understand that the requirement that $e$ is a prime number. For me, any number would work in the process I described.

Also, why $m$ is not assumed to be coprime with $n$ at $(2)$? Since $m$ is the message, it can happen that $m$ is not coprime with $n$.

In the wikipedia article, it says that $e$ must be less that $\phi(n)$. Why?

Why, in the wikipedia article where he proves it using fermat's little theorem, it assumes that $ed$ is congruent to $1$ mod $\phi(n)$?

I've seen all this at khan academy, but the process they described does not answer my questions. I would like some help with the intuition, as always. I'm not looking for some one line proof, so please help me understand the requirement that $e$ is prime, for example, by using the process I described.

Please be patient, I'll give time to choose the answers, so you guys have time to write a good one <3

Answer 1

The reason $e$ must be coprime to $\phi(n)$ is that otherwise you can never have the key equation $ed = k\phi(n) + 1$, which is equivalent to saying that $ed$ is congruent to $1$ mod $\phi(n)$. If you rewrite this equation as $1 = ed-k\phi(n)$, then any common divisor of $e$ and $\phi(n)$ divides the right hand side. But the left hand side has no nontrivial divisors, so we are forced to conclude that $e$ and $\phi(n)$ have no nontrivial common divisors, i.e. they are coprime.

Another way of saying this is that we want to solve for $d = \frac{k\phi(n) + 1}{e}$, but we want an integer, not just a rational number. Unless $e$ is coprime to $\phi(n)$, we will not to be able to choose $k$ such that this formula yields an integer value for $d$.

You also ask why $e < \phi(n)$ is assumed. In general, encoding will tend to take longer the larger the value of $e$, since the number of multiplications necessary to compute $m^e$ will (often) increase. Thus, it is common to choose $e$ to be some reasonably small prime number that does not divide $\phi(n)$. If you chose $e>\phi(n)$, then you could have equivalently chosen $e-\phi(n)$, since $m^e \equiv m^{e-\phi(n)}\pmod{n}$ follows from $m^{\phi(n)} \equiv 1\pmod{n}$.

For your question about $m$ and $n$ being coprime, even though Euler's theorem usually requires $m$ and $n$ to be coprime, the Wikipedia article you link provides a proof (based on cases and the Chinese remainder theorem) that when $n = pq$ is the product of two primes, then $m^{l} \equiv m \pmod{n}$ for any $l$ congruent to 1 mod $\phi(n)$, even when $m$ is divisible by $p$ or $q$. Note that for practical purposes $p$ and $q$ are large primes, and thus a vast majority of possible messages will be coprime to $pq$.

If for some reason you didn't want to send such messages anyway, it would be relatively easy to choose an encoding scheme that didn't use such messages. Note that $1^e = 1$ and $0^e = 0$ for any $e \ge 1$, so there already exist at least two messages that you can't send securely.