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): hash=sha256(); hash.update(str(r).encode()); hash.update(M.encode()); 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