Schnorr groups

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 h^r is not congruent to 1 mod p. Then g = h^r 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 a^b (mod m) by computing a^b 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

• Elliptic curves over finite fields
• Fast exponentiation
• Bayesian methods at Bletchley Park

Photo of Claus Schnorr by Konrad Jacobs CC BY-SA 2.0 de