3.4.2　Shamir算法

回到本节开头的故事，冒险者们想到了在秘密分享中非常经典的Shamir算法[59]。

1. 示例

这个算法可以分为两个阶段，即份额分发阶段和秘密重构阶段。

（1）份额分发阶段

1）确定N和K的具体数值，比如N=5，K=3。

2）选择一个模数p，之后所有的计算都需要模这个数，比如p=17。

3）随机挑选打开保险箱需要的正确答案S，比如S=13。

4）随机挑选t-1个小于p的不相同的随机数，例如a1=10, a2=2。

5）分别计算，比如

6）将作为份额分给第个人，并且要求他不能分给其他人。

（2）秘密重构阶段

1）集齐任意K个人的份额，例如，（1, 8），（2, 7），（4, 0）。

2）列出方程组，其中是第i个人的份额，K是待解的答案，是未知量，解下列方程组

3）解上述方程组，可得S=13，a1=10，a2=2，打开保险箱的数字就是13。

2. 原理

现在，我们来介绍Shamir方案的原理。对于一个（K，N）-秘密分享门限方案，我们假设需要共享的秘密为S，那么只需要构造一个常数项为S的K-1次多项式，取任意N个不一样的点作为份额分给N个人，那么只要凑齐K个人，便可以解出系数和常数项。除了用示例中解方程组的方式以外，还可以用拉格朗日插值多项式的方式快速求解。

更加具体地说，Shamir方案是一个（K，N）-秘密分享门限方案，假设秘密为S，p是一个大素数，是模p的有限域。那么Shamir方案可以表示为接下来两个阶段。

• 份额分发阶段：首先分发者在有限域上任意构造一个K-1次的多项式，使得，并且。然后分发者再随机选择N个非零的，且互不相同的数，其中，并且计算，并且把分发给成员，作为他们的秘密份额。

• 秘密重构阶段：任意K个成员合作可以重构出秘密。假设由任意K个成员所组成的集合为B={i1,i2,…,iK}(|B|=K)，根据拉格朗日插值公式，可以计算出F(x)：

其中，，那么秘密就是S=F(0)。