Shamir 秘密共享：多项式数学

Shamir 秘密共享（1979）将秘密编码为有限域上随机的 k-1 次多项式的 y 轴截距（f(0)）。任意 k 个点都能唯一确定该多项式（拉格朗日插值）；少于 k 个点则不会泄露任何信息。

要在 n 个参与方之间以阈值 k 共享秘密 S：选择一个大于 S 和 n 的素数 p。选取随机系数 a_1, ..., a_{k-1}。定义 f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p)。参与方 i 收到份额 (i, f(i))。

秘密 S=7，p=17，k=2（线性多项式）。选择 a_1=3。f(x)=7+3x mod 17。份额：(1,10)、(2,13)、(3,16)。任意两个点都能确定这条直线。f(0)=7。单独一个点：可能存在无穷多条直线，因此关于 S 的信息为零。

给定 k 个点 (x_1,y_1),...,(x_k,y_k)，使用拉格朗日公式重构 f(0)：S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p。所有运算都是模运算。不使用浮点数——在有限域上进行精确重构。

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

对于 k-1 个份额，对于每个可能的秘密值 S，都恰好存在一个穿过这 k-1 个点的 k-1 次多项式。因此，知道 k-1 个份额时，S 在 [0, p-1] 中的每个值都具有相同的可能性——不会泄露任何信息。

p 必须大于秘密值和 n。常见选择是 p = 2^127-1（梅森素数），用于 128 位秘密值。这样可以确保所有份额都能放入 128 位，并且运算高效。对于 512 位秘密值，也可以使用 p=2^521-1。

基本 SSS 不提供份额完整性保护：恶意参与者可以提交错误的份额，导致秘密重构错误。Feldman VSS（可验证秘密共享）发布承诺 g^{a_i} mod p，使份额能够在不泄露多项式的情况下得到验证。

可以定期刷新份额：生成一个具有相同秘密值 S 的新多项式，重新分发新份额，使旧份额失效。攻击者在刷新后攻破某位参与者时，获取到的旧份额也没有用处。这种方法用于长期运行的密钥管理系统。

ssss（Linux 命令行工具）、python-secret-sharing，hashicorp/vault 使用 SSS 实现其密封机制，Trezor 硬件钱包使用 SSS 备份钱包种子（SLIP-39）。它们都在大素数域上运行。

SSS 要求由受信任的分发者生成并分发份额（分发者知道秘密）。没有分发者的场景需要 DKG（分布式密钥生成）。重构会将秘密暴露给持有 k 个份额的任何人——MPC 或阈值签名可以消除这一问题。

在 Shamir 的 (3,5) 秘密共享中，重构秘密至少需要多少个份额？

Shamir 的 SSS 将秘密编码为多项式的 y 截距。拉格朗日插值可以从 k 个份额中恢复秘密。少于 k 个份额时，可实现完美的信息论安全性。下一节：可视化秘密共享和加法秘密共享。