Skip to content

Instantly share code, notes, and snippets.



Last active Mar 16, 2021
What would you like to do?
Tutorial covering the Eliptic Curve Digital Signature Algorithm (ECDSA) available under
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)
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)
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)
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])
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
convert ecdsa_knowledge_alice.png ecdsa_knowledge_bob.png ecdsa_knowledge_eavesdropper.png +append ecdsa_knowledge.png
import numpy as np
import matplotlib.pyplot as plt
def plotF(sols_x, sols_y, p,
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:
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_xlim([-1, p])
axs.set_ylim([-1, p])
if url:
plt.figtext(0.0, 0.01, url, rotation=0)
def plotSig(es, ss, rs, r_primes, labels, n, p,
fig, axs = plt.subplots(len(es), 1)
for ax, e, s, r, r_p, label in zip(axs, es, ss, rs, r_primes, labels):
ax.set_yticklabels(['', '$e$', '$s$', '$r$', '$r^\prime$'])
ax.set_xlim([-1, p+1])
ax.set_ylim([0, 5])
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)
a = [1,2,5,6,9,11,15,17,18]
# Draw a horizontal line
plt.eventplot(a, orientation='horizontal', colors='b')
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 = ''
# 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:
point = tuple([cx, cy])
# 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,
title='What Alice knows',
# visualize what Bob knows
plotF(sols_x, sols_y, p,
title='What Bob knows',
# visualize what eavesdropper knows
plotF(sols_x, sols_y, p,
title='What eavesdropper knows',
# 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 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,
# ...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)
[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',
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment