Shamir门限方案的实现及应用优化建议

1979年，Shamir利用有限域上的多项式方程结合拉格朗日插值公式构造了一个（t，n）门限方案。

设GF（p）是一有限域，共享密钥k∈GF（p）。可信任中心给n（n＜p）个共享者A_i（1≤i≤n）分配共享密钥的过程如下：

1）可信任中心TA随机选择一个t-1次多项式：

其中，g（x）∈GF（p）[x]；a₀=k就是共享密钥。

2）可信任中心TA在GF（p）中选择n个非零的、互不相同的元素x₁，x₂，…，x_n，分别计算：

y_i=g（x_i），i=1，2，…，n

也就是找出曲线g（x）上的n个点。

3）把第i个点，即把（x_i，y_i）作为秘密份额分配给第i个共享者A_i，其中x_i是公开的，通常可以直接取共享者A_i的身份ID_i，y_i是属于共享者A_i的秘密份额，i=1，2，…，n。

每个（x_i，y_i）对被看成多项式g（x）在二维空间上的一个坐标点。由于g（x）是t-1次多项式，因此t个或t个以上的坐标点可唯一确定g（x），从而共享密钥k也确定下来，即k=g（0）；反过来，如果坐标点小于t个，则无法确定g（x），也无法确定k。

假如已知t个秘密份额（x_r，y_r），r=1，2，…，t，由拉格朗日插值公式可重建多项式g（x）如下：

显然，只要知道g（x），易于计算出共享密钥k。由于k=g（0），因此有

即k是t个秘密份额（x_r，y_r），r=1，2，…，t的线性组合。若令

则有(www.xing528.com)

由于所有x_i（i=1，2，…，n）都是预先公开知道的，因此如果预先计算出所有b_r（r=1，2，…，t），则可以加快多项式重构时的运行速度。

【例7-2】 在Shamir门限方案中，假设t=3，n=5，p=17，可信任中心TA将5个秘密份额分配给5个用户A、B、C、D和E保管。现有其中任意3个用户A、C和E到场，他们的秘密份额分别为（1，8）、（3，10）和（5，11）。请重构出多项式g（x），求解共享密钥k。

【解析】 已知A、C和E的秘密份额分别为（1，8）、（3，10）和（5，11），由于

该式的累加和中的三项分别为

所以

共享密钥k=g（0）=13

如今，Shamir门限方案是一个备受关注的秘密共享方案，它有如下优点：

1）它是一个完全的门限方案。由于份额的分布是等概率的，因此仅知道t-1个或者更少的份额与不知道任何份额的效果是一样的。

2）每个秘密份额的大小与共享密钥的大小相近。

3）可以扩充新的秘密共享者，且计算新的份额不影响任何原有份额的有效性。

4）它的安全性不依赖于任何未证明的假设。