考虑有必要确保银行保险库安全的情况。 如果没有钥匙，这是绝对不可或缺的，这是在工作的第一天就给您的。 您的目标是安全保存密钥。

假设您决定始终随身携带钥匙，并根据需要提供对商店的访问权限。 但是您很快就会意识到，这种解决方案实际上无法正常扩展，因为每次您都需要物理状态才能打开存储库时。 那你答应过的假期呢？ 此外，问题更令人恐惧：如果丢失了一把钥匙怎么办？

考虑到休假，您决定复制密钥并将其委托给另一名员工。 但是，您知道这也不理想。 通过使密钥数量加倍，还使密钥盗窃的可能性加倍。

绝望的是，您销毁了重复项并决定将原始密钥分成两半。 现在，您认为，必须亲自出现两个具有密钥片段的受信任人员才能收集密钥并打开商店。 这意味着小偷需要窃取两个片段，这是窃取一个密钥的难度的两倍。 但是，您很快就会意识到，此方案并不仅仅比一个密钥好得多，因为如果有人丢失了一半密钥，则无法还原完整密钥。

可以使用一系列其他键和锁来解决该问题，但是使用这种方法，您将很快需要大量的键和锁。 您决定在理想的方案中需要拆分密钥，以使安全性不完全依赖一个人。 您还得出结论，片段数必须有一个特定的阈值，这样，如果丢失一个片段（或者一个人去度假），则整个密钥仍然可以使用。

如何分享秘密

1979年Adi Shamir在发表自己的著作《 如何共享秘密》时曾想过这种密钥管理方案。 文章简要解释了所谓的 $$$（k，n）$ 有效地将秘密值（例如，加密密钥）划分为阈值的阈值方案 $$$n$ 零件。 然后，当且仅当至少 $$$k$ 来自 $$$n$ 零件组装好后，即可轻松还原秘密 $$$S$ 。

从安全性的角度来看，此方案的一个重要特性是，如果攻击者至少没有攻击者，则绝对不应知道任何事情。 $$$k$ 零件。 甚至可用性 $$$k-1$ 零件不应提供任何信息。 我们称此属性为语义安全 。

多项式插值

Shamir阈值方案 $$$（k，n）$ 围绕多项式插值的概念建立。 如果您不熟悉此概念，则实际上很简单。 通常，如果您曾经在图表上绘制点，然后将它们与直线或曲线相连，那么您已经使用了它！


可以通过两个点画出数量不限的2次多项式，要选择唯一的多项式，需要第三个点。 插图： 维基百科

考虑一阶多项式， $$$f（x）= x + 2$ 。 如果要在图表上绘制此函数，需要多少个点？ 好吧，我们知道这是一条线性函数，形成一条线，因此至少需要两个点。 接下来，考虑一个二阶多项式函数， $$$f（x）= x ^ 2 + 2x + 1$ 。 这是一个二次函数，因此至少需要三个点才能构建图形。 那么三阶多项式呢？ 至少四分。 依此类推。

关于此属性的真正酷的事情是，鉴于多项式函数的阶数，至少 $$$学位+ 1$ 点，我们可以导出此多项式函数的其他点。 这些附加点的外推称为多项式内插 。

保密

您可能已经意识到Shamir的聪明方案在这里发挥了作用。 假设我们的秘密 $$$S$ 那是吗 $$$42$ 。 我们可以转 $$$S$ 到图表上的某个点 $$$（0.42）$ 并提出一个带度的多项式函数 $$$k-1$ 满足这一点。 回想一下 $$$k$ 将是所需片段的阈值，因此，如果将阈值设置为三个片段，则必须选择阶数为2的多项式函数。

我们的多项式将采用以下形式 $$$f（x）= a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$ 在哪里 $$$a_0 = S$ 和 $$$a_1，...，a_ {k-1}$ -随机选择正整数。 我们只是建立一个带度数的多项式 $$$k-1$ 自由系数在哪里 $$$a_0$ 是我们的秘密 $$$S$ ，以及以下每个 $$$k-1$ 成员具有随机选择的正系数。 如果您回到原始示例并假设 $$$S = 42，k = 3，a_1，...，a_ {k-1} = [3,5]$ 然后我们得到函数 $$$f（x）= 42 + 3x + 5x ^ 2$ 。

在这个阶段，我们可以通过连接来生成片段 $$$n$ 中的唯一整数 $$$f（x）= 42 + 3x + 5x ^ 2$ 在哪里 $$$x \ neq 0$ （因为这是我们的秘密）。 在此示例中，我们想要分布四个阈值为3的片段，因此我们随机生成点 $$$（18，1716），（27，3768），（31，4940），（35，6272）$ 并向四个值得信赖的人（关键人物）分别发送一个积分。 我们还告诉人们 $$$k = 3$ ，因为它被视为公共信息，是恢复的必要条件 $$$S$ 。

秘密恢复

我们已经讨论了多项式插值的概念及其在Shamir阈值方案基础上的事实 $$$（k，n）$ 。 当四个代理中的任何三个要恢复时 $$$S$ 他们只需要插值 $$$f（0）$ 有其独特之处。 为此，他们可以确定自己的观点 $$$（x_1，y_1），...，（x_k，y_k）=（18，1716），（27，3768），（31，4940）$ 并使用以下公式计算Lagrange插值多项式。 如果编程对您来说比数学更容易理解，那么pi本质上是一个for语句，它将所有结果相乘，而sigma是一个for语句，将所有结果相加。

$$

$$P（x）= \ sum_ {j = 1} ^ {k} p_j（x）$$

$$

$$P_j（x）= y_j \产品_ {\ scriptstyle m = 1 \ top \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

在 $$$k = 3$ 我们可以如下解决此问题并返回原始多项式函数：

$$

$$\开始{对齐} P（x）＆= {y_1} \左（{x-x_2 \在x_1-x_2}上\ cdot {x-x_3 \在x_1-x_3}上\右）+ {y_2} \左（ {x-x_1 \ over x_2-x_1} \ cdot {x-\ _ 3 \ over x_2-x_3} \ right）+ {y_3} \ left（{x-x_1 \ over x_3-x_1} \ cdot {x-x_2 \在x_3-x_2}上\右）\\ P（x）＆= {1716} \左（{x-27 \在18-27上} \ cdot {x-31 \在18-31上} \右）+ {3768 } \左（{x-18 \超过27-18} \ cdot {x-31 \超过27-31} \右）+ {4940} \左（{x-18 \超过31-18} \ cdot {x -27 \超过31-27} \右）\\ P（x）＆= 42 + 3x + 5x ^ 2 \结束{aligned}$$

因为我们知道 $$$S = P（0）$ 恢复 $$$S$ 简单地执行：

$$

$$\开始{aligned} P（0）＆= 42 + 3（0）+ 5（0）^ 2 \\ P（0）＆= 42 \ end {aligned}$$

使用不安全的整数算法

尽管我们已经成功应用了Shamir的基本思想 $$$（k，n）$ ，到目前为止，我们仍然有一个我们忽略的问题。 我们的多项式函数使用不安全的整数算法。 请注意，对于攻击者在我们的函数图上获得的每个其他点，其他点的选择较少。 使用整数算法构建多项式函数的点数增加的图形时，您可以亲眼看到。 这对我们陈述的安全目标适得其反，因为攻击者在至少有一定了解之前，不必学习任何绝对知识 $$$k$ 碎片。

为了说明采用整数算术的方案有多弱，请考虑一个攻击者得到两分的情况 $$$（18，1716），（27,3768）$ 并且知道公共信息 $$$k = 3$ 。 他可以根据这些信息推断出 $$$f（x）$ 等于2并连接公式中的已知值 $$$x$ 和 $$$f（x）$ 。

$$

$$\开始{对齐} f（x）＆= a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f（x）＆= S + a_1x + a_2x ^ 2 \\ f（18）\ equiv 1716＆= S + a_118 + a_218 ^ 2 \\ f（27）\ equiv 3768＆= S + a_127 + a_227 ^ 2 \ end {aligned}$$

然后，攻击者可以找到 $$$a_1$ 盘点 $$$f（27）-f（18）$ ：

$$

$$\ begin {aligned} 3768-1716＆=（S-S）+（27a_1-18a_1）+（729a_2-324a_2）\\ 2052＆= 9a_1 + 405a_2 \\ 9a_1＆= 2052-405a_2 \\ a_1＆= \ frac {2052-405a_2} {9} \\ a_1＆= 228-45a_2 \ end {aligned}$$

既然我们已经确定 $$$a_1，...，a_ {k-1}$ 作为随机选择的正整数，可能的数目有限 $$$a_2$ 。 使用此信息，攻击者可以推断 $$$a_2 \在[1,2,3,4,5]$ ，因为大于5的所有内容都可以 $$$a_1$ 负面的。 正如我们所确定的，这是事实 $$$a_2 = 5$

然后，攻击者可以计算出可能的值 $$$S$ 更换 $$$a_1$ 在 $$$f（18）$ ：

$$

$$\开始{对齐} 1716＆= S + a_118 + a_218 ^ 2 \\ 1716＆= S + 18 \左（228-45a_2 \右）+ a_218 ^ 2 \\ 1716-S＆= 18 \左（228- 45a_2 \右）+ a_218 ^ 2 \\ -S＆= 18 \左（228-45a_2 \右）+ a_218 ^ 2-1716 \\ -S＆= 4104-810a_2 + a_218 ^ 2-1716 \\ S＆= -4104 + 810a_2-a_218 ^ 2 + 1716 \\ S＆= 810a_2-324a_2 -2388 \\ S＆= 486a_2-2388 \ end {aligned}$$

选择的选项有限 $$$a_2$ 很明显，选择和检查值有多么容易 $$$S$ 。 只有五个选项。

用不安全的整数算法解决问题

为了消除此漏洞，Shamir建议使用模块化算法， $$$f（x）$ 在 $$$f（x）\ mod p$ 在哪里 $$$p \ in \ mathbb {P}：p> S，p> n$ 和 $$$\ mathbb {P}$ -所有素数的集合。

快速回想一下模块化算术的工作原理。 带有箭头的时钟已经是一个熟悉的概念。 她使用的手表 $$$\ mod 12$ 。 时针一经过十二时，便返回至一。 该系统的一个有趣特性是，仅通过查看时钟，我们就无法推断时针旋转了多少圈。 但是，如果我们知道时针已经过12次四次，则可以使用一个简单的公式来完全确定经过的小时数 $$$a = mq + r$ 在哪里 $$$m$ 是我们的除数（在这里 $$$m = 12$ ）， $$$q$ 系数是多少（除数除以除数等于原始数，这里 $$$q = 4$ ），以及 $$是余数，通常返回操作员的呼叫模（此处为 $$$r = 1.5$ ） 知道所有这些值可以让我们求解方程 $$$a = 49.5$ 但是如果跳过系数，我们将永远无法恢复原始值。

您可以通过将电路应用于前面的示例并使用来演示如何提高电路的安全性 $$$p = 73$ 。 我们新的多项式函数 $$$f’（x）= 42 + 3x + 5x ^ 2 \ mod 73$ 和新点 $$$（18，37），（27，45），（31，49），（35，67）$ 。 现在，密钥保持者可以再次使用多项式插值来恢复我们的功能，只有这一次加法和乘法运算必须伴随模归约 $$$p$ （例如 $$$48 + 93 \ mod 73 = 68$ ）

使用这个新示例，假设攻击者认识到了其中两个新点， $$$（18，37），（27，45）$ 以及公共信息 $$$k = 3，p = 73$ 。 这次，攻击者根据他拥有的所有信息，显示以下功能，其中 $$$\ mathbb {N}$ 是所有正整数的集合，并且 $$$q_x$ 代表模块的系数 $$$f’（x）$ 。

$$

$$\开始{aligned} f'（x）＆= S + a_1x + a_2x ^ 2 \ mod 73 \\ f'（x）＆= S + a_1x + a_2x ^ 2-73q_x：q_x \ in \ mathbb {N} \\ f'（18）\ equiv 37＆= S + a_118 + a_218 ^ 2-73q_ {18} \\ f'（27）\ equiv 45＆= S + a_127 + a_227 ^ 2-73q_ {27} \ end {aligned}$$

现在我们的攻击者再次发现 $$$a_1$ 通过计算 $$$f’（27）-f’（18）$ ：

$$

$$\ begin {aligned} 45-37＆=（S-S）+（27a_1-18a_1）+（729a_2-324a_2）+（-73q_ {27}-（-73q_ {18}））\\ 8＆= 9a_1 + 405a_2 + 73（q_ {18}-q_ {27}）\\ -9a_1＆= -8 + 405a_2 + 73（q_ {18}-q_ {27}）\\ 9a_1＆= 8-405a_2-73（q_ {18}-q_ {27}）\\ a_1＆= \ frac {8-405a_2-73（q_ {18}-q_ {27}）} {9} \\ a_1＆= \ frac {8} {9} -45a_2-\ frac {73} {9}（q_ {18}-q_ {27}）\ end {aligned}$$

然后他再次试图退出 $$$S$ 更换 $$$a_1$ 在 $$$f’（18）$ ：

$$

$$\开始{对齐} 37＆= S + 18 \左（\ frac {8} {9}-45a_2-\ frac {73} {9}（q_ {18}-q_ {27}）\右）+ a_218 ^ 2-73q_ {18} \\ -S＆= 18 \左（\ frac {8} {9}-45a_2-\ frac {73} {9}（q_ {18}-q_ {27}）\ right） + a_218 ^ 2-73q_ {18}-37 \\ S＆= -18 \左（\ frac {8} {9}-45a_2-\ frac {73} {9}（q_ {18}-q_ {27} ）\对）-324a_2 + 73q_ {18} + 37 \\ S＆= 486a_2 + 21 + 219q_ {18}-146q_ {27} \ end {aligned}$$

这次他有一个严重的问题。 公式中没有值 $$$a_2$ ， $$$q_ {18}$ 和 $$$q_ {27}$ 。 由于这些变量有无数的组合，因此它无法接收任何其他信息。

安全注意事项

Shamir的秘密共享方案从信息论的角度提供了安全性 。 这意味着即使对具有无限计算能力的攻击者，数学也具有抵抗力。 但是，该电路仍然包含几个已知问题。

例如，沙米尔（Shamir）的方案不会创建测试片段 ，也就是说，人们可以自由展示假片段并干扰正确机密的恢复。 具有足够信息的敌对碎片守卫者甚至可以通过更改来产生另一个碎片 $$$S$ 自行决定。 通过使用经过验证的机密共享方案 （例如Feldman方案）可以解决此问题。

另一个问题是任何片段的长度等于相应秘密的长度，因此秘密的长度易于确定。 通过平凡地填充具有固定长度的任意数字的秘密，可以解决此问题。

最后，重要的是要注意，我们的安全问题可能超出了计划本身的范围。 对于真实的密码应用程序，当攻击者尝试从应用程序运行时，缓存，崩溃等中提取有用的信息时，通常会威胁到第三方渠道的攻击。 如果这是一个令人担忧的问题，则应在开发过程中仔细考虑使用安全措施，例如以恒定的运行时间进行功能和搜索，防止将内存保存到磁盘上，并考虑本文不涉及的许多其他事项。

演示版

此页面包含Shamir秘密共享方案的交互式演示。 该演示是基于ssss-js库进行的，该库本身就是流行的ssss程序的JavaScript端口。 请注意，计算大值 $$$k$ ， $$$n$ 和 $$$S$ 可能需要一些时间。