5
$\begingroup$

I'm implementing classical Schnorr signatures for real-world use. By "classical" I mean that the operations take place in a finite group, no elliptic curves.

I'm following https://en.wikipedia.org/wiki/Schnorr_signature and https://en.wikipedia.org/wiki/Schnorr_group and some academic papers.

After choosing $p=qr+1$ with $p$ and $q$ prime I need to calculate a suitable "generator" $g$.

As explained on the Wikipedia page I set $h=2$ and try to see if $h^r \textrm{mod } p$ is different from 1 (it always has been so far) and that value becomes $g$.

The trouble is, $g$ is (logarithmically) about as large a number as $p$ when chosen this way.

Is there a way to choose a smaller $g$ so that less parameter data needs to be passed around?

If I understand correctly, any $g$ s.t. $g^q=1 \textrm{ mod }p$ ought to work (provided, of course, $g \ne 1$). It's easy to see why $2^r$ works; it's because $(2^r)^q=2^{rq}=2^{p-1}$ which is 1 by Fermat's little theorem.

But can a smaller $g$ be derived somehow?

$\endgroup$
  • 1
    $\begingroup$ Just try small candidates for g. ​ ​ $\endgroup$ – user991 Apr 9 '17 at 12:27
  • $\begingroup$ Can you just set $r = 2$? In just about every case I've encountered, $g = 3$ will work in that case. $\endgroup$ – Bristol Apr 26 '18 at 20:48
  • $\begingroup$ @Bristol It's been a while since I was fooling around with Schnorr signatures, but IIRC setting a larger $r$ increases the security level at a lower cost than just increasing $q$. $\endgroup$ – EnTaroAdun Apr 27 '18 at 20:24
  • 1
    $\begingroup$ @Bristol: problem is, the signature has the size of $q$, and $p$ must be large, thus we must use a large $r$ if we want short signatures. And, as stated in that answer, we can use a small $h$, but AFAIK not a small $g$. $\endgroup$ – fgrieu Aug 26 at 13:05
1
$\begingroup$

FIPS 186-4 appendix A.2 gives an algorithm to generate $g$. They are not talking about Schnor signatures but apparently DSA uses just the same kind of finite cyclic groups.

The algorithm really just tries random $1 < h < p-1$ until it finds an $h$ that fulfills $h^r \not\equiv 1 \pmod{p}$. Apparently the probability to find such an $h$ is not too small.

Fermat's little theorem states that $a^{p-1} \equiv 1 \pmod{p}$ for any prime $p$ and $a \in \mathbb{Z}^+$ with $p \nmid a$.

Thus, with $h<p$ you automatically get $p \nmid h$ and therefore $g^q \equiv h^{rq} \equiv h^{p-1} \equiv 1 \pmod{p}$.

I guess the goal cannot be to find a $g$ with a small bit width to save data. As you calculate $g = h^r \text{ mod } p$ with $r$ being random (uniformly distributed), the possible values for $g$ should be uniformly distributed as well.

$\endgroup$

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.