门限多重影子秘密共享方案及应用

杨 捷

(南京工业职业技术学院 图书馆，江苏 南京 210023)

引言

现代密码与信息安全其体制的安全性密切依赖于密钥的使用。因此，对秘密数据的保管成为密码学与信息安全领域一个极其重要的研究内容。1979 年 Shamir［1］和 Blakley［2］分别基于 Lagrange 内插多项式与射影几何的理论各自独立地提出了(t，n)门限秘密共享方案。其含义是把秘密数据分拆成n个子数据分交n个人保管，使得当有t个人或t个以上的人提供子数据就能汇集起来进行运算恢复出原先的秘密数据，而少于t个人就不行。这一秘密共享的思想为秘密数据安全存放给出了一个科学的框架。由于秘密数据安全存放十分重要，三十多年来许多学者对此进行了大量研究，给出了许多有创意的方案。Stadler［3］提出了在线秘密共享机制，引入公告牌发布一些有关信息;还有一些方案针对多秘密共享防欺诈［4，5］等方面进行了研究。但是这些方案都有一个致命弱点，就是让分发者掌握了秘密。如果分发者把掌握到的秘密出卖给攻击者，那么体制就形同虚设了。因为有此隐患，有些方案假设分发者是可信的，并在分发者是可信的前提下讨论问题。然而这一前提过于理想化。本方案不让分发者知道秘密，而只传给他影子秘密，让门限方案构成对影子秘密的保护，影子秘密与秘密持有者的私钥协同作用构成对秘密的保护。相应于这种思路，本文在秘密集与共享集之间给出了一种结构上的联系，即多个秘密均由共享集中的若干成员提供，对此进行了讨论，给出了相应于这种联系的共享方案。方案中虽然有一个分配中心(分发者)，但不必为可信的;方案中也用了公告牌，共享者不独可以阅读、下载，对公告内容如有疑问还可提出质疑。

1 方案的构成

1.1 初始化阶段

设{K1，K2，…，Km}为秘密集，{U1，U2，…，Um，Um+1，…，Un}为秘密共享集，D为子秘密分发者。D取大素数p，q满足q|p－1;g∈，g的阶为q;h:{0，1}*→为抗碰撞，单向的Hash函数。Ui以αi为私钥，βi为公钥，βi=gαimodP，i=1，2，…，n 秘密Ki∈为秘密共享集中的成员Ui所持有。Ui计算ki=(Ki+h(αi))modq，称 ki为 Ki的影子秘密，i=1，2，…，m。U1，U2，…，Um将 k1，k2，…，km传 给 D，Um+1，Um+2，…，Un不持有秘密，仅仅参与秘密共享。本方案需要一个公告牌，D可以公布、更新公告牌上的内容，共享者可以阅读下载，也可对公告内容提出异议［6］。在初始化阶段 D 在公告牌上公布 p，q，g，h以及 h1，h2，…，hm，这里 hi是 ki的散列值，i=1，2，…，m。对公告牌上的hi，Ui计算h(ki)，核对h(ki)=hi是否成立。如果成立，认为传给D的ki，D已安全收到，如果h(ki)≠hi则Ui对D在公告牌上公布的数值hi进行质疑提出异议，直到D在公告牌上给出ki的正确的散列值为止。对数值ki除Ki的持有者Ui之外其他的人无权过问。i=1，2，…，m

1.2 子秘密的生成与分发

(1)D 在公布 k1，k2，…，km的散列值之后，如果U1，U2，…，Um未提出异议，D 便认为 k1，k2，…，km在传送过程中未受到窜改。此时D便以k1，k2，…，km以及t个随机数a1，a2，…，at∈(t＜ n)为系数作Zq上的m+t－1次多项式

(2)D 计算 f(1)，f(2)，…，f(n)，将(1，f(1))，(2，f(2))，…，(n，f(n))分别传给 U1，U2，…Un保管;计算 f(n+1)，f(n+2)，…，f(n+m)，将(n+1，f(n+1))，(n+2，f(n+2))，…，(n+m，f(n+m))公布于公告牌。

(3)D 计算多项式 f(x)的系数 k1，k2，…，km，a1，a2，…，at的变换值 k'1=gk1modp，k'2=gk2mod p，…，k'm=gkmmod p，a1'=ga1modp，a'2=ga2modp，…，a't=gatmodp，然后用变换值构造验证公式gf(x)=k'1并将它公布于公告牌。

(4)Ui收到(j，f(j))后，将x=j代入验证公式，如果等式成立则接收(j，f(j))作为子秘密保管，不成立则向D质疑要求对错误数据进行更正。

(5)对于公告牌上的数对(j，f(j))j=n+1，n+2，…，n+m共享集中的成员，以及其他任何人都可将j的值代入验证公式进行验证。若都成立，则说明D没有欺诈，若有数对代入使等式不成立，此时验证者应立即向D提出异议。

1.3 秘密恢复阶段

如果Ui(1≤i≤m)想恢复Ki，他可以委托一位恢复者先去恢复影子秘密ki。恢复者可以是共享集中的任何人，也可以是Ui自己。恢复过程如下:

(1)恢复者从掌握子秘密的n个共享者手中提取t个人的子秘密，即t个秘密数对，例如提取的是(1，f(1))，(2，f(2))，…，(t，f(t))再从公告牌上下载m个数对(n+1，f(n+1))，(n+2，f(n+2))，…，(n+m，f(n+m))。

(2)恢复者将所得数对用公告牌上的验证公式逐个验证。

(3)当t+m个数对全部验证无误后记它们为(xi，yi)i=1，2，…，m+t并作 Zq上的插值多项式

(4)如果得出的插值多项式是m+t－1次的(如低于m+t－1次，恢复者需另取一个子秘密替换原先使用过的任一子秘密重构插值多项式，直到是m+t－1次为止)恢复者便对该多项式中xi－1次方的系数求散列值。

(5)如果这一散列值为公告牌上的hi时，恢复者将该项系数传送给Ui。

(6)Ui收到该系数后，求其散列值，得到hi后由Hash函数的抗碰撞性，他可以相信该系数就是影子秘密ki。然后Ui便可利用ki与自己的私钥去恢复秘密 Ki=(ki－ h(αi))modq。

值得指出的是恢复者在获得m+t个数对后可跳过步骤(2)直接去构造插值多项式，并对xi－1次方的系数求散列值。只有在散列值不是hi时，为了查找哪个数对被篡改才需要用步骤(2)通过验证公式逐个验证。

2 安全性分析

本方案的安全性依赖于离散对数的难解性与Hash函数的抗碰撞性与单向性;而不依赖系统成员的诚信品质。

1.在系统内部共享者的不诚信行为可以表现在他将窜改过的子秘密(x，y)传给恢复者。恢复者将(x，y)在验证公式上进行验证，只有当等式gy=成立时才会接收。这就是说共享者的不诚信行为要想得逞必须在已知x或者说在已知时从上面的等式中解出离散对数y，无疑这是困难的。

2.而恢复者的不诚信行为可以表现在当他恢复了f(x)之后他把xi－1的系数ki换成异于ki的∈Zq传给Ui，要使欺诈行为不被发现他必须找到满足h)=h(ki)的∈Zq，由哈希函数的抗碰撞性可知这也是困难的。

3.又分发者的不诚信行为可能表现在他在构造多项式f(x)时用xi－1代替kixi－1(ki≠)，目的是使Ui(1≤i≤m)的影子秘密ki不能恢复。但是要使欺诈行为成功同样需要满足h()=h(ki)=hi，由上面的讨论可知找到这样的是困难的。

4.分发者、恢复者及系统外的攻击者假设他们获得了影子秘密ki(1≤i≤m)，由于他们不知道秘密持有者的私钥αi所以无法利用公式Ki=(ki－h(αi))modq获得秘密 Ki，而要从 Ui的公钥 βi找出私钥 αi需解 βi=gαimodp，这又是困难的。

3 应用的例子

为了说明本方案的应用现举一个具体的例子。

一次重要的考试，出了m份试卷，这些试卷不能丢失、不能泄露、也不能被篡改，问题是如何存放它们。

假设m份试卷其上的考题都是来自某些公开的题库，且是从题库中第1000题至9999题这一范围内选出的，这就是说考题在题库中的编号都是4位数，在此情况下试卷的存放可转化为相关数据的存放，方法是将试卷中考题在题库中的编号依次连接起来形成一个整数，m份试卷形成m个整数，记它们为K1，K2，…，Km。试卷不能泄露，这些相关的整数也就不能泄露，它们是必须保密的秘密数据，我们称K1，K2，…，Km为秘密集。现在用本文所介绍的方案将它们存放，依照方案的步骤首先由秘密持有者(出题者)对各秘密数据分别加密形成影子秘密k1，k2，…，km，再对影子秘密使用(k，n)门限方案，其主要步骤是由分发者将影子秘密分成n个子秘密，分交n个共享者保管，完成这一步后便将试卷、秘密数据、影子秘密全部销毁，剩下的只是n个共享者手中保存的子秘密，别的什么都没有了。当要重新获得第i(1≤i≤m)份试卷时恢复者从n个掌握子秘密的共享者中提取k(﹤n)个人的子秘密，按方案中的方法操作可重新获得影子秘密ki并将它提交给秘密持有者(出题者)，出题者对影子秘密ki验证无误后对它解密，重新获得秘密数据Ki，将此数据每4位为一个分段并将这些分段视为考题在相应题库中的编号，从编号就可以得到考题，这样就恢复了第i份试卷。根据对方案的安全性分析，可知秘密数据的存放是安全的，能有效的防止秘密数据的丢失、篡改和泄露，因秘密数据可产生试卷也就等于说试卷不会丢失、不会被篡改、不会泄露。因此应用本方案方法就解决了试卷的存放问题。

4 结束语

本文给出的方案有别于传统的门限方案，其特点是(秘密所有者的)私钥与门限共同承担了对秘密的保护，也同时承担了对秘密的恢复，但是私钥、门限两者在方案中的功能还是各有侧重的，保护主要靠私钥，恢复主要靠门限。在使用公告牌的方法上本方案也有别于传统的做法，提出了对公告牌上的内容共享者如有异议可对分发者提出质疑，这一做法使得系统成员之间可以互相制约，分清责任。

由于门限方案中仅出现秘密的影子，所以一切数据都可在公共信道上传输，又摆脱了方案对分发者诚信的依赖，同时也不怕外部人员的攻击，所以此方案既是安全的又是经济的。

［1］ SHAMIR A.How to share a secret［J］.Communications of the ACM，1979，22(11):612-613.

［2］ BLAKLEY G R.Safeguarding cryptographic keys［C］//Proceedings of National Computer Conference.Montvale，NJ:AFIPS Press，1979，48:313-317.

［3］ STADLER M.Publicly verifiable secret sharing［C］//Proc.of Advances in Cryptology-Eurocrypt'96.Berlin:Springer-Verlag 1996，190-199.

［4］ Yang CC，Chang T Y，Hwang M S，A(t，n)multi-secret sharing scheme［J］.Applied Mathematics and Computation，2004，151(2):483-490.

［5］ 黄东平，刘锋，王道顺，戴一奇.一种安全的门限多秘密共享方案［J］.电子学报，2006，34(11):1937-1940.

［6］ 杨捷，李继国.基于密钥协商的门限多秘密共享方案［J］.计算机工程，2010，36(20):153-154.