:FRONTMATTER:  layout: post title: "Cryptography: ECSchnorr" date: 20190625 tags: ["cryptography", "schnorr", "math", "ellipticcurve", "sagemath"]  :END:
Overview
"If you can't explain it simply, you don't understand it well enough"  Einstein
ECSchnorr, as the name suggests, is a Schnorrtype digital signature scheme over elliptic curve, it's ECDSA's little sister and Schnorr's big brother with multiple implementations out there: maybe most widely deployed being EdDSA (used in Monero) or the upcoming MuSig implementation 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.
import hashlib p = 103 F = FiniteField(p) E = EllipticCurve(F, [0, 7]) G = E([97, 10]) n = G.order() k = randint(2, n) P = k * G t = randint(2, n) R = t * G m = 6 h = int(hashlib.sha256(str(P) + str(R) + str(m)).hexdigest(), 16) s = (t + h * k) % n hv = int(hashlib.sha256(str(P) + str(R) + str(m)).hexdigest(), 16) print "YOU ARE A CRYPTOSTAR!" if s * G == R + hv * P else "YOU SUCK!"
YOU ARE A CRYPTOSTAR!
Elliptic curve multiplication trapdoor
Nothing new under the sun so far, the same elliptic curve `EC` defined over finite field `p` with generator `G` of order `n`. See ECDSA post for more elliptic curve information. We start the show by generating a random private key `k` and calculate the public key point `P`.
import hashlib p = 103 F = FiniteField(p) E = EllipticCurve(F, [0, 7]) G = E([97, 10]) n = G.order() k = randint(2, n) P = k * G
`P` is public parameter while `k` is kept secret:
P
(68 : 17 : 1)
Signature

Here is the biggest difference between ECDSA and ECSchnorr:
 ECDSA uses division (aka multiplicative inverse) to calculate the signature `u, v` parameters
 ECSchnorr uses a preimage hash of public key `P`, random point `R` and message itself `m`.
The rest is simple arithmetic, generate temporary nonce `t` and calculate the point `R` on elliptic curve, preimage hash `h` and signature challenge `s`:
t = randint(2, n) R = t * G m = 6 h = int(hashlib.sha256(str(P) + str(R) + str(m)).hexdigest(), 16) s = (t + h * k) % n
Then the returned signature is a tuple of a point on elliptic curve and scalar value:
(R, s)
((60 : 99 : 1), 56)
Verification
A thirdparty receives the (R, s) signature tuple, calculates the deterministic preimage hash `hv` and checks whether or not the equation `s * G = R + h * P` is valid. This is all folks.
hv = int(hashlib.sha256(str(P) + str(R) + str(m)).hexdigest(), 16) print "YOU ARE A CRYPTOSTAR!" if s * G == R + hv * P else "YOU SUCK!"
YOU ARE A CRYPTOSTAR!
Intuition
Starting with verification equation and going backwards: replace `s` with corresponding formula, then replace `P` and after reduction we are left with `G == G`
s * G == R + h * P (t + h * k) * G == R + h * P (t + h * k) * G == t * G + h * k * G (t + h * k) * G == (t + 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 :)