— 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 []