考虑一个您需要保护银行金库的场景。 如果没有钥匙，它被认为是绝对坚不可摧的，而钥匙是在工作第一天给你的。 您的目标是安全地存储密钥。
假设您决定始终随身携带密钥，并根据需要提供对存储的访问。 但您很快就会意识到，这样的解决方案在实践中无法很好地扩展，因为每次打开存储时都需要您亲自到场。 你答应的假期怎么样？ 此外，更可怕的问题是：如果你丢了唯一的钥匙怎么办？
考虑到您的假期，您决定复制一份钥匙并将其委托给另一名员工。 但是，您知道这也不理想。 通过将钥匙数量增加一倍，钥匙被盗的可能性也会增加一倍。
无奈之下，您销毁了副本并决定将原始钥匙分成两半。 现在，您可能会认为两个拥有密钥碎片的值得信赖的人必须亲自在场才能收集密钥并打开金库。 这意味着小偷需要偷两把钥匙，这比偷一把钥匙难度高一倍。 然而，您很快意识到这个方案并不比只有一把钥匙好多少，因为如果有人丢失了半把钥匙，则无法恢复完整的钥匙。
这个问题可以通过一系列额外的钥匙和锁来解决，但这种方法很快就需要 很多 钥匙和锁。 您认为理想的设计是共享密钥，这样安全性就不会完全依赖于一个人。 您还得出结论，碎片的数量必须有某个阈值，以便如果一个碎片丢失（或者如果一个人去度假），整个钥匙仍然可以使用。
如何分享秘密
这种类型的密钥管理方案是 Adi Shamir 在 1979 年发表其著作时提出的 。 文章简单解释了所谓 
用于有效地将秘密值（例如密钥）划分为的阈值方案 部分。 那么，当且仅当至少 из 零件组装完毕，即可轻松还原秘密 .
从安全角度来看，该方案的一个重要特性是攻击者绝对不应该知道任何事情，除非他至少有 部分。 就连存在感 零件不应提供任何信息。 我们称这个属性为 语义安全.
多项式插值
沙米尔阈值方案 围绕这个概念构建 多项式插值。 如果您不熟悉这个概念，它实际上非常简单。 事实上，如果您曾经在图表上绘制过点，然后用直线或曲线将它们连接起来，那么您就已经使用过它了！
通过两个点，您可以绘制无限多个 2 次多项式。要从中选择唯一的一个，您需要第三个点。 插图：
考虑一个一阶多项式， 。 如果你想在图表上绘制这个函数，你需要多少个点？ 好吧，我们知道这是一个形成直线的线性函数，因此它至少需要两个点。 接下来，考虑一个二阶多项式函数， 。 这是一个二次函数，因此至少需要三个点来绘制图形。 三阶多项式怎么样？ 至少有四分。 等等等等。
这个属性真正酷的地方在于，给定多项式函数的次数，并且至少 点，我们可以为这个多项式函数导出额外的点。 我们将这些附加点的外推称为 多项式插值.
编造一个秘密
您可能已经意识到，这就是沙米尔的巧妙计划发挥作用的地方。 说出我们的秘密 - 。 我们可以转 到图上的一点 并提出一个有次数的多项式函数 ，满足这一点。 让我们提醒您 将是我们所需片段的阈值，因此如果我们将阈值设置为三个片段，我们必须选择一个二阶多项式函数。
我们的多项式将具有以下形式 哪里 и — 随机选择的正整数。 我们只是构造一个有次数的多项式 ，其中自由系数 - 这是我们的秘密 ，以及对于每个后续的 项中存在随机选择的正系数。 如果我们回到原来的例子并假设 ，然后我们得到函数 .
此时我们可以通过连接来生成片段 中的唯一整数 哪里 （因为这是我们的秘密）。 在此示例中，我们希望以阈值 XNUMX 分布四个片段，因此我们随机生成点 并向四个值得信赖的人（密钥的保管人）每人发送一分。 我们还让人们知道 ，因为这被认为是公共信息并且是恢复所必需的 .
恢复秘密
我们已经讨论了多项式插值的概念以及它如何成为 Shamir 阈值方案的基础 。 当四名受托人中的任何三名想要恢复时 ，他们只需要插值 有自己的独特之处。 为此，他们可以确定自己的观点 并使用以下公式计算拉格朗日插值多项式。 如果编程对你来说比数学更清晰，那么 pi 本质上是一个运算符 for，将所有结果相乘，西格玛是 for，将所有内容相加。
在 我们可以这样解决它并返回原始多项式函数：
既然我们知道 ， 恢复 简单地完成：
使用不安全的整数算术
虽然我们已经成功应用了Shamir的基本思想 ，我们留下了一个迄今为止我们一直忽略的问题。 我们的多项式函数使用不安全的整数运算。 请注意，攻击者在我们的函数图上每获得一个额外的点，其他点的可能性就会减少。 当您使用整数算术为多项式函数绘制越来越多的点时，您可以亲眼看到这一点。 这与我们声明的安全目标适得其反，因为攻击者应该一无所知，直到他们至少拥有 碎片。
为了证明整数运算电路有多弱，请考虑攻击者获得两个点的场景 并了解公共信息 。 从这些信息他可以推断出 ，等于二，并将已知值代入公式中 и .
然后攻击者可以发现 ， 数数 :
既然我们已经定义了 作为随机选择的正整数，可能的数量有限 。 使用此信息，攻击者可以推断出 ，因为任何大于 5 的值都可以 消极的。 事实证明这是真的，因为我们已经确定
然后攻击者可以计算可能的值 更换 в :
选项有限 很明显选择和检查值是多么容易 。 这里只有五个选项。
解决整数运算不安全的问题
为了消除这个漏洞，Shamir 建议使用模运算，替换 上 哪里 и ——所有素数的集合。
让我们快速记住模运算是如何工作的。 带指针的时钟是一个熟悉的概念。 她使用的手表是 。 时针一过十二，就回到一。 该系统的一个有趣的特性是，仅通过查看时钟，我们无法推断出时针转了多少圈。 然而，如果我们知道时针已经经过了 12 四次，我们就可以使用一个简单的公式完全确定已经过去的小时数 哪里 是我们的除数（这里 ), 是系数（除数与原始数字相乘多少次而没有余数，这里 ）和 是余数，通常返回模运算符调用（这里 ）。 知道所有这些值可以让我们解方程 ，但如果我们错过了系数，我们将永远无法恢复原始值。
我们可以通过将该方案应用于我们之前的示例并使用来演示这如何提高我们方案的安全性 。 我们的新多项式函数 ，以及新的点 。 现在密钥保管者可以再次使用多项式插值来重构我们的函数，只是这次加法和乘法运算必须伴随模数约简 （例如 ).
使用这个新示例，我们假设攻击者了解了其中两个新点， ，以及公开信息 。 这次，攻击者根据他拥有的所有信息，输出以下函数，其中 是所有正整数的集合，并且 表示模系数 .
现在我们的攻击者再次发现 , 计算 :
然后他再次尝试 更换 в :
这次他遇到了严重的问题。 公式缺失值 , и 。 由于这些变量的组合有无数种，他无法获得任何额外的信息。
安全注意事项
沙米尔的秘密共享计划表明 信息论角度的安全。 这意味着即使对于具有无限计算能力的攻击者，数学也具有抵抗力。 然而，该电路仍然存在几个已知问题。
例如，Shamir 的方案并没有创建 待检查的片段，即人们可以随意呈现虚假片段并干扰正确秘密的恢复。 拥有足够信息的敌对碎片保管者甚至可以通过改变来产生另一个碎片 由您自行决定。 这个问题可以使用以下方法解决 可验证的秘密共享方案，例如费尔德曼的方案。
另一个问题是任何片段的长度都等于相应秘密的长度，因此秘密的长度很容易确定。 这个问题可以通过简单的方法解决 填充 具有任意数字的秘密，最多固定长度。
最后，值得注意的是，我们的安全担忧可能超出了设计本身。 对于现实世界的加密应用程序，通常存在侧通道攻击的威胁，攻击者试图从应用程序执行时间、缓存、崩溃等中提取有用的信息。 如果这是一个问题，那么在开发过程中应该仔细考虑使用保护措施，例如函数和恒定时间查找、防止内存被保存到磁盘，以及一些超出本文范围的其他注意事项。
演示
上 有沙米尔秘密共享方案的互动演示。 基于库的演示 ，它本身就是流行程序的 JavaScript 端口 。 请注意计算大值 , и 可能需要一些时间。
来源： habr.com