3
$\begingroup$

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)?

$\endgroup$
2
  • 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
    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
    Aug 22, 2020 at 14:57

0

Your Answer

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

Browse other questions tagged or ask your own question.