# Schnorr

## Cryptography

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!