Shamir 秘密共享方案深度解析：从拉格朗日插值到分布式密钥生成

在密码工程实践中，有一个看似矛盾的难题：如何让多个人共同管一个密钥，既没有完整副本可单方面挪用，又能在需要时恢复使用？

Shamir 秘密共享方案给出了优雅的数学解答。本文从有限域上的多项式理论出发，完整拆解 (k,n) 门限方案的构造逻辑、安全性证明、以及从经典方案到可验证秘密共享（VSS）、分布式密钥生成（DKG）的工程演进。

一、方案定义与核心参数

Adi Shamir 在 1979 年提出的秘密共享方案，核心思想是将秘密 $S$ 拆分为 $n$ 个份额（share），满足：

• 任意 k 个或以上的份额可以恢复秘密
• 任意 k-1 个或更少的份额无法获得关于秘密的任何信息

符号定义

• $p > S$，确保秘密在域内可表示
• $p > n$，确保每个参与者分到不同的 $x$ 坐标
• 推荐使用 256 比特以上的安全素数

二、数学构造：有限域上的多项式

2.1 分享过程（Dealer 分发）

步骤1: 随机选择 k-1 个系数 a_1, a_2, ..., a_{k-1} ∈_R F_p
步骤2: 构造 k-1 次多项式:
        f(x) = S + a_1·x + a_2·x² + ... + a_{k-1}·x^{k-1}
        （S 是常数项，a_0 = S）
步骤3: 计算 n 个份额:
        (1, f(1)), (2, f(2)), ..., (n, f(n))
步骤4: 将每个份额安全地分发给对应的参与者

关键性质：

• $k-1$ 次多项式由 $k$ 个点唯一确定
• 少于 $k$ 个点无法唯一确定多项式，信息论安全

2.2 重构过程（拉格朗日插值）

给定任意 $k$ 个份额 $(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)$，通过拉格朗日插值恢复 $S = f(0)$：

$$S = f(0) = \sum_{i=1}^{k} y_i \cdot \prod_{\substack{j=1 \\ j \neq i}}^{k} \frac{x_j}{x_j - x_i} \pmod p$$

推导：

拉格朗日基多项式： $$L_i(x) = \prod_{\substack{j=1 \\ j \neq i}}^{k} \frac{x - x_j}{x_i - x_j}$$

重构多项式： $$f(x) = \sum_{i=1}^{k} y_i \cdot L_i(x)$$

代入 $x = 0$： $$S = f(0) = \sum_{i=1}^{k} y_i \cdot L_i(0) = \sum_{i=1}^{k} y_i \cdot \prod_{j \neq i} \frac{x_j}{x_j - x_i}$$

2.3 数值示例

设 $p = 2^{256} - 189$（安全素数），$k = 3$，$n = 5$，$S = 123456789$：

随机系数: a_1 = 987654321, a_2 = 111111111

f(x) = 123456789 + 987654321·x + 111111111·x²

份额:
  P_1: (1, 123456789 + 987654321 + 111111111) = (1, 1222222221)
  P_2: (2, 123456789 + 1975308642 + 444444444) = (2, 2543210875)
  P_3: (3, 123456789 + 2962962963 + 999999999) = (3, 4086419751)

重构（任选 3 个份额恢复 f(0) = 123456789）

三、信息论安全性分析

3.1 核心定理

定理：Shamir 方案在信息论意义下是完美安全的，即任意 $k-1$ 个份额不泄露关于 $S$ 的任何信息。

证明概要：

给定 $k-1$ 个份额 $(x_1, y_1), ..., (x_{k-1}, y_{k-1})$，对于任意可能的秘密 $S' \in \mathbb{F}_p$，存在唯一一个 $k-1$ 次多项式 $f'(x)$ 满足：

• $f'(x_i) = y_i$（通过已知份额）
• $f'(0) = S'$（秘密值）

$$P(S = S' | k-1 \text{ 个份额}) = \frac{1}{p}$$

结论：在有限域 $\mathbb{F}_p$ 上，$k-1$ 个份额不改变秘密的先验分布，即零信息泄露。

3.2 安全参数选择

四、工程实现与密码学陷阱

4.1 Python 实现

import random
from typing import List, Tuple

class ShamirSecretSharing:
    """Shamir (k,n) 门限秘密共享"""
    
    # 256 位大素数（示例，生产环境使用标准安全素数）
    P = 2**256 - 189  # 大素数（注意：非安全素数，生产环境应使用标准安全素数）
    
    @staticmethod
    def _eval_poly(coeffs: List[int], x: int, p: int) -> int:
        """多项式求值 f(x) mod p"""
        result = 0
        power = 1
        for c in coeffs:
            result = (result + c * power) % p
            power = (power * x) % p
        return result
    
    @classmethod
    def split(cls, secret: int, k: int, n: int) -> List[Tuple[int, int]]:
        """将秘密分为 n 个份额，门限 k"""
        p = cls.P
        assert 0 < secret < p, "秘密超出域范围"
        assert k <= n, "门限不能大于份额数"
        
        # 随机系数（a_0 = S, a_1..a_{k-1} 随机）
        coeffs = [secret] + [random.randrange(1, p) for _ in range(k - 1)]
        
        # 计算份额
        shares = [(i, cls._eval_poly(coeffs, i, p)) for i in range(1, n + 1)]
        return shares
    
    @classmethod
    def _lagrange_basis_at_zero(cls, x_coords: List[int], i: int, p: int) -> int:
        """计算 L_i(0) mod p"""
        xi = x_coords[i]
        numerator = 1
        denominator = 1
        for j, xj in enumerate(x_coords):
            if j != i:
                numerator = (numerator * xj) % p
                denominator = (denominator * (xj - xi)) % p
        # 模逆元
        inv_denominator = pow(denominator, p - 2, p)
        return (numerator * inv_denominator) % p
    
    @classmethod
    def reconstruct(cls, shares: List[Tuple[int, int]], k: int = None) -> int:
        """从份额恢复秘密"""
        p = cls.P
        if k is None:
            k = len(shares)
        assert len(shares) >= k, "份额数量不足"
        
        # 取前 k 个份额
        shares = shares[:k]
        x_coords = [s[0] for s in shares]
        
        # 拉格朗日插值在 x=0 处求值
        secret = 0
        for i, (xi, yi) in enumerate(shares):
            Li = cls._lagrange_basis_at_zero(x_coords, i, p)
            secret = (secret + yi * Li) % p
        
        return secret

# 验证
if __name__ == "__main__":
    secret = 123456789012345678901234567890
    k, n = 3, 5
    
    shares = ShamirSecretSharing.split(secret, k, n)
    print(f"原始秘密: {secret}")
    print(f"份额数量: {len(shares)}")
    
    # 任取 k 个份额重构
    recovered = ShamirSecretSharing.reconstruct(shares[:k])
    print(f"恢复结果: {recovered}")
    assert recovered == secret, "重构失败!"
    print("✓ 验证通过")

4.2 常见工程陷阱

五、可验证秘密共享（VSS）

经典 Shamir 方案假设 Dealer 诚实，但现实中 Dealer 可能分发不一致的份额。Verifiable Secret Sharing (VSS) 通过密码学承诺解决这个问题。

5.1 Feldman VSS

构造：在循环群 $\mathbb{G}$（阶为 $p$）中，Dealer 公布系数的承诺：

$$C_0 = g^S, \quad C_1 = g^{a_1}, \quad \ldots, \quad C_{k-1} = g^{a_{k-1}}$$

验证：份额持有者 $i$ 验证：

$$g^{y_i} = C_0 \cdot C_1^{x_i} \cdot C_2^{x_i^2} \cdots C_{k-1}^{x_i^{k-1}}$$

安全性：

• 信息论安全：秘密 $S$ 仍然信息论隐藏
• 计算绑定：伪造假承诺需计算离散对数
• 参数要求：$k < p$（群的阶）

5.2 Pedersen DKG（分布式密钥生成）

在 VSS 基础上，每个参与者选择一个子秘密，所有子秘密之和构成最终秘密：

$$S = \sum_{i=1}^{n} S_i \pmod p$$

关键优势：

• 无单一 Dealer，消除单点信任
• 生成秘密 $S$ 无人知晓完整值
• 最终公钥 $P = g^S$ 由各参与者联合计算

• BLS 阈值签名
• ECDSA 阈值签名（GG18/GG20）
• 分布式随机信标（drand）
• 跨链桥多签钱包

六、国密场景应用

6.1 SM2 密钥的分布式管理

需求：SM2 签名私钥 $d$ 不能由单一人掌握，需要 (k,n) 门限控制。

方案：

• 使用 Shamir 拆分 $d = d_1 + d_2 + \cdots + d_n \pmod n$（$n$ 为 SM2 曲线阶）
• 各份额 $d_i$ 存储在不同 HSM 中
• 签名时：各节点用 $d_i$ 部分签名，聚合为完整 SM2 签名

6.2 基于 SM3 的秘密承诺

用途：在 VSS 中替代哈希承诺，增强绑定性。

import hmac
import hashlib

def sm3_commit(share: bytes, randomness: bytes) -> bytes:
    """使用 HMAC-SM3 作为承诺（近似）"""
    # 注意：gmssl 提供 SM3 哈希，此处用 sha256 占位
    # 生产环境应使用 gmssl.sm3.sm3_hash 实现纯 SM3 的 HMAC
    return hmac.new(randomness, share, hashlib.sha256).digest()

6.3 密钥分片备份

典型场景：CA 主密钥 $K_{master}$ 的安全备份。

策略: (3,5) 门限
份额分布:
  D_1 → 安全主管 A（HSM 内）
  D_2 → 安全主管 B（HSM 内）
  D_3 → 保险库 A（离线存储）
  D_4 → 保险库 B（异地）
  D_5 → 加密云存储（托管）

恢复条件: 任意 3 份 + 授权审批
安全分析: 单点失效不丢密钥，两人共谋可恢复

七、与 GM/T 0130-2023 的关系

GM/T 0130-2023《基于 SM2 算法的无证书及隐式证书公钥机制》中，密钥分发的安全性依赖于分布式信任。秘密共享在其中扮演的角色：

• KGC 主密钥保护：KGC（密钥生成中心）的主密钥 $s$ 可拆分为 $n$ 个份额分散管理
• 部分私钥验证：用户可通过份额验证 KGC 分发的部分私钥正确性
• 多 KGC 架构：使用 DKG 消除单 KGC 密钥托管风险

八、性能参考

九、总结

Shamir 秘密共享是密码工程中最优美的构造之一——用简单的多项式理论解决复杂的信任分配问题。从经典的 (k,n) 门限方案到可验证秘密共享，再到分布式密钥生成，其数学根基始终是有限域上的拉格朗日插值。

核心要点：

• Shamir 方案信息论安全，$k-1$ 个份额不泄露任何信息
• 必须使用素数域上的整数运算，避免浮点数
• $x_i \neq 0$，否则直接暴露秘密
• VSS 方案可验证份额正确性，防止恶意 Dealer
• DKG 消除单点信任，是门限签名的前置技术
• 国密场景需配合 SM2 门限签名协议使用

相关实践：

• BLS 阈值签名实战（即将推出）
• 分布式随机信标 drand 架构
• GM/T 0130-2023 无证书公钥机制
• NIST SP 800-57 密钥管理标准

• GM/T 0130-2023《基于 SM2 算法的无证书及隐式证书公钥机制》
• Pedersen, T. P. (1991). "Non-Interactive and Information-Theoretic Verifiable Secret Sharing"
• Feldman, P. (1987). "A Practical Scheme for Non-interactive Verifiable Secret Sharing"
• Gennaro, R., et al. (1999). "Secure Distributed Key Generation for Discrete-Log Based Cryptosystems"