EC-Schnorr

EC-Schnorr, as the name suggests, is a Schnorr-type digital signature scheme over elliptic curve, it's ECDSA's little sister and Schnorr's big brother implemented in the upcoming MuSig in Bitcoin.

It is also one of my favorite digital signature scheme because of its simplicity. As you will see later it is just a linear equation that opens the door to multi signatures and signature aggregation.

  p = 103                      # EC parameters
  F = FiniteField(p)
  E = EllipticCurve(F, [0, 7])
  G = E([97, 10])
  n = G.order()

  k = randint(2, n)            # private key
  P = k * G                    # public key

  import hashlib
  def H(R, P, m):              # hash function
    data = bytes(R) + bytes(P) + bytes(m)
    digest = hashlib.sha256(data).digest()
    return int.from_bytes(digest, byteorder="little")

  r = randint(2, n)            # signing
  R = r * G
  m = 6
  sh = H(R, P, m)
  s = (r + sh * k) % n         # signature (R, s)

  vh = H(R, P, m)              # verification
  print("YOU ARE A CRYPTOSTAR!") if s * G == R + vh * P else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

Nothing new under the sun so far, the same elliptic curve E defined over finite field p with generator G of order n. See ECDSA post for more elliptic curve information.

  p = 103                      # EC parameters
  F = FiniteField(p)
  E = EllipticCurve(F, [0, 7])
  G = E([97, 10])
  n = G.order()

We start the show by generating a random private key k and calculate the public key point P which is public parameter while k is kept secret.

  k = randint(2, n)            # private key
  P = k * G                    # public key
  P

(78 : 48 : 1)

Here is the biggest difference between ECDSA and EC-Schnorr:

• ECDSA uses division (aka multiplicative inverse, which is more expensive) to calculate the signature (u, v) parameters
• EC-Schnorr uses multiplication of private key and a hash of public key P, random point R and message m

The rest is simple arithmetic, generate random nonce r and calculate the random point R, compute the signing hash sh (using our little H function) and last the signature challenge s:

  import hashlib
  def H(R, P, m):              # hash function
    data = bytes(R) + bytes(P) + bytes(m)
    digest = hashlib.sha256(data).digest()
    return int.from_bytes(digest, byteorder="little")

  r = randint(2, n)            # signing
  R = r * G
  m = 6
  sh = H(R, P, m)
  s = (r + sh * k) % n         # signature (R, s)

The signature is a tuple of a point on elliptic curve and scalar value.

  (R, s)

((78 : 55 : 1), 102)

A third-party receives the (R, s) signature, calculates the verification hash vh and checks whether or not the equation s * G = R + h * P is valid.

  vh = H(R, P, m)              # verification
  print("YOU ARE A CRYPTOSTAR!") if s * G == R + vh * P else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

Starting with verification equation and going backwards: replace s with corresponding formula, then replace P and G and after reduction we are left with G == G

  s * G == R + h * P
  (r + h * k) * G == R + h * P
  (r + h * k) * G == r * G + h * k * G
  (r + h * k) * G == (r + h * k) * G
  G == G

True
True
True
True
True

Pretty brilliant huh? but it does not stop here, s * G = R + h * P is a linear equation and we can add / multiply each side while the equation stays valid.

What if we add 2 equations together, side by side?

• s1 * G1 = R1 + h1 * P1
• s2 * G2 = R2 + h2 * P2

But this is a subject for another post :)