一類門限簽名方案的密碼學分析與改進

第１１卷第２期２ｏ１２年３月

杭州師範大學學報（自然科學版）

ｍａｒ．２０１２

一類門限簽名方案的密碼學分析與改進

褚晶晶　，於秀源

（１．杭州師範大學理學院，浙江杭州３１００３６；２．杭州師範大學護理學院，浙江杭州３１００３６）

摘要：２００８年，ｘｉｅ等人提出了一種新的基於模秘密共享的門限簽名方案，即利用孫子定理來實現秘密共享的門限簽名方案．該文指出ｘｉｅ等人的方案是不安全的：任意ｔ人與ｄｃ合謀即可生成乙個有效的門限簽名並嫁禍給他人；任意少於ｔ人聯合ｄｃ也可生成乙個有效的門限簽名．為克服該方案的安全性弱點，給出了乙個改進的方案．

關鍵詞：門限簽名｝秘密共享；模秘密共享；合謀攻擊中圖分類號：ｔｐ３０９

文獻標誌碼：ａ

文章編號

０　引言

（ｔ，ｎ）門限簽名最早由ｄｅｓｍｅｄｔ和ｆｒａｎｋｅｌ口］提出，其中ｔ％ｎ，它是指由ｎ個成員所組成的可參與簽名群中，任何ｔ個或ｔ個以上成員才能代表該群體生成乙個有效的簽名（若有多於ｔ個人想簽名，只需其中的

ｔ個人簽名即可），任何少於ｔ個人所生成的簽名是無效的．門限簽名具有對簽名驗證人的匿名性及對可信中心的可被追蹤性．

直到現在，門限簽名得到了廣泛的研究，提出了各種各樣的門限簽名方案．有基於離散對數及二次剩

餘難解問題的　，有基於大數因式分解難解問題的引，也有基於橢圓曲線體制的　，但不論是基於何種數

學難題的門限簽名都要以秘密共享作為它的基礎．門限秘密共享的主要思想是將乙個金鑰分成若干子金鑰分配給各個成員保管，當需要重構金鑰或使用它進行某種密碼運算時，必須多於特定數量（門限值）的成員才能共同完成，少於特定數量的任何成員組都不能計算得到此金鑰．

ｘｉｅ等人在文獻ｅ６］中指出文獻ｅ７］ｅ８］等很多基於拉格朗日插值共享的簽名方案是不能抵抗合謀攻

擊後，又在模秘密共享思想的基礎上提出了新的基於模秘密共享的門限簽名方案　］．本

文指出，文獻ｅ６］的方案也是不安全的，該方案也不能抵抗內部成員的合謀攻擊，而且可以利用合謀得到的群金鑰進而偽造簽名並嫁禍他人．為克服他的安全性弱點，本文給出了乙個改進的方案，分析表明，本改進

方案是安全的．

１　ｘｉｅ等人方案簡介＿６］

ｘｉｅ等人方案由系統初始化、部分簽名的生成、門限簽名的生成、門限簽名的驗證４個階段組成．

收稿日期

**專案：國家自然科學**專案

通訊作者：褚晶晶（１９８６），女，碩士，主要從事數論及其應用研究

１５８１．１系統初始化階段

杭州師範大學學報（自然科學版）２０１２往

（１）可信中心ｔｃ選取兩個大素數ｐ和ｇ，ｑ１ｐ一１，ｇ是ｇｆ（）上階為ｇ的生成元，即ｇ　三１（ｍｏｄｐ），

ｈ（）是乙個安全的單向ｈａｓｈ函式．設可參與簽名的群體中有ｎ個成員，用集合ｇ一來表示該群體的所有成員．該群體中任何個或個以上成員可代表該群體進行簽名（若有多於ｔ個人想簽

名，只需其中的ｔ個人簽名即可）．

（２）可信中心ｔｃ隨機選取　∈　ｚ　作為系統的群私鑰，蘭　ｍｏｄｐ則為系統的群公鑰．

（３）可信中心ｔｃ選取乙個素數ｒ（ｒ＞ｚ），乙個正整數ｓ以及個正整數ｍ　，，…，ｍ　，它們滿足以下條件一１，ｉ≠ｊ，ｉ，ｊ一

…ｍ一臥鞏其中ｌ［］代

表的長度．

（１）ｔ【』為每個計算秘密鑰ｚ　三的公開鑰為三三三ｒｍｏｄｐ．

（）ｔｌ、將通過秘密通道傳送給各個ｕ　，公開ｐ，ｑ，ｇ，ｈ（）及　，並將５，ｒ，（ｉ一１，２，…，）和

，（１．２。…川）仔入乙個只有群成員可以訪問的記事本①．

１．２部分簽名的生成階段

（１）沒參與門限簽名的ｔ個成員是己，，要簽名的訊息為ｍ．每個ｕ　隨機選取忌　∈　ｚ　，併計

算和廣播ｒｇ，ｍｏｄｐ給其他成員．

（２）每個ｕ　計算ｒ三ｌｌｆｉｍｏｄｐ以及ｎ　三志其中ｍｉ—ｍｌｍ２

，＝１將（（，ａ　），

傳送給指定的簽名收集者ｄｃ．

１．３門限簽名的生成階段

ｔｄｃ首先計算ｒ三然後驗證等式及ｇ　三

ｉ＝１ｔ

如果所有的等式都成立，則ｄｃ計算

ａ三（（ｎ　一

ｉ一１於是，（ａ，ｒ）是對訊息ｍ的門限簽名．１．４　ｆ－１限簽名的驗證階段

門限簽名的驗證人收到（ａ，ｒ）後，通過下面的等式來驗證簽名的正確性：ｙｈ『ｍ』尉ｒ　蘭　ｍｏｄｐ

２　對ｘｉｅ等人方案的密碼學分析

本節給出了對ｘｉｅ等人方案中群私鑰的合謀解密攻擊、個人私金鑰ｚ　的合謀解密攻擊、任意ｔ人聯合ｄｃ嫁禍他人的合謀偽造攻擊和任意少於ｔ人聯合ｄｃ的合謀偽造攻擊．

２．１群私鑰的合謀解密攻擊ｌｌ。］

由１．１（５）可知，對於可參與簽名的群成員ｕ　來說，ｍ　（ｉ一１，２，…，）及ｓ，ｒ是可以通過訪問檔案得知的，是不保密的．設參與過某次門限簽名的ｔ個成員是ｕ

…，，若該小組成員徇私共謀，各自在這

一小組內部公開自己的私鑰，即可很容易地按照下面的方法求出群私鑰ｚ：

設這ｔ個私鑰是ｚ，…，，則由孫子定理可知，存在唯一的一ｍ　，滿足方程組

ｘ三是≤ｆ

顯然　＋　ｒ滿足上述方程組，而且由於ｒ＞ｘ及ｓ的選取方式（見上文１．１（３）④），可知

因此，必是ｚ。＝　＋ｓｒ，即ｚ—　。一ｓｒ是唯一確定的．

既然已經公開，那這裡所說的將它們也「存入乙個只有群成員可以訪問的記事本」就沒有意義了

第２期褚晶晶，等：一類門限簽名方案的密碼學分析與改進１５９

２．２個人私金鑰ｘ　的合謀解密攻擊

合謀小組由已獲得的群私鑰ｚ及可訪問的存有ｍ　（ｉ一１，２，…，）等資訊的檔案，利用等式

ｚ，三　＋ｓｒｍｏｄｍ　就能解得

３２…，ｚ　以外的任意乙個個人私鑰（一

２．３　任意ｔ人聯合ｄｃ嫁禍他人的合謀偽造攻擊

２．３．１部分簽名偽造階段

如果上述共謀獲取群私鑰的ｔ個成員希望某個檔案可以被簽名驗證通過，又不想在某些意外情況下

承擔責任，讓追蹤者追蹤不到自己而嫁禍給別人，即可進行以下簽名（當ｎ≥２ｔ時，合謀偽造尤其容易發生，因為合謀小組裡的任何乙個成員都可以逃脫意外發生時的追蹤，從而嫁禍給他們這ｔ個成員以外的可

參與門限簽名的另外ｔ個成員）：

（１）設意欲偽造新的門限簽名的ｆ個成員是ｑ一｛己，…，ｕ　），要簽名的訊息為ｍ　．他們想要栽贓

的ｔ個成員ｊ．＼一

｝．ｑ小組（一起或者由負責人）隨機選取ｔ個

２ｔｔ＋２，…，２），計算ｒ三ｇ　ｍｏｄｐ及ｒ　三ｌｊｍｏｄｐ．

ｊ＝１（２）然後ｑ小組利用已獲得的ａ小組的私鑰及其他資訊，計算

ａ＂三其中三ｌｍｏｄｍ　．

並將，ｍ　ｓ，ｒ）傳送給指定的簽名收集者ｄｃ．

２．３．２門限簽名偽造階段②

２ｔ（１）ｄｃ首先計算ｒ　三ｉｌｒｍｏｄｐ，然後驗證等式

ｊ—１及ｇ。ｑ三　ｊｍ　～　ｍ

ｒｒ　ｍｏｄｐ．

２￡（２）若上式都成立，則ｄｃ計算ａ　三

ｊ一斗１

則對訊息ｍ　的門限簽名是（ａ　，ｒ　）．

２．３．３偽造的門限簽名通過驗證階段

驗證人收到（ａ　，尺　）後，計算ｙⅲ　，ｒ　三ｍｏｄｐ是否成立，由上面的陳述可知，等式成立，所以偽造的門限簽名通過了驗證人的驗證，偽造成功．

２．４任意少於ｔ人聯合ｄｃ的合謀偽造攻擊

驗證式中不含帶有簽名人身份的資訊，也不含數字ｔ，因此驗證人不能追蹤到簽名人，也不能確認是否是ｚ個人一起籤的名．只要ｄｃ同意，任意少於ｔ個的簽名人都可以與ｄｃ合謀生成

乙個可闖過驗證人驗證的簽名．

３　對ｘｉｅ等人方案的改進

３．１系統初始化

（１）同ｘｉｅ等人方案中１．１（１）．需要注意，改進的方案中，令ｎ％２　（更安全並符合實際情形中票數過半原則），而這個參與者其中ｔ人參與簽名的不同組合有ｃ　個ｅ，把群秘密分配到ｃ　個不同組合中去．

（２）為這個不同組合分別構造其對應的秘密鑰ｅ，（一使得群秘密ｅ是與所有ｃ　個

②若ｄｃ事先不知道誰參與簽名，則會根據ｍ　去追蹤簽名人，所以在他知道了ｍ　後，利用ｍｄ所對應的來進行驗證，因此ｎ小組可以闖過ｄｃ的驗證從而借ｄｃ之手再次達到偽造門限簽名的目的；若ｄｃ事先就會被告知該次參與門限簽名的成員，且ｎ小組說服了ｄｃ與

其合謀來偽造門限簽名，則仍可以繼續偽造以闖過驗證人的驗證．

１６ｏ杭州師範大學學報（自然科學版）２０１２年

共享秘密ｅ，有關的和，即滿足ｅ一∑　（ｅｓ），其中ｆ是乙個關於ｅ　的函式．可通過下述方法來構造ｅ：

ｊ一１首先任意選取ｔ對不同的數為成員ｕ　的身份標識，ｚ　為成員ｕ　的私金鑰．利用孫子定理構造第乙個子群的私金鑰ｅ　三

如果ｅ　三０（ｍｏｄｍ　），則重新選擇某

ｍ　ｍ　一ｍ１

，ｍ個／／＇，／或ｚ　，這樣就可以得到第乙個簽名組共享的子秘密ｅ　，其中③ｍ　一

ｍｌ三繼上一節ｔ對不同數的選擇後，現再取第　＋１對不同的與前面選取的任意一１對

數結合，用孫子定理構造ｔ個ｅ　，ｊ一２，３，…，＋１，滿足所有的共享子秘密且兩兩不等，任

意多個ｇｍ７ｍ的和模上ｍ不等於零，即∑ｅｍ

ｊ＝１≠０（ｍｏｄｍ），其中在此表示

不同個的取法標記．按照此方法，可以構造ｃ　個子秘密ｅ，，ｊ一１，２，…，ｃ　．

（３）由上，記群秘密為ｅ三

，＝１…　，ｍｊ一三

１（ｍｏｄｍｉ）．計算群公鑰　—ｇｅｍｏｄｐ，並儲存ｍ　、ｚ　和己，之間的對應關係，以便對簽名進行追蹤．

（４）隨機選取ｄ　∈　ｚ　，ｊ一１，２，…，ｃ　，計算ｄ，三ｇｄｍｏｄｐ．計算群中每乙個成員ｕ　的公鑰三ｇ　ｍｏｄｐ，並計算ｃ：組的金鑰ｅ　所對應的ｅ—ｓ三再計算ｒ　使之滿足ｇ　三ｄ　ｒ　ｍｏｄｐ，

ｊ一１，２，…，ｃ　．

（５）ｔｃ在系統內公開引數只有系統內的成員可以訪問這些資料．並將與ｍ　通過秘密通道傳送給各個，對於任意乙個ｕ　，可以通過驗證方程ｙ　三ｇ　ｍｏｄｐ是否成立來判別得到的３２。是否有效的金鑰．再把ｒ　與ｍ　傳送給ｄｃ．

３．２部分簽名的生成階段

（１）設由群ｇ中個成員構成的第個子群ｇ。一同意代表群體對訊息簽名，則ｖ∈ｇ。隨機選取ｋ　ｅ　ｚ。，並計算和廣播三ｇ　ｍｏｄｐ給其他成員，一１，２，…，ｔ．

（２）每個ｕ　計算ｒ三¨　ｍｏｄｐ以及

ｉ一１ａ，三ｉｚ　ｍ　ｍ　＋尼

其中ｍｊ一ｍ　，嗨　ｍｌｍｏｄｍ

並將傳送給指定的簽名收集者ｄｃ．

３．３門限簽名的生成階段

ｄｃ首先計算０三口　ｍｏｄｐ，然後驗證等式

ｉ—ｌｍ　ｍｊ三ｌｍｏｄｍ　及ｇ「三

如果所有的等式都成立，則ｄｃ生成訊息的門限群簽名計算ａ三並取ｒ一　，ｄ—ｄ　．

３．４　ｆ－１限簽名的驗證階段

門限簽名的驗證人收到（ａ，ｒ，ｄ）後，通過下面的等式來驗證簽名的正確性：

ｈ（ｍ，ｒ，ｄ）一一　），

為一開始選擇的ｍ　，ｍｚ，…，的任意排列．為方便敘述，把上述子群記為第一組，下標第乙個數字代表組號，以下將用字母ｊ表示組號，易知ｊ一１，２，…，ｃ　．

第２期褚晶晶，等：一類門限簽名方案的密碼學分析與改進１６１

其中證明：ｙｒ。ｒ　ａ　一ｙｒｊａ一一巧ａｒ７ｒｊｇ　備「ｒ７一

ｙｒ；一｝０ｇ

一ｇ一　ｒ７　一ｇ　ｇ～ｒ７　一ｇ５ｒ一ｄ　＝ｄ

３．５安全性分析

（１）從以上的驗證式可知，驗證者根據簽名無法知道哪些成員參與了簽名，但在發生糾紛時ｔｃ可以通過ｄ　找到對應的簽名成員．因此本方案具有匿名性和可追蹤性．

（２）改進的方案在系統初始化階段中使用了子群金鑰的形式．在乙個子群中成員只秘密掌握與，ｎ　，他們不知道屬於自己子群的ｅ，，只有ｔｃ知道這個金鑰．若想解得ｅ，，有兩個可能途徑：一是通過

∑ｎ蘭這一等式，求出∑尼的值，這將面臨離散對數問題；二

ｉ—ｌｉ＝１

ｉ＝１是通過ｅｊ蘭直接計算求得，那必須得子群中所有的成員坦誠出自己所掌握的秘

ｉ：１密．．７／７與ｍ　（從部分簽名傳送到ｄｃ的過程中可知並非嚴格保密，但不影響以下的分析），這樣的合謀是毫無意義的，因為洩露自己的私秘密不能得到群以外的秘密．

（３）群私鑰ｅ的獲取也必須通過解決離散對數問題或是整個群內成員的秘密坦誠才能成功，因此個

人私鑰ｚ　，子群金鑰ｅ，及群私鑰ｅ都難以得到．

（４）該方案可抵抗合謀攻擊，因為在初始化條件中，我們設定了　＜２ｔ，而簽名是以子群為單位的，若要偽造簽名並嫁禍給他人，則在某一子群中個人間的合謀洩密行為，在接下來的偽造過程中，至少一人會在其他的子群簽名中會反而害到自己，所以，首先這是一種情理上的不可能性．且由（３）可知，因為各種私鑰的難解性，偽造也不可能．另外，由文獻ｅ６１４．１中２）的分析可知，本方案也是不能偽造部分簽名的．

由上可知，改進的方案可以抵抗第二部分所提出的一切攻擊，所以改進的方案是安全的．

４　結束語

本文對ｘｉｅ等人方案進行了合謀解密攻擊和合謀偽造攻擊，表明該方案是不安全的，任意ｔ人與ｄｃ合謀即可生成乙個有效的門限簽名並嫁禍給他人，任意少於ｔ人聯合ｄｃ也可生成乙個有效的門限簽名．

本文給出了乙個改進方案，彌補了原方案的安全性缺陷．

參考文獻：

［２１費如純，王麗娜，於戈．基於離散對數和二次剩餘的門限數字簽名體制ｅｊ］．通訊學報蔣瀚，徐秋亮，周永彬．基於ｒｓａ密碼體制的門限**簽名［ｊ］．計算機學報彭慶軍．一種基於橢圓曲線的可驗證門限簽名方案ｅｊ］．通訊技術

［５］朱培棟，姚諦，趙建強，等．基於秘密分享的安全組通訊協議設計與實現［ｊ］．計算機工程與應用

於秀源，薛昭雄．密碼學與數論基礎［ｍ］．濟南：山東科學技術出版社

［１１］楊建喜，劉東．一種安全的門限群簽名方案及橢圓曲線上的實現［ｊ］．計算機工程與科學下轉第１７３頁）

第２期謝明文，等：廣義ｍｏｒｐｈｉｃ環的註記１７３

參考文獻

ｚ（口口

屍一（上接第１６１頁）

一類門限簽名方案的密碼學分析與改進

一類超越不定方程的解

一類疫苗查漏補種的通知

探索規律中一類求和問題的解法

一類門限簽名方案的密碼學分析與改進

一類超越不定方程的解

一類疫苗查漏補種的通知

探索規律中一類求和問題的解法

相關推薦