What does the order of $U(N)$ has to do with RSA key generation?
The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function.
$\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This implies:
$$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$
We want the RSA encryption exponent $e$ and decryption exponent $d$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $m$ followed by decryption consistently returns the original plaintext. That is, we want that $\forall m\in[0,N)$, it holds $((m^e)\bmod N)^d\bmod N=m$. We can write this goal as:
$$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$
We can now see what $\Phi(N)$ has to do with RSA key generation: if
$$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$
then by definition of that, and given that $e$ and $d$ are strictly positive integers, $\exists k\in N$ such that $e\,d=k\,\Phi(N)+1$, and we nearly can use $\eqref{eq1}$ to prove that $\eqref{eq2}$ holds. The one gap is that we only prove the weaker
$$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$
We have proven that condition $\eqref{eq3}$ is sufficient to insure that textbook RSA encryption of a plaintext $m$ followed by decryption returns the original plaintext, at least when $\gcd(m,N)=1$. Since $N$ is the product of large primes, $\gcd(m,N)=1$ holds for most $m$.
Further, under the extra condition that $N$ is squarefree (including $ N=p\,q$ with $p$ and $q$ distinct primes), it can be proven that for all $m$ textbook RSA encryption followed by decryption returns the original plaintext.
Otherwise said: one way to see RSA is as working with message and ciphertext in the group $(\Bbb Z_N^*,*)$, but that restricts the message space. It can be extended to $(\Bbb Z_N,*)$ when $N$ is squarefree, that is when $N$ is not divisible by the square of any prime.
We first prove that $\eqref{eq3}$ implies that $m^{(ed)}-m\equiv0\pmod{p_i}$ for each prime $p_i$ dividing $N$, by treating separately the case $m\equiv 0\pmod{p_i}$. The integer $m^{(ed)}-m$ is thus divisible by each $p_i$, thus by their product, which is $N$ when $N$ is squarefree, thus $m^{(ed)}-m\equiv0\pmod N$.
Notice that the condition $\eqref{eq3}$ is sufficient, but not necessary. For a necessary and sufficient condition, we want
$$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$
where $\lambda$ is the Carmichael function.
Notations:
- $\forall$ is read "for all". $\in$ is read "in". $\exists$ is read "exists".
- $\Bbb N$ is the set of natural numbers: $\Bbb N=\{0,1,2,3,4,5,\ldots\}$.
- $\Bbb P$ is the subset of $\Bbb N$ consisting of primes: $\Bbb P=\{2,3,5,7,11,\ldots\}$.
- $\Bbb Z$ is the set of (signed) integers: $\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
$(\Bbb Z,+)$ is a group.
- $x\equiv y\pmod n$ is read "$x$ is equivalent to $y$ modulo $n$".
It means that $n$ exactly divides $x-y$ (for $n$ a strictly positive integer).
Alternative notations are $x\equiv y\ \ [n]$ or $x=y\pmod n$ or $x=y\ \ [n]$.
- $x=y\bmod n$ is read "$x$ is set to $y$ modulo $n$" or "$x$ equals $y$ modulo $n$".
It means that (after the setting, if any) $0\le x<n$ and $x\equiv y\pmod n$ (see above for the meaning).
When $y\ge0$, the quantity $y\bmod n$ is the remainder of the Euclidean division of $y$ by $n$. The quantity $y\bmod n$ is $0$ when $n$ divides $y$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $y<0$, we can compute $y\bmod n$ as $n-1-((-y-1)\bmod n)$.
Note: Textbook RSA encryption and decryption reduce their result $\bmod N$, ensuring that the ciphertext and the deciphered plaintext are in $[0,N)$.
- $\Bbb Z_n$ is the finite set of integers modulo $n$. That is, the elements of $\Bbb Z$ equivalent modulo $n$ are regrouped into a single element of $\Bbb Z_n$. Thus $\Bbb Z_n$ has $n$ elements.
$(\Bbb Z_n,+)$ is a group. With multiplication noted $*$ when not omitted, it becomes the ring $(\Bbb Z_n,+,*)$.
When the modulo $n$ is prime, $(\Bbb Z_n,+,*)$ is a field, because all elements except $0$ have a multiplicative inverse. As practice of notation: $\forall p\in\Bbb P$, $\forall x\in\Bbb Z_p$, if $x\ne0$ then $\exists y\in\Bbb Z_p$ such that $x*y=1\pmod p$ (also noted $x\,y=1\pmod p$ as a shortcut).
- $\Bbb Z_n^*$ is the set of the elements of $\Bbb Z_n$ that have an inverse under multiplication, that is the set of $x$ with $n$ and $x$ having no common positive divisor beyond $1$, that is $\gcd(x,n)=1$.
$(\Bbb Z_n^*,*)$ is a group including when $n$ is not prime. It has $\Phi(n)$ elements.
