[密码学】一文读懂SHAMIR门限方案

秘密共享-SHAMIR门限方案

前言

先来看一个故事，1月8日，贵州省锦屏县平秋镇圭叶村开始了第七届村主任换届选举。这个藏身大山深处的偏僻小山村，最近刚刚因一枚奇特的公章而成为了人们关注的焦点。为了在村里进行民主理财管理，一年多前，村民想出了一个点子，把村财务公章分成五瓣交由5位选出的村民代表掌管，专门审核村干部的开销。近日消息一传出后，顿时引起了外界的广泛热议。这枚“五瓣章”更是被网友称为史上最牛公章。

那么在密码学当中，有没有这种方案，必须满足一定人数才能解出来整个秘密消息，而少于预设的人数阈值则解不出来这个秘密消息呢？

Shamir(t,w)门限方案

下面来简单聊聊Shamir提出的门限方案

初始化阶段

庄家(Dealer)，后文我们把庄家记作「D」，在 当中选择w个不同的非0元素，分别记作 其中 ，此处显然要求有限域当中元素个数要大于w的，然后D把 的值发送给 ，这里 是公开的。

分配共享阶段

然后假设D需要共享的秘密信息为 。D在 当中独立随机的选择t-1个元素 。

然后根据如下的规则计算 其中

然后，D将 的值发送给 作为共享。

还原秘密的值

在上面的方案当中，庄家构造了一个次数至多是t-1的一个多项式，此多项式的常数项即为需要共享的秘密信息。然后对于每个参与者得到的是该多项式上面的一个点 。

假设参与者 需要确定秘密K的值，那么我们可以得到

其中 是庄家D选择的多项式。然后根据上面所得到的坐标，我们可以得到t个具有t个未知数的线性方程组，如果这些方程是线性无关的，这样我们就可以得到唯一解，因此我们可以最终求得 也就是需要共享想秘密信息。

有关如何通过坐标来求得多项式，这就涉及到我比较头疼的内容了，因为我高数这块学的实在是不咋地，这个可以用拉格朗日插值法来搞，不过对于上面的图当中的例子，直接解方程问题也不大，下面我先来带着读者用解方程的方法来搞一下。

解方程实现

对于每个参与者能拿到的坐标如下:

、、

然后我们带入上面的多项式，得到下面的三个式子

我们要在上面这一堆式子当中找到 当中找到在 的解。

这个用高斯消元法，直接来解，因为我们实际上只需要解出来 然后呢，消元的时候，就可以有目的性的，我们直接剩下我们所需要的。

然后下面我们手动来算一下(我才不是为了水字数)，第一行乘以14 然后和第二行相加。然后第一行乘以12加到第三行。

然后，第二行乘以15加到第一行，

然后解得 ，因此的最终庄家所共享的秘密K = 13，和上面我们描述的一致。

拉格朗日插值法

「拉格朗日插值公式」假定p是素数， 是 中的不同元素，假定是当中的元素，无需不同，存在次数至多为m的唯一多项式,使得，并且多项式如下:

注意对于拉格朗日插值法当中的运算，也都是基于有限域上来计算的。我们带入一下前文所用到的参数，可得:

同样的注意到我们是不需要计算出来完整的多项式的，我们只需要计算 。然后我们将 x = 0带入公式(1)，可得

然后注意到最开始有关shamir门限方案有关 的说明，我们可以提前预计算

因此，对于共享的秘密信息K我们可以写成

好了，通过上面得到的公式(3)我们来计算一下上面的例子。

这样，我们就可以计算出来最终共享秘密的值

参考资料

• 密码学原理与实践(第三版)  [加]Douglas R.Stinson
• https://www.zhihu.com/question/58333118/answer/262507694
• https://iuk.one/1033-1010.pdf
• https://news.sina.com.cn/c/p/2008-01-10/035814707702.shtml