# Small generator for classical Schnorr signatures?

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?

• Just try small candidates for g. ​ ​ – user991 Apr 9 '17 at 12:27
• Can you just set $r = 2$? In just about every case I've encountered, $g = 3$ will work in that case. – Bristol Apr 26 '18 at 20:48
• @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$. – EnTaroAdun Apr 27 '18 at 20:24
• @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$. – fgrieu Aug 26 '19 at 13:05

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 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.