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!