### Shamir (k,n) 门限方案的 Python 实现 Shamir 的秘密共享算法是一种用于将机密数据分割成多个部分的方法，这些部分可以独立分发给不同的参与者。只有当至少 k 个参与者的份额被组合在一起时才能重建原始的秘密。 下面是一个简单的 Python 实现： ```python import numpy as np from sympy import mod_inverse, randprime def generate_shares(secret, n, k, prime=None): """ 将秘密分成 n 份，其中任意 k 份能够恢复原秘密 参数: secret : int - 要分享的秘密数值 n : int - 总共产生的份额数量 k : int - 恢复所需最少份额数 prime : int - 可选的大素数，默认自动生成 返回值: list of tuples [(index, share)] 表示第 index 位上的份额 value """ if not isinstance(secret, int) or secret < 0: raise ValueError("Secret must be a non-negative integer") if k > n or n <= 0 or k <= 0: raise ValueError(f"Invalid values for n={n} and/or k={k}") # Choose large enough safe prime p such that all operations are within field F_p if prime is None: while True: prime_candidate = randprime(2 ** 31, 2 ** 32) if pow(prime_candidate, 1, 4 * (secret + 1)) != 0: break prime = prime_candidate coefficients = [secret] + [np.random.randint(0, prime) for _ in range(k - 1)] shares = [] for i in range(1, n + 1): xi = i yi = sum(coefficients[j] * pow(xi, j, prime) % prime for j in range(len(coefficients))) % prime shares.append((xi, yi)) return shares def reconstruct_secret(shares, prime=None): """通过拉格朗日插值法重构秘密""" if len(set([s[0] for s in shares])) != len(shares): raise ValueError('Duplicate indices found') if prime is None: max_val = max(max(s) for s in shares) prime = next_prime(max_val) result = 0 for j in range(len(shares)): xj, yj = shares[j] numerator, denominator = 1, 1 for m in range(len(shares)): if m == j: continue xm = shares[m][0] numerator *= (-xm) % prime denominator *= ((xj - xm) % prime) lagrange_term = (numerator * mod_inverse(denominator, prime)) % prime result += yj * lagrange_term return result % prime ``` 此代码实现了两个主要功能函数 `generate_shares` 和 `reconstruct_secret`. 前者负责创建份额而后者则用来从足够的份额中重新计算出最初的秘密[^1].