5
$\begingroup$

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the group with the order $p$ and need a subgroup with order $q$.

This is for security reasons (discrete logarithm calculation algorithms) or for computational optimization?

$\endgroup$
8
$\begingroup$

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since $p$ is a prime, $p-1$ is composite (as long as $p > 3$). Group theory tells us that there is a subgroup of size $d$ for every $d$ that divides $p-1$. By choosing a subgroup of order $q$, where $q$ is prime, we ensure that there are no (non-trivial) subgroups. This avoids small subgroup confinement attacks.


As mentioned in the other answer and comments, there are easy ways to find suitable $p$ and $q$. One is by using primes, $p$ and $q$, such that $p = 2q + 1$. Such a $p$ is called a safe prime. Another is by setting $p = qr + 1$, where $r$ has (potentially) unknown factorization. The group generated by this $q$ is called a Schnorr group.

| improve this answer | |
$\endgroup$
4
$\begingroup$

One relevant point is that if $p-1$ is not of a form like $2q$ for $q$ prime, then it could be difficult to find the multiplicative order of an element. You can't use Lagrange's theorem to determine the order if you can't factor $(p-1)/2$, but the mere fact that you haven't yet found a small factor wouldn't show that one doesn't exist. Using a $p$ where $p-1$ has a large known prime factor could be the difference between knowing the order of an element and merely hoping that the order is large.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ There are alternatives to safe primes; we can have $p = qr + 1$, for a value of $r > 2$. With a prime of this form, it is easy to find an element of order $q$ (even if you don't know the factorization of $r$). One advantage is that it is easier to find primes of this form (select $q$ to be a prime of moderate size, say, 256 bits, then search for a prime of the form $qr + 1$) than it is to find a safe prime. Personally, I prefer safe primes; however we should realize that it's not the only alternative $\endgroup$ – poncho Oct 6 at 11:42
  • $\begingroup$ @poncho Good point. In fact, that was part of my motivation for the way that I worded the final sentence (about $p-1$ having a large known prime factor rather than just saying that it was of the form $2q$). Note that if $p-1 = qr$ then you do in fact have a factorization of $p-1$ even if it isn't a complete factorization. In that scenario you might be able to determine the order of some elements (including all of those with order $q$) but not others. I agree that safe primes are preferable. $\endgroup$ – John Coleman Oct 6 at 11:52
  • 1
    $\begingroup$ What poncho is said the Schnorr group $\endgroup$ – kelalaka Oct 6 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.