It is not the first time digital signatures appear on this blog as we have already introduced the ECDSA signatures earlier as well as a more general introduction to the elliptic curve cryptography has been provided in the Diffie-Hellman key exchange over eliptic curve tutorial.
To be honest, I was planning to write about something completely different but it was so heavily reliant on the Schnorr signature which is at the same time sufficiently different from ECDSA to deserve its own blog post. The concept I was going to write about will remain a surprise at the moment. If you read it in the future you might want to check what happened next and find it immediately.
As you might have already seen in the ECDSA signatures tutorial, the digital signature permits to prove a message has been seen by a person owning a particular private-public key pair. The example we provided in that particular tutorial consisted of a mysterious messages from a from a friend and digital signature helped estimate which of the messages is more likely to be true.
In this tutorial we will do something similar, we will use different kind of signature and we will produce a multi-signature, which is a signature produced by multiple individuals. The Schnorr signatures (Schnorr, n.d.) have been known before ECDSA signatures, yet they were not so widely used due to the patent which expired in the year 2008. One of the advantages is existence of a proof that breaking the Schnorr signature is equivalent of breaking the discrete logarithm problem. Another one is the linear nature of the signature making it possible to easily combine multiple signatures together.
Let us break the convention and denote private key as , generator point we can keep as . Public key is thus
and additionally we find a random integer which must fit within the prime order of the group generated by and we produce a point on the curve as follows
then we calculate
where is the signed message and denotes concatenation and is the hash function as those explained in our hashing functions tutorial. The signature is a tuple
To verify the signature we proceed as follows. Given and message we have to check if
in Python using our own ECC library as in previous tutorial the signature method is
def sign(m, k, d, Gx, Gy, n, p=17, a=0, b=7): # calculate public key R = k*G _, _, Rx, Ry = eccScalarMult(k, Gx, Gy, a, b, p) # calculate e = H(M || r) where || is concatenation e = hashtard(m, p=n) # calculate the signature s = np.mod(k - d*e, n) # signature is s, R return s, Rx, Ry
where is the random nonce, is the order of the group generated by and is the order of the entire finite field. We also the verification method
def verify(m, s, Gx, Gy, Px, Py, Rx, Ry, n, p=17, a=0, b=7): # e_v = H(M || r_v) e = hashtard(m, p=n) # lhs = s*G _, _, sGx, sGy = eccScalarMult(s, Gx, Gy, a, b, p) # e*P _, _, ePx, ePy = eccScalarMult(e, Px, Py, a, b, p) # rhs = R+(e*P) r_x, r_y = eccFiniteAddition(Rx, Ry, ePx, ePy, a, b, p) # test if lhs = rhs if r_x == sGx and r_y == sGy: return True, r_x, r_y return False, r_x, r_y
The implementation is confusing, please refer to previous ECC tutorials for more details.
Now to produce multi-signature we start by combining the keys of each of the participants using curve point addition
in the implementation of ECC I prepared for those tutorials that would be
Px_comb, Py_comb = eccFiniteAddition(Px_alice, Py_alice, Px_bob, Py_bob, a, b, p)
then each of the participant is producing the signature, this should give us and for Bob. The and can be combined using modulo integer addition and for random points we use eliptic curve addition
which gives as a multi-signature . This signature is verifiable only for the composite key , for the individual keys of Alice and Bob it is not valid.
As usual let us perform a little demo. Lets imagine a scenario in which a very important message needs to be signed by both Alice and Bob. Message goes as follows
I say we take off and nuke the entire site from orbit. It's the only way to be sure.
Private keys of Alice and Bob are respectively and . Very insecure and small numbers, as they must fit in the range of prime order of group resulting from the generating point. Keys can be visualized as follows.
then their respective random nonces are and . Along with the ready signatures we can visualize as
and we can observe that only for the composite the recreated point matches proving the signature is valid. For this example I had to increase the prime order of the finite field from into to increase the number of available point for the nonces and keys.
If you run the source code of this example you will see the outputs confirming validity of the result
Trying to verify signature with just Alice's public key failed Trying to verify signature with just Bob's public key failed Trying to verify signature with composite public key valid
This was short tutorial, but I hope it will end up useful as once we have Schnorr signatures and multi-signatures we can go into more advanced concepts, such as Pedersen commitments, confidential transactions, adaptor signatures and much much more!
I would like to thank John Tromp for answering my questions and providing comments regarding Schnorr signatures on the cryptography channel in the grincoin keybase team. I also thank vegycslol for a discussion that helped improve the quality of this tutorial and make it lot less confusing.
If you find typos or errors in this text please do not hesitate to let me know, for which best way is to simply tweet me.
- Schnorr, C. P. Efficient Identification and Signatures for Smart Cards. In Advances in Cryptology — CRYPTO’ 89 Proceedings (pp. 239–252). Springer New York. https://doi.org/10.1007/0-387-34805-0_22