王新++解建军（等）

【 摘 要 】 基于有限域GF（q） 上多项式Lagrange插值理论，Shamir提出秘密共享（t， w）门限方案。本文讨论Shamir门限方案算法，并对算法实现进行算例验证，同时对部分共享更新、新参与者的加入、全部共享的再分配等方面进行分析。

【 关键词 】 秘密共享；Lagrange插值；Shamir门限方案；有限域；密钥管理

Study of Scheme on Sharing Secret on Finite Field GF（q）

Wang Xin 1，2 Xie Jian-jun 1，2 Sun Hong-liang 1 Liu Jin-sheng 1

（ 1.College of Mathematics and Information Science， Hebei Normal University HebeiShijiazhuang 050024；

2.Hebei Key Laboratory of Computational Mathematics and Applications HebeiShijiazhuang 050024 ）

【 Abstract 】 Based on Lagrange polynomial interpolation theory of finite field GF（q）， Adi Shamir presented the first secret sharing method so-called Shamir （t， w） threshold scheme. An algorithm description of Shamir threshold scheme is given in this paper， some actual data are used to verify the availability， the article also discusses the question for update of partial sub sharing secret ， redistribute for all parties new share and so on.

【 Keywords 】 secret sharing； lagrange interpolation； shamir threshold scheme； finite field；key management

1 引言

Shamir在文献[1]中基于有限域GF（q）上多项式Lagrange插值理论提出秘密共享思想，Shamir（t， w）门限方案把秘密或密钥K分成w个子部分，每个子部分由一个参与者秘密保存，要求至少利用t个参与者子秘密才可以重建密钥K，少于t个参与者则无法构建出K。

2 Shamir （t， w）门限方案算法

秘密共享Shamir（t， w）门限方案的算法包括初始参数选取、共享的计算与分配、原始秘密重建三部分。 下文中D代表庄家，负责分配所有的共享，P代表所有参与者的集合且D？埸P，Pi∈P代表第i个参与者，xi 代表Pi的公开身份，yi 代表Pi的共享。

2.1 初始参数选取

庄家D随机选取不同的w个非零值xi∈Zq（1≤ i ≤w）作为每个参与者Pi （1≤ i ≤w）的公开身份，q为素数且大于K和w。

2.2 共享的计算与分配

假设D欲共享秘密K∈Zq。 D随机秘密选择t-1非零值ai∈Zq （1≤ i ≤ t-1）。 D构造下面的函数：

计算yi =a（xi）（1≤ i ≤w），并将yi秘密分发给Pi作为共享，其中K = a（0） = a0。

2.3 原始秘密重构

不妨设t个参与者的集合S={Pi1，Pi2，…，Pit}希望重构秘密K。根据多项式Lagrange插值理论，可唯一地构造出次数至多为t-1的多项式y=c（x）使得c（xik）= yik （1≤ k ≤ t），由多项式的唯一性可知y=c（x）=a （x），即它们是同一个多项式， c（x）的构造形式如下：

（2-2）

由K= a（0）可得如下的表达式：

（2-3）

定义

有

（2-5）

3 实验数据及算例验证

本文利用Java实现Shamir类进行Shamir（t， w）门限算法分析，并对文献[1]中的数据验证，其中q=31847，t=5，w=10，重构密钥值。表1-表3分别对应t个参与者为{P1， P3， P5， P7， P9}、{P2， P4， P6， P8， P10}、{P1， P3， P6， P8， P9}时进行计算密钥值。……