禇晶晶，于秀源

（1.杭州師范大學(xué)理學(xué)院，浙江杭州310036；2.杭州師范大學(xué)護(hù)理學(xué)院，浙江杭州310036）

一類門限簽名方案的密碼學(xué)分析與改進(jìn)

禇晶晶1，2，于秀源1

（1.杭州師范大學(xué)理學(xué)院，浙江杭州310036；2.杭州師范大學(xué)護(hù)理學(xué)院，浙江杭州310036）

2008年，XIE等人提出了一種新的基于模秘密共享的門限簽名方案，即利用孫子定理來實現(xiàn)秘密共享的門限簽名方案.該文指出XIE等人的方案是不安全的：任意t人與DC合謀即可生成一個有效的門限簽名并嫁禍給他人；任意少于t人聯(lián)合DC也可生成一個有效的門限簽名.為克服該方案的安全性弱點，給出了一個改進(jìn)的方案.

門限簽名；秘密共享；模秘密共享；合謀攻擊

0 引 言

（t，n）門限簽名最早由Desmedt和Frankel［1］提出，其中t＜n，它是指由n個成員所組成的可參與簽名群中，任何t個或t個以上成員才能代表該群體生成一個有效的簽名（若有多于t個人想簽名，只需其中的t個人簽名即可），任何少于t個人所生成的簽名是無效的.門限簽名具有對簽名驗證人的匿名性及對可信中心的可被追蹤性.

直到現(xiàn)在，門限簽名得到了廣泛的研究，提出了各種各樣的門限簽名方案.有基于離散對數(shù)及二次剩余難解問題的［2］，有基于大數(shù)因式分解難解問題的［3］，也有基于橢圓曲線體制的［4］，但不論是基于何種數(shù)學(xué)難題的門限簽名都要以秘密共享作為它的基礎(chǔ).門限秘密共享［5］的主要思想是將一個密鑰分成若干子密鑰分配給各個成員保管，當(dāng)需要重構(gòu)密鑰或使用它進(jìn)行某種密碼運算時，必須多于特定數(shù)量（門限值）的成員才能共同完成，少于特定數(shù)量的任何成員組都不能計算得到此密鑰.

XIE等人在文獻(xiàn)［6］中指出文獻(xiàn)［7］［8］等很多基于拉格朗日插值共享的簽名方案是不能抵抗合謀攻擊后，又在Asmuth-Bloom模秘密共享思想［9］的基礎(chǔ)上提出了新的基于模秘密共享的門限簽名方案［6］.本文指出，文獻(xiàn)［6］的方案也是不安全的，該方案也不能抵抗內(nèi)部成員的合謀攻擊，而且可以利用合謀得到的群密鑰進(jìn)而偽造簽名并嫁禍他人.為克服他的安全性弱點，本文給出了一個改進(jìn)的方案，分析表明，本改進(jìn)方案是安全的.

1 XIE等人方案簡介［6］

XIE等人方案由系統(tǒng)初始化、部分簽名的生成、門限簽名的生成、門限簽名的驗證4個階段組成.

1.1 系統(tǒng)初始化階段

（1）可信中心TC選取兩個大素數(shù)p和q，q｜p-1，g是GF（p）上階為q的生成元，即gq≡1（modp），H（·）是一個安全的單向Hash函數(shù).設(shè)可參與簽名的群體中有n個成員，用集合G＝｛U1，U2，…，Un｝來表示該群體的所有成員.該群體中任何t個或t個以上成員可代表該群體進(jìn)行簽名（若有多于t個人想簽名，只需其中的t個人簽名即可）.

（2）可信中心TC隨機選取x∈RZq作為系統(tǒng)的群私鑰，y≡gxmodp則為系統(tǒng)的群公鑰.

（3）可信中心TC選取一個素數(shù)r（r＞x），一個正整數(shù)s以及n個正整數(shù)m1，m2，…，mn，它們滿足以下條件［9］：①gcd（mi，mj）＝1，i≠j，i，j＝1，2，…，n；②m1＜m2＜…＜mn，rm1m2…mn；③m1m2…mt＞rmnmn-1…mn-t＋2；④m1m2…mt＞x＋sr＞mnmn-1…mn-t＋2；⑤L［m1m2…mt］＞L［p］＋L［q］.其中L［x］代表x的長度.

（4）TC為每個Ui（i＝1，2，…，n）計算秘密鑰xi≡x＋sr modmi，Ui的公開鑰為yi≡gximodp.

（5）TC將xi通過秘密信道發(fā)送給各個Ui，公開p，q，g，H（·）及y，并將s，r，mi（i＝1，2，…，n）和yi（i＝1，2，…，n）存入一個只有群成員可以訪問的記事本①yi（i＝1，2，…，n）既然已經(jīng)公開，那這里所說的將它們也“存入一個只有群成員可以訪問的記事本”就沒有意義了..

1.2 部分簽名的生成階段

（1）設(shè)參與門限簽名的t個成員是U1，U2，…，Ut，要簽名的消息為M.每個Ui隨機選取ki∈RZq，并計算和廣播ri≡gkimodp給其他成員.

（2）每個Ui計算以及）＋kiR（mod m1m2…mt），其中Mi＝m1m2…mi-1mi＋1…mt，M-1iMi≡1modmi.將（（ri，ai），M-1i，Mi，mi，s，r）發(fā)送給指定的簽名收集者DC.

1.3 門限簽名的生成階段

于是，（A，R）是對消息M的門限簽名.

1.4 門限簽名的驗證階段

門限簽名的驗證人收到（A，R）后，通過下面的等式來驗證簽名的正確性：yH（M，R）RR≡gAmodp

2 對XIE等人方案的密碼學(xué)分析

本節(jié)給出了對XIE等人方案中群私鑰x的合謀解密攻擊、個人私密鑰xi的合謀解密攻擊、任意t人聯(lián)合DC嫁禍他人的合謀偽造攻擊和任意少于t人聯(lián)合DC的合謀偽造攻擊.

2.1 群私鑰x的合謀解密攻擊［10］

由1.1（5）可知，對于可參與簽名的群成員Ui來說，mi（i＝1，2，…，n）及s，r是可以通過訪問文件得知的，是不保密的.設(shè)參與過某次門限簽名的t個成員是Ui1，Ui2，…，Uit，若該小組成員徇私共謀，各自在這一小組內(nèi)部公開自己的私鑰，即可很容易地按照下面的方法求出群私鑰x：

設(shè)這t個私鑰是xi1，xi2，…，xit，則由孫子定理可知，存在唯一的x0，0≤x0＜mi1mi2…mit，滿足方程組

顯然x＋sr滿足上述方程組，而且由于r＞x及s的選取方式（見上文1.1（3）④），可知

因此，必是x0＝x＋sr，即x＝x0-sr是唯一確定的.

2.2 個人私密鑰xi的合謀解密攻擊

合謀小組由已獲得的群私鑰x及可訪問的存有mi（i＝1，2，…，n）等信息的文件，利用等式

xi≡x＋sr modmi就能解得xi1，xi2，…，xit以外的任意一個個人私鑰xij（j＝t＋1，t＋2，…，n）.

2.3 任意t人聯(lián)合DC嫁禍他人的合謀偽造攻擊

2.3.1 部分簽名偽造階段

如果上述共謀獲取群私鑰的t個成員希望某個文件可以被簽名驗證通過，又不想在某些意外情況下承擔(dān)責(zé)任，讓追蹤者追蹤不到自己而嫁禍給別人，即可進(jìn)行以下簽名（當(dāng)n≥2t時，合謀偽造尤其容易發(fā)生，因為合謀小組里的任何一個成員都可以逃脫意外發(fā)生時的追蹤，從而嫁禍給他們這t個成員以外的可參與門限簽名的另外t個成員）：

（1）設(shè)意欲偽造新的門限簽名的t個成員是Ω＝｛Ui1，Ui2，…，Uit｝，要簽名的消息為M′.他們想要栽贓的t個成員是Λ＝｛Ui，t＋1，Ui，t＋2，…，Ui，2t｝.Ω小組（一起或者由負(fù)責(zé)人）隨機選取t個kij∈RZq（j＝t＋1，

t＋2，…，2t），計算rij≡gkijmodp及

（2）然后Ω小組利用已獲得的Λ小組的私鑰及其他信息，計算

其中Mij＝mi，t＋1mi，t＋2…mi，j-1mi，j＋1…mi，2t，M-1ijMij≡1modmij.

并將（（rij，aij），M-1ij，Mij，mij，s，r）發(fā)送給指定的簽名收集者DC.

2.3.2 門限簽名偽造階段②若DC事先不知道誰參與簽名，則會根據(jù)mij去追蹤簽名人，所以在他知道了mij后，利用mij所對應(yīng)的yij來進(jìn)行驗證，因此Ω小組可以闖過DC的驗證從而借DC之手再次達(dá)到偽造門限簽名的目的；若DC事先就會被告知該次參與門限簽名的成員，且Ω小組說服了DC與其合謀來偽造門限簽名，則仍可以繼續(xù)偽造以闖過驗證人的驗證.

則對消息M′的門限簽名是（A′，R′）.

2.3.3 偽造的門限簽名通過驗證階段

驗證人收到（A′，R′）后，計算yH（M′，R′）R′R′≡gA′modp是否成立，由上面的陳述可知，等式成立，所以偽造的門限簽名通過了驗證人的驗證，偽造成功.

2.4 任意少于t人聯(lián)合DC的合謀偽造攻擊

驗證式y(tǒng)H（M，R）RR≡gAmodp中不含帶有簽名人身份的信息，也不含數(shù)字t，因此驗證人不能追蹤到簽名人，也不能確認(rèn)是否是t個人一起簽的名.只要DC同意，任意少于t個的簽名人都可以與DC合謀生成一個可闖過驗證人驗證的簽名.

3 對XIE等人方案的改進(jìn)

3.1 系統(tǒng)初始化

（1）同XIE等人方案中1.1（1）.需要注意，改進(jìn)的方案中，令n＜2 t（更安全并符合實際情形中票數(shù)過半原則），而這n個參與者其中t人參與簽名的不同組合有Ctn個［11］，把群秘密分配到Ctn個不同組合中去.

（2）為這Ctn個不同組合分別構(gòu)造其對應(yīng)的秘密鑰Ej（j＝1，2，…，Ctn），使得群秘密E是與所有Ctn個共享秘密Ej有關(guān)的和，即滿足，其中f是一個關(guān)于Ej的函數(shù).可通過下述方法來構(gòu)造Ej：

首先任意選取t對不同的數(shù)mi∈RZq，xi∈RZq，mi為成員Ui的身份標(biāo)識，xi為成員Ui的私密鑰.利用孫子定理構(gòu)造第一個子群的私密鑰（mod M1），如果E1≡0（mod M1），則重新選擇某個mi或xi，這樣就可以得到第一個簽名組共享的子秘密E1，其中③M1＝m11m12…m1t，M1i＝M1i≡1（modm1i），1≤i≤t.

繼上一節(jié)t對不同數(shù)的選擇后，現(xiàn)再取第t＋1對不同的mi∈RZq，xi∈RZq，與前面選取的任意t-1對數(shù)結(jié)合，用孫子定理構(gòu)造t個Ej，j＝2，3，…，t＋1，滿足所有的共享子秘密Ej≠0（mod Mj）且兩兩不等，任意多個的和模上M不等于零，即（modM），其中λ＝1，2，…，i在此表示不同λ個的取法標(biāo)記.按照此方法，可以構(gòu)造個子秘密Ej，j＝1，2，….

（4）隨機選取dj∈RZq，j＝1，2，…，，計算Dj≡gdjmodp.計算群中每一個成員Ui的公鑰yi≡modp，并計算組的密鑰Ej所對應(yīng)的≡E-Ej（mod M），再計算Rj使之滿足≡Dj·Rjmodp， j＝1，2，…，.

（5）TC在系統(tǒng)內(nèi)公開參數(shù)p，q，g，H（·），y，Dj，Mj，yi，只有系統(tǒng)內(nèi)的成員可以訪問這些數(shù)據(jù).并將xi與mi通過秘密信道發(fā)送給各個Ui，對于任意一個Ui，可以通過驗證方程yi≡gximodp是否成立來判別得到的xi是否有效的密鑰.再把Rj與mi發(fā)送給DC.

3.2 部分簽名的生成階段

（1）設(shè)由群G中t個成員構(gòu)成的第j個子群G0＝｛Uj1，Uj2，…，Ujt｝同意代表群體對消息m簽名，則?Uji∈G0隨機選取kji∈RZq，并計算和廣播rji≡gkjimodp給其他成員，i＝1，2，…，t.

（2）每個Uji計算modp以及

其中Mji＝Mji≡1modmji.

并將（（rji，aji），M-1ji，Mji，mji）發(fā)送給指定的簽名收集者DC.

3.3 門限簽名的生成階段

如果所有的等式都成立，則DC生成消息m的門限群簽名（A，R，D）.

3.4 門限簽名的驗證階段

門限簽名的驗證人收到（A，R，D）后，通過下面的等式來驗證簽名的正確性：

③m11，m12，…，m1t為一開始選擇的m1，m2，…，mt的任意排列.為方便敘述，把上述子群記為第一組，下標(biāo)第一個數(shù)字代表組號，以下將用字母j表示組號，易知j＝1，2，…，Ctn.

其中α＝H（m，R，D）.

3.5 安全性分析

（1）從以上的驗證式可知，驗證者根據(jù)簽名無法知道哪些成員參與了簽名，但在發(fā)生糾紛時TC可以通過Dj找到對應(yīng)的簽名成員.因此本方案具有匿名性和可追蹤性.

（2）改進(jìn)的方案在系統(tǒng)初始化階段中使用了子群密鑰的形式.在一個子群中成員只秘密掌握xi與mi，他們不知道屬于自己子群的Ej，只有TC知道這個密鑰.若想解得Ej，有兩個可能途徑：一是通過這一等式，求出的值，這將面臨離散對數(shù)問題；二是通過直接計算求得，那必須得子群中所有的成員坦誠出自己所掌握的秘密xi與mi（從部分簽名發(fā)送到DC的過程中可知mi并非嚴(yán)格保密，但不影響以下的分析），這樣的合謀是毫無意義的，因為泄露自己的私秘密不能得到群以外的秘密.

（3）群私鑰E的獲取也必須通過解決離散對數(shù)問題或是整個群內(nèi)成員的秘密坦誠才能成功，因此個人私鑰xi，子群密鑰Ej及群私鑰E都難以得到.

（4）該方案可抵抗合謀攻擊，因為在初始化條件中，我們設(shè)置了n＜2t，而簽名是以子群為單位的，若要偽造簽名并嫁禍給他人，則在某一子群中個人間的合謀泄密行為，在接下來的偽造過程中，至少一人會在其他的子群簽名中會反而害到自己，所以，首先這是一種情理上的不可能性.且由（3）可知，因為各種私鑰的難解性，偽造也不可能.另外，由文獻(xiàn)［6］4.1中2）的分析可知，本方案也是不能偽造部分簽名的.

由上可知，改進(jìn)的方案可以抵抗第二部分所提出的一切攻擊，所以改進(jìn)的方案是安全的.

4 結(jié)束語

本文對XIE等人方案進(jìn)行了合謀解密攻擊和合謀偽造攻擊，表明該方案是不安全的，任意t人與DC合謀即可生成一個有效的門限簽名并嫁禍給他人，任意少于t人聯(lián)合DC也可生成一個有效的門限簽名.本文給出了一個改進(jìn)方案，彌補了原方案的安全性缺陷.

［1］Desmedt Y，F(xiàn)rankel Y.Shared Generation of Authenticators and Signatures［C］／／Advances in Cryptology-Crypto'91.Berlin：Springer-Verlag，1992：457-469.

［2］費如純，王麗娜，于戈.基于離散對數(shù)和二次剩余的門限數(shù)字簽名體制［J］.通信學(xué)報，2002，5（23）：65-69.

［3］蔣瀚，徐秋亮，周永彬.基于RSA密碼體制的門限代理簽名［J］.計算機學(xué)報，2007，2（30）：241-247.

［4］彭慶軍.一種基于橢圓曲線的可驗證門限簽名方案［J］.通信技術(shù)，2008，3（41）：104-106.

［5］朱培棟，姚諦，趙建強，等.基于秘密分享的安全組通信協(xié)議設(shè)計與實現(xiàn)［J］.計算機工程與應(yīng)用，2007，43（30）：116-119.

［6］Xie Qi，Shen Zhonghua，Yu Xiuyuan.Threshold Signature Scheme Based on Modular Secret Sharing［C］／／International Conference on Computational Intelligence and Security，Suzhou：IEEE Computer Society，2008：442-445.

［7］Jan J K，Tseng Y M，Chien H Y.A threshold signature scheme withstanding the conspiracy attack［J］.Communications of the Institute of Information and Computing Machinery，1999，2（3）：31-38.

［8］Xie Qi，Yu Xiuyuan.Improvement of WPL's（T，N）threshold signature scheme［C］／／Proceedings of 16thInternational Conference on Computer Communication，Beijing：ICCC，2004，9（2）：1032-1035.

［9］Asmuth C，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory，1983，29（2）：208-210.

［10］于秀源，薛昭雄.密碼學(xué)與數(shù)論基礎(chǔ)［M］.濟南：山東科學(xué)技術(shù)出版社，1993：145-146.

［11］楊建喜，劉東.一種安全的門限群簽名方案及橢圓曲線上的實現(xiàn)［J］.計算機工程與科學(xué)，2009，31（2）：17-19.

Cryptanalysis and Improvement of a Threshold Signature Scheme

CHU Jing-jing1，2，YU Xiu-yuan1
（1.College of Science，Hangzhou Normal University，Hangzhou 310036，China；2.College of Nursing，Hangzhou Normal University，Hangzhou 310036，China）

In 2008，Xie et al.proposed a new threshold signature scheme based on modular secret sharing，which means secret sharing can be achieved by Chinese remainder theorem.The paper indicated that their scheme is insecure.Any t signers who conspire with DC can forge a valid threshold signature and frame others，and any less than t individuals who conspire with DC also can forge a valid threshold signature.To overcome the security weakness，the paper provided a modified scheme.

threshold signature；secret sharing；modular secret sharing；collusion attack

11.3969／j.issn.1674-232X.2012.02.013

TP309 MSC2010：94A60

A

1674-232X（2012）02-0157-05

2010-11-19

國家自然科學(xué)基金項目（10671051）.

褚晶晶（1986—），女，碩士，主要從事數(shù)論及其應(yīng)用研究.E-mail：cjj0814＠hotmail.com