For educational purposes (by purpose with small values for the prime order q), I tried to write a small Python implementation of the Schnorr signature described in the Wikipedia article https://en.wikipedia.org/wiki/Schnorr_signature

I implemented the following in python (Python 3.6)

from hashlib import sha256
from random import randint

def hashThis(r, M):
    return int(hash.hexdigest(),16);

## Notation
# generator g
g = 2

# Prime q (for educational purpose I use explicitly a small prime number - for cryptographic purposes this would have to be much larger)
q = 2695139

## Key generation
#Private signing key x
x = 32991
# calculate public verification key y
y = pow(g, x, q)

## Signing
M = "This is the message"
k = randint(1, q - 1)
r = pow(g, k, q)
e = hashThis(r, M) % q # part 1 of signature
s = (k - (x * e)) % q # part 2 of signature

## Verification

rv = (pow(g, s, q) * pow (y, e, q)) % q
ev = hashThis(rv, M) % q

print ("e " + str(e) + " should equal ev " + str(ev))
# e 2241534 should equal ev 2462540

As you can see, e and ev should be equal - however, they are clarly not.

I don't know where the problem lies - do you have any ideas what I am doing wrong

Many thanks in advance


Beware, notice the $s$ is computed modulo $(q-1)$ (due to Fermat's little theorem). You have to write $s = (k - (x * e)) \mod{ (q-1)}$.

  • $\begingroup$ Thank you for your answer - indeed it works correctly with this small modification. However, could you elaborate more on the link between Fermat's little theorem and the usage of modulo (q - 1)? Why do I need to calculate e modulo q but s modulo (q - 1)? $\endgroup$ – user49404 Apr 11 '18 at 18:19
  • $\begingroup$ It is related to the fact that for any $a$, $a^{q-1}=1 \mod{q}$ holds (if $q$ is prime). That means that for any field element $a$, for any exponent $e$ and for any integer $r$, one has $a^{e} = a^{e+r \times (q-1)} = a^e \times a^{r\times(q-1)} = a^{e} \times (a^{(q-1)})^r = a^e \times 1^r = a^e \times 1 = a^e \mod{q}$. Actually, when thinking about field element, you have to think "$\mod{q}$", when thinking about exponent, you have to think about "$\mod{(q-1)}$". Since $s$ is used as an exponent, you have to think $\mod{q-1}$ ;-) $\endgroup$ – Jérémy Métairie Apr 11 '18 at 18:38
  • $\begingroup$ I cannot quite follow your conclusion. e is also used as an exponent ( y^e ) but is calculated mod q. And why does the exponent have to be mod q - 1? Would it violate Fermat's little theorem if the exponent was q? $\endgroup$ – user49404 Apr 11 '18 at 20:20
  • $\begingroup$ What I mean is that $g^s = g^{(s+r \times (q-1))}$. Somehow, $s$ is not affected by multiples of $(q-1)$. Of course, exponentiation is performed over $\mod{q}$. If you consider $s \mod{q}$ (meaning you can add multiple of $q$ to $s$) you would have something like $g^{s+r \times q} = g^{s} \times (g^q)^r$. Notice that because $g^{q-1} = 1$ then $g^q=g$. Since then $g^{s} \times (g^q)^r = g^s \times g^r$ which differs from $g^s$. $\endgroup$ – Jérémy Métairie Apr 12 '18 at 6:13