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 dd, generator point we can keep as GG. Public key is thus

P=dG\begin{aligned} P = d G \end{aligned}

and additionally we find a random integer kk which must fit within the prime order of the group generated by GG and we produce a point on the curve as follows

R=kG\begin{aligned} R = k G \end{aligned}

then we calculate

s=kH(mP)d\begin{aligned} s = k - H(m \vert\vert P) d \end{aligned}

where mm is the signed message and \vert\vert denotes concatenation and H()H() is the hash function as those explained in our hashing functions tutorial. The signature is a tuple

<s,R>(I)\begin{aligned} \left< s, R \right> \tag{I} \end{aligned}

To verify the signature we proceed as follows. Given <s,R>\left< s, R \right> and message mm we have to check if

sG=R+H(mP)P\begin{aligned} s G = R + H(m \vert\vert P) P \end{aligned}

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 kk is the random nonce, nn is the order of the group generated by GG and pp 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

Pc=PA+PB\begin{aligned} P_c = P_A + P_B \end{aligned}

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 <sA,RA>\left< s_A, R_A \right> and <sB,RB>\left< s_B, R_B \right> for Bob. The sAs_A and sBs_B can be combined using modulo integer addition and for random points we use eliptic curve addition

sc=sA+sBmodpRc=RA+RB\begin{aligned} s_c &= s_A + s_B \mod p \\ R_c &= R_A + R_B \end{aligned}

which gives as a multi-signature <sc,Rc>\left< s_c, R_c \right>. This signature is verifiable only for the composite key PcP_c, 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 22 and 33. 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 33 and 44. 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 p=17p = 17 into p=29p = 29 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
Trying to verify signature with just Bob's public key
Trying to verify signature with composite public key

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!

If you like to know more, I based this tutorial on what the heck is Schnorr medium article and cryptography fandom Schnorr signature page.

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.

  1. Schnorr, C. P. Efficient Identification and Signatures for Smart Cards. In Advances in Cryptology — CRYPTO’ 89 Proceedings (pp. 239–252). Springer New York.

[Back to Top]