Shamir 秘密共享的工作原理

有些秘密太重要，不能只交给一个人保管；但如果那个人消失，秘密也会丢失，同样不可承受。 一家公司希望使用主密钥时必须有三名高管在场。一个家庭希望账户恢复需要不止一个信封。一个团队希望备份在有人缺席时仍能恢复，但又不能让任何一个人掌握全部信息。 Adi Shamir（RSA 中的 S）在 1979 年发表了一种方法。将秘密拆分成若干碎片，使得其中的一定数量可以恢复秘密，而任何更少的数量则完全无法透露任何信息。注意：不是“很难破解”，而是“毫无信息”。 核心思想一页纸就能讲清楚。

两点确定一条直线

从已知知识入手：两个不同的点确定唯一一条直线。 单个点则不能。通过一个点有无数条直线，每条直线与纵轴的交点都不相同。 现在，把秘密藏在直线与纵轴的交点处。假设秘密是数字 7。画一条过该高度的随机直线。斜率不重要，它只是隐藏秘密的随机性。 给每个人直线上的一点。没有人得到直线本身。 拥有一个点的人可以画出无数条通过该点的直线。每条直线对应不同的秘密。他的碎片与每一种可能的答案都一致，因此单凭碎片本身无法获得任何有用信息。 将两个点放在一起，直线就被固定了。一旦知道直线，就能从它与纵轴的交点读出秘密。 这就是 2-of-n 秘密共享方案。你可以生成任意多个点，但任意两个点就足以恢复直线。

更多人意味着更多弯曲

如果需要更高的门限，就使用弯曲更多次的曲线。 抛物线需要三个点才能确定。所以如果秘密藏在抛物线与纵轴的交点，那么任意三个碎片可以恢复秘密，而任意两个则不能。 一般地，门限 k 使用次数为 k-1 的多项式：

• 2 份：直线
• 3 份：抛物线
• 4 份：三次曲线 实际实现使用有限域算术，而不是方格纸，但思想的形状是相同的。秘密是零点处的值。随机系数隐藏了它。每个碎片是多项式上的一个点。 有用之处不在于秘密难以从过少的碎片中算出，而在于过少的碎片不包含关于秘密的任何信息。缺少一个碎片时，每个可能的秘密仍然都有可能。

我们为什么关心

我们在 Ente 的 Legacy Kit 中使用了这个思想。 不过，我们的问题不仅仅是“如何拆分秘密”，还有“如何让恢复成为可能，而不会把拆分的秘密变成永久的恢复密钥？” Legacy Kit 将 Shamir 方案作为更大流程中的一层。卡片并不携带恢复密钥。它们本地重建一个单独的密钥，然后参与服务器协调的恢复过程——这样下发的卡片可以被撤销，丢失的卡片也不会成为永久的隐患。 本文只解释了“任意两个，单个不行”背后的数学原理。

延伸阅读

• Adi Shamir 的《How to Share a Secret》
• Bruce Schneier 的《Sharing Secrets Among Friends》
• Max Levchin 的 PayPal 故事
• Ente 的源代码
• 返回所有文章