Advertisement
skip420

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,
  17.        0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
  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.  
  89. def point_add(point1, point2):
  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
  137.     addend = point
  138.  
  139.     while k:
  140.         if k & 1:
  141.             # Add.
  142.             result = point_add(result, addend)
  143.  
  144.         # Double.
  145.         addend = point_add(addend, addend)
  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.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement