在前面的章节中，我们已经分析了分组密码的加密算法和分组模式，这些都是对称加密算法的核心内容。然而，在实际应用中，我们经常需要在多个参与者之间共享一个秘密，而不希望任何单一参与者能够独自获得这个秘密或者一旦有一个人背叛就无法恢复秘密。这就引入了门限秘密共享算法（Threshold Secret Sharing），其中最著名的就是 Shamir 门限秘密共享算法。

Shamir 门限秘密共享算法是一种基于多项式插值的秘密共享方案，它允许将一个秘密分成 $n$ 份，并且只要有 $k$ 份（$k \leq n$）就可以恢复出原始的秘密，而任何少于 $k$ 份的信息都无法获得任何关于秘密的线索。这种算法在分布式系统、密钥管理和安全多方计算等领域有着广泛的应用。

Shamir 门限秘密共享算法的数学原理 😇

Shamir 门限秘密共享算法加密

首先，我们来思考一个问题，对于一个 $k$ 次多项式 $F(x) = a_0 + a_1 x + a_2 x^2 + … + a_k x^k$，我们要求出 $F(0)$ 的值，也就是多项式的常数项 $a_0$，我们需要知道多少个点 $(x_i, F(x_i))$ 才能唯一确定这个多项式呢？

这个答案实际上是多项式唯一确定性定理（拉格朗日插值定理），它告诉我们，要唯一确定一个 $k$ 次多项式，我们至少需要知道 $k+1$ 个不同的点。这个定理是 Shamir 门限秘密共享算法的数学基础，但是我们在这里不详细展开证明，只要知道就好了。为了方便理解，不妨想一下两点确定一条直线。

因此，在 Shamir 门限秘密共享算法中，我们将秘密 $s$ 作为多项式 $F(x)$ 的常数项，即 $F(0) = s$，然后随机选择 $k$ 个系数 $a_1, a_2, …, a_k$ 来构造一个 $k$ 次多项式。接下来，我们选择 $n$ 个不同的非零点 $x_1, x_2, …, x_n$（$k \leq n$），为了进一步增大安全性，我们将数据放在有限域 $\mathbb{F}_p$ 中使点离散化，计算出对应的 $F(x_i)$，将这些点 $(x_i, F(x_i))$ 分发给参与者。

Shamir 门限秘密共享算法解密

恢复我们使用拉格朗日插值法来计算 $F(0)$，也就是秘密 $s$。首先计算基多项式（这里的除法会转化为模逆元）：

我们发现，$L_i(i) = 1$，而 $L_i(j) = 0$（$j \neq i$），因此我们可以通过以下公式来恢复函数 $F$：

这样构造会发现，将所有的 $x_i$ 代入上式，只有当 $i = j$ 时才会有贡献，刚好满足所有条件，因此最终我们可以得到这就是原函数，所以 $F(0) = s$。

Shamir 门限秘密共享算法实现 🥰

接下来，我们来看看 Shamir 门限秘密共享算法的一个简单实现示例：

from sage.all import *
from Crypto.Util.number import *
import random

# 加密部分

# 1. 设定参数与有限域
# 选择一个大素数 p，建立有限域 GF(p) 保证离散化和安全性
p = random_prime(2^128)
F = GF(p)

# 2. 秘密与参与者设定
secret = b'our_key'
secret_value = bytes_to_long(secret)  # 需要保护的秘密 s
s = F(secret_value)

k = 3  # 多项式的次数 k，由于次数为 k，需要 k+1 个点才能还原多项式
n = 6  # 分发给 n 个参与者

print(f"设定的素数 p: {p}")
print(f"原秘密 s (F(0)): {s}")

# 3. 构造 k 次多项式 F(x) = s + a_1*x + a_2*x^2 + ... + a_k*x^k
# 常数项为 s，随机选择剩余的 k 个系数
coeffs = [s] + [F.random_element() for _ in range(k)]
R.<x> = PolynomialRing(F)
F_poly = R(coeffs)

print(f"构造的多项式 F(x): {F_poly}")

# 4. 生成 n 个份额 (x_i, F(x_i))
# 这里为了简便，选取 x_i = 1, 2, ..., n, 实际上可以乱序
shares = []
for i in range(1, n + 1):
    x_i = F(i)
    y_i = F_poly(x_i)
    shares.append((x_i, y_i))
    print(f"参与者 {i} 取得的份额: (x={x_i}, y={y_i})")

# 解密部分

# 1. 收集份额
# 重建需要 k+1 个份额，这里我们随机抽取 k+1 个参与者的份额
threshold = k + 1
collected_shares = random.sample(shares, threshold)

print(f"收集到的 {threshold} 个份额用于解密:")
for share in collected_shares:
    print(f"(x={share[0]}, y={share[1]})")

# 2. 拉格朗日插值法恢复 F(0) (即原秘密 s)
# L_i(0) = ∏(0 - x_j) / (x_i - x_j) (j ≠ i)
recovered_s = F(0)

for i in range(threshold):
    x_i, y_i = collected_shares[i]

    # 计算对应的拉格朗日基多项式在 x=0 处的值 L_i(0)
    L_i_0 = F(1)
    for j in range(threshold):
        if i != j:
            x_j, y_j = collected_shares[j]
            # 在 GF(p) 上的四则运算会自动进行取模和求模逆元
            L_i_0 *= (- x_j) / (x_i - x_j)

    # f(0) = Σ y_i * L_i(0)
    recovered_s += y_i * L_i_0

# 3. 校验恢复结果
if recovered_s == s:
    print("解密成功！秘密完好无损地被恢复了。")
    print(f"秘密是 {long_to_bytes(int(recovered_s))} !!!")
else:
    print("解密失败！")

有了这个实现，我们就可以在多个参与者之间安全地共享一个秘密，并且只有当足够数量的参与者合作时才能恢复出这个秘密。当然，我们也发现用这个算法直接加密信息会导致 $s$ 的值过大，因此我们通常会先使用对称加密算法（如 AES）加密我们的数据，然后将 AES 的密钥作为秘密 $s$ 来进行共享，这样既保证了安全性又提高了效率。

上一章：加解密模式分析 - 分组模式解析 👈
下一章：
回到开始：关于我 👈

相关链接：