3
$\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?

$\endgroup$
3
  • 1
    $\begingroup$ Why should $k - xe + ex * G$ be equal to $k * G$ ? $\endgroup$
    – Ruggero
    Nov 16, 2018 at 12:55
  • $\begingroup$ Ah i made a typo. i mean k - xe * G + ex * G. edited now $\endgroup$
    – cookiekid
    Nov 16, 2018 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, 2018 at 16:11

1 Answer 1

3
$\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

$\endgroup$
5
  • $\begingroup$ In fact, the Wikipedia page is also completely wrong since it keeps mixing additive and multiplicative notations. $\endgroup$ Nov 16, 2018 at 13:00
  • 4
    $\begingroup$ I have fixed the Wikipedia page. $\endgroup$ Nov 16, 2018 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, 2018 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, 2018 at 13:33
  • $\begingroup$ @ fgrieu Thank you for documenting Schnorr signature scheme and further development. $\endgroup$ Nov 16, 2018 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.