兩個自認證簽密方案的攻擊及改進＊

王 云

（青海大學成人教育學院，青海西寧810001）

1 引言

我們的社會已經進入了一個嶄新的時代，傳統商務、事務處理、政府服務越來越多地需要通過計算機和通信網絡來實現，而只有在開放網絡能提供安全通信的前提下，上述事務才能實現。如何在開放網絡中保證通信的安全性，就是利用密碼技術。簽密技術和自認證公鑰技術是密碼學中兩種新的密碼技術。簽密技術能在一個邏輯步驟內完成數字簽名和加密兩項功能［1］：自認證公鑰技術使得用戶的公鑰無需被單獨認證，而且用戶的私鑰由用戶自己獨立生成，密鑰生成中心PKG無法假冒用戶。兩種密碼技術的相互結合，便出現了許多自認證簽密方案［2～5］。

本文對俞惠芳、王彩芬［6］提出的一個高效的自認證簽密方案和王之倉等［7］提出的基于離散對數問題的簽密方案進行分析研究，發現這兩個方案存在安全隱患。存在已知明文與密文對的偽造攻擊：即任意第三方可借助竊取到的明文與密文對假冒發送方偽造任意消息的簽名。進而對文獻［6］提出改進，改進后的方案既保留了原方案的優點又有效克服了原方案的不足。通過新舊方案的分析對比表明：改進的方案具有通信成本低、計算效率高、安全性強、算法簡單等優點。

2 預備知識——雙線性映射

設G1為q階加法循環群，G2為q階乘法循環群，在G1和G2上計算離散對數為困難問題。稱e：G1×G2→G2為G1到G2雙線性映射，如果滿足下述條件：

雙線性：對任意P、Q∈G1，a、b∈Z＊q，e（aP，b Q）＝e（P，Q）ab成立。

非退化性：?P、Q∈G1滿足e（P，Q）≠1。

可計算性：對任意的P、Q∈G1，存在一個有效算法計算e（P，Q）。

3 文獻［6］方案介紹及其改進

3.1 文獻［6］方案介紹

3.1.1 系統設置

（1）G1、G2是可信機構CA選擇的兩個階為q（q為素數）的循環群，其中，G1為加法群；G2為乘法群；p為G1的生成元。e是G1×G2→G2的雙線性映射。

（2）定義三個密碼學上安全的哈希函數：

（3）CA選取s∈R作為系統主密鑰，計算PCA＝sp作為其公鑰。

（4）保密系統主密鑰s，公開系統參數：｛G1，G2，q，e，p，n，H0，H1，H2｝。

3.1.2 用戶密鑰的提取

身份為IDA的簽密者A選擇秘密值rA∈R，并計算PA＝rAp。然后簽密者A發送（IDA，PA）給CA。CA收到（IDA，PA）后，計算QA＝H（IDA，PA）和xA＝sQA，并將（IDA，QA，XA）發送給簽密者A。簽密者A收到（IDA，QA，XA）后，可通過驗證方程e（xA，P）＝e（QA，PCA）是否成立來檢驗xA的合法性。如果上式成立，則簽密者就接受xA作為自己的部分私鑰，計算SA＝rAQA＋xA作為自己的私鑰，并將pA作為自己的公鑰。接收者B的部分私鑰以及公私鑰對（xB，PB，SB）可采用相似的方法獲得。

3.1.3 簽密

簽密者A發送消息m給接收者B，執行以下步驟：

（1）選擇k∈R，計算R＝kp；

（2）計算V＝e（QB，PB＋PCA）k，c＝H1（V）⊕m；

（3）計算S＝H2（m，R）SA；

（4）輸出密文組σ＝（R，c，S）。

3.1.4 解簽密

B收到密文（R，c，S）后，執行以下步驟：

（1）計算V＝e（R，SB）。

（2）恢復消息m＝c⊕H1（V）。

（3）檢查等式e（P，S）＝e（QA，PA＋PCA）是否成立。如果等式成立，簽密（R，S）和公鑰PA同時被驗證，B接收（R，S）；否則，驗證失敗，認為（R，S）不合法。

3.2 文獻［6］的分析

假設O竊取A向B發送的已知消息m的一組密文（R，c，S），則O可假借A的名義向B發送任意消息m′的合法密文組（R′，c′，S′），具體過程如下：

（1）選擇r0∈R，計算R′＝r0R；

（3）計算S′＝S＊H2（m′，R′）H2（m，R）－1；

（4）輸出密文組σ＝（R′，c′，S′），則密文組（R′，c′，S′）也是合法密文。正確性證明過程如下：

3.3 文獻［6］的改進方案

除簽名和驗證步驟外，與原方案相同的部分不再重復，以下只列出簽名和驗證過程。

3.3.1 簽名過程

（1）選擇k∈R，計算R＝kp，R′＝kQA；

（2）計算V＝e（QB，PB＋PCA）k，c＝H1（V）⊕m；

（3）計算S＝H2（m，R）kSA；

（4）輸出密文組σ＝（R，R′，c，S）。

3.3.2驗證過程

恢復消息后，檢查等式e（P，S）＝e（R′，PA＋PCA）是否成立。如果等式成立，簽密（R，S）和公鑰PA同時被驗證，B接收（R，S）；否則，驗證失敗，認為（R，S）不合法。

3.3.3 文獻［6］與改進方案的仿真結果對比

針對文獻［6］可取q＝12347，a＝2，p＝11，rA＝7，s＝5，QA＝13，則pA＝77，XA＝65，SA＝156，則簽名者A的部分私鑰和公私鑰對為（65，77，156）；同理rB＝17，QB＝19，則PB＝187，XB＝95，SB＝418，簽名者B的部分私鑰和公私鑰對為（95，187，418），簽名者A對消息m簽名，取k＝2，則R＝22，v＝e（QB，PB＋PAC）3，c＝H1（v）⊕m，H2（m，R）＝4，s＝624，假設第三者O已經成功竊取已知消息m的一組簽名（22，｛0，1｝m，624），O可輕易獲得簽名者A的私鑰SA＝624＊4－1＝156。可對任意消息M′進行簽名，取r0＝3，R′＝66，V′＝V3，c′＝H1（v′）⊕M′，H2（m′，R′）＝6，則S′＝936，這一組數據滿足簽名方程，是合法數據。

針對改進方案同樣取上述數據，即簽名者A的部分私鑰和公私鑰對為（65，77，156），簽名者B的部分私鑰和公私鑰對為（95，187，418），假設第三者O已經成功竊取已知消息m的一組簽名（22，｛0，1｝m，624），由于簽名方程中含有未知數k，無法進行偽造，只能猜測，但猜測成功的概率只有1/12347，可以忽略不計。要使得方案更加安全，只需q取更大的數即可。

3.4 改進方案的安全性分析

改進的方案在不額外增加參數的前提下，將秘密隨機值k巧妙加入到簽名方案中，只增加了兩次數乘運算，就保證了簽名方案的安全性能。因為任何人想從R、R′得出參數k的值是不可行的，這相當于解決ECDL問題，而簽名方案中必須要知道參數k的值，故攻擊者無法獲得關于消息的任何有用信息。即使有人得到了消息的明文和密文對，要想進行偽造簽名也是不可能的。因為簽名方程中添加了參數k，k對攻擊者來說是不可能知道的。所以改進方案的安全性大大加強，效率也非常高，同時也滿足原簽名方案的其他特性。

3.5 文獻［7］的介紹及分析

文獻［6］簽名方案中關鍵的一步，即S＝H2（m，R）SA中沒有其它參數，只有簽名者的私鑰SA和H2（m，R）兩項乘積。相似方案都存在類似的安全隱患，如文獻［7］。別的不再多述。

3.5.1 系統初始化

PKG選擇兩個大素數p1和q1，并滿足p1＝2p′＋1，q1＝2q′＋1，其中p′、q′也是大素數。計算p＝p1q1，并選擇一個階為p′q′的生成元g和一個安全的可變長的單向哈希函數H。隨機選擇一個秘密值s∈作為主密鑰，計算其公鑰y＝gsmod p，最后，保密p1、q1、p′、q′、s，公開p、g、H和y。

3.5.2 用戶注冊

身份為du的用戶u選擇一個秘密值ru∈R，計算yu＝grumod p，然后用戶發送（du，yu）給PKG。PKG計算Qu＝H（du，yu）和xu＝gsQu，并將（Qu，xu）發給用戶u。用戶u收到后，驗證方程yQu＝xumod p檢驗xu的合法性。若上式成立用戶就計算Su＝ruH（xu）作為自己的私鑰，yu作為自己的公鑰。簽密者和密文接收者相應的身份、部分私鑰、公鑰以及私鑰分別簡記為（dA，xA，yA，SA）和（dB，xB，yB，SB）。

3.5.3 簽密

簽密者A發送消息m給接收者B，執行以下步驟：

（1）選擇k∈R，計算R＝gkmod p；

（3）計算S＝H（m，R）g－kgSAmod p；

（4）輸出密文組σ＝（R，c，S）。

3.5.4 解簽密

B收到密文（R，c，S）后，執行以下步驟：（1）計算V＝RSB mod p。

（2）恢復消息m＝c⊕H（V）。

假設O已成功竊取A向B發送的已知消息m的一組密文（R，c，S），則O可假借A的名義向B發送任意消息m′的合法密文組（R′，c′，S′），具體過程如下：

（1）選擇r0∈R，計算R′＝Rr0 mod p；

（3）計算S′＝S＊H2（m′，R′）R－r0 RH（m，R）－1；

（4）輸出密文組σ＝（R′，c′，S′），則密文組（R′，c′，S′）也是合法密文。正確性證明過程如下：

由原方案可知，V＝RSB mod p，則V′＝Vr0 mod p＝Rr0 SB mod p＝R′SB mod p；

4 結束語

本文對俞惠芳等提出的一個高效的簽密方案和王之倉等提出的一個基于離散對數的簽密方案的安全性進行了研究分析，發現這兩個方案的相似之處，即類似方案均存在已知明文與密文對的偽造攻擊，進而對其進行改進。通過添加隨機參數的方法，恰倒好處地克服了原方案的安全隱患，相比現行簽密方案更加安全有效。如何將其應用在現今飛速發展的電子商務和電子政務中將是今后的一個重點研究方向。

［1］ Zheng Yu－liang.Digital signcryption or how to achieve cost（signature ＆encryption）?cost（signature）＋cost（encryption）［C］∥Proc of Cryptology，CRYPYO’97，1997：165－179.

［2］ Geng Li，Wang Shang－ping，Zhou Feng，et al.A new ID－based signcryption scheme［J］.Computer Engineering，2004，30（19）：52－54.（in Chinese）

［3］ Bao Feng，Deng R H.A signcryption scheme with signature directly verifiable by public key［C］∥Proc of Cryptography，PKC’98，1998：55－59.

［4］ Yum D H，Lee P J.New signcryption schemes based on KCDSA［C］∥Proc of ICISC’01，2001：305－317.

［5］ Girault M.Self－certified public keys［C］∥Proc of Advances in Cryptology－EUROCRYPT’91，1991：491－497.

［6］ Yu Hui－fang，Wang Cai－fen.An efficient self－certified signcryption scheme［J］.Computer Engineering，2009，35（16）：138－142.（in Chinese）

［7］ Wang Zhi－cang，Yu Hui－fang.Self－certified signcryption scheme based on discrete logarithm problem［J］.Computer Applications and Software，2010，27（10）：223－225.（in Chinese）

附中文參考文獻：

［2］ 耿莉，王尚平，周峰等.一種新的基于身份的簽密方案［J］.計算機工程，2004，30（19）：52－54.

［6］ 俞慧芳，王彩芬.一個高效的自認證簽密方案［J］.計算機工程，2009，35（16）：138－142.

［7］ 王之倉，俞慧芳.基于離散對數問題的自認證簽密方案［J］.計算機應用與軟件，2010，27（10）：223－225.