Tutorial covering the Eliptic Curve Digital Signature Algorithm (ECDSA) available under https://mareknarozniak.com/2021/03/16/ecdsa/

ecdsa_knowledge.png

ecdsa_knowledge_alice.png

ecdsa_knowledge_bob.png

ecdsa_knowledge_eavesdropper.png

figures.sh

#!/bin/sh
convert ecdsa_knowledge_alice.png ecdsa_knowledge_bob.png ecdsa_knowledge_eavesdropper.png +append ecdsa_knowledge.png

plotting.py

import numpy as np
import matplotlib.pyplot as plt


def plotSig(es, ss, rs, r_primes, labels, p,
        title=None,
        url=False,
        filename='signatures.png'):
    fig, axs = plt.subplots(len(es), 1)
    plt.suptitle(title)
    for ax, e, s, r, r_p, label in zip(axs, es, ss, rs, r_primes, labels):
        ax.set_xticks(range(p+1))
        ax.set_yticks(range(5))
        ax.set_yticklabels(['', '$e$', '$s$', '$r$', '$r^\prime$'])
        ax.set_xlim([-1, p+1])
        ax.set_ylim([0, 5])
        ax.set_axisbelow(True)
        ax.grid()
        ax.axvline(p, color='black')
        ax.text(p - 0.5, 0.5, '$p$', va='center')
        ax.axvline(e, color='tab:purple')
        ax.axvline(s, color='tab:orange')
        color = 'tab:red'
        if r == r_p:
            color = 'tab:blue'
        ax.axvline(r, color=color, linestyle='dashed')
        ax.axvline(r_p, color=color, linestyle='dotted')
        ax.scatter(e, 1, color='tab:purple')
        ax.scatter(s, 2, color='tab:orange')
        ax.scatter(r, 3, color=color)
        ax.scatter(r_p, 4, color=color)
        ax.text(p + 1.25, 2.5, label, rotation=-90, va='center')
    if url:
        plt.figtext(0.0, 0.01, url, rotation=0)
    plt.tight_layout()
    fig.savefig(filename)

requirements.txt

numpy
matplotlib
minicurve

run.py

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

from plotting import plotSig


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(e, k, d, P, p):
    Q = k*P
    s = np.mod(inverse(k, p)*(e + d*Q.x), p)
    return s, Q.x


def verify(e, s, r, G, P, p):
    Q1 = np.mod(e*inverse(s, p), p)*G
    Q2 = np.mod(r*inverse(s, p), p)*P
    R = Q1+Q2
    if R.x == r:
        return True, R.x
    return False, R.x


# article URL
url = 'https://mareknarozniak.com/2021/03/16/ecdsa/'

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

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

# Alice key pair
d_a = 8
P_a = d_a*G
P_a.setColor('tab:orange')
P_a.setLabel('Alice')

# Bob key pair
d_b = 5
P_b = d_b*G
P_b.setColor('tab:orange')
P_b.setLabel('Bob')

# visualize what Alice knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = True
P_b.tracing = False
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What Alice knows')
plt.figtext(0.0, 0.01, url, rotation=0)
vis.plot('ecdsa_knowledge_alice.png')

# visualize what Bob knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = False
P_b.tracing = True
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What Bob knows')
vis.plot('ecdsa_knowledge_bob.png')

# visualize what eavesdropper knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = False
P_b.tracing = False
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What eavesdropper knows')
vis.plot('ecdsa_knowledge_eavesdropper.png')

# Bob writes the real message
m1 = '''
Dear Alice,

I am not sure where I am. It seems to be some kind of prison or a labor camp. I managed to convince someone to sneak out and send this letter to you. Please please please try to find me.

Miss you,
Bob
'''

# Bob signs his message
s1, r1 = sign(hashtard(m1, p), 3, d_b, G, p)

# There is another message from Bob
m2 = '''
Dear Alice,

I am currently taking long holidays in a beautiful place. The food is delicious here. I spend most of my time having fun with new friends. The means of communications are not perfect here so I do not send you my address. Please do not try to reach me, I will message you first.

All the best,
Bob
'''

# ...and it already has a signature!
s2, r2 = 4, 5

# Alice verifies the first message using Bob's public key
res, rp1 = verify(hashtard(m1, p), s1, r1, G, P_b, p)
print('Bob\'s signature on message 1 is valid?', res)

# ...and the second message
res, rp2 = verify(hashtard(m2, p), s2, r2, G, P_b, p)
print('Bob\'s signature on message 2 is valid?', res)

# brute force Bob's key
d_b_f = mc.bruteForceKey(G.x, G.y, P_b.x, P_b.y, a, b, p)

# forge his signature under second message using brute forced key
sf, rf = sign(hashtard(m2, p), 8, d_b_f, G, p)

# check if it gets verified
res, rpf = verify(hashtard(m2, p), sf, rf, G, P_b, p)
print('Bob\'s forged signature on message 2 is valid?', res)

plotSig(
    [hashtard(m1, p), hashtard(m2, p), hashtard(m2, p)],
    [s1, s2, sf],
    [r1, r2, rf],
    [rp1, rp2, rpf],
    ['sig 1', 'sig 2', 'sig 2 (forged)'], p,
    title='ECDSA Signatures',
    url=url,
    filename='signatures.png')

signatures.png