2.2 Shamir 门限秘密分享：多项式取点
2.2 Shamir 门限秘密分享：多项式取点
本节摘要：Shamir 方案用一个 t-1 次多项式把秘密变成 n 个点，任意 t 个点可唯一还原多项式、t-1 个点在信息论上推不出任何东西。本节用秘密 42、门限 3、五方参与的完整演算展示取点与插值，并逐条验证门限性质。
核心概念
加法分享的规则是"n 份里凑齐全部 n 份才能还原"，缺点是任何一份丢失都全盘皆输。现实需求常常是"5 个人保管，任意 3 人在场就能开，少于 3 人开不了"——这就是门限（threshold）语义。Shamir 1979 年的方案漂亮在哪里：把秘密藏进多项式的常数项。
分发。 想分享秘密 S、门限为 t：随机选一个 t-1 次多项式 P(x) = S + a1·x + a2·x² + … + a(t-1)·x^(t-1)，其中系数 a1 到 a(t-1) 在模 p 下随机抽取，S 是常数项。给第 i 个参与方的份额就是曲线上的一个点 (i, P(i) mod p)。直觉：两点定一条直线，三点定一条抛物线——t 个点唯一确定 t-1 次多项式，常数项自然到手。
完整演算。 取 p = 97，秘密 S = 42，门限 t = 3，即用二次多项式。随机抽 a1 = 7、a2 = 2，得 P(x) = 42 + 7x + 2x² mod 97。给五个参与方取点：
P(1) = 42 + 7 + 2 = 51 P(2) = 42 + 14 + 8 = 64 P(3) = 42 + 21 + 18 = 81 P(4) = 42 + 28 + 32 = 102 mod 97 = 5 P(5) = 42 + 35 + 50 = 127 mod 97 = 30
于是五份份额为 (1,51)、(2,64)、(3,81)、(4,5)、(5,30)。重组：任取三份做拉格朗日插值。取 (1,51)、(3,81)、(5,30) 三点，还原 P(0) 的公式为各 y 值乘上对应的拉格朗日基函数在 0 处的取值再求和：
L1(0) = (0-3)(0-5) / (1-3)(1-5) = 15 / 8 ≡ 15 * 85 = 1275 mod 97 = 14 L2(0) = (0-1)(0-5) / (3-1)(3-5) = 5 / -4 ≡ 5 * 72 = 360 mod 97 = 69 L3(0) = (0-1)(0-3) / (5-1)(5-3) = 3 / 8 ≡ 3 * 85 = 255 mod 97 = 61 S = 51*14 + 81*69 + 30*61 = 714 + 5589 + 1830 = 8133 mod 97 = 42
（其中 8 的逆元是 85：8×85 = 680 = 97×7 + 1；-4 的逆元是 72。42 稳稳回来了。）
图：Shamir 门限的取点与插值
为什么 t-1 份绝对安全
这是本节最值得吃透的论证，也是"概念筑基"该有的深度。假设只拿到 t-1 = 2 个点，比如 (1,51) 和 (2,64)。过这两点的二次多项式有无穷多个（模 97 下恰有 97 个）：对任何猜测的截距 S'，都存在唯一一条二次曲线同时穿过这两点和 (0, S')。也就是说，每一个候选秘密都恰好对应一种系数配置，两种假设下的概率分布完全相同——份额没有提供任何区分秘密的证据。这与加法分享里"均匀随机掩码"是同一种安全哲学：随机性的维度抹平了所有假设的似然。
用代码验证 t-2 门限下的不可区分性（概念演示）：
P = 97 S, T = 42, 3 # 秘密与门限 coeff = [7, 2] # t-1 = 2 个随机系数 pts = [(i, (S + coeff[0]*i + coeff[1]*i*i) % P) for i in range(1, 6)] def lagrange0(subset): # 用子集还原 P(0) total = 0 for j, (xj, yj) in enumerate(subset): num = den = 1 for m, (xm, _) in enumerate(subset): if m != j: num = num * (0 - xm) % P den = den * (xj - xm) % P total = (total + yj * num * pow(den, -1, P)) % P return total assert lagrange0(pts[:3]) == 42 # 三份 → 精确还原 # 两份 → 对每个候选秘密都存在一致的假想多项式，无信息
工程实践要点
门限选多少？ t 越大可用性越差（要凑更多人）而安全性越强；金融门限签名常取"n 中 2/3"或"n 中过半"。份额 x 坐标不能取 0（0 号点是秘密本身），也不能重复（重复点会降低有效门限）。多项式运算全程在域上——这也是素数 p 必须是素数的原因：模合数下逆元可能不存在，插值会失效。若你在环（如模 2^64）上做 Shamir，要么放弃插值、要么换用配套的打包技巧，这是 SPDZ 实现里的实际考量（5.1 节会回到这一点）。
💡 关键直觉：Shamir 把"凑几个人"翻译成了"几次曲线"——代数对象的自由度就是安全性的度量。自由度还剩多少，攻击者就还差多少信息。
本节要点：t-1 次多项式的常数项藏秘密；t 点唯一插值、t-1 点信息论安全；全程域运算、份额永不还原是 MPC 里的常态用法。下一节回到运算问题：多项式点上的乘法怎么在不还原秘密的前提下进行。
门限参数的现实权衡
t 与 n 的选取是业务决策不是技术决策。密钥托管场景的通行配置是"n 中三分之二"：五方保管、三方开门，兼顾可用性与合谋成本。跨机构联合计算的另一种选择是"全体到场"，它事实上退化为加法分享——联合计算本来就要全员在线，门限的可用性红利用不上；此时 Shamir 的价值在别处：份额能直接参与域上运算，且增发新点就能吸纳新参与方，无需重拆秘密。
另一个常被忽略的参数是素数 p 的规模。教学用 97，生产按安全强度选大素数，或直接换到环上（5.1 节）。p 太小会遭遇暴力枚举——要分清两件事：门限的信息论安全说的是"份额不泄密"，挡不住对手在过小的秘密空间里直接猜。参数表里的每个数字都要问一句"它防的是哪种攻击"，这句话是密码工程与密码科普的分界线。
Shamir 的两个高阶用途预告
门限分享的想象力远不止"凑人头开保险箱"，预告两个后续会用到的进阶形态。主动式份额更新：参与方定期互相交换"份额的增量"，多项式常数项不变而各点值全部换新——已泄露的旧份额瞬间作废，这套机制（ proactive secret sharing）是长期密钥保护的标准配置，也是门限签名服务（7.5 节）运维清单里"份额轮换"的技术底座。可验证秘密分享（VSS）：分发方可能给某人发错误份额（无论是作恶还是出错），VSS 让每个参与方都能验证自己拿到的点确实在原多项式上，验证材料用承诺技术生成而不泄露多项式本身——它是多方协议里"分发环节可信"的标准答案，恶意模型（第 5 章）的各种校验思想与它同源。
这两个进阶形态指向同一个观察：Shamir 方案的真正遗产是把"信任的门槛"变成了可计算的参数——几个人、几份、谁能验证、如何更新，全部落入代数结构。1980 年代这个方案诞生时，分布式系统与密码学还是两个圈子；今天它同时是密钥管理、共识协议、MPC 三大领域的地基构件，一篇十页的论文撬动三个行业，这种杠杆率在整个计算机科学里都属罕见。
读到这里建议停一停，合上书把二次多项式那条曲线在纸上画一遍：五个点、任意三点成线、两点悬空。这个画面会在第 5 章的算术运算、第 7 章的门限签名里反复回来——它值得成为你脑子里最熟悉的一张图。