# Working on subgroup of $\mathbb{Z}^*_p$ in practice

It is said that, given a group $\mathbb{Z}^*_p$, we can always have a subgroup whose order is prime. To this end, for a safe prime $p=2q+1$, compute $x_i^2 \bmod p$ for all $x_i \in \mathbb{Z}^*_p$.

Questions:

1. Do we need to only work on the values that exist in this subgroup (whose order is prime)?
2. What if we need some values that do not exist in the subgroup, but they are in $\mathbb{Z}^*_p$?
3. To work on the elements of subgroup do we do $\bmod q$?

Because this way limits our choice of elements and we cannot work on any arbitrary values.

• Your choice of $p$ is not necessarily prime (take, for instance, $q=7$). Did you mean that $p$ be a safe prime? – yyyyyyy Jul 3 '15 at 14:56
• It is unclear what you are asking. Are you asking what role large multiplicative subgroups play in cryptography, or do you simply want to know more about the algebraic properties of the fields and groups involved? – Henrick Hellström Jul 3 '15 at 14:56
• @yyyyyyy Yes, I meant both $q, p$ to be large prime. – user13676 Jul 3 '15 at 15:00
• It is important to know in exactly what sense you "need to work on some elements not in the subgroup". Your question does not include any reference to any cryptographic scheme or algorithm. – Henrick Hellström Jul 3 '15 at 15:18
• To emphesize Henrick's point, different cryptosystems have different answers; in DH, we do want to stick to the subgroup; for SRP, we have to work with elements in the entire group – poncho Jul 3 '15 at 15:43

## 1 Answer

When using any cryptosystem that relies on the Decisional Diffie-Hellman assumption (e.g., ElGamal, ECIES, Diffie-Hellman key exchange, etc.) then you need a group of prime order. Note that $\mathbb Z_p^*$ where $p$ is prime has order $p-1$. However, if $p=rq+1$ where $q$ is also a large prime, then you have a subgroup of $\mathbb Z_p^*$ of order $q$. If you take $r=2$, then these are the so-called safe primes (once it was thought that for RSA it's best to use these types of primes, and that's why they are called "safe"; however, today, it is accepted that it's best to just choose random primes for RSA). In order to get a subgroup of order $q$, indeed you just take the squares.

Answering your specific questions:

1. For the cryptosystems that I mentioned above, YES you MUST work in the subgroup.
2. You need to map any value that you need into the subgroup. You can map any value between 1 and q-1 by just squaring it.
3. No, you do not do $\bmod q$ on the elements (you do $\bmod q$ when working on values in the exponent).

I recommend that you take a book that gives the number-theory background necessary for crypto...

• Thank you for the answers. Indeed "Introduction to modern cryptography" (1st edition, page 367), by Katz and Lindell (@Lindell) explains that clearly . – user13676 Jul 7 '15 at 9:23