Source code and results for the Schnorr signature tutorial available under https://mareknarozniak.com/2021/05/25/schnorr-signature/

figures_thumbnail.sh

#!/bin/sh
convert -background none multisignature_alice.png multisignature_bob.png multisignature_composite.png +append multisignature_keys.png
convert -background none multisignature_nonces.png multisignature_lhs_signatures.png multisignature_rhs_signatures.png +append multisignature_verification.png

multisignature_alice.png

multisignature_bob.png

multisignature_composite.png

multisignature_keys.png

multisignature_lhs_signatures.png

multisignature_nonces.png

multisignature_rhs_signatures.png

multisignature_verification.png

requirements.txt

numpy
matplotlib
minicurve

run.py

import math
import matplotlib.pyplot as plt
import numpy as np
import hashlib


from minicurve import MiniCurve as mc
from minicurve import Visualizer
from minicurve.helpers import inverse


def add_digits(num, p):
    return (num - 1) % p if num > 0 else 0


def hashtard(m, p):
    hash = hashlib.sha256(str.encode(m))
    num = int.from_bytes(hash.digest(), 'big')
    num = add_digits(num, p)
    return num


def sign(m, k, d, G, p):
    # calculate public key R = k*G
    R = k*G
    # calculate e = H(M || r) where || is concatenation
    e = hashtard(m, p)
    # calculate the signature
    s = np.mod(k + d*e, p)
    # signature is s, R
    return s, R


def verify(m, s, G, P, R, p):
    # e_v = H(M || r_v)
    e = hashtard(m, p)
    # calculate the verification
    lhs = s*G
    rhs = R+e*P
    # test if lhs = rhs
    if lhs == rhs:
        return True, lhs, rhs
    return False, lhs, rhs


# article URL
url = 'https://mareknarozniak.com/2021/05/25/schnorr-signature/'

# eliptic curve and finite field parameters
p = 13
a = 1
b = 7

# message
m = 'I say we take off and nuke the entire site from orbit. It\'s the only way to be sure.'

# pick a generator point
G = mc(a, b, p, x=10, y=4, label='G', color='tab:green', tracing=True)

# Alice's private key
d_alice = 7

# Alice's nonce
k_alice = 3

# Bob's private key
d_bob = 4

# Bob's nonce
k_bob = 5

# public key is P = d*G
P_alice = d_alice*G
P_bob = d_bob*G

# combine their public keys
P_comb = P_alice + P_bob

# include public keys in the message to be signed
m += str(P_alice.x) + ' ' + str(P_alice.y) + ' ' + str(P_bob.x) + ' ' + str(P_bob.y)

# produce Alice's signature
s_alice, R_alice = sign(m, k_alice, d_alice, G, p)

# produce Bob's signature
s_bob, R_bob = sign(m, k_bob, d_bob, G, p)

# combine their nonces
R_comb = R_alice + R_bob

# combine those signatures into a multi-signature
s_comb = np.mod(s_alice + s_bob, p)

print('Trying to verify signature with just Alice\'s public key')
valid_alice, v_lhs_alice, v_rhs_alice = verify(m, s_alice, G, P_alice, R_alice, p)

if not valid_alice:
    print('failed')
else:
    print('valid')

print('Trying to verify signature with just Bob\'s public key')
valid_bob, v_lhs_bob, v_rhs_bob = verify(m, s_bob, G, P_bob, R_bob, p)

if not valid_bob:
    print('failed')
else:
    print('valid')

print('Trying to verify signature with composite public key')
valid_comb, v_lhs_comb, v_rhs_comb = verify(m, s_comb, G, P_comb, R_comb, p)

if not valid_comb:
    print('failed')
else:
    print('valid')

# visualization

P_alice.setColor('tab:orange')
P_alice.setLabel('Alice')

P_bob.setColor('tab:orange')
P_bob.setLabel('Bob')

P_comb.setColor('tab:orange')
P_comb.setLabel('Alice + Bob')

# Alice's private key

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [G, P_alice]
vis.generatePlot(title='Alice\'s Public Key')
plt.figtext(0.0, 0.01, url, rotation=0)
vis.plot('multisignature_alice.png')

# Bob's private key

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [G, P_bob]
vis.generatePlot(title='Bob\'s Public Key')
vis.plot('multisignature_bob.png')

# composite key

P_alice.tracing = False
P_bob.tracing = False

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [G, P_alice, P_bob, P_comb]
vis.generatePlot(title='Composite Public Key', addition=True)
vis.plot('multisignature_composite.png')

# nonces

R_alice.setColor('tab:purple')
R_alice.setLabel('Alice')

R_bob.setColor('tab:purple')
R_bob.setLabel('Bob')

R_comb.setColor('tab:purple')
R_comb.setLabel('Composite Nonce')

R_alice.tracing = False
R_bob.tracing = False

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [G, R_alice, R_bob, R_comb]
vis.generatePlot(title='Nonces', addition=True)
plt.figtext(0.0, 0.01, url, rotation=0)
vis.plot('multisignature_nonces.png')

# visualize the signature verification (LHS)

v_lhs_alice.setColor('tab:red')
v_lhs_alice.setLabel('Alice (LHS)')
v_lhs_alice.tracing = False

v_lhs_bob.setColor('tab:red')
v_lhs_bob.setLabel('Bob (LHS)')
v_lhs_bob.tracing = False

v_lhs_comb.setColor('tab:red')
v_lhs_comb.setLabel('Composite (LHS)')
v_lhs_comb.tracing = False

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [v_lhs_alice, v_lhs_bob, v_lhs_comb]
vis.generatePlot(title='LHS of the signatures')
vis.plot('multisignature_lhs_signatures.png')

# visualize the signature verification (RHS)

v_rhs_alice.setColor('tab:cyan')
v_rhs_alice.setLabel('Alice (RHS)')
v_rhs_alice.tracing = False

v_rhs_bob.setColor('tab:cyan')
v_rhs_bob.setLabel('Bob (RHS)')
v_rhs_bob.tracing = False

v_rhs_comb.setColor('tab:cyan')
v_rhs_comb.setLabel('Composite (RHS)')
v_rhs_comb.tracing = False

vis = Visualizer(a, b, p)
vis.makeField()
vis.points = [v_rhs_alice, v_rhs_bob, v_rhs_comb]
vis.generatePlot(title='RHS of the signatures')
vis.plot('multisignature_rhs_signatures.png')