itoonx · December 15, 2022 09:33 · Dec 15, 2022 · Dec 15, 2022
diff --git a/gistfile1.txt → Shamir_Secret_Sharing_Scheme.py b/gistfile1.txt → Shamir_Secret_Sharing_Scheme.py
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -0,0 +1,69 @@
+import random
+
+# Returns a random prime number with n bits
+def generate_prime(n):
+  while True:
+    p = random.getrandbits(n)
+    if is_prime(p):
+      return p
+
+# Returns the result of evaluating a polynomial with coefficients
+# `coefficients` at point `x` using the Horner scheme
+def horner(coefficients, x):
+  result = 0
+  for coefficient in coefficients:
+    result = result * x + coefficient
+  return result
+
+# Returns the result of evaluating a polynomial with coefficients
+# `coefficients` at point `x` using the Lagrange interpolation
+# method
+def lagrange_interpolate(coefficients, x):
+  result = 0
+  for i, coefficient in enumerate(coefficients):
+    numerator = coefficient
+    denominator = 1
+    for j, coefficient2 in enumerate(coefficients):
+      if i != j:
+        numerator = numerator * (x - j)
+        denominator = denominator * (i - j)
+    result += numerator / denominator
+  return result
+
+# Generate a random polynomial with the given degree and secret
+# coefficient
+def generate_polynomial(degree, secret):
+  coefficients = [secret] + [random.randint(1, degree) for _ in range(degree)]
+  return coefficients
+
+# Generate a set of shares using the Shamir Secret Sharing
+# scheme with the given polynomial and number of shares
+def generate_shares(polynomial, shares):
+  points = []
+  for i in range(1, shares + 1):
+    points.append((i, horner(polynomial, i)))
+  return points
+
+# Recover the secret using the given shares and prime
+def recover_secret(shares, prime):
+  result = 0
+  for i, share in enumerate(shares):
+    numerator = share[1]
+    denominator = 1
+    for j, share2 in enumerate(shares):
+      if i != j:
+        numerator = numerator * (0 - share2[0])
+        denominator = denominator * (share[0] - share2[0])
+    result += numerator / denominator
+  return result % prime
+
+# Tests the Shamir Secret Sharing scheme
+def test_shamir():
+  prime = generate_prime(10)
+  secret = random.randint(1, prime - 1)
+  polynomial = generate_polynomial(3, secret)
+  shares = generate_shares(polynomial, 5)
+  recovered = recover_secret(shares, prime)
+  assert secret == recovered, f"{secret} != {recovered}"
+
+test_shamir()
No results found