A Schnorr group is a multiplicative group of integers modulo an odd prime $p$ of prime order $q$, normally such that $p$ is much greater than $q$.

As far as I know, the normal way to find a Schnorr group is to:

  1. determine $q$ as a random prime in the desired range of the group size (e. g. $2^{255} \le q < 2^{256}$), which ultimately also determines the signature size of Schnorr signatures;
  2. pick a random number $r$ that brings $p$ into the desired $b$-bit range such that $\lfloor log_2r \rfloor=b-\lfloor log_2q\rfloor$ (e. g. $2^{1792} \le r < 2^{1793}$ for bit size $b=2048$ of $p$, with the value of $q$ being in the range of the example noted above), where $p$ should be fairly large to resist attacks, namely it should be at least a 2048-bit number;
  3. compute $p=qr+1$ and check whether the resulting $p$ is prime;
  4. for $g=h^r\pmod{p}$, check whether $g \equiv 1\pmod{p}$ and return to step 2 if so, else $g$ is the generator of the group.

However, for efficiency reasons, I'm interested in groups with the generator $g=2$ because exponentiation of $2$ is a trivial bit shift. When generating groups with the method outlined above, there is an approximate chance of $\frac{\lfloor\log_2{q}\rfloor}{\lfloor\log_2{p}\rfloor}$ that $2$ is a member of the group – and all members of the group are generators of the group because $q$ is prime. However, that is still an effectively impossible chance.

Is there a way to generate a Schnorr group with $g=2$ that doesn't rely on random chance and is reasonably efficient to compute (possible to do within at most weeks on commodity hardware)?

  • 1
    $\begingroup$ Is there a specific reason you want a Schnorr group, rather than a safe prime (which would make this problem comparatively easy)? $\endgroup$
    – poncho
    Commented Aug 22, 2020 at 14:25
  • $\begingroup$ @poncho That's because I want to do Schnorr signatures over the resulting group. It doesn't have to be a Schnorr group specifically as long as it's a group suitable for DL-based Schnorr signatures (implying $q$ being small and $p$ being large). $\endgroup$
    – xorhash
    Commented Aug 22, 2020 at 14:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.