Shamir 秘密共享

前言

秘密共享：

• 将秘密 S 派生 n 个碎片，并设置阈值 m，集齐不少于 m 个碎片，即可恢复出秘密 S，少于 m 个碎片则无法获得关于 S 的任何信息

常见的秘密共享方法有

• Shamir 秘密共享

• Blakley 秘密共享

• CRT 秘密共享

准备工作

• 秘密：S

• 参与方个数：n

• 阈值：m

• 有限域：$\mathbb{F}_p$

秘密分发

• 生成随机数：$\{a_0=S,a_1,\ldots,a_{m-1}\}$

• 构造多项式 $f(x)=a_0+a_1\times x+a_2\times x^2+\ldots +a_{m-1}\times x^{m-1}$

• 任取 n 个在 $\mathbb{F}_p$ 中的数 $\{x_1,x_2,\ldots,x_n\}$

• 在 $\mathbb{F}_p$ 中计算 $\{f(x_1),f(x_2),\ldots,f(x_n)\}$

• 将 $\{x_i,y_i=f(x_i)\}$ 发送给 n 个参与方

秘密恢复

基于拉格朗日插值公式，$f(x)$ 的另一个表示方法如下：

取 $x=0$ 的值，即为秘密 S

一个 (3,5) 的算例

取 $p=17$、$S=13$，$a_1=10$、$a_2=2$，即 $f(x)=13+10x+2x^2$。

五个份额（$x_i=1,\dots,5$）依次是 $(1,8)$、$(2,7)$、$(3,10)$、$(4,0)$、$(5,11)$。

取 $(1,8)$、$(3,10)$、$(5,11)$，对应 $L_1(0)=4$、$L_3(0)=3$、$L_5(0)=11$：

换 $(2,7)$、$(4,0)$、$(5,11)$，对应 $L_2(0)=9$、$L_4(0)=12$、$L_5(0)=14$：

两组都还原出 $S=13$。

Python 实现

只依赖标准库：

import secrets

P = 2**127 - 1  # 梅森素数，须为素数

def split(secret, m, n, p=P):
    """把 secret 拆成 n 份，任意 m 份可还原。"""
    if not 1 <= m <= n < p:
        raise ValueError("需要 1 <= m <= n < p")
    if not 0 <= secret < p:
        raise ValueError("secret 必须落在 [0, p) 内")
    poly = [secret] + [secrets.randbelow(p - 1) + 1 for _ in range(m - 1)]
    shares = []
    for x in range(1, n + 1):
        y = 0
        for c in reversed(poly):  # Horner 求值
            y = (y * x + c) % p
        shares.append((x, y))
    return shares

def combine(shares, p=P):
    """拉格朗日插值求 f(0)。"""
    secret = 0
    for i, (xi, yi) in enumerate(shares):
        num = den = 1
        for j, (xj, _) in enumerate(shares):
            if i == j:
                continue
            num = num * (-xj) % p
            den = den * (xi - xj) % p
        secret = (secret + yi * num * pow(den, -1, p)) % p  # pow(a, -1, p) 需 Python 3.8+
    return secret

参考资料：

1. 密码学系列-Shamir秘密共享 https://zhuanlan.zhihu.com/p/577211618