Shamir 秘密共享方案

这是个好玩的东西。简单的讲，就是某个数字例如K=77，可以分成5个，只有3个人都选择恢复这个数字才能恢复这个数字。
这能干的事情就很多了。
至于详细地说。。。看下面：

后来把它做成了一个能跑的服务：cnb.cool/t1mmoc/tspace/pwngore/shamir-file-split。 下面先讲原理，再讲那份抄来的 Python 代码里两个会让门限失效的 bug，最后讲工程化之后真正要解决的问题。

基本原理

Shamir 秘密共享方案是一种基于多项式插值原理的密码学技术，由 Adi Shamir 在 20 世纪 70 年代提出。其核心思想是将一个秘密数据分割成多个份额，只有当足够数量的参与者（达到一个预设的阈值）将他们的份额组合在一起时，才能重建出原始秘密。

详细步骤

构造多项式

1. 选择一个有限域 GF(q)，其中 q 是一个素数，且要大于最大的秘密值和参与者的数量。
2. 构造一个 k−1 次多项式 f(x)=a₀+a₁x+a₂x²+…+a_{k−1}x^{k−1}，其中 a₀ 为秘密，a₁,a₂,…,a_{k−1} 是在有限域内随机选择的系数。

生成份额

对于每个参与者 i（1≤i≤n），计算该多项式在 x=i 处的值，即份额 s_i=f(i)，然后将这些份额分发给各个参与者。

秘密恢复

当有足够的参与者（至少 k 个）提供他们的份额时，可以通过插值法（如拉格朗日插值法）来重建多项式 f(x)，从而计算出 f(0)，即原始秘密。

用途

安全领域

• 门限密码学
  • 在加密货币钱包管理等场景中，将私钥分割成多个部分分发给不同信任方，只有达到一定数量的信任方提供份额时才能组合出私钥，防止因单点故障或恶意行为导致私钥泄露或系统崩溃。
• 关键基础设施保护
  • 对于核电站、军事指挥中心等关键设施的操作系统密码或启动密钥等重要信息，将其分割成多个部分分发给不同授权人员，确保只有足够数量的授权人员同时提供份额时才能启动或操作关键设施。

分布式系统

• 数据备份与恢复
  • 在分布式存储系统中，将数据加密密钥分割成多个份额存储在不同节点上，当部分节点故障或数据丢失时，只要还有足够数量的存活节点提供份额，就可以恢复出原始密钥进而恢复数据。
• 容错机制
  • 在分布式计算任务中，将关键参数分割成多个份额分配给不同计算节点，即使部分节点出现故障或计算错误，只要还有足够数量的正确节点提供份额，就可以恢复出正确的关键参数，保证整个计算任务的正常进行。

示例

https://www.cnblogs.com/pyrie/p/sss_py.html

感谢作者pyrie的代码。

# https://www.cnblogs.com/pyrie/p/sss_py.html

import Crypto.Util.number as numb
import random


# 求逆的函数，之前的版本用python2写的，这次用的python3，只把整除符号改了一下
def oj(a, n):
    a = a % n
    s = [0, 1]
    while a != 1:
        if a == 0:
            return 0
        q = n // a
        t = n % a
        n = a
        a = t
        s += [s[-2] - q * s[-1]]
    return s[-1]


# max_length 为p的长度，同时也是秘密的最大长度
# secret_is_text =0 默认输入时文本， 非0时认为是数字
# p 默认为0， 会根据max_length 自动生成，不为0时直接使用，需要保证p为素数， 函数内没有素性检验
def create(max_length=513, secret_is_text=0, p=0):
    if not p:
        p = numb.getPrime(max_length)

    w = int(input("请输入秘密保存人数："))
    t = int(input("请输入秘密恢复所需人数："))
    while not (t > 0 and t <= w):
        t = int(input("请重新输入："))
    s = input("请输入你的秘密:")

    if secret_is_text:
        s = numb.bytes_to_long(s.encode("utf-8"))
    else:
        try:
            s = int(s)
        except Exception as e:
            s = numb.bytes_to_long(s.encode("utf-8"))

    x_list = list()
    a_list = list()
    i = w
    while i > 0:
        x = random.randint(p // 2, p)  # 该范围没有特定限制，如果想让xi,yi取小一点儿的话可把范围写小点儿，但是要大于w
        if x not in x_list:
            x_list.append(x)
            i -= 1

    for a in range(t):
        a_list.append(random.randint(p // 2, p))  # 同上

    result = list()
    for x in x_list:
        y = s
        for a_n in range(t):
            a = a_list[i]
            y += a * pow(x, i + 1, p)
        result.append((x, y))
    return t, p, result


# get_text=1 默认恢复为字符串，若想得到数字填0
def restore(p, information, get_text=1):

    x_list = list()
    y_list=list()
    for x, y in information:
        x_list.append(x)
        y_list.append(y)

    s = 0
    for x_i in range(len(x_list)):
        tmp_num = y_list[x_i]
        x_i_j = 1
        for x_j in range(len(x_list)):
            if x_i != x_j:
                tmp_num = tmp_num * (0 - x_list[x_j]) % p
                x_i_j *= x_list[x_i] - x_list[x_j]
        tmp_num = tmp_num * oj(x_i_j, p) % p
        s += tmp_num

    s = s % p
    print(s)
    if get_text:
        try:
            s = numb.long_to_bytes(s)
            s = s.decode("utf-8")
        except Exception as e:
            print(e)

    return s


t, p, result = create()             #result为秘密碎片的列表
print(result)
print(restore(p, result[:t]))     #这里我取了result的前t个，实际中可以取任意t个。

我看看我是何时复制这些代码的，嗯，25-03-26。
确实好玩，但也仅限于"好玩"，实用性确实有，但目前对我没有效果。

下面是我后来补的：先手算一遍把原理钉死，再说那份 Python 到底哪里不对，最后是把它做成服务之后遇到的真实问题。

手算一遍

用自己写测试时挑的那组数：秘密 s = 11，门槛 k = 3，总额 n = 5，有限域 GF(17)。

k = 3 意味着多项式是 2 次：f(x) = 11 + 8x + 7x² (mod 17)。常数项就是秘密，后两个系数随机取。

五个份额就是往 x = 1..5 里代：

份额就是 (1,9) (2,4) (3,13) (4,2) (5,5)。

现在只拿其中三份 (2,4) (3,13) (4,2) 去恢复。拉格朗日插值在 x = 0 处求值，系数是：

λ₂ = (0-3)(0-4) / (2-3)(2-4) = 12 / 2   = 6
λ₃ = (0-2)(0-4) / (3-2)(3-4) = 8 / -1   = -8
λ₄ = (0-2)(0-3) / (4-2)(4-3) = 6 / 2    = 3

代回去：

s = 4×6 + 13×(-8) + 2×3 = 24 - 104 + 6 = -74 ≡ 11 (mod 17)

11，对上了。 换任意三份结果都一样，而只拿两份是解不出来的——两个点只能定一条直线，原函数的二次项信息还缺一个约束。

这里藏着一个必须记住的约定：x 永远不能取 0。因为 f(0) 就是秘密本身，谁的份额如果落在 x=0，就等于把秘密直接发出去了。所以份额的 index 一定从 1 开始（最好别用连续的 1、2、3，见下面）。

那份 Python 其实跑不出它想要的结果

上面那段代码是从 pyrie 的博客 抄的，原作者自己写着是 Python2 移植过来的。按代码逻辑推，它有两个会让门限失效的问题——注意是失效，不是报错。

问题一：所有系数取的是同一个值，多项式退化成直线

i = w
while i > 0:
    ...
    i -= 1                      # 循环结束时 i == 0

for a in range(t):
    a_list.append(random.randint(p // 2, p))   # 生成了 t 个系数

for x in x_list:
    y = s
    for a_n in range(t):
        a = a_list[i]           # ← i 是上面 while 留下的 0，恒等于 0
        y += a * pow(x, i + 1, p)   # ← 幂次也是 i+1，恒等于 1
    result.append((x, y))

内层想写的是"第 i 项系数 × x 的 i+1 次方"，但变量名写错成了外层的 i，而那个 i 在生成 x 之后已经归零。结果每一项都是 a_list[0] × x¹，加 t 次：

f(x) = s + t · a₀ · x        ← 一次函数

次数从 k-1 掉到 1。 后果是：k = 3 时，任意两份份额就能解出秘密（两个点定一条直线），k = 5 时也一样。你以为是 3-of-5，实际是 2-of-5，而且不会有任何异常。

问题二：randint 的上界是闭区间，x 可能等于 p

x = random.randint(p // 2, p)   # 上界 p 是能取到的

randint(a, b) 含两端。万一 x 取到 p，那么 pow(p, 1, p) = 0，算出来的份额就是 y = s——

那一份份额直接等于秘密。 拿到它的人不需要凑够 k 份。

（顺带，y 也没有取模，会变成一个比 p 大的数，不过 restore 里做了 % p，无害。）

这两条的教训

门限方案的 bug 有个共同特征：它不会崩，只会让门槛静默地变低。上面第一条把 k 变成 2，第二条把某一份变成"万能钥匙"。你拿几份去恢复，永远都能恢复出正确结果——所以自测根本发现不了。

真正能发现它们的测试只有一种：构造 k-1 份，断言恢复失败。只测"k 份能恢复"是不够的，那只验证了正确性，没验证安全性。

我的实现：先解决"Shamir 只能拆一个整数"

这是把原理变成服务时撞上的第一堵墙。Shamir 的输出必须是有限域里的一个元素，文件不是。

所以做的是信封加密：

文件
 ├─ SHA-256                                     → 存库，恢复后比对
 ├─ Deflate 压缩
 ├─ AES-256-GCM 加密（随机 key + 12 字节 IV = 44 字节）
 │    └─ 密文 PUT 到 WebDAV，文件名 = UUID
 └─ Shamir 分割那 44 字节

只拆密钥，不拆文件。 理由很实际：BigInteger 的乘除是 O(n²)，1 GB 的文件转成 BigInteger 做插值，算到天亮也算不完；而且每次读文件都得先凑齐 k 份，等于放弃随机访问。

工程化踩到的四个坑

第四条还带出一个实现细节：既然 x 是随机的，那"再发一份新份额"就不能重新跑一遍分割（系数变了，旧份额全废）。所以系数不是每次现取随机数，而是由 seed 派生：

val random = SecureRandom(seed.toByteArray())
for (i in 0 until k - 1) coefficients.add(BigInteger(p.bitLength(), random))

同一个 seed 一定还原同一条多项式，于是可以传入 ignoreIndex（已有的 x），只补发新的份额——这就是"无限分发"的基础。代价也很清楚：seed 一旦泄漏，任何人配合任意一份份额都能算出秘密。

三个设计取舍

一、份额的 y 不进数据库。 secret_share 表只存 x，share_content_y 标了 @Transient。所以拖库拿不到完整份额，凑不齐门限。唯一会破例的是 saveSecret 模式（早期为了"发完了还能再发一份"，把 secret 和 seed 存回了库）——那一刻门限方案就归零了，后来在提交 302e854 里禁掉了。

二、管理员必须参与。 生成一把独立的 44 字节密钥，用它把文件密钥再加密一层，Shamir 分割的是这层密文。管理员密钥只在成功后展示一次、不入库。恢复时必须有 k 份份额 并且 拿到管理员密钥，等于把双人复核塞进了密钥链。

三、份额由持有者各自提交。 恢复页不是"一个人贴 k 个字符串"，而是 k 个人各自把自己的份额提交到同一个文件 ID，服务器凑够 k 份才解开。提交只进内存（5 分钟过期、重复 x 拒收），不上库也不落盘。这才是"3 个人都在场"的字面实现——否则一个人把 5 份都揣兜里，门限就只是形式。

实测那天留下的证据

整理旧目录时翻到 2025-05-17 晚上的实测记录：一份 md 里躺着五条份额字符串，两张页面截图。这三样东西比代码更能说明门限方案在实践中会怎么退化。

第一，3-of-5 的方案，一个人留了 5 份。

那份 md 里有完整的五条，同一个文件 UUID，同一个 k=3。结构上这件事等于把 3-of-5 变成了 1-of-1：份额没分居，门限就只是个参数。这正是我后来在服务里加"多人协同提交"的原因——不是技术升级，是把设计意图补上。

第二，服务当年是明跑在公网 HTTP 上的。

截图地址栏是 http://<公网IP>:8080/shamir/upload，没有域名、没有证书，Chrome 标着"不安全"。也就是说，秘密的碎片以明文经过公网。单份泄漏凑不够 k，但上传成功页是一次性把 n 份全渲染出来的——抓一次包就是全部份额。这两个问题（份额不分居 + 链路不加密）叠加，整套系统等价于"用 SHA 命名的公开文件"。

第三，有个"不解密，直接下载秘密文件"的按钮。

它把密文原样返回，给备份、验活、迁移用，设计上合理。但配上前面两条，观感就是：外壳和内胆都可以直接拿走。

顺带记一下当时的测试载荷——三份不同实现的 Candy Crush（KMP 版、编译后的 web 产物、纯 HTML/JS 版，共 24 MB）。选它不奇怪：现成、有子目录、有非 ASCII 文件名、体积够大。真正要压的东西只有大文件才试得出来：

• Deflate 对已压缩素材（图片、mp3）几乎零收益，甚至可能膨胀
• Unicode 文件名在 multipart 里怎么走
• 1 GB 上限下整体读进堆的实际占用
• 份额 Base32 编码后的长度（决定这条字符串好不好抄）

时间线很短：

不到一个月，从"跑通"到"意识到不对劲"——中间那步是加管理员密钥，再往后就不碰了。

回应当年那两句吐槽

“每次恢复密钥后，密钥就要改变，挺烦的。”

其实不必。那把 AES 密钥只服务这一个文件，恢复一百次也不会削弱它。真正需要重新分割的时机只有一个：某个持有者退出了（他手里的份额要作废）。这跟"恢复过几次"无关——现状是原地重分发即好。

“如果能实现同态加密，每个人用自己的那部分解密就好了。”

这条今天仍然没有便宜的解，但方向得纠正一下：同态加密解决的是"在密文上直接计算"，不是"分布式解密"。想要"每个人出自己那份就能拼出明文"，那就是门限密码学（threshold cryptography）——Shamir 秘密共享正是它的地基，不需要同态。真正贵的是"部分解密 + 组合"的协议（比如门限 RSA / 门限 ECDSA），不是秘密共享本身。

至于零知识证明和 RSA 同态加密，2026 年再看，结论没变：一个证明"我知道"而不说是什么，一个能算但贵得离谱。跟"把文件拆五份"不是一个量级的问题。

“拿到全部份额的人同时也担任着公布的责任。”

这句是当年最准的一句。所以现在的做法是反过来的：不让任何人拿到全部份额——份额分居在不同持有者手里，各自提交，服务器只做凑数与解封；服务器自己连一份完整的 y 都不存。责任分散，才不用指望谁"公布"。

仓库

cnb.cool/t1mmoc/tspace/pwngore/shamir-file-split

Spring Boot 3.4 + Kotlin + SQLite + WebDAV，30 多个文件，ShamirAlgorithm.kt 145 行是核心。仓库里做了脱敏：application.properties 换成 .example，WebDAV 地址和密码全部置空，data/ 和 target/ 不纳入，重新 git init 不带历史。

⚠️ 但原仓库（GitCode）的历史里仍然留着真实凭据。那个仓库如果还公开，WebDAV 密码该换了。