2
$\begingroup$

Wikipidia says Schnorr signature generation is defined like this:

Y = x * G //this is the key we are trying to provide a signature for
k = random scalar
r = k * G
e = Hash_to_scalar(r || message)
s = k - xe
signature = (s, e)

This seems correct, but then to verify it's defined as:

r = s * G * e * Y
e = Hash_to_scalar(r || message)

Shouldn't it be:

r = s * G + e * Y
e = Hash_to_scalar(r || message)

because:

r = k - xe * G + ex * G == k * G; //this works
r = k - xe * G * ex * G != k * G; //this doesnt work

Or have I made a silly mistake somewhere?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Why should $k - xe + ex * G$ be equal to $k * G$ ? $\endgroup$ – Ruggero Nov 16 '18 at 12:55
  • $\begingroup$ Ah i made a typo. i mean k - xe * G + ex * G. edited now $\endgroup$ – cookiekid Nov 16 '18 at 13:00
  • $\begingroup$ Since Wikipedia pages evolve, it is a good idea to look at the version history to find the version that you probably looked at, rather than the most recent version. $\endgroup$ – user63532 Nov 16 '18 at 16:11
2
$\begingroup$

The equation in Wikipedia is r = s*G + e*Y, and not r = s*G * e*Y

Thus, r = s*G + e*Y = (k - xe)*G + e*(x*G) = k*G - xe*G + xe*G = k*G

Improve this answer
$\endgroup$
  • $\begingroup$ In fact, the Wikipedia page is also completely wrong since it keeps mixing additive and multiplicative notations. $\endgroup$ – Thomas Pornin Nov 16 '18 at 13:00
  • 4
    $\begingroup$ I have fixed the Wikipedia page. $\endgroup$ – Thomas Pornin Nov 16 '18 at 13:02
  • $\begingroup$ @Conrado yes that was an edit made by me. Previously it said r = s * G * e * Y but i edited it to see if a moderator would remove correct me in case i was wrong :) $\endgroup$ – cookiekid Nov 16 '18 at 13:02
  • 3
    $\begingroup$ @Thomas Pornin: useful fix! But the signature scheme as originally described differs slightly: the signature is $\left(H\left(g^k\mathbin\|M\right), k+x\,H\left(g^k\mathbin\|M\right)\right)$ with the hash much shorter than $q$; also notice the $+$ (Claus-Peter Schnorr described both as features). Detailed description of the original scheme and bibliography there. Practice often differs, especially for Elliptic Curve variants, taxonomy there. $\endgroup$ – fgrieu♦ Nov 16 '18 at 13:33
  • $\begingroup$ @ fgrieu Thank you for documenting Schnorr signature scheme and further development. $\endgroup$ – Vadym Fedyukovych Nov 16 '18 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.