Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems.
The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008.
There has been a proposal to include Schnorr signatures in Bitcoin, but it has not been accepted at this point. (The proposal would use Schnorr signatures but over an elliptic curve rather than a Schnorr group.)
Group construction
Pick a large prime p. Then the integers mod p form a finite field. The non-zero elements form an Abelian group of order p-1 under multiplication. Then p – 1 is composite, and so it can be factored into qr where q is prime. We want q to be large as well because it will be the order of our Schnorr group.
Pick any h such that hr is not congruent to 1 mod p. Then g = hr is the generator of our Schnorr group. Why does g have order q? A simple calculation shows
where the last step follows from Fermat’s little theorem. This shows that the order of g is either q or a divisor of q, but by construction g is not congruent to 1 (mod p), and q has no other factors since it is prime.
Python code
Here’s a toy example using small numbers. Let p = 23, q = 11 and r = 2. Then we can pick h to be any number that is not a root of 1 (mod 23), i.e. any number except 1 or 22. Say we pick h = 7. Then g = 49 = 3 (mod 23).
Here’s a Python script to verify our claims and print out the elements of our Schnorr group.
from sympy import isprime
p, q, r, h = 23, 11, 2, 7
assert(isprime(p))
assert(isprime(q))
assert(p-1 == q*r)
g = h**r % p
assert(g != 1)
assert(g**q % p == 1)
for i in range(q):
print( g**i % p )
This shows that our group elements are {1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8}.
In theory we could use the same script with much larger numbers, but in that case we wouldn’t want to print out the elements. Also, the code would take forever. We naively computed ab (mod m) by computing ab first, then taking the remainder modulo m. It is far more efficient to reduce modulo m along the way. That’s what Python’s three-argument pow function does.
Here’s a revised version that runs quickly with large numbers.
from sympy import isprime
p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
q = 341948486974166000522343609283189
r = 338624364920977752681389262317185522840540224
h = 3141592653589793238462643383279502884197
assert(isprime(p))
assert(isprime(q))
assert(p-1 == q*r)
g = pow(h, r, p)
assert(g != 1)
assert(pow(g, q, p) == 1)
Related posts
Photo of Claus Schnorr by Konrad Jacobs CC BY-SA 2.0 de
I want to write something about Schnorr groups in a scientific paper. Do you know where this procedure of creating them has first been published? I cannot find it in here: https://link.springer.com/article/10.1007/BF00196725 Is it somewhere in Schnorr’s patent (https://patents.google.com/patent/US4995082A/en)?
Thanks anyway for this very accessible explanation of Schnorr groups! Could not find anything like this anywhere else.