基于变形的EIGamal的门限秘密共享方案

李佳佳，谢 冬，沈忠华

（杭州师范大学理学院，浙江杭州310036）

0 引 言

随着计算机和网络通信的广泛应用，人们的生活、工作越来越多的涉及到电子商务，在电子商务中，密钥的安全管理成为一个极为重要的问题．秘密共享思想的提出便是为解决密钥的安全管理问题．秘密共享的概念最早于1979年被Shamir［1］和Blakley分别独立的提出来，并且给出了秘密共享的具体方案，随后越来越多专业人员对秘密共享进行较为深入的探索．近年来，秘密共享也越来越多的被应用到信息安全当中，用来保证一些重要信息的安全性，如何斌、黄杰等人的一种分布式可验证的多秘密共享方案［2］和孙宝林等人的RSA算法和Asmuth－Bloom秘密共享问题的研究［3］等．秘密共享的思想是将秘密s以合理的方式拆分，并将拆分后的每一个份额交由不同的参与者管理，而想要恢复秘密s，必须由若干个参与者一同合作，单个参与者是无法获得关于秘密s的任何信息．一类特殊的秘密共享叫做门限秘密共享方案，令t＜n是正整数，门限秘密共享方案是将秘密s拆分成n份，当且仅当不少于t个参与者共同合作时，才能恢复秘密s．在门限数字签名方案之中，利用插值多项式生成参与者密钥，是一种普遍并且有效的方法，如王斌、李建华的无可信中心的门限签名方案［4］和张建中、周莹莹的对一个门限签名方案的进一步分析和改进［5］等，在秘密共享方案之中，利用插值多项式生成参与者的密钥也是可行的．

现在，很多的秘密共享方案都较为理想化，但在实际应用中往往存在着一些困难，如权利分配过于平均．事实上，无论是一个公司还是政府机关，权利绝对平均分配都是不可能的．例如某公司有几笔巨款，为了合理的分配钱的用途，该公司的总裁要在他和他的可信职工之间共享这笔钱的账号和密码，利用这些可信职工手中的秘密份额和总裁手中的份额可以恢复出这笔钱的账号和密码，从而使用这笔钱．在钱的使用上，总裁和可信职工的权利不会是平均分配的，总裁具有一票否决权．本文基于插值多项式和变形的EIGamal型签名方案——Schnorr方案［6］，提出了一种安全的t，（）n门限秘密共享方案，该方案的安全性是基于离散对数的难解性．在新方案中，秘密分发者参与到群签名中来，没有秘密分发者的参与，群中t个或多于t个成员也无法恢复秘密值s．此外，系统还具有良好的稳定性．

1 方案描述

在本方案之中，有一个秘密分发者中心D（这里假设其是可信的）和参与者组成的集合P＝．方案分为6部分，分别为：参与者成员pi的私钥xi和公钥yi的获取、秘密分发者D的私钥a和公钥a0的获取、秘密份额的生成、参与者身份的验证、秘密份额的验证、秘密的恢复．

1．1 参与者成员pi的私钥xi和公钥yi的获取

（1）首先，秘密分发者D选取大素数p，并选取Zp的本原元g（g≠1），p、g作为系统参数，是公开的（这里假设在Zp中离散对数是难解的）；

（2）参与者pi（i＝1，2，…，n）随机选取xi∈［1，p－2］（当i≠j时，有xi≠xj），并计算：yi＝gximodp．在这里把xi作为pi的私钥，保密保留下来；yi作为pi的公钥，在系统内公开．如果有两个或若干个yi是相同的，为避免某个成员的私钥泄露，那么公钥相同的参与者必须同时再次选取私钥xi，并由yi＝gximodp计算公钥yi，直到所有的公钥都不相同为止；

（3）秘密分发者D随机选取ki∈［1，p－2］，并计算：这样秘密分发者D就得到λi，ti，并将ti发送给参与者pi；

（4）参与者pi（i＝1，2，…，n）用他的私钥计算：，得到ri．

1．2 秘密分发者D的私钥a和公钥a0的获取

秘密分发者D执行以下步骤来获取私钥a和公钥a0以及对秘密值s进行变换：

（1）随机选取大素数f、q，并且满足q／（f－1），q＞s；选取g∈Zf（g≠1），并且满足gq＝1modf，f、q、g作为系统参数，是公开的（这里假设在Zf中离散对数是难解的）；

（2）随机选取a∈［1，q］，计算同余式：a0＝gamodf，得到a0．把a作为秘密分发者D的私钥，秘密保存；a0作为秘密分发者D的公钥，在系统内公开；

1．3 秘密份额的生成

设（t，n）门限秘密共享方案满足n≥2t－1，所有的参与者组成的群记为Pn＝｛p1，p2，…，pn｝，参与者pi（i＝1，2，…，n）按照以下步骤生成自己的秘密份额：

（1）参与者pi（i＝1，2，…，n）随机地选取一个常数项为0的t－1次多项式Si（x）＝ai1x＋ai2x2＋…＋ait－1xt－1modq，并且为其他n－1个成员计算Sij＝Si（yj）modq，然后将Sij秘密地发给成员pj；

（3）现在定义函数S（x）＝；

（4）对S（x）求t－1次导数，若St－1（x）≠0modq，则S（x）是一个t－1次多项式．秘密分发者通过等式：mj＝S0＋Sj得到mj，即mj＝S（yj）；否则，重新执行（1）（2）（3）．

通过以上步骤得到参与者pi的秘密份额yi和mi（i＝1，2，…，n）．

1．4 参与者身份的验证

作为（t，n）门限秘密共享方案，只有当不少于t位参与者同意合作时才能恢复秘密s．不失一般性，设t位参与者同意恢复秘密s，他们组成的集合为．每一位参与者pi（i＝1，2，…，t）在系统内公布ri，秘密分发者D在系统内公布λi，则每一个人都可以通过验证式子λi＝ri是否成立来确定参与者pi的合法性．若式子成立，则pi具合法性，否则pi重新发送ri，直到式子λi＝ri成立为止．

这是因为ti＝gkimodp，只有合法参与者的私钥xi，才能使下式成立：

这就防止了不法分子伪造签名，进而伪造秘密份额．

1．5 秘密份额的验证

当同意恢复秘密的所有参与者pi（i＝1，2，…，t）都通过身份验证时，下面验证他们所提供的秘密份额的有效性．

每位参与者pi（i＝1，2，…，t）提供他的秘密份额yi和mi（i＝1，2，…，n），则有mi＝S（yi）．由于是（t，n）门限秘密共享方案，所以t个参与者利用多项式插值公式计算，可以得到．然后验证同余式是否成立．若成立，则pi（i＝1，2，…，t）提供的秘密份额yi和mi是有效的，否则是无效的．

1．6 秘密的恢复

当同意恢复秘密的所有参与者pi（i＝1，2，…，t）都通过身份的验证和份额密钥的验证，则证明所提供的yi和mi是有效的．在1．5中得出有效的S0，再利用秘密分发者D的私钥a通过同余式S0＝sakmodq，即s＝S0＋akmodq就可以恢复秘密值s．

2 性能分析

2．1 可行性

由1．3可知，S（x）是一个常数项为S0的t－1次插值多项式，不妨设S（x）＝S0＋s1x＋s2x2＋…＋st－1xt－1，当参与者pi（i＝1，2，…，n）通过身份的验证和份额密钥的验证后，提供他们的秘密份额yi和mi，得到插值条件：mj＝S（yj），可以建立线性代数方程组：

方程组的系数行列式为：

当i≠j时，xi≠xj，所以A≠0，因此S（x）是唯一确定的，S0也是唯一确定的，并且，其中

根据行列式按列展开可以得到：

2．2 安全性

本文当中在参与者同意恢复秘密之后，每一位参与者必须经过身份的验证和秘密份额的验证，才能合作恢复出合法有效的秘密值s．要通过身份的验证，必须保证等式λi＝ri的成立．而在等式的验证之中，起关键作用的是参与者pi的私钥xi，而只有合法的参与者才知道正确的xi，利用，才能保证等式（1）的成立，从而通过身份的验证．秘密份额的验证和秘密的恢复，是参与者首先利用插值多项式得出S0之后，验证等式成立后，分发者利用自己的私钥a和等式S0＝s－akmodq恢复出秘密值s．显然，与之前的身份验证一样，也是基于离散对数的难解性，可以防止秘密份额被伪造或者在传输过程被篡改，从而恢复出正确的秘密值s．

方案中，恢复秘密值s不仅需要参与者利用插值多项式得出S0，还需要秘密分发者D的私钥a，在这种情况下方案是安全的．方案当中，秘密分发者起很重要的作用．当参与者成员之中有部分成员没有参与时（只要小于n－t个），还是可以恢复秘密值s；但没有秘密分发者的参与，群中t个或多于t个成员也无法恢复秘密值s．秘密分发者的作用相当于上述总裁一票否决权．

3 结束语

在许多文章中，秘密共享方案大多是基于中国剩余定理和插值多项式的，如程宇、刘焕平可验证的Asmuth－Bloom门限秘密共享方案［7］等．本文把插值多项式应用在秘密共享方案之中，防止了秘密份额的伪造和篡改．一方面，插值多项式公式结构整齐紧凑，在理论分析中十分方便．另一方面，在方案之中，除了参与者之外，还有秘密分发者，秘密份额的产生、秘密值的恢复都需要秘密分发者，因此选取秘密分发者相当重要．

［1］A．Shamir．How to share a secret［J］．Communication of the ACM，1979，22（11）：612－6130．

［2］何斌，黄杰，黄根勋，等．一种分布式可验证的多秘密共享方案［J］．微计算机信息，2006（22）：61－62，82．

［3］孙宝林，胡斌．RSA算法和Asmuth－Bloom密钥共享问题的研究［J］．武汉科技学院学报，2002，15（3）：29－31．

［4］王斌，李建华．无可信中心的（t，n）门限签名方案［J］．计算机学报，2003，26（11）：1581－1584．

［5］张建中，周莹莹．对一个门限签名方案的进一步分析与改进［J］．计算机工程与应用，2012（19）：106－108．

［6］赵泽茂．数字签名理论［M］．北京：科学出版社，2007：42－43．

［7］程宇，刘焕平．可验证的Asmuth－Bloom门限秘密共享方案［J］．哈尔滨师范大学自然科学学报，2011，27（3）：35－38．