📚 课程目录第4章密钥分享的生成与重构

4. 密钥分享的生成与重构：有限域运算实现

上节课我们聊了 Shamir 密钥共享的基本思想，说白了就是把一个秘密切成碎片，分给一群人，凑够指定人数才能复原。今天咱们要把这个想法落地——不过不是在整数世界里瞎搞，而是要在有限域里做运算。为什么？因为整数除来除去容易出分数，分数一出来精度就完蛋，而且整数环没有“唯一逆元”这种好东西。

我最早做这个的时候，直接拿普通整数拉格朗日插值，结果算出来一堆分数，用浮点数存，最后拼出来的秘密差了那么一点点。嗯，后来才意识到，必须用有限域。

有限域：为什么是它？

有限域，也叫伽罗瓦域，记作 GF(p) 或 GF(2^k)。这里 p 是个素数，域里的元素就是 0 到 p-1 的整数，加减乘除全都在模 p 下做。
核心好处：每个非零元素都有逆元，除法不再是问题。而且域是封闭的，结果永远落在 0..p-1 里，不会跑偏。

我一般选 GF(2^8) 或 GF(p) 这类比较大的素数域。比如秘密是 128 位的整数，那就选个比 2^128 大的素数，比如 p = 2^128 – 159（一个常用的大素数）。

选择素数 p 时注意：p 必须大于你要分享的秘密值，同时要大于所有子密钥可能取到的最大值。否则重构时会取模出错。

密钥生成：构造多项式

假设我们想实现 (k, n) 门限。秘密是 S，在域内是个整数。我随机选 k-1 个系数 a₁, a₂, ..., aₖ₋₁，每个系数都是从域里均匀随机取的。然后构造多项式：

f(x) = S + a₁·x + a₂·x² + ... + aₖ₋₁·x^(k-1)   (所有运算都在 GF(p) 下)

然后取 n 个不同的 x 值（比如 1, 2, 3, ..., n），算出 f(1), f(2), ..., f(n)，这就是 n 份子密钥。
注意：x 值本身是公开的，R 或 ID 编号；真正保密的是 f(x) 的值。谁拿到了一份子密钥 (xᵢ, yᵢ)，就相当于多项式上的一个点。

参数	含义	生成方式
S	原始秘密	直接给出
k	门限值	需求指定
a₁..aₖ₋₁	随机系数	域内均匀随机选取
xᵢ	参与者标识	1..n 或唯一编号
yᵢ = f(xᵢ)	子密钥碎片	多项式求值

  我在项目里踩过一个坑：随机系数一定要足够随机，不能用线性同余那种弱随机器生成系数，否则攻击者拿到少量子密钥就能反推系数。建议用密码学安全的随机数生成器。

密钥重构：拉格朗日插值

当 k 个参与者拿出自己的子密钥 (xᵢ, yᵢ)，我们就能用拉格朗日插值公式恢复出多项式，进而得到秘密 S = f(0)。公式如下：

S = Σ [ yⱼ · Π (0 – xₘ) / (xⱼ – xₘ) ]   对所有 j 求和，m ≠ j

所有运算都在 GF(p) 下。这里面除法就是乘以分母的模逆元。所以我们需要一个能计算模逆元的函数（扩展欧几里得算法）。

我习惯写成循环形式，先计算每个拉格朗日基多项式在 x=0 处的值，再乘上对应的 y，最后累加。这样逻辑清晰，不容易出错。

代码示例：Python 实现

import random

def modinv(a, p):
    return pow(a, p-2, p)  # 费马小定理，p为素数

def generate_shares(secret, k, n, p):
    coeffs = [secret] + [random.randrange(1, p) for _ in range(k-1)]
    shares = []
    for x in range(1, n+1):
        y = 0
        for i, c in enumerate(coeffs):
            y = (y + c * pow(x, i, p)) % p
        shares.append((x, y))
    return shares

def reconstruct_secret(shares, p):
    x_vals, y_vals = zip(*shares)
    secret = 0
    for i in range(len(shares)):
        xi, yi = x_vals[i], y_vals[i]
        num = 1
        den = 1
        for j in range(len(shares)):
            if i == j:
                continue
            xj = x_vals[j]
            num = (num * (-xj)) % p
            den = (den * (xi - xj)) % p
        li = (num * modinv(den, p)) % p
        secret = (secret + yi * li) % p
    return secret

注意！上面的生成函数使用了 random.randrange，这不够安全。生产环境请换成 secrets.randbelow() 或专用密码学库。我曾在测试环境用 Python 内置 random，结果被人用几百份样本推算出种子，直接重现了所有系数——还好只是测试。

核心流程示意图

下面这张图展示了从秘密到子密钥生成，再到重构的完整链路：

避坑指南：我曾经犯过的错误

x 值不能为 0：因为秘密是 f(0)，如果某个子密钥的 x=0，那 y 就等于秘密本身，直接把秘密交出去了。所以 x 从 1 开始取。
系数 aₓ 不能为 0：如果某个系数恰好为 0，相当于降低了多项式阶数，那么门限值会变小。虽然是极小概率，但安全实现里应该检查一下，随机到 0 就重新采样。
模逆元计算性能：用 pow(a, p-2, p) 对大数据很慢？实测 p=2^128 量级时，平方乘大概 128 次乘法，现代 CPU 上几百微秒，可以接受。如果拆解成多线程场景，可以预计算所有分母的逆元，用查表加速重构。
有限域溢出：Python 大整数没问题，但用 C/C++ 时要注意乘法结果可能超过 64 位，需要用带模乘的大整数库。

关于素数域 vs 二进制域

这里我多说一句。有人喜欢用 GF(2^k) 二进制域，因为那里的加法和乘法可以用移位和异或实现，速度更快，尤其适合硬件。但二进制域里的元素本质是多项式，理解和调试起来麻烦一点。我个人偏好素数域，因为它更直观，而且 Python 里大整数运算已经很快了。除非你明确要做硬件加速或者底层优化，否则 GF(p) 够用。