# Small generator for classical Schnorr signatures?

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

I'm following Schnorr signature and Schnorr group at Wikipedia, 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. – user2552 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.