数学建模¶

任课教师：谈之奕
学期：2026-2027 秋冬学期

春一周¶

密码学-秘密共享¶

Shamir 门限机制（t,n）

Shamir 门限机制是 Adi Shamir 于 1979 年提出的一种秘密共享（Secret Sharing）方案，核心思想是：把一个秘密拆成 n 份分片，交给 n 个人，任意 t 个或更多人合作才能还原秘密，而少于 t 个人（哪怕知道 t−1 份）对秘密一无所知。

数学原理¶

核心工具是多项式插值（拉格朗日插值）。在有限域 GF(p) 上：

构造多项式：设秘密为 s，随机选取系数 a₁, a₂, …, a_{t−1}，构造 t−1 次多项式：

\[f(x) = s + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1}\]

常数项 f(0) = s 就是秘密本身，其余系数完全随机。

生成分片：计算 n 个点 (x_i, y_i) = (i, f(i))，i = 1, 2, …, n，每个点交给一个参与者。
还原秘密：任意 t 个分片持有者把他们的点代入拉格朗日插值公式：

\[f(0) = \sum_{i=1}^{t} y_i \prod_{j \neq i} \frac{x_j}{x_j - x_i}\]

即可唯一求出 f(0)，即秘密 s。

t−1 个点只能约束一个 t−1 次多项式的部分自由度，穿过这 t−1 个点的多项式有无穷多个（在有限域上也有 p 种），f(0) 可以是域里的任何值且概率均等。这就是信息论安全性（完美保密）：不依赖计算困难假设，而是从根本上没有泄露任何信息——这与 RSA 这类"难以破解但理论上可破解"的密码体制有本质区别。