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)
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)
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!
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!