# E_Random

Jan 21st, 2022
1,135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python3
2.
3. import collections
4. import random
5.
6. EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')
7.
8. curve = EllipticCurve(
9.     'secp256k1',
10.     # Field characteristic.
11.     p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
12.     # Curve coefficients.
13.     a=0,
14.     b=7,
15.     # Base point.
16.     g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
18.     # Subgroup order.
19.     n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
20.     # Subgroup cofactor.
21.     h=1,
22. )
23.
24.
25. # Modular arithmetic ##########################################################
26.
27. def inverse_mod(k, p):
28.     """Returns the inverse of k modulo p.
29.
30.    This function returns the only integer x such that (x * k) % p == 1.
31.
32.    k must be non-zero and p must be a prime.
33.    """
34.     if k == 0:
35.         raise ZeroDivisionError('division by zero')
36.
37.     if k < 0:
38.         # k ** -1 = p - (-k) ** -1  (mod p)
39.         return p - inverse_mod(-k, p)
40.
41.     # Extended Euclidean algorithm.
42.     s, old_s = 0, 1
43.     t, old_t = 1, 0
44.     r, old_r = p, k
45.
46.     while r != 0:
47.         quotient = old_r // r
48.         old_r, r = r, old_r - quotient * r
49.         old_s, s = s, old_s - quotient * s
50.         old_t, t = t, old_t - quotient * t
51.
52.     gcd, x, y = old_r, old_s, old_t
53.
54.     assert gcd == 1
55.     assert (k * x) % p == 1
56.
57.     return x % p
58.
59.
60. # Functions that work on curve points #########################################
61.
62. def is_on_curve(point):
63.     """Returns True if the given point lies on the elliptic curve."""
64.     if point is None:
65.         # None represents the point at infinity.
66.         return True
67.
68.     x, y = point
69.
70.     return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
71.
72.
73. def point_neg(point):
74.     """Returns -point."""
75.     assert is_on_curve(point)
76.
77.     if point is None:
78.         # -0 = 0
79.         return None
80.
81.     x, y = point
82.     result = (x, -y % curve.p)
83.
84.     assert is_on_curve(result)
85.
86.     return result
87.
88.
90.     """Returns the result of point1 + point2 according to the group law."""
91.     assert is_on_curve(point1)
92.     assert is_on_curve(point2)
93.
94.     if point1 is None:
95.         # 0 + point2 = point2
96.         return point2
97.     if point2 is None:
98.         # point1 + 0 = point1
99.         return point1
100.
101.     x1, y1 = point1
102.     x2, y2 = point2
103.
104.     if x1 == x2 and y1 != y2:
105.         # point1 + (-point1) = 0
106.         return None
107.
108.     if x1 == x2:
109.         # This is the case point1 == point2.
110.         m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
111.     else:
112.         # This is the case point1 != point2.
113.         m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
114.
115.     x3 = m * m - x1 - x2
116.     y3 = y1 + m * (x3 - x1)
117.     result = (x3 % curve.p,
118.               -y3 % curve.p)
119.
120.     assert is_on_curve(result)
121.
122.     return result
123.
124.
125. def scalar_mult(k, point):
126.     """Returns k * point computed using the double and point_add algorithm."""
127.     assert is_on_curve(point)
128.
129.     if k % curve.n == 0 or point is None:
130.         return None
131.
132.     if k < 0:
133.         # k * point = -k * (-point)
134.         return scalar_mult(-k, point_neg(point))
135.
136.     result = None
138.
139.     while k:
140.         if k & 1:
143.
144.         # Double.
146.
147.         k >>= 1
148.
149.     assert is_on_curve(result)
150.
151.     return result
152.
153.
154. # Keypair generation and ECDHE ################################################
155.
156. def make_keypair():
157.     """Generates a random private-public key pair."""
158.     private_key = random.randrange(1, curve.n)
159.     public_key = scalar_mult(private_key, curve.g)
160.
161.     return private_key, public_key
162.
163.
164. print('Curve:', curve.name)
165.
166. # Alice generates her own keypair.
167. alice_private_key, alice_public_key = make_keypair()
168. print("Alice's private key:", hex(alice_private_key))
169. print("Alice's public key: (0x{:x}, 0x{:x})".format(*alice_public_key))
170.
171. # Bob generates his own key pair.
172. bob_private_key, bob_public_key = make_keypair()
173. print("Bob's private key:", hex(bob_private_key))
174. print("Bob's public key: (0x{:x}, 0x{:x})".format(*bob_public_key))
175.
176. # Alice and Bob exchange their public keys and calculate the shared secret.
177. s1 = scalar_mult(alice_private_key, bob_public_key)
178. s2 = scalar_mult(bob_private_key, alice_public_key)
179. assert s1 == s2
180.
181. print('Shared secret: (0x{:x}, 0x{:x})'.format(*s1))
182.