Abstract	Journal on 2025-09-09
Authors	Walter Fan
Category	learning note
Status	v1.0
Updated	2025-09-09
License	CC-BY-NC-ND 4.0

多项式方程引出的密钥分享算法

沙米尔密钥分享（Shamir’s Secret Sharing，简称SSS）是一种密码学算法，核心作用是将一个秘密（比如密码、密钥、敏感数据等）拆分成多个“份额”（share），只有当收集到足够多的份额时，才能重新拼出原始秘密。它由以色列密码学家阿迪·沙米尔在1979年提出，本质是通过“阈值机制”实现秘密的安全分发和重建。

核心概念：阈值参数

SSS的运作依赖两个关键参数： - n：总共生成的份额数量（比如拆分成5份）。 - k：重建秘密所需的最小份额数量（比如至少需要3份），这个k被称为“阈值”。

这种机制通常被称为“k-of-n”方案。例如“3-of-5”方案中，秘密被拆成5份，任意3份都能拼出秘密，但如果只有2份或更少，就完全无法得知秘密的任何信息。

工作原理：多项式插值（通俗解释）

SSS的数学基础是“多项式插值”，可以简单理解为： 1. 用多项式隐藏秘密：
假设我们要保护的秘密是一个数字（比如“100”），我们可以把它当作一个多项式在x=0处的取值（即f(0)=秘密）。多项式的次数由阈值k决定：次数 = k-1。
例如，如果k=3（需要3份才能重建），就用一个二次多项式：f(x) = a₀ + a₁x + a₂x²，其中a₀就是我们的秘密（比如100），而a₁、a₂是随机生成的数（比如a₁=5，a₂=3），这样多项式就变成：f(x) = 100 + 5x + 3x²。

1. 生成份额：
   给x取n个不同的数值（比如x=1、2、3、4、5），代入多项式计算出对应的y值。每个（x,y）对就是一个“份额”。
   比如x=1时，y=100+5×1+3×1²=108，那么（1,108）就是一份份额；x=2时，y=100+5×2+3×4=122，（2,122）是另一份份额，以此类推。

2. 重建秘密：
   当收集到k个不同的份额时，就能通过数学方法反推出原来的多项式，再代入x=0，得到的f(0)就是原始秘密。
   比如用（1,108）、（2,122）、（3,144）这3份，就能算出多项式是100+5x+3x²，进而得到f(0)=100。

关键特性

• 安全性：少于k份的份额完全无法推断出秘密（哪怕是部分信息）。例如“3-of-5”方案中，2份份额只能画出无数条可能的多项式，无法确定哪条是正确的，自然也得不到f(0)。
• 灵活性：可以根据需求自由选择k和n。比如小团队可用“2-of-3”（3人各持1份，任意2人合作就能解密），大型机构可用“5-of-10”（10人持份，需至少5人同意才能解密）。
• 去中心化：没有任何单个人持有完整秘密，降低了秘密被单人泄露或窃取的风险。

举个生活中的例子：保险箱密码

假设公司有一个存放核心数据的保险箱，密码是“666”，现在要用“3-of-5”方案保护这个密码：

1. 拆分秘密：
   设定k=3（至少3人才能打开），n=5（拆成5份）。
   选一个二次多项式（次数=3-1=2），比如f(x) = 666 + a₁x + a₂x²，随机取a₁=2，a₂=1，多项式就是f(x)=666 + 2x + x²。
   生成5个份额（x=1到5）：
2. x=1：f(1)=666+2×1+1²=669 → 份额1：（1,669）
3. x=2：f(2)=666+2×2+2²=674 → 份额2：（2,674）
4. x=3：f(3)=666+2×3+3²=681 → 份额3：（3,681）
5. x=4：f(4)=666+2×4+4²=690 → 份额4：（4,690）
6. x=5：f(5)=666+2×5+5²=701 → 份额5：（5,701）

把这5份份额分别交给5位高管。

1. 重建密码：
   某天需要打开保险箱，任意3位高管拿出自己的份额，比如高管1（1,669）、高管3（3,681）、高管5（5,701）。
   通过这3个点反推多项式：
   代入x=1、3、5，解方程组可得到f(x)=666 + 2x + x²，再算f(0)=666，即保险箱密码。

2. 安全性验证：
   如果只有2位高管（比如高管1和2），他们的份额是（1,669）和（2,674）。这两个点可以对应无数个二次多项式（比如f(x)=666+2x+x²，或f(x)=600+68x-10x²等），每个多项式的f(0)都不同，完全无法确定真正的密码是666。

如果要保护密码的是字符串（比如“OpenSesame”“密码123456”），Shamir密钥分享的核心逻辑不变，只需要先把字符串转换为数字（因为多项式运算基于数字），再按之前的步骤拆分；恢复时，把得到的数字再转回字符串即可。

具体步骤用一个例子说明：假设要保护的秘密是字符串 “KEY”。

步骤1：字符串转数字

任何字符串都可以通过编码（如ASCII、UTF-8）转换为数字。以ASCII为例：
- 'K' 的ASCII码是 75
- 'E' 的ASCII码是 69
- 'Y' 的ASCII码是 89

可以将这三个数字拼接成一个大整数（或按顺序处理），比如：756989（即秘密对应的数字）。

步骤2：用Shamir方案拆分数字

假设采用“2-of-3”方案（2份即可恢复），步骤和之前完全相同：
1. 选择一次多项式 f(x) = a₀ + a₁x，其中 a₀ = 756989（秘密数字），随机选 a₁ = 12345，则多项式为 f(x) = 756989 + 12345x。
2. 生成3个份额（x取1、2、3）：
- x=1：f(1) = 756989 + 12345×1 = 769334 → 份额（1, 769334）
- x=2：f(2) = 756989 + 12345×2 = 781679 → 份额（2, 781679）
- x=3：f(3) = 756989 + 12345×3 = 794024 → 份额（3, 794024）

步骤3：恢复数字并转回字符串

任意2人（比如拿到份额1和2）合作：
1. 用两个点（1,769334）和（2,781679）反推多项式：
设 y = a₀ + a₁x，代入得：
- 769334 = a₀ + a₁×1
- 781679 = a₀ + a₁×2
解得 a₁ = 12345，a₀ = 756989（即秘密数字）。

1. 将数字756989拆分为原始ASCII码：
2. 前两位“75” → 'K'
3. 中间两位“69” → 'E'
4. 最后两位“89” → 'Y'

拼接后得到原始字符串 “KEY”。

注意事项

• 如果字符串很长（比如超过10个字符），拼接的数字可能非常大，实际中会用“分组处理”（比如每3个字符一组转换为数字，每组单独拆分），或用哈希、对称加密等方式先压缩为固定长度的数字（如AES密钥）再拆分。
• 编码方式需统一（比如约定用UTF-8），否则恢复时可能出现乱码。

通过这两个例子可以看出，Shamir密钥分享既保证了秘密不会被少数人滥用，又能在需要时通过足够多的人合作恢复秘密，非常适合需要多人共同管理敏感信息的场景（如区块链私钥、银行金库密码、企业核心数据加密密钥等）。

---

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。