基于中国剩余定理的秘密共享方案*

李洁平，韦性佳

0 引 言

秘密共享是密码学的一个重要工具。1979年，Shamir[1]和Blakley[2]两人分别基于拉格朗日多项式和射影几何理论，提出了两种不同的秘密共享方案，对现代密码学的研究具有非常重要的作用。之后，有关秘密共享方面的研究成为许多研究者的课题。1983年，Asmuth和Bloom[3]等人基于中国剩余定理提出了一种的新秘密共享方案。该方案结构简明，理论知识容易理解，且较Shamir的秘密共享方案效率更高。

1985年，Chor等人[4]第一次提出可验证的理念,并且构造了一种可验证的秘密共享方案。1992年，Pedersen[5]提出了一种更方便和实用的秘密共享方案。但是，早期的秘密共享方案存在计算量大、效率相对较低等问题。直到Neal Koblitz[6]等人发现在有限域上椭圆曲线离散对数问题（ECDLP）是难解问题后，椭圆曲线（Elliptic Curve，简称ECC）就以它计算量小、效率较高等优势快速成为密码学研究的一个重要工具。2005年，Qing.L[7]等人提出了一个基于中国剩余定理的可验证秘密共享方案。该方案只有在秘密分发者诚实的情况下，检测出参与者之间的欺骗。

1997年，Anderson[8]首次提出前向安全性理论（Forward Security）；2001年，Itkis和 Reyzin[9]提出一种前向安全签名方案，实现了有效的签名验证和存储，但效率相对较低。2002年，Kozlov[10]等人利用一种快速更新算法，提出了一种前向安全的签名方案，不仅周期短，而且适合移动计算。目前，国内学者对前向安全性理论也做了大量研究，如王彩芬等人[11]提出的具有前向安全性的秘密共享方案,基于有限域上离散对数难解问题（ECDLP）和强RSA假设，有效实现了秘密的前向安全性，且具有很强的实践价值。本文方案在已有秘密共享方案[12-14]研究成果的基础上，提出了一种基于中国剩余定理的可验证方案，利用椭圆曲线计算量小、效率高的优势，减少了方案的运算成本，同时方案基于强RSA假设[15-16]，实现了方案的前向安全性。

1 预备知识

1.1 椭圆曲线离散对数问题（ECDLP）

给定有限域GF(q)上的椭圆曲线E和生成元P∈E(GF(q))，且阶为q，对∀Q∈〈P〉，寻找a∈[0,q-1]，使得Q=aP，称为椭圆曲线离散对数问题。

1.2 双线性变换

定义1：设(G1,+)和(G2,+)是2个阶为素数p的循环群，其中前者为加法群，后者为乘法群。令g为G的生成元，如果满足以下性质，则称变换e∶G1×G1→ G2为双线性变换：

（1）双线性。对任意P1、P2和Q∈G1，有：

（2）非退化性。存在P∈G1即e(P,P)≠1，即e(P,P)是G2的生成元。

（3）可计算性。对任意P1、P2∈G1，存在有效的算法计算e(P1,P2)。

1.3 中国剩余定理（孙子定理）

给定一组两两互素的正整数m1,m2,…,mk和整数c1,c2,c3,…,ck，则同余方程组为：

对于模M具有唯一的解：

其中：

1.4 前向安全性理论

前向安全性理论（Forward Security Theory）具体如下：（1）Pi(i=1,2…n)将S的有效期分为T个时间段，1,2…T；（2）在整个有效期内，公钥PKU不变，但第j个时间段私钥SKU随着时间段j的改变而变换；（3）第j个时段时，Pi计算Sj=f (Sj-1)，其中f是一个单向函数；（4）算出Sj后，立即删除Sj-1，这样即使攻击者A获得了第j个时间段的Sj，也不能获得关于S0,S1,…,Sj-1的任何信息，如图1所示。

图1 密钥更新流程

1.5 系统中的记号与参数

P：参与者符号，而Pi为第i个参与者，有Pi∈ P,i=1,2,…,n；

D：秘钥分配者，且D∉P；

K：要分享的秘密（初始者）。

2 提出方案

2.1 系统初始化

（1）D选择mi∈i=1,2,…,n 且 (mi,mj)=1,mi为素数；选择初始共享秘密x0∈

（2）计算如下参量：

①秘密份额：

（3）公开系统公钥：

将(ci,0,mi,0)作为私钥份额通过秘密通道发送给用户Pi。

2.2 子秘密的更新

当Pi收到初始私密份额(ci,0,mi,0)后，计算ci,j=作为第j个时间段的子份额，然后立即删除, j=1,2…T。

2.3 秘密的验证

2.3.1 初始阶段秘密的验证

Pi选择ki,0∈RZ*q，计算初始公钥：

然后，进行D验证：

若等式成立，则Pi诚实的；同样，Pi通过等式可验证D的份额(ci,0,mi,0)是有效的。

2.3.2 验证更新子秘密

这个阶段，用户Pi通过下面过程研究第j个时间段秘密份额的有效性：

然后，验证 e ( P , Qi,j) =?e( Mi, Ki) e( Ci, Ki)。若等式成立，D可以验证Pi更新子秘密的正确性，而Pi也可以验证D的诚实性。

3 秘密恢复

第j个时间段，所有用户{P1,P2,…,Pn}利用自己的秘密份额(ci,j,mi)，合作完成如下过程：

（1）计算 M=m1m2…mn；

（3）利用中国剩余定理，计算第j个时间段的共享秘密：

当秘密恢复成员计算出共享秘密后，计算：

（1）得到第j个时间段的共享秘密xj；

（2）利用式（9）中的共享秘密xj和系统公钥X，验证等式：

若等式成立，则说明恢复的共享秘密是有效的。

4 正确性及安全性分析

4.1 方案的正确性

定理1：方案在初始阶段秘密验证了Pi和D是诚实的，即等式（8）正确。

证明：根据已知条件，有：

等式成立。

证明：根据已知条件，有：

等式成立。

定理3：方案中秘密恢复的验证是正确的，即等式（10）正确。

等式成立，所以恢复的秘密是正确的。

4.2 方案的安全性

定理4：公钥{Ci,0,Mi,Xj,Ci,Ki,Qi,j}不会泄露私钥{ki,j,ci,j,mi,xj}的任何信息。

证明：若敌手已知 Ci,0、Mi、Ci、Ki、Qi,j想获取私钥ki,j、ci,j、mi，由于Ki,j=ki,jP，Ci,j=ci,jP，Qi,j=ki,j(mi+ci,j)P，Mi=miP，则必须解决椭圆曲线离散对数问题。但是，ECDLP是难解决的。所以，敌手无法通过公钥获取得到私钥的任何信息。

定理5：方案具有前向安全性

假设敌手已经掌握第j个时间段的共享密钥xj,想要获取前j个时间段的共享秘密xl,l=0,1,…, j-1，有两种方式：

（1）若想通过Xl=xlP解出xl，必须解决椭圆曲线离散对数问题。但是，ECDLP是难解决的。所以，敌手无法获得前j个时间段xl；

5 结 语

本文利用中国剩余定理，提出了一种具有前向安全的可验证秘密共享方案。该方案的创新之处在于：在秘密更新阶段，将强RSA问题融入子秘密的更新即，每个用户利用自己的私钥通过非交互式的方式更新自己的份额，极大地节省了可信中心的运算量；方案实现了参与者的可验证性，利用基于椭圆曲线的双线性对每个时间段的参与者实现互相验证，这样可以及时检测出系统中的欺诈行为，保障系统的安全性。

[1] Shamir A.How to Share a Secret[J].Communication of the ACM 1979,22(11):612-613.

[2] Blakley G R.Safeguarding Cryptographic Keys[C].Proceedings of AFIPS 1979 National Computer Conference,1979:313-317.

[3] Asmuth C,Bloom J.A Modular Approach to Key Safeguarding[J].IEEE Transactions on Information Theory,1983,29(02):208-210.

[4] Chor B,Doldwasser S,Micali S,et al.Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults[C].Proceedings of the 26th IEEE Symposium on Foundations of Computer Sciences,1985:383-395.

[5] Pedersen T P.Non-interactive and Informationtheoretic Secure Verifiable Secret Sharing[C].Cryptology CRYPTO’91,1992:129-140.

[6] Koblitz N.Elliptic Curve Cryptosystems [J].Mathematics of Computation,1987,48(48):203-209.

[7] Qiong L,Zhifang W,Xiamu N.et al.A Non-interactive Modular Verifiable Secret Sharing Scheme[C].In ICCCAS 2005:International Conferenc on Communications,Circuits and Systems,2005:84-87.

[8] Anderson R.Two Remarks on Public-key Cryptology[C].Fourth ACM Conference on Computer and Communications Security,1997.

[9] Itkis G,Reyzin L.Forward-secure Signatures with Optimal Signing and Verifying[C].Intenational Cryptology Conference on Advances in Cryptology,2001:332-354.

[10] Kozlov A,Reyzin L.Forward-secure Signature with Fast Key Update[C].International Conference on Security in Communication Networks,2002:241-256

[11] 王彩芬,刘国军,贾爱库等.具有前向安全性质的秘密共享方案[J].电子与信息学报,2006,9(28):1974-1976.WANG Cai-fen,LIU Guo-jun,JIA Ai-ku,et al.A Secret Sharing Scheme with Forward Security[J].Journal of Electronics & Information Technolo gy,2006,9(28):1974-1976.

[12] 芦殿军,张秉儒,赵海兴.基于多项式秘密共享的前向安全门限签名方案[J].通信学报,2009,30(01):45-49. LU Dian-jun,ZHANG Bing-ru,ZHAO Hai-xing.Forward-secure Threshold Signature Scheme Based on Polynomial Secret Sharing[J].Journal on Communicatio ns,2009,30(01):45-49..

[13] 田有亮,马建峰,彭长根等.椭圆曲线上的信息论安全的可验证秘密共享方案[J].通信学报,2008,29(10):45-50.TIAN You-liang,MA Jian-feng,PENG Chang-gen,et al.Information-theoretic Secure Verifiable Secret Sharing Scheme on Elliptic Curve Group[J].Journal on Communic ations,2008,29(10):45-50.

[14] 李慧贤,蔡皖东,裴庆祺.可验证秘密共享方案的设计与分析[J].西安电子科技大学学报:自然科学版,2008,35(01):148-151.LI Hui-xian,CAI Wan-dong,PEI Qing-qi.Design and Analysis of a Verifiable Secret Sharing Scheme[J].Journal of Xidian University(Natural Science Edition),2008,35(01):148-151.

[15] 汪保友,胡运发.基于强RSA假设的签名方案[J].软件学报,2002,13(08):1729-1734.LI Hui-xian,HU Yun-Fa.Signature Scheme Based on Strong RSA Hypothesis[J].Journal of Software,2002,13(08):1729-1734.

[16] 徐文华,贺前华,李韬.基于强RSA假设的数字签名方案[J].华中科技大学学报:自然科学版,2008,36(12):24-26.XU Wen-hua,HE Qian-hua,LI Tao.Signature Scheme Based Strong RSA Assumption[J].J. Huazhong Univ. of Sci.& Tech.(Natural Science Edition),2008,36(12):24-26.