Skip to content

Instantly share code, notes, and snippets.

@marekyggdrasil
Last active September 12, 2021 14:53
Show Gist options
  • Save marekyggdrasil/11df1679132a36c8f3ab14a6dfcba416 to your computer and use it in GitHub Desktop.
Save marekyggdrasil/11df1679132a36c8f3ab14a6dfcba416 to your computer and use it in GitHub Desktop.
Tutorial covering the Eliptic Curve Digital Signature Algorithm (ECDSA) available under https://mareknarozniak.com/2021/03/16/ecdsa/
#!/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 plotSig(es, ss, rs, r_primes, labels, 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.text(p - 0.5, 0.5, '$p$', 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)
numpy
matplotlib
minicurve
import matplotlib.pyplot as plt
import numpy as np
import hashlib
from plotting import plotSig
from minicurve import MiniCurve as mc
from minicurve import Visualizer
from minicurve.helpers import inverse
def add_digits(num, p):
return (num - 1) % p if num > 0 else 0
def hashtard(m, p):
hash = hashlib.sha256(str.encode(m))
num = int.from_bytes(hash.digest(), 'big')
num = add_digits(num, p)
return num
def sign(e, k, d, P, p):
Q = k*P
s = np.mod(inverse(k, p)*(e + d*Q.x), p)
return s, Q.x
def verify(e, s, r, G, P, p):
Q1 = np.mod(e*inverse(s, p), p)*G
Q2 = np.mod(r*inverse(s, p), p)*P
R = Q1+Q2
if R.x == r:
return True, R.x
return False, R.x
# article URL
url = 'https://mareknarozniak.com/2021/03/16/ecdsa/'
# eliptic curve and finite field parameters
p = 13
a = 1
b = 7
# pick a generator point
G = mc(a, b, p, x=10, y=4, label='G', color='tab:green', tracing=True)
# Alice key pair
d_a = 8
P_a = d_a*G
P_a.setColor('tab:orange')
P_a.setLabel('Alice')
# Bob key pair
d_b = 5
P_b = d_b*G
P_b.setColor('tab:orange')
P_b.setLabel('Bob')
# visualize what Alice knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = True
P_b.tracing = False
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What Alice knows')
plt.figtext(0.0, 0.01, url, rotation=0)
vis.plot('ecdsa_knowledge_alice.png')
# visualize what Bob knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = False
P_b.tracing = True
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What Bob knows')
vis.plot('ecdsa_knowledge_bob.png')
# visualize what eavesdropper knows
vis = Visualizer(a, b, p)
vis.makeField()
P_a.tracing = False
P_b.tracing = False
vis.points = [G, P_a, P_b]
vis.generatePlot(title='What eavesdropper knows')
vis.plot('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, p), 3, d_b, G, p)
# 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, p), s1, r1, G, P_b, p)
print('Bob\'s signature on message 1 is valid?', res)
# ...and the second message
res, rp2 = verify(hashtard(m2, p), s2, r2, G, P_b, p)
print('Bob\'s signature on message 2 is valid?', res)
# brute force Bob's key
d_b_f = mc.bruteForceKey(G.x, G.y, P_b.x, P_b.y, a, b, p)
# forge his signature under second message using brute forced key
sf, rf = sign(hashtard(m2, p), 8, d_b_f, G, p)
# check if it gets verified
res, rpf = verify(hashtard(m2, p), sf, rf, G, P_b, p)
print('Bob\'s forged signature on message 2 is valid?', res)
plotSig(
[hashtard(m1, p), hashtard(m2, p), hashtard(m2, p)],
[s1, s2, sf],
[r1, r2, rf],
[rp1, rp2, rpf],
['sig 1', 'sig 2', 'sig 2 (forged)'], 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