摘  要： 在基于椭圆曲线离散对数的安全机制的前提下，讨论了(t，n)门限加密模式。在该模式中，系统公钥由成员协同产生， t个或t个以上成员可以间接地解开密文。由于(t，n)门限加密模式秘密信息较少，所以具有良好的安全性，且计算复杂度较低。
关键词： 秘密共享；可信中心；加密

    门限秘密共享由SHAMIR[1]和BLAKLEY[2]于1979年独立提出，他们分别利用有限域中的Lagrange插值多项式和几何映射构造出了(t，n)门限秘密共享方案，这些方案存在着可信中心。随后许多学者对可信中心的存在情况进行了深入研究。1991年，INGEMARSSON和SIMMONS[3]提出了一种无可信中心秘密共享思想。HARN[4]于1994年提出了一种基于ELGamal签名的、不需要可信中心的门限群签名方案，该方案没有可信中心，但是超过门限值的成员能够协同恢复其他成员的私钥。参考文献[5-7]等分别提出了一个无需可信中心的门限签名方案，但签名者之间需要进行秘密通信来交换信息。参考文献[8]提出的门限签名方案无需秘密通信。随后，很多学者对这方面进行了大量的研究和改进[9-10]。
    目前，无可信中心秘密共享的研究主要集中在门限数字签名上，对于门限加密的研究尚且不多。为此，本文在基于椭圆曲线公钥体制的前提下，提出了无可信中秘密共享加密模式。该模式中，成员协同作用生成各自的秘密份额，参与者之间无需传递任何秘密信息。由秘密份额计算出相关的可公开信息，从而生成系统公钥。解密过程中，也是由合作的参与者通过秘密份额计算一个可验证的伪份额，最终间接地完成解密，从而保证了系统私钥可重复使用。利用公开信息来验证参与者提供的有用信息，在很大程度上提高了系统的执行效率。
1 预备知识
1.1 SHAMIR的门限秘密共享方案
(1)初始化阶段：秘密分发者D随机地从GF(q)(q为素数且q>n)中选取n个不同的非零元素x1，x2，…，xn，D将xi分配给Pi(i=1，2，……，n)，且xi的值是公开的。
(2)秘密分发阶段：设共享秘密为s∈GF(q)，D随机地选择GF(q)中的t-1个元素a1，a2，…，at-1，构造一个t-1次多项式f(x)=s+a1x+a2x2+…+at-1xt-1 mod q，D计算yi=f(xi)(i=1，2，…，n)，yi作为s的子秘密。
    (3)秘密恢复阶段：t个成员Pi(i=1，2，…，t)交换各自的秘密份额，得到：(x1，y1)，(x2，y2)，(x3，y3)，…，(xt，yt)，就可通过式(1)恢复共享秘密s。
    s=■yi■■mod q(1)
1.2 椭圆曲线实现 Elgamal密码体制
首先选取一条椭圆曲线Ep(a，b)，p为一个奇素数，G为椭圆曲线的基点，q为G的阶，Ep(a，b)和G公开。设明文为m，将明文通过编码嵌入到曲线上得点Pm，再对点Pm进行加密。另设用户UA及UB。
(1)UB加密：用户UA选SA作为私钥，并以PA=SAG作为公钥。任一用户UB如果想向UA发送消息Pm，可选取一随机正整数k，产生以下点对作为密文：Cm={kG，Pm+kPA}。
(2)UA解密：UA解密时，以密文点对中的第2个点减去用自己的秘密钥与第1个点的倍乘，即Pm+kPA-SAkG=Pm+k(SAG)-SAkG=Pm。
2 本方案的描述
2.1 系统初始化
初始化过程完成各参与者的私钥、秘密份额及系统公钥的产生。假设P={P1，P2，…，Pn}为n个成员的集合，每个成员Pi(Pi∈P)拥有私钥di，IDi是每个Pi唯一的身份标识，t为门限值。首先选取一条椭圆曲线Ep(a，b)，G为椭圆曲线的基点，q为G的阶，Ep(a，b)和G公开。
(1)Pi∈P在[1，q-1]中随机选择一个整数di作为私钥，公钥为diG，并产生随机数集{ai，k|k=1，2，…，t-1}。构造一个t-1次多项式：
fi(x)=di+ai，1x+…+ai，t-1xt-1mod q(2)
其中di=fi(0)。Pi把fi(IDj)发送给其他n-1个成员Pj(j≠i)∈P。fi(IDi)自己保留。再计算验证参数：?琢ik=ajkG，k∈{1，２，…，t-1}。
每个Pj(j≠i)∈P接收到其他n-1个成员的广播信息后，Pj通过式(3)验证fi(IDi)：     
fi(IDj)G=diG+■(IDj)k?琢ik(3)
若式(3)成立，则fi(IDj)有效；否则，Pj拒绝fi(IDj)，并要求Pi重新发送。
(2) 秘密份额的生成：每个Pi从其他n-1个成员接收到了所有正确的秘密份额以后，通过式(4)计算各自的秘密份额，并广播Yi=F(IDi)G mod q。
F(IDi)=■fj(IDi)mod q(4)
(3) 系统公钥生成：系统私钥F(0)=■F(IDi)■■mod q，基于拉格朗日插值多项式，利用公开信息计算系统公钥：
y=F(0)G modq
=(■F(IDi)■■mod q)G mod q
 =[(■F(IDi)■■mod q)·(G mod q)]mod q
 =(■F(IDi)■■G)mod q(5)
 =■(■■F(IDi)G mod q)mod q
 =■(■■Yi)mod q
然后公开y。
2.2 加密过程    
为不失一般性，假设明文为m，将m通过编码映射到曲线上得点Pm，再对点Pm进行加密。
(1)UA选取一个随机数k，并使其满足1≤k≤q-1。
(2)计算C1=kG mod q和C2=Pm+ky mod q，产生点对密文：Cm={C1，C2}。
(3)将密文Cm发送给P。
2.3 验证过程
P中任意t个或t个以上的参与者合作可以解开密文，为不失一般性，设P中t个参与者集合为W={P1，P2，…，Pn}。收到密文后，W中每个成员Pi利用自己的秘密份额，通过式(6)各自计算出si(i=1，2，…，t)，参与者彼此交换份额si。
si=F(IDi)■■C1(6)
每个Pi(j≠i)∈P能够通过判断等式siG=C1Yi■■是否成立来验证Pi(i=1，2，…，t)所提供的份额的真伪。如果等式成立，那么Pi所提交的份额是正确的，接着执行下面的步骤；否则就要求Pi重新发送份额。
2.4 解密过程
当收到了t份si后，就通过式(7)计算得出F(0)C1 modq。
 F(0)C1 modq=[(■F(IDi)■■mod q)·(KG mod q)]mod q
=(■F(IDi)■■KG)mod q
=■(F(IDi)■■KGmod q)(7)
=■(F(IDi)■■C1)
=■si
解密时，以密文对中的第2个点减去用组私钥与第1个点的倍乘，即：
Pm=Pm+[k(F(0)G mod q)-F(0)kG mod q] mod q=
Pm+k(F(0)G mod q)mod q-F(0)kG mod q=
Pm+ky mod q-F(0)kG mod q=(8)
    C2-F(0)C1=
    C2-∑si
3 方案分析
３.1 方案特点
(1)本方案不需要可信中心管理参与者的密钥，成员协同产生各自的秘密份额，每个参与者只需保留一个自己的私钥和一份秘密份额。
(2)在初始化阶段，系统公钥由达到门限值的成员组协同产生并公开，但这些成员组是无法共同生成系统私钥F(0)的，即P中任一成员都不知道系统私钥。
(3)秘密份额产生后，公开Yi=F(IDi)G mod q，系统公钥不是由系统私钥直接产生，而是由公开信息间接生成。在解密过程中，每个合作的参与者只需向解密者提交一个由秘密份额计算的、可验证的伪份额si，即可间接达到解密效果。
3.2 安全性分析
(1)系统私钥F(0)是安全的。基于求解椭圆曲线上离散对数问题的困难性，由系统公钥y=F(0)G mod q无法计算出系统私钥F(0)，由■si=F(0)C1 mod q也不能计算出系统私钥F(0)，从公钥diG(i∈{1，２，…，n})无法得到di(i∈{1，２，…，n})，所以无法生成系统公钥F(0)=■fi(0)mod q=■di mod q。对于由每个成员的秘密份额得出的公开信息Yi=F(IDi)G mod q(i∈{1，２，…，t})，由于无法获取秘密份额F(IDi)，故无法生成系统私钥F(0)=■F(IDi)■■mod q。
(2)能够有效地阻止主动攻击。如果有伪造者想要假冒成合法成员P中的一员(如Pi)，那么它要构造一个多项式fi′(x)。但是，由于伪造者不知道Pi的私钥di，所以fi′(0)≠di。如果fi′(0)≠di，则份额fi′(IDj)就不满足式(3)的验证，从而达不到伪造的初衷，所以伪造者不能阻止诚实成员生成系统公钥。
(3)解密前能够验证Pi是否提供虚假信息来欺骗其他参与者。解密过程中，解密者通过判断式siG=C1Yi■■成立与否来验证各成员提供的信息的真伪。除了si以外，其他信息均公开或可计算，所以要伪造一个新的满足条件等式的si是不可行的。
(4) 有别于传统的研究方法，本方案中对防欺骗研究侧重于安全交换协议。具体做法体现在方案中秘密份额的生成和认证，能在事前有效地阻止恶意成员的欺骗行为。是否满足式(3)是判断份额正确性的标准。
本文构造了一个无可信中心的秘密共享加密模式，每个参与者只需要产生一个私钥，秘密份额由成员协同产生，成员协同产生用于加密的系统公钥，t个或t个以上成员利用秘密份额计算并提供正确的信息，可以间接地解开密文。本文是基于椭圆曲线公钥密码体制的，系统私钥的安全性基于椭圆曲线上的离散对数问题的难解性。该方案中，每个成员需保留的秘密信息只有一个自己的私钥和一份秘密份额，即使存在着超过门限值的成员协同作用，也无法将其他成员的私钥恢复，使无可信中心的特点及优点得到了较好的实现。
参考文献
[1] SHAMIR A. How to share a secret[J]. Communications of the ACM， 1979，22(11)：612-613.
[2] BLAKLEY G R. Safe guarding cryptographic keys[C]，Proceedings of National Computer Conference. Montvale， NJ： AFIPS Press， 1979： 313-317.
[3] INGEMARSSON I， SIMMONS G L. A protocol to set up shared secret schemes without the assistance of a mutually trusted party[C]. Proceedings of Eurocrypt’90， Mar 21-24， 1991： 266-282.
[4] HARN L . Group-oriented(t，n) threshold digital signature scheme and digital multisignature[J]. IEEE Proceeding of Computer and Digital and Techniques， 1994， 141(5)： 307-313.
[5] 王斌，李建华.无可信中心的 (t，n) 门限签名方案[J].计算机学报，2003，26(11)：1581-1584.
[6] MIYAZAKI K， TAKARAGI K . A threshold  digital signature scheme for a smart card based system. IEICE Trans. Fundamentals， 2001， E84-A(1)： 205-213.
[7] CHANG Ting Yi， YANG Chou Chen， HWANG Min Shiang. A threshold signature scheme for group communications without  a shared distribution center. Future Generation Computer Systems， 2004， 20(6)： 1013-1021.
[8] TAKARAGI K， MIYAZAKI K， TAKAHASHI M， et al. A threshold digital signature issuing scheme without secret communication[EB/OL]. http： //grouper. ieee. org/groups/1363/Study Group/ contributions/th-sche. pdf， 2002-12-01.
[9] 庞辽军，谭示崇，王育民.一个预防欺诈的(t，n)门限数字签名方案[J].电子与信息学报，2007，29(4)：895-897.
[10] 庞辽军，李慧贤，王育民.一个(t，n)门限签名-(k，m)门限验证的群签名方案[J].计算机科学，2006，33(11)：76-78.