As I understand it, RSA works as follows:
- Pick two large primes $p$ and $q$
- Compute $n = p \cdot q$
- The associated group $\mathbb{Z}^*_n$ consists of all integers in the range $[1, n - 1]$ that are coprime to $n$ and will have $\phi(n) = (p-1)(q-1)$ elements
- Select the public exponent $e$, which must be coprime to $\phi(n)$
- Compute the private exponent $d$ by solving $ed = k\cdot \phi(n)+1$ with the extended Euclidean algorithm
- To encrypt a message $m$ we compute $c = m^e$ mod $n$
- To decrypt a cipertext $c$ we compute $m = c^d$ mod $n$
I read in a textbook that only the numbers in $\mathbb{Z}^*_n$ are “valid numbers” for RSA operations.
I am now wondering whether or not the message $m$ must be a member of the group $\mathbb{Z}^*_n$ ?
That would be weird because it would restrict the possible messages that can be encrypted.
Thanks!