— layout: post title: "Cryptography: Schnorr" date: 2019-06-19 tags: ["cryptography", "schnorr", "discrete-logarithm", "math", "sagemath"] —

Overview

"If you can't explain it simply, you don't understand it well enough" - Einstein

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.

  import random, hashlib
  p = 103
  q = 17
  r  = 6
  h = random.choice([h for h in range(1, p) if h**r % p != 1 ])
  g = h**r % p
  k = random_prime(q)
  y = g**k % q
  m = 6
  t = random_prime(q)
  r = g**t % q
  e = int(hashlib.sha1(str(r) + str(m)).hexdigest(), 16) % q
  s = (t - k*e)
  rv = (g**s * y**e) % q
  ev = int(hashlib.sha1(str(rv) + str(m)).hexdigest(), 16) % q
  print "YOU ARE A CRYPTOSTAR!" if ev == e else "YOU SUCK!"
2
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:

  p = 103
  q = 17
  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:

  h = random.choice([h for h in range(1, p) if h**r % p != 1 ])
  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`.

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

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

  (g, y)

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`.

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

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

  (e, s)
(-93, 14)

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:

  rv = (g**s * y**e) % q
  ev = int(hashlib.sha1(str(rv) + str(m)).hexdigest(), 16) % q
  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`.

  rv = g**s * y**e
  rv = g**(t - k*e) * y**e
  rv = g**(t - k*e) * g**(k*e)
  rv = g**t

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

  p = 199
  q = 109
  q
  r = [r for r in range(1, 1000) if p == q*r + 1 ]
  r
  # q = [i for i in prime_range(103) if p == q*r+ 1]
  # q
109
[]