import random
from typing import List, Tuple
def generate_coefficients(secret: int, threshold: int) -> List[int]:
coefficients = [secret]
for _ in range(threshold - 1):
coefficients.append(random.randint(1, 256))
return coefficients
def create_shares(
secret: int, total_shares: int, threshold: int
) -> List[Tuple[int, int]]:
coefficients = generate_coefficients(secret, threshold)
shares = []
for x in range(1, total_shares + 1):
y = sum(coeff * (x**exp) for exp, coeff in enumerate(coefficients))
shares.append((x, y))
return shares
def reconstruct_secret(shares: List[Tuple[int, int]], threshold: int) -> int:
def _lagrange_interpolation(x: int, x_s: List[int], y_s: List[int]) -> int:
def _basis(j: int) -> int:
num = 1
den = 1
for m in range(len(x_s)):
if m != j:
num *= x - x_s[m]
den *= x_s[j] - x_s[m]
return num // den
result = 0
for j in range(len(y_s)):
result += y_s[j] * _basis(j)
return result
x_s, y_s = zip(*shares)
return _lagrange_interpolation(0, x_s, y_s)
if __name__ == "__main__":
secret = 2732
total_shares = 5
threshold = 2
shares = create_shares(secret, total_shares, threshold)
print("shares:", shares)
selected_shares = shares[:threshold]
print(zip(*selected_shares))
x_s, y_s = zip(*selected_shares)
print(x_s, y_s)
recovered_secret = reconstruct_secret(selected_shares, threshold)
print("Recovered Secret:", recovered_secret)
$ python3 test.py
shares: [(1, 2961), (2, 3190), (3, 3419), (4, 3648), (5, 3877)]
(1, 2) (2961, 3190)
Recovered Secret: 2732