Skip to content

Instantly share code, notes, and snippets.

@marekyggdrasil

marekyggdrasil/ecc.py

Last active Mar 16, 2021
Embed
What would you like to do?
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