Understanding why the public exponent $e$ is chosen the way it is in RSA

Question

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities (preferably with a intuitive concept behind rather than only a proof)

We have $p$ and $q$ which are prime and produce the product $n=pq$. Then the number $\phi = (p-1)(q-1)$ is generated. The public exponent $e$ is chosen so that $\text{gcd}(e,\phi) = 1$ ($e$ must not be a number that divides neatly into e and into (p-1)(q-1), except for 1). Why do we use $\phi$ and not $n$? Where does the need for this new number arise and $n$ is not supposed to be used? And why must $e$ not be a factor of $\phi$? What would result if we did choose $e$ as another number?

I don't understand where this constraint comes from. What is the property of $\phi$ that is created by this restriction? Is there an easy to understand intuition behind it?

Answer 1

$\newcommand{\Z}{\mathbb{Z}}$$\renewcommand{\phi}{\varphi}$I am expanding on the comment of @mixedmath

If $\gcd(e, \phi(n)) > 1$, then the function $\Z_{n} \to \Z_{n}$ given by $x \mapsto x^{e}$ is not injective. Thus there are two different messages $x \ne y$ that are mapped onto the same $x^{e} = y^{e}$, and there it goes any possibility of (uniquely) recovering the orginal message.

To see this, suppose $r$ is a prime divisor of $\gcd(e, \phi(n)) > 1$. Then $r$ divides the order $\phi(n)$ of the group $G$ of invertible elements of $\Z_{n}$. Take $x$ to be an element of order $r$ in $G$. Then $x \ne 1$, but $x^{r} = 1$. Since $r$ also divides $e$, we have $x^{e} = 1 = 1^{e}$.

Answer 2

Firstly, the exponent $e$ is not private rather public and shared with everyone. The $e$ is chosen to be relatively prime to $\phi(n)$ because $Z{^*}_n$ is a multiplicative group i.e. the set of all +ve integers less than $n$ that are relatively prime to $n$. Since the multiplicative inverse $d$ of $e$ is unique and finding it is very hard without knowing the factors $p, q$. Which is also known as the security of RSA.

In RSA, Encryption is performed as, $x^e \equiv a$ mod $n$ and Decryption as, $a^d = x^{ed} \equiv x$ mod $n$.

The Decryption gives the original value/message $x$ and is always correct because of the Euler's Theorem. Since $ed \equiv 1$ mod $\phi(n)$ implies that $ed = 1 + \phi(n)t$ where $t$ is an integer. So $a^d = x^{ed} = x^{1 + \phi(n)t} = x x^{\phi(n)t} = x$ because from Euler theorem we know $\forall$ integers b s.t. gcd$(b,n)=1$ we have $x^{\phi(n)} \equiv 1$ mod $\phi(n)$

Now you can easily perceive that if you use gcd$(e, n) = 1$, then what problems can arise.