shamir门限方案python实现

Shamir门限方案是一种秘密分享方案，它可以将一个秘密S分成n个部分，其中只有k个部分可以重组得到原始秘密，k的值小于n。下面是Shamir门限方案的Python实现：

import random

def generate_shares(s, k, n, p):
    """
    生成Shamir门限方案的秘密分享
    :param s: 原始秘密
    :param k: 重组秘密所需的部分数量
    :param n: 总的分享数量
    :param p: 素数
    :return: 一个包含n个元素的列表，其中每个元素都是一个二元组(x, y)，表示(x, f(x))的点
    """
    if k > n:
        raise ValueError("k must be less than or equal to n")

    # 生成多项式f(x) = a0 + a1*x + ... + ak-1*x^(k-1)，其中a0 = s
    coefficients = [s] + [random.randint(1, p - 1) for _ in range(k - 1)]

    def f(x):
        """
        计算f(x)
        """
        result = 0
        for i, coeff in enumerate(coefficients):
            result += coeff * pow(x, i, p)
        return result % p

    # 生成n个分享
    points = [(i, f(i)) for i in range(1, n + 1)]
    return points

def recover_secret(shares):
    """
    恢复秘密
    :param shares: 一个包含k个或更多元素的列表，其中每个元素都是一个二元组(x, y)，表示(x, f(x))的点
    :return: 原始秘密
    """
    k = len(shares)
    if k == 0:
        raise ValueError("shares list must not be empty")

    # 计算所有可能的多项式的值
    p = shares[0][1].bit_length() - 1
    x_values, y_values = zip(*shares)
    secrets = []
    for i in range(k):
        xi, yi = shares[i]
        numerator = denominator = 1
        for j in range(k):
            if i == j:
                continue
            xj, yj = shares[j]
            numerator *= -xj
            denominator *= xi - xj
        coefficient = numerator * pow(denominator, -1, p) % p
        secrets.append((coefficient, yi))

    # 求出f(0)，即原始秘密
    result = 0
    for coeff, yi in secrets:
        result += coeff * yi
    return result % p

在这个实现中，`generate_shares`函数接受一个原始秘密`s`，需要重组秘密的部分数量`k`，总分享数量`n`和一个素数`p`，然后返回一个包含n个二元组的列表，其中每个二元组表示一个分享点(x, f(x))。`recover_secret`函数接受一个包含k个或更多元素的分享点列表，然后返回原始秘密。