Shamir秘密分享如何运作

# Shamir 秘密共享的原理 来源：https://ente.com/blog/how-shamirs-secret-sharing-works/ 有些秘密太过重要，不能托付给一个人，也太过重要，不能因为那个人消失而丢失。 一家公司希望使用主密钥前需要三位主管在场。一个家庭希望账户恢复需要不止一个信封。一个团队希望备份能在成员缺失时存活，同时又不让任何人掌握全部信息。 Adi **S**hamir（R**S**A 中的那个 **S**）在 1979 年发表了一种实现方式。将一个秘密分割成碎片，使得其中一定数量的碎片可以恢复秘密，而任何更少的碎片则完全不泄露任何信息。不是“难以破解”，而是“完全不泄露”。 核心思想一页纸就能讲清楚。 ## 两点确定一条直线 从一个已知事实开始：两个不同的点唯一确定一条直线。 一个点不行。无数条直线通过一个点，每条直线在纵轴上的截距都不同。 两个点固定一条直线；一个点允许无数条直线。 现在将秘密隐藏在这条直线与纵轴相交的地方。假设秘密是数字 7。在该高度处画一条随机直线。斜率不重要，它只是隐藏秘密的随机性。 一条直线 y = 2x + 7。秘密 7 位于它与 y 轴的交点处。 给每个人分配这条直线上的一个点。没有人得到直线本身。 拥有一个点的人可以画出通过该点的许多可能直线。每条直线对应一个不同的秘密。他们的份额与所有可能的答案兼容，因此单凭这一点对他们毫无用处。 Bob 持有一个份额。许多候选直线通过它，每条直线对应不同的秘密。 将两个点放在一起，直线就被确定了。一旦你知道这条直线，就可以从它与零轴的交点读出秘密。 Alice 和 Bob 的份额共同确定了直线并揭示了秘密。 这就是一个 2-of-n 秘密共享方案。你可以创建任意多个点，但任意两个点都足以恢复这条直线。 ## 更多人意味着更多弯曲 对于更高的阈值，使用弯曲程度更大的曲线。 抛物线需要三个点来确定。因此，如果将秘密隐藏在抛物线与纵轴的交点处，那么任意三个份额可以恢复秘密，而任意两个则不能。 抛物线需要三个点来确定；秘密位于 x = 0 处。 通常，阈值为 `k` 使用次数为 `k - 1` 的多项式。 - 2 个份额：直线 - 3 个份额：抛物线 - 4 个份额：三次曲线 实际实现使用有限域算术而不是方格纸，但核心思想是相同的。秘密是零点的值。随机系数隐藏了它。每个份额是多边形上的一个点。 有用的部分不是秘密难以从太少的份额中计算出来，而是太少的份额不包含关于秘密的任何信息。缺少一个份额时，每个可能的秘密仍然都是可能的。 ## 为什么我们关心这个 我们在 Ente 的 Legacy Kit（https://ente.com/blog/legacy-kit）中使用了这个想法。 不过，我们面临的不仅仅是“如何分割秘密？”，还有“如何在不让分割后的秘密变成永久恢复密钥的情况下实现恢复？” Legacy Kit 将 Shamir 方案作为更大流程中的一层。卡片并不携带恢复密钥。它们在本地重建一个单独的密钥，然后该密钥参与服务器协调的恢复——因此已签发的卡片可以被撤销，丢失的卡片不会成为永久责任。 这篇文章只介绍“任意两个，而不是一个”背后的数学原理。 ## 延伸阅读 - Adi Shamir 的《How to Share a Secret》（https://cacm.acm.org/research/how-to-share-a-secret/） - Bruce Schneier 的《Sharing Secrets Among Friends》（https://www.schneier.com/essays/archives/1992/04/sharing_secrets_amon.html） - Max Levchin 的 PayPal 故事（https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of） - Ente 的源代码（https://github.com/ente-io/ente）