Instantly share code, notes, and snippets.

# marekyggdrasil/ecdsa_knowledge.png

Last active September 12, 2021 14:53
Show Gist options
• 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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/bin/sh convert ecdsa_knowledge_alice.png ecdsa_knowledge_bob.png ecdsa_knowledge_eavesdropper.png +append ecdsa_knowledge.png
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 numpy matplotlib minicurve
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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')