Tutorial covering the concept of Elliptic Curve Cryptography and Diffie-Hellman Key Exchange, tutorial available under https://mareknarozniak.com/2020/11/30/ecdh/
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): | |
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 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 |
import numpy as np | |
import matplotlib.pyplot as plt | |
def plotR(a, b, | |
line=None, | |
vert=None, | |
highlights=[], | |
annotations=[], | |
title=None, | |
url=False, | |
filename='curve.png'): | |
# calculate the curve | |
y, x = np.ogrid[-5:5:200j, -5:5:200j] | |
# elliptic curve over real space | |
cont = np.power(y, 2.)-np.power(x, 3.)-x*a-b | |
# plot it | |
fig, axs = plt.subplots(1, 1) | |
if vert is not None: | |
axs.axvline(x=vert, color='black', linestyle='--') | |
axs.contour(x.ravel(), y.ravel(), cont, [0], colors='tab:blue') | |
if line is not None: | |
m, y0 = line | |
Y = m*x + y0 | |
axs.plot(x.ravel(), Y[0], color='tab:orange') | |
for xs, ys, color in highlights: | |
axs.scatter(xs, ys, color=color, zorder=3) | |
delta = 0.1 | |
for txt, Rx, Ry in annotations: | |
axs.annotate(txt, (Rx+delta, Ry+delta), zorder=3) | |
axs.set_title(title) | |
axs.set_xlim([-5., 5.]) | |
axs.set_ylim([-5., 5.]) | |
axs.set_axisbelow(True) | |
axs.grid() | |
if url: | |
plt.figtext(0.0, 0.01, 'https://mareknarozniak.com/2020/11/30/ecdh/', rotation=0) | |
plt.tight_layout() | |
fig.savefig(filename) | |
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 i in range(p): | |
axs.annotate(chr(i + 65), (sols_x[i] + delta, sols_y[i] + delta)) | |
for xs, ys, color in highlights: | |
axs.scatter(xs, ys, color=color) | |
for txt, Rx, Ry in annotations: | |
axs.annotate(txt, (Rx - 4*delta, Ry - 6*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, 'https://mareknarozniak.com/2020/11/30/ecdh/', rotation=0) | |
plt.tight_layout() | |
fig.savefig(filename) |
import matplotlib.pyplot as plt | |
import numpy as np | |
from ecc import eccContAddition, eccFiniteAddition, eccScalarMult, bruteForceKey | |
from plotting import plotR, plotF | |
curves = [ | |
('secp256k1, $a=0,b=7$', 0, 7, 1.3, 2.1), | |
('$a=-3,b=1$', -3, 1, -1.5, 2.1), | |
('$a=-3,b=1$', -3, 8, -2., 2.1)] | |
for i, (title, a, b, Px, Qx) in enumerate(curves): | |
Py = np.sqrt(np.power(Px, 3.)+Px*a+b) | |
Qy = np.sqrt(np.power(Qx, 3.)+Qx*a+b) | |
Rx, Ry, m = eccContAddition(Px, Py, Qx, Qy, a, b) | |
Y0 = Py-m*Px | |
url = i == 0 | |
highlights = [ | |
([Px, Qx, Rx, Rx], [Py, Qy, Ry, -Ry], 'tab:orange')] | |
annotations = [ | |
('P', Px, Py), | |
('Q', Qx, Qy), | |
('-R', Rx, Ry), | |
('R', Rx, -Ry)] | |
plotR(a, b, | |
title=title, | |
line=(m, Y0), | |
vert=Rx, | |
highlights=highlights, | |
annotations=annotations, | |
url=url, | |
filename='ecdh_curve_{0}.png'.format(str(i))) | |
a = 0 | |
b = 7 | |
p = 17 | |
plotR(a, b, | |
title='secp256k1, $a=0,b=7$', | |
url=True, | |
filename='ecdh_real.png'.format(str(i))) | |
# secp256k1 curve over finite field | |
sols_x = [] | |
sols_y = [] | |
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) | |
plotF(sols_x, sols_y, p, | |
title='secp256k1, $a=0,b=7$', | |
filename='ecdh_finite.png') | |
idx_p = 3 | |
idx_q = 5 | |
Px, Py, Qx, Qy = sols_x[idx_p], sols_y[idx_p], sols_x[idx_q], sols_y[idx_q] | |
Rx, Ry = eccFiniteAddition(Px, Py, Qx, Qy, a, b, p) | |
highlights = [ | |
([Px, Qx, Rx], [Py, Qy, Ry], 'tab:orange')] | |
annotations = [ | |
('(P)', Px, Py), | |
('(Q)', Qx, Qy), | |
('(R)', Rx, Ry)] | |
plotF(sols_x, sols_y, p, | |
title=r'$D+F=B$', | |
highlights=highlights, | |
annotations=annotations, | |
filename='ecdh_discrete_addition.png') | |
generator = 16 | |
Px, Py = sols_x[generator], sols_y[generator] | |
private_keys = [4, 13] | |
names = ['alice', 'bob'] | |
communicate_with = [1, 0] | |
public_keys = [] | |
for i, (private_key, name) in enumerate(zip(private_keys, names)): | |
Raxs, Rays, public_x, public_y = eccScalarMult(private_key, Px, Py, a, b, p) | |
public_key = (public_x, public_y) | |
public_keys.append(public_key) | |
highlights = [ | |
([Px], [Py], 'tab:green'), | |
([public_x], [public_y], 'tab:orange')] | |
url = i == 0 | |
plotF(sols_x, sols_y, p, | |
Raxs=Raxs, | |
Rays=Rays, | |
highlights=highlights, | |
title='{0} Public Key'.format(name.capitalize()), | |
url=url, | |
filename='ecdh_public_key_{0}.png'.format(name)) | |
# Diffie-Hellman Key Exchange | |
for private_key, name, partner in zip(private_keys, names, communicate_with): | |
public_x, public_y = public_keys[partner] | |
Raxs, Rays, secret_x, secret_y = eccScalarMult(private_key, public_x, public_y, a, b, p) | |
highlights = [ | |
([public_x], [public_y], 'tab:green'), | |
([secret_x], [secret_y], 'tab:orange')] | |
url = i == 0 | |
plotF(sols_x, sols_y, p, | |
Raxs=Raxs, | |
Rays=Rays, | |
highlights=highlights, | |
title='{0} Cipher'.format(name.capitalize()), | |
url=url, | |
filename='ecdh_cipher_{0}.png'.format(name)) | |
# break the Bob key! | |
Px, Py = sols_x[generator], sols_y[generator] | |
pub_x, pub_y = public_keys[1] | |
k = bruteForceKey(Px, Py, pub_x, pub_y, a, b, p) | |
print('Bob private key: ', k) | |
# break the Alice key! | |
pub_x, pub_y = public_keys[0] | |
k = bruteForceKey(Px, Py, pub_x, pub_y, a, b, p) | |
print('Alice private key: ', k) | |
# convert ecdh_curve_0.png ecdh_curve_1.png ecdh_curve_2.png +append ecdh_curve.png | |
# convert ecdh_public_key_alice.png ecdh_public_key_bob.png +append ecdh_public_key.png | |
# convert ecdh_cipher_alice.png ecdh_cipher_bob.png +append ecdh_cipher.png | |
# convert ecdh_real.png ecdh_finite.png +append ecdh.png |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment