鄭 紅， 范 佳

(1.四川九洲空管科技有限責(zé)任公司，四川 綿陽 621000;2.保密通信重點實驗室，四川 成都 610041)

0 引言

1984年Shamir[1]提出了基于身份的密碼體制。在該體制下，用戶的公鑰是用戶的身份信息，如email地址、身份證號碼和員工工號等;并且用戶的私鑰是由一個可信的第三方，稱為私鑰生成中心(private key generator，PKG)的機(jī)構(gòu)來產(chǎn)生。因為基于身份的密碼系統(tǒng)不需要使用數(shù)字證書，因此可以避免傳統(tǒng)的公鑰密碼系統(tǒng)(基于PKI的公鑰密碼系統(tǒng))建立和管理公鑰基礎(chǔ)設(shè)施的代價。

2001年，Boneh，Shacham和Lynn(BSL)提出了基于雙線性對的數(shù)字簽名[2]。雙線性對運(yùn)算使得BSL方案不僅簽名非常短，而且構(gòu)造簡單，驗證也非常方便。但是BSL簽名方案只能在隨機(jī)預(yù)言機(jī)模型下提供可證安全分析。2006年，Paterson和Schuldt(PS)同樣基于雙線性對，構(gòu)造了第一個可以在標(biāo)準(zhǔn)模型下證明安全的基于身份數(shù)字簽名算法(簡稱為PS算法)[3]。PS算法是Waters簽名算法[4]的擴(kuò)展，直接使用了兩次獨立的Waters身份處理函數(shù)，所以其效率并不高。最近幾年密碼學(xué)者們一直在為提高這個算法而努力。2009年李繼國等[5]提出一個對PS數(shù)字簽名算法的一個改進(jìn)方案。改進(jìn)后的方案在計算效率上有所提高，主要體現(xiàn)在驗證簽名時，改進(jìn)算法的計算量比PS算法減小了三分之一。2011年王之怡等人[6]對李繼國等的算法進(jìn)一步進(jìn)行改進(jìn)，提出了一種短公鑰的基于身份的數(shù)字簽名方案，該方案聲稱其通過改進(jìn)參數(shù)選擇，從而大大減少了公鑰參數(shù)數(shù)量。2013年黃斌和鄧小鴻[7]對李繼國等設(shè)計的方案[5]成功進(jìn)行了攻擊，使得攻擊者能夠構(gòu)造任意ID的用戶私鑰。

本文將對王之怡等人提出的短公鑰的基于身份數(shù)字簽名算法進(jìn)行安全性攻擊。

1 簽名算法回顧

王之怡等人設(shè)計的短公鑰的基于身份的數(shù)字簽名算法共包含如下四個算法，算法描述如下:

(2)私鑰提取DerMSK(ID):TA隨機(jī)選擇r∈Zp，計算身份為ID的用戶私鑰為:

(3)簽名SMPK(dID，M):身份為ID的簽名者首先進(jìn)行一個隨機(jī)化處理得到

緊接著，身份為ID的簽名者隨機(jī)選擇t∈Zp，生成對消息M的簽名 σ ={σ0，σ1，σ2}為:

(4)驗證 VID(M，σ):令(M，σ0，σ1，σ2)為收到的簽名，驗證者驗證等式:

若該等式成立，則簽名合法，否則為非法簽名。

2 對該簽名算法的攻擊

該算法的設(shè)計者宣稱該算法滿足以下安全性:令H1，H2，H3，H4是抗碰撞Hash函數(shù)，假設(shè)在雙線性映射群中計算Diffie-Hellman(CDH)數(shù)學(xué)難題成立，那么該算法是能抗適應(yīng)性選擇消息偽造簽名攻擊(UCMA)的。

UCMA安全性定義如下的攻擊游戲來描述。該攻擊游戲由一個挑戰(zhàn)者和一個攻擊者來完成。該游戲包含如下三個階段:

第一階段:挑戰(zhàn)者運(yùn)行Setup(1k)獲得主公私鑰對(MPK，MSK)，并將主公鑰MPK發(fā)送給攻擊者;

第二階段:攻擊者適應(yīng)性地進(jìn)行以下兩種詢問。

(1)私鑰提取詢問:攻擊者提交身份ID給挑戰(zhàn)者，挑戰(zhàn)者使用主私鑰計算dID=DerMSK(ID)，并將進(jìn)行應(yīng)答;

(2)簽名詢問:攻擊者適應(yīng)性地選取身份和消息{ID，M}進(jìn)行簽名詢問，挑戰(zhàn)者首先生成身份對應(yīng)的私鑰dID=DerMSK(ID)，進(jìn)一步使用dID生成簽名，最后返回簽名結(jié)果;

第三階段:攻擊者輸出{σ*，M*，ID*}，要求攻擊者未詢問過身份ID*的私鑰且未詢問過{M*，ID*}的簽名，如果攻擊者輸出的簽名能通過驗證，那么攻擊者攻擊成功。

UCMA安全性定義:如果任何概率多項式時間攻擊者在以上游戲中攻擊成功的優(yōu)勢∈(其中∈=|Pr[攻擊者攻擊成功]-1/2|)可以忽略，則稱一個基于身份簽名算法是UCMA安全的。

以下將通過兩種攻擊說明該算法并不滿足以上的UCMA安全性。

攻擊1:具體的攻擊步驟如下:

(1)在 H2中尋找碰撞(ID1，ID2)滿足 ID1≠ID2，H2(ID1)=H2(ID2):注意到在算法中描述時只提到H2:{0，1}*→Zk1，并沒有明確k1的大小。在后面的安全性證明的過程中才確定k1=1+qE，(其中qE為攻擊者在攻擊游戲中進(jìn)行簽名詢問的次數(shù)，qE=230)。目前一臺普通的單機(jī)(2.93G雙核CPU，4G內(nèi)存)運(yùn)行一次SHA-1的時間大約為2-22秒，運(yùn)行230+2次運(yùn)算的時間為128秒。假設(shè)H2運(yùn)行時間與SHA-1時間相當(dāng)，在H2中找到一個碰撞的時間至多為128秒(由于k1=230+1，運(yùn)行230+2次H2，必然會找到一個碰撞)。

(2)攻擊者通過私鑰詢問獲得ID1的私鑰:

可以很容易地驗證

(4)由于此時攻擊者已經(jīng)掌握了身份為ID2的用戶的合法私鑰，因此可以偽造該用戶的所有簽名。

攻擊2:具體的攻擊步驟如下:

攻擊者通過找尋H4的碰撞((M1)，(M2))滿足M1≠M(fèi)2，H4(M1)=H4(M2)。通過詢問某個ID對消息M1的簽名，可以構(gòu)造該ID對于M2的簽名。

3 結(jié)語

本文對一個具有短公鑰特征的基于身份的數(shù)字簽名算法進(jìn)行了安全性分析，發(fā)現(xiàn)其并不滿足其所

聲稱的安全性——抗適應(yīng)性選擇消息偽造簽名攻擊。本文的第一種公鑰針對用戶私鑰。在該種攻擊下，攻擊者如果獲得某個用戶私鑰，則他可以計算系統(tǒng)內(nèi)所有其他用戶的合法私鑰。本文的第二種攻擊針對簽名偽造。在該種攻擊下，攻擊者如果獲得了某個用戶的一個合法簽名，則他可以偽造該用戶對任意其他消息的合法簽名。

[1] Shamir A.Identity-based Crypto Systems and Signature Schemes[C]//Advances in Cryptology-Crypto'84.Berlin:Springer-Verlag，1984:47-53.

[2] Boneh D，Shacham H and Lynn B.Short Signatures from the Weil Pairing[J].J.of Cryptology，2004，17(4):297-319.

[3] Paterson K，Schuldt J.Efficient Identity-based Signatures Security in Standard Model[C]//Advances in Cryptology Proceedings of ACISP 2006.Berlin:Springer-Verlag，2006:207-222.

[4] Waters B.Efficient Identity-based Encryption Without Random Oracles[C]//Proc.of Eurocrypt'05，Berlin:Springer-Verlag，2005:114-127.

[5] 李繼國，姜平進(jìn).標(biāo)準(zhǔn)模型下可證安全的基于身份的高效簽名方案[J].計算機(jī)學(xué)報，2009，32(11):2130-2136.

[6] 王之怡，劉鐵，康立等.短公鑰的可證明安全基于身份數(shù)字簽名算法[J].計算機(jī)科學(xué)，2011，38(3):136-139.

[7] 黃斌，鄧小鴻.高效的基于身份簽名方案的安全性分析[J].計算機(jī)應(yīng)用，2013，33(1):168-170.