Score:0

RSA - is the message a member of the multiplicative group of integers modulo n?

cn flag

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.

Thanks!

kelalaka avatar
in flag
Welcome to [cryptography.se] Do these answer your question? 1) [Does RSA work for any message M?](https://crypto.stackexchange.com/questions/1004/does-rsa-work-for-any-message-m) . We have dupes for this 2) [RSA Proof of Correctness](https://crypto.stackexchange.com/q/2884/18298)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.