Tutorial covering the Eliptic Curve Digital Signature Algorithm (ECDSA) available under https://mareknarozniak.com/2021/03/16/ecdsa/
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 |
#!/bin/sh | |
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, | |
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() | |
''' |
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') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment