As I understand it, RSA works as follows:

  1. Pick two large primes $p$ and $q$
  2. Compute $n = p \cdot q$
  3. 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
  4. Select the public exponent $e$, which must be coprime to $\phi(n)$
  5. Compute the private exponent $d$ by solving $ed = k\cdot \phi(n)+1$ with the extended Euclidean algorithm
  6. To encrypt a message $m$ we compute $c = m^e$ mod $n$
  7. 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.




Browse other questions tagged or ask your own question.