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

ecc.py

import numpy as np


# ECC addition in R
def eccContAddition(Px, Py, Qx, Qy, a, b):
    if np.isclose([Px], [Qx])[0]:
        m = (3.*Px**2.+a)/(2.*Py)
    else:
        m = (Py-Qy)/(Px-Qx)
    Rx = m**2 - Px - Qx
    Ry = Py + m*(Rx - Px)
    return Rx, Ry, m


# EC point addition
def onCurve(X, Y, a, b, p):
    # None is the infinity point
    if X is None and Y is None:
        return True
    return np.mod(Y**2 - X**3 - a*X - b, p) == 0


def extendedEuclideanAlgorithm(x1, x2):
    # base case
    if x1 == 0:
        return x2, 0, 1
    # recursive call
    gcd, x_, y_ = extendedEuclideanAlgorithm(x2 % x1, x1)
    x = y_ - (x2 // x1) * x_
    y = x_
    return gcd, x, y


# modular multiplicative inverse
def inverse(n, p):
    if n == 0:
        raise ZeroDivisionError('Stahp dividing by zero you!!!')
    if n < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse(-n, p)
    gcd, x, _ = extendedEuclideanAlgorithm(n, p)
    assert gcd == 1
    assert np.mod(n*x, p) == 1
    return np.mod(x, p)


def eccFiniteAddition(Px, Py, Qx, Qy, a, b, p):
    if None in [Px, Py]:
        return Qx, Qy
    if None in [Qx, Qy]:
        return Px, Py
    assert onCurve(Px, Py, a, b, p)
    assert onCurve(Qx, Qy, a, b, p)
    if Px == Qx and Py != Qy:
        # point1 + (-point1) = 0
        return None, None
    if Px == Qx:
        m = (3*Px**2 + a)*inverse(2*Py, p)
    else:
        m = (Py - Qy)*inverse(Px - Qx, p)
    Rx = np.mod(m**2 - Px - Qx, p)
    Ry = np.mod(-(Py + m*(Rx - Px)), p)
    assert onCurve(Rx, Ry, a, b, p)
    return Rx, Ry


def eccNegation(Px, Py, a, b, p):
    assert onCurve(Px, Py, a, b, p)
    Rx = Px
    Ry = np.mod(-Py, p)
    assert onCurve(Rx, Ry, a, b, p)
    return Rx, Ry


# EC point multiplication
def eccScalarMult(k, Px, Py, a, b, p):
    assert onCurve(Px, Py, a, b, p)
    if np.mod(k, p) == 0:
        return [], [], None, None
    if k < 0:
        # k * point = -k * (-point)
        Rx, Ry = eccNegation(Px, Py)
        return eccScalarMult(-k, Rx, Ry)
    rx, ry = Px, Py
    Rxs, Rys = [rx], [ry]
    for i in range(k-1):
        rx, ry = eccFiniteAddition(rx, ry, Px, Py, a, b, p)
        assert onCurve(rx, ry, a, b, p)
        Rxs.append(rx)
        Rys.append(ry)
    return Rxs, Rys, rx, ry


def generateGroup(Gx, Gy, a, b, p):
    Qx, Qy = Gx, Gy
    orbit = [(0, 0)]
    while (not (Qx == 0 and Qy == 0)) and (None not in [Qx, Qy]):
        point = tuple([Qx, Qy])
        orbit.append(point)
        Qx, Qy = eccFiniteAddition(Qx, Qy, Gx, Gy, a, b, p)
    return orbit


def bruteForceKey(Px, Py, pub_x, pub_y, a, b, p):
    for k in range(p):
        _, _, public_x, public_y = eccScalarMult(k, Px, Py, a, b, p)
        if public_x == pub_x and public_y == pub_y:
            return k

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 plotF(sols_x, sols_y, p,
        Raxs=[],
        Rays=[],
        highlights=[],
        annotations=[],
        title=None,
        url=False,
        filename='curve_finite_field.png'):
    fig, axs = plt.subplots(1, 1)
    axs.scatter(sols_x, sols_y, zorder=1)
    delta = 0.1
    for xs, ys, color in highlights:
        axs.scatter(xs, ys, color=color)
    for txt, Rx, Ry in annotations:
        axs.annotate(txt, (Rx - 6*delta, Ry + 3*delta))
    if None in Raxs and None in Rays:
        Raxs.remove(None)
        Rays.remove(None)
    for k in range(len(Raxs)-1):
        ox, oy = Raxs[k], Rays[k]
        dx, dy = Raxs[k+1], Rays[k+1]
        axs.arrow(ox, oy, dx-ox, dy-oy, head_width=0.2, length_includes_head=True, color='black')
    axs.set_title(title)
    axs.set_xticks(range(p))
    axs.set_yticks(range(p))
    axs.set_xlim([-1, p])
    axs.set_ylim([-1, p])
    axs.set_axisbelow(True)
    axs.grid()
    if url:
        plt.figtext(0.0, 0.01, url, rotation=0)
    plt.tight_layout()
    fig.savefig(filename)


def plotSig(es, ss, rs, r_primes, labels, n, 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.axvline(n, color='black', linestyle='dotted')
        ax.text(p - 0.5, 0.5, '$p$', va='center')
        ax.text(n - 0.5, 0.5, '$n$', 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)

'''
plt.figure()
a = [1,2,5,6,9,11,15,17,18]
  # Draw a horizontal line
plt.eventplot(a, orientation='horizontal', colors='b')
plt.axis('off')
plt.show()
'''

run.py

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


from ecc import inverse, eccContAddition, eccFiniteAddition, eccScalarMult, generateGroup, bruteForceKey
from plotting import plotF, plotSig


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


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


def sign(e, k, d, Gx, Gy, n, p=17, a=0, b=7):
    k1 = inverse(k, n)
    _, _, r, _ = eccScalarMult(k, Gx, Gy, a, b, p)
    s = np.mod(k1*(e + d*r), n)
    return s, r


def verify(e, s, r, Gx, Gy, Px, Py, n, p=17, a=0, b=7):
    s_ = inverse(s, n)
    _, _, xr1, yr1 = eccScalarMult(np.mod(e*s_, n), Gx, Gy, a, b, p)
    _, _, xr2, yr2 = eccScalarMult(np.mod(r*s_, n), Px, Py, a, b, p)
    Rx, Ry = eccFiniteAddition(xr1, yr1, xr2, yr2, a, b, p)
    if Rx == r:
        return True, Rx
    return False, Rx


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

# eliptic curve and finite field parameters
p = 17
a = 0
b = 7

# secp256k1 curve over finite field
sols_x = [0]
sols_y = [0]
points = []
for cx in range(p):
    for cy in range(p):
        if np.mod(cy**2-cx**3-cx*a-b, p) == 0:
            sols_x.append(cx)
            sols_y.append(cy)
            point = tuple([cx, cy])
            points.append(point)

# pick a generator point
Gx = sols_x[3]
Gy = sols_y[3]

# generate a cyclic group and get its order
group = generateGroup(Gx, Gy, a, b, p)
n = len(group)

# Alice key pair
d_a = 8
Pxas, Pyas, Pxa, Pya = eccScalarMult(d_a, Gx, Gy, a, b, p)

# Bob key pair
d_b = 5
Pxbs, Pybs, Pxb, Pyb = eccScalarMult(d_b, Gx, Gy, a, b, p)

annotations = [
    ('G', Gx, Gy),
    ('Alice', Pxa, Pya),
    ('Bob', Pxb, Pyb)]

highlights = [
    ([Gx], [Gy], 'tab:green'),
    ([Pxa], [Pya], 'tab:orange'),
    ([Pxb], [Pyb], 'tab:orange')]

# visualize what Alice knows
plotF(sols_x, sols_y, p,
    Raxs=Pxas,
    Rays=Pyas,
    highlights=highlights,
    annotations=annotations,
    title='What Alice knows',
    url=url,
    filename='ecdsa_knowledge_alice.png')

# visualize what Bob knows
plotF(sols_x, sols_y, p,
    Raxs=Pxbs,
    Rays=Pybs,
    highlights=highlights,
    annotations=annotations,
    title='What Bob knows',
    filename='ecdsa_knowledge_bob.png')

# visualize what eavesdropper knows
plotF(sols_x, sols_y, p,
    highlights=highlights,
    annotations=annotations,
    title='What eavesdropper knows',
    filename='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), 8, d_b, Gx, Gy, n)

# 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), s1, r1, Gx, Gy, Pxb, Pyb, n)
print('Bob\'s signature on message 1 is valid?', res)

# ...and the second message
res, rp2 = verify(hashtard(m2), s2, r2, Gx, Gy, Pxb, Pyb, n)
print('Bob\'s signature on message 2 is valid?', res)

# brute force Bob's key
d_b_f = bruteForceKey(Gx, Gy, Pxb, Pyb, a, b, p)

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

# check if it gets verified
res, rpf = verify(hashtard(m2), sf, rf, Gx, Gy, Pxb, Pyb, n)
print('Bob\'s forged signature on message 2 is valid?', res)


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

signatures.png