Schnorr is another digital signature scheme known for its simplicity, no division, no inversion, just plain old multiplication. Here is my simple 16 lines implementation in Python.

 1  import random, hashlib
 2  p = 103
 3  q = 17
 4  r  = 6
 5  h = random.choice([h for h in range(1, p) if h**r % p != 1 ])
 6  g = h**r % p
 7  k = random_prime(q)
 8  y = g**k % q
 9  m = 6
10  t = random_prime(q)
11  r = g**t % q
12  e = int(hashlib.sha1(str(r) + str(m)).hexdigest(), 16) % q
13  s = (t - k*e)
14  rv = (g**s * y**e) % q
15  ev = int(hashlib.sha1(str(rv) + str(m)).hexdigest(), 16) % q
16  print "YOU ARE A CRYPTOSTAR!" if ev == e else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

Discrete logarithm trapdoor

To generate a Schnorr group that stands at the base of our Schnorr signature scheme we need to generate `p`, `q` and `r` numbers that satisfy the equation: `p = q*r + 1` where `p` and `q` are primes. You can use any algorithm (even brute-force) to generate the numbers, here are mine:

1  p = 103
2  q = 17
3  r  = 6

Next we need to find a generator `g` that generates our sub-group of order `q`. Basically we brute-force and select all numbers less than `p` that satisfy the equation `h**r % p != 1`, choose a random one then the remainder is our generator `g`. The math is a bit involved, please see Schnorr group for more info:

4  h = random.choice([h for h in range(1, p) if h**r % p != 1 ])
5  g = h**r % p

Once we have the generator `g` we need to pick a random prime number as private key `k` and generate the public key `y`.

6  k = random_prime(q)
7  y = g**k % q

And finally `g`, `y` are public parameters while `k` is kept secret:

(g, y)

(64, 16)

Signature

For signing we first generate a temporary random nonce `t` and the corresponding member of the group `r`. Then group member `r` gets concatenated with the message `m` that we need to sign, hash everything together and create pre-image `e`. And finally the challenge signature number `s`.

 8  m = 6
 9  t = random_prime(q)
10  r = g**t % q
11  e = int(hashlib.sha1(str(r) + str(m)).hexdigest(), 16) % q
12  s = (t - k*e)

The signature that is made public to third-party for verification is the pair `e, s`:

(e, s)

(10, -7)

Verification

Given the public parameters and the signature above we can easily calculate random group member `rv` that is used to hash the final pre-image for verification:

13  rv = (g**s * y**e) % q
14  ev = int(hashlib.sha1(str(rv) + str(m)).hexdigest(), 16) % q
15  print "YOU ARE A CRYPTOSTAR!" if ev == e else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

Intuition

Starting with the verification equation and replacing `s` and `y` with corresponding formulas we end up with `rv == r`.

1  rv = g**s * y**e
2  rv = g**(t - k*e) * y**e
3  rv = g**(t - k*e) * g**(k*e)
4  rv = g**t

Because `rv` and `r` are equal the two pre-image hashes must be equal as well. MAGIC!