兩種無證書簽密方案的密碼分析和改進

樊愛宛　潘中強　趙偉艇

1(平頂山學院軟件學院　河南 平頂山 467002)2(平頂山學院網絡計算中心　河南 平頂山 467002)

?

兩種無證書簽密方案的密碼分析和改進

樊愛宛1潘中強2趙偉艇1

1(平頂山學院軟件學院河南 平頂山 467002)2(平頂山學院網絡計算中心河南 平頂山 467002)

摘要對兩種新提出的無證書安全簽密方案進行密碼學分析，證明這兩種方案都是不安全的。對于第一種方案，不僅使主密鑰泄露，而且在類型Ⅰ和類型Ⅱ敵手攻擊下是無法保證機密性和抗偽造性。對于第二種方案，在類型Ⅰ敵手攻擊下，不僅可以利用公鑰替換偽造任何用戶對任意消息的簽密，而且可以冒充合法接受者解簽密消息。利用公鑰與哈希函數綁定、增加隨機數和公鑰配對參與運算的方法，分別對它們進行改進。在隨機預言機模型中，對改進方案進行安全性證明，表明改進方案是安全的。

關鍵詞無證書簽密機密性攻擊偽造性攻擊公鑰替換隨機預言機模型

0引言

1997年，Zheng[1]提出的簽密思想解決了先簽名后加密的計算效率低的問題，其思想是將加密和簽名融合于一個邏輯步驟里，同時實現信息的機密性和不可否認性。2003年，Al-Riyami等[2]提出了無證書的密碼系統(tǒng)解決了公鑰復雜的證書管理和密碼托管問題，其思想是利用密鑰生成中心KGC(Key Generation Center)產生用戶的部分私鑰與用戶隨機選擇的秘密值，共同組成用戶公鑰對與私鑰對?；诤灻芘c無證書的高效性和強安全性等特點，2008年Barbosa 等[3]開始將無證書密碼系統(tǒng)應用于簽密思想中，提出了無證書簽密方案。

近年來，一些無證書簽密方案被相繼提出。2009年，Sharmila[4]指出Barbosa 等人的方案存在漏洞，其所提出的方案不能保證保密性和不可否認性。2010年，Selvi等[5]針對Xie等[6]提出的無證書簽密方案進行分析，指出其方案無法抵抗Type I攻擊。2011年劉文浩等[7]利用離散對數難解問題，提出了一種不使用雙線性對的無證書簽密方案。然而，Shi等[8]證明了該方案存在簽名的選擇性偽造攻擊和密文機密性問題。2014年，Zhou等[9]提出的一可證明的安全無證書簽密生成方案，Shi等[10]設計了一個安全的無證書線上線下簽密方案。然而，這些方案都采用了雙線性對計算方式，運算效率偏低。

最近，夏昂等[11]和高健鑫等[12]分別提出了高效安全無線性對的無證書簽密方案(以下簡稱XZ方案和GAO方案)，并通過形式化證明了方案的安全性。本文通過對XZ方案和GAO方案分析，發(fā)現對于XZ方案，不僅使主密鑰泄露，而且在類型Ⅰ和類型Ⅱ敵手攻擊下是無法保證機密性和抗偽造性。對于GAO方案，類型Ⅰ敵手可以利用公鑰替換偽造任何用戶對任意消息的簽密。針對以上兩種方案的安全缺陷，分別進行了改進，并在隨機預言模型下證明了改進方案在適應性選擇消息攻擊下是具有不可偽造性和加密不可區(qū)分性。

1預備知識

1.1數學難解問題

定義1離散對數問題(DLP)：兩個大素數q(0

定義2計算Diffie-Hellman問題(CDHP)：兩個大素數q(0

1.2無證書簽密系統(tǒng)及安全模型

一個無證書簽名系統(tǒng)由7個算法組成：系統(tǒng)初始化、部分密鑰生成、設置秘密值、設置私鑰、設置公鑰、簽密和解簽密。

在無證書簽密系統(tǒng)中存在2種攻擊者。

Type Ⅰ：攻擊者A1無法獲取KGC的主密鑰s，但是可以任意替換公鑰。此類型主要是模仿非法用戶進行的攻擊。

Type Ⅱ：攻擊者A2可以獲取KGC的主密鑰s，但是不可以任意替換公鑰。此類型主要是模仿能夠為用戶生成部分密鑰的KGC進行的攻擊。

無證書簽密的安全模型及攻擊者的基本攻擊詢問方式可見文獻[7]。

2對XZ方案的安全性分析及改進

2.1XZ方案描述

設置公鑰用戶A的公鑰為PKID= (XA, YA)。

設置私鑰用戶A的私鑰為SKID=(xA, yA)。

(1) 選取k，計算R = k yAYB。

(2) 計算W = YB(dA+ H2(IDA, IDB))。

(3) 計算t= (k yA) /xA；v= H3(W, IDA)⊕(m‖R‖t)。

(4) 發(fā)送消息簽密結果σ=(t, v)。

解簽密解簽密者B按如下方式處理身份為IDA的用戶A發(fā)送簽密結果：

(1) 計算W′= yB(XA+ H1(IDA, XA)P + H2(IDA, IDB) Ppub)。

(2) 計算m= H3(W′, IDA)⊕v，得到R和t。

(3) 計算t yBXA= R等式是否成立。若成立則接受m，否則拒絕。

2.2XZ方案安全性分析

經過安全性分析發(fā)現，XZ方案既不能保證KGC主密鑰的安全，也無法抵抗偽造性和機密性攻擊，更無法保證前向安全性。

1) KGC主系統(tǒng)密鑰的泄露

XZ方案中，用戶A在簽密過程中利用KGC的秘值xA，參與了t= (k yA) /xA的計算。由于dA=xA+ H1(ID, XA)s，用戶A在知道dA，xA和 H1(ID, XA)值的基礎上，能夠計算出KGC的主系統(tǒng)密鑰s。

2) 偽造性攻擊

XZ方案不能抵抗TypeⅡ偽造性攻擊。具體攻擊如下：

(1) A2已知主系統(tǒng)密鑰s和部分私鑰dA，根據dA=xA+ H1(ID,XA)s，求出xA。

(2) A2隨機選取t，計算R=t xAYB。

(3) A2計算W= YB(dA+ H2(IDA, IDB))。

(4) A2計算v= H3(W, IDA)⊕(m‖R‖t)。

(5) A2冒充用戶A發(fā)送消息簽密結果v。

敵手A2偽造的簽密結果，能夠通過W′= zB(XA+ H1(IDA, XA)Ppub+ H2(IDA, IDB)P)進行解密，具體證明如下：

W′=YB(dA+H2(IDA,IDB))

=zBP(dA+H2(IDA,IDB))

=zBP(xA+sH1(IDA,XA)+H2(IDA,IDB))

=zB(XA+H1(IDA,XA)Ppub+H2(IDA,IDB)P)

=W

接收方B通過H3(W, IDA)⊕v，求解出m，R和t。敵手A2偽造的簽密也能夠通過t zBXA= R等式的判斷，從而使接收方對消息進行接收。具體證明如下：

tzBXA=tzBxAP=txAYB=R

由以上分析可知，偽造的簽密可以滿足驗證式，即敵手A2偽造的簽密是有效的。

3) 機密性攻擊

XZ方案在Type Ⅰ下無法抵抗A1公鑰替換的機密性攻擊。具體攻擊如下：

若A1獲取了用戶A發(fā)送簽密消息v，則執(zhí)行以下步驟：

(2) 計算m= H3(W′, IDA)⊕v，得到R和t。

敵手A1冒充用戶B接收的簽密結果，一定能夠通過接收方的W′= zB(XA+ H1(IDA, XA)Ppub+ H2(IDA, IDB)P)和發(fā)送方W = YB(dA+ H2(IDA, IDB))兩個等式的判斷。

4) 無法保證前向安全性

假設敵手得到某一次的σ=(t, v)及W，那么就可以利用W解簽密以后的簽密結果。這是因為W = YB(dA+ H2(IDA, IDB))，W的求解是固定的，并沒有隨著每次會話的改變而改變。

2.3改進方案的描述

簽密過程如下：

(1) 選取r，計算R = rP。

(2) 計算kA= H2(IDA, XA, YA, Ppub) ；kB= H2(IDB, XB, YB, Ppub) ；hB= H1(IDB, XB)。

(3) 計算W =r(kBYB+ XB+ hBPpub)；v= H3(W)⊕m。

(4) 計算h = H4(IDA, XA, YA, R, v, W, m) ；t=[( kAzA+ dA)/( r+h)] mod q。

(5) 發(fā)送消息簽密結果σ=(R, v, t)。

解簽密過程如下：

(1) 計算kA= H2(IDA, XA, YA, Ppub) ；kB= H2(IDB, XB, YB, Ppub) ；hA= H1(IDA, XA)。

(2) 計算W = (kBzB+ dB)R；m= H3(W)⊕v。

(3) 計算h = H4(IDA, XA, YA, R, v, W, m)。

(4) 判斷t(R +hP)= kAYA+ XA+ hAPpub等式是否成立。若成立則接收m，否則拒絕。

改進說明：

(1) 針對KGC產生的xA導致主密鑰泄露的問題，改進方案采用不再將xA參與用戶簽密運算的方式進行解決。

(2) 針對對稱密鑰無法保證簽密的前向安全性的問題，改進方案采用用戶隨機產生的r參與每次會話對稱密鑰的產生運算的方式進行解決。

(3) 針對Type Ⅰ下的機密性攻擊和TypeⅡ下偽造性攻擊成功的原因：KGC產生的部分公鑰和用戶產生的部分公鑰無法相互制約，改進方案采用均有發(fā)送方與接收方的公鑰對與私鑰對參與的方式進行解決。

3對GAO方案安全性分析及改進

3.1方案描述

設置私鑰將系統(tǒng)參數params、DA和skA作為輸入值，用戶A生成私鑰SKA。 SKA=(DA, skA)= (tA, zA)。

設置公鑰將系統(tǒng)參數params、PA和pkA作為輸入值，用戶A生成公鑰PKA=(PA, pkA)= (wA, uA)。

(3) 計算c= E((wBuByh1)r1, ( r2, m))。

(4) 返回σ=(h,s,c)。

解簽密假設一個簽密信息=(h,s,c)，發(fā)送方用戶A的身份為IDA，公鑰為PKA，接收方用戶B的身份為IDB，公鑰為PKB，私鑰為SKB，用戶B根據以下步驟生成解簽密信息δ，并進行接受明文信息或者拒絕的操作:

3.2方案安全性分析

經過安全性分析發(fā)現，GAO方案既無法抵抗偽造性和機密性攻擊，也無法抵抗機密性攻擊。

1) 不可偽造性

Type Ⅰ攻擊者A1對GAO方案進行偽造攻擊，具體攻擊如下：

(5) 計算c=E((wBuByh1)r1, ( r2, m))。

(6) 返回σ= (h, s, c)。

由于：

=g(a+h)s(zB+tB)

=gr1(zB+tB)

=(gzBgsB+sH1(IDB,wB))r1

=(gzBgtB)r1

=gr1(zB+tB)

并且：

所以，偽造的簽密信息能夠通過用戶B的驗證。由此可見，A1通過以上步驟可以偽造一個合法的消息，GAO方案不具有不可偽造性。

2) 機密性

Type Ⅰ攻擊者A1對GAO方案進行機密性攻擊，具體攻擊如下：

(6) 返回σ= (h, s, c)。

攻擊者A1可以根據下列式子得出R的值。

R=gr1=(wAuAyH1(IDA,wA)gh)s

攻擊者A1可以根據下列式子得出m的值。

=D((gb)r1,c)

=D((gr1)b,c)

所以，簽密信息能夠被攻擊者A1解簽密。由此可見，A1通過以上步驟可以冒充接收方并得到一個合法的消息，GAO方案不具有機密性。

3.3改進方案的描述

簽密：

(2) 計算h1= H1(IDB, wB)，hA= H2(IDA, wA, uA, y)，hB= H2(IDB, wB, uB, y)。

(3) 計算ξ = (wBuBhByh1)r1，c = E(ξ, m)，h = H3(m, R, IDA, wA, uA,ξ)。

(5) 返回σ= (R, s, c)。

解簽密：

(1) 計算h1= H1(IDB, wB)，h2= H1(IDA, wA)，hA= H2(IDA, wA, uA, y)，hB= H2(IDB, wB, uB, y)。

(2) 計算ξ=(R)hBzB+tB，m = D(ξ, c)，h = H3(m, R, IDA, wA, uA,ξ)。

改進說明：

(1) 針對機密性攻擊的問題，改進方案在產生通信對稱密鑰ξ = (wBuBhByh1)r1，相對于原方案(wBuByh1)r1，利用hB防止uB的公鑰替換。

4改進方案的安全性分析

限于篇幅，本文僅對GAO的改進方案進行安全性分析。XZ的改進方案可以采用類似方式處理，但是GAO改進方案的證明是以離散對數的DLP和CDHP計算困難性為基礎的。而XZ改進方案的證明是以橢圓曲線的DLP和CDHP計算困難性為基礎的。

定理1在計算DLP困難和隨機諭言模型的假設下，改進方案在適應性選擇消息攻擊下是存在性不可偽造的。此定理由引理1和引理2推導出。由于兩個引理的證明相似，為了節(jié)約空間，僅給出引理1的具體證明。

引理1假設一個Type Ⅰ攻擊者A1以不可忽略的概率贏得了Game 1的勝利，則存在一個算法C，以一個不可忽略的概率解決DLP難題。

初始化C計算y=ga，params=(q, p, g, y, H1, H2, H3, E, D)。C將params發(fā)送給A1。

公鑰詢問C構建公鑰列表(IDU, wU, uU)。A1向C提出IDU的詢問，C以下面步驟進行回答：

(1) 如果C的公鑰列表中存在IDU，C向A1返回PKU= (wU, uU)。

秘密值提取A1向C提出IDU的詢問，C以下面方式進行回答：

(1) C以IDU為參數，運行公鑰查詢，在公鑰列表中得到(IDU, wU, uU)。

(2) C查找私鑰列表(IDU, zU, tU)，將zU返回給A1。

部分秘鑰提取A1向C提出IDU的詢問，C以下面方式進行回答:

(1) C以IDU為參數，運行公鑰查詢，在公鑰列表中得到(IDU, wU, uU)。

(2) 如果IDU≠ID*，C查找私鑰列表(IDU, zU, tU)，將zU返回給A1。

(3) 如果IDU=ID*，C返回“⊥”，并終止算法。

(1) C以IDU為參數，運行公鑰查詢，在公鑰列表中得到(IDU, wU, uU)。

簽密C構建簽密列表(IDS, PKS, IDR, PKR, m,σ)。其中S為發(fā)送方身份，R為接收方身份。A1向C提出(IDA, PKA, IDB, PKB, m)的詢問，C以下面方式進行回答：

(1) 如果IDA≠ID*，C依據方案的簽密算法，計算σ= (R, s, c)，將結果添加到簽密列表，并將σ返回給A1。

解簽密A1向C提出(IDA, PKA, IDB, PKB,σ)的詢問，C以下面方式進行回答:

(1) 如果IDB≠ID*，C依據方案的解簽密算法，將m返回給A1。

(2) 如果IDB=ID*，且IDA≠ID*，C檢查是否有(IDA, PKA, IDB, PKB, *,σ)是否在簽密列表中，若存在C將對應的m返回給A1，否則返回“拒絕”。

最后，A1輸出σ= (R, s, c)。如果IDA≠ID*，C返回“⊥”，并終止算法。如果IDA=ID*，且IDB≠ID*，C返從私鑰列表和公鑰列表中查找(IDB, zB, tB)和(IDA, wA, uA)，其中公鑰PKA= (wA, uA)已經被A1替換。C可以通過m=D((R)hBzB+tB,c)得到明文。通過偽造引理可得，如果對C算法采用隨機參數不變，選擇不同隨機諭言機H1和H2的方式進行回放，A1就能得到3個不同的簽名ψ(i)= (R, s(i))，i=1,2,3。由于以上簽名是有效的，所以下面的等式是成立的。

R = (uAhA (i)wAyh2 (i)gh(i))s(i)

通過r1、 zA、 sA和a能夠計算R、 wA、 uA和y：R = gr1, wA= gsA, uA= gzA, y = ga。從以上分析，可以得到如下等式：

r1= zAhA(i)s(i)+ sAs(i)+ ah2(i)s(i)+ h(i)s(i)

在以上等式中r1、 zA、 sA和a都是未知的，C從以上線性無關方程組中求解這些值，從而輸出a，難度相當于求解DLP難題。如果對方案攻擊成功的概率是不可忽略，則C能夠以不可忽略的概率解決DLP問題。所以，本方案在計算DLP困難和隨機諭言模型的假設下，改進方案在適應性選擇消息攻擊下是存在性不可偽造的。

引理2假設一個TypeⅡ攻擊者A2以不可忽略的概率贏得了Game 2的勝利，則存在一個算法C，以一個不可忽略的概率解決DLP難題。

定理2在計算CDHP困難和隨機諭言模型的假設下，改進方案在適應性選擇消息攻擊下是具有加密不可區(qū)分性。此定理由引理3和引理4推導出。由于兩個引理的證明相似，為了節(jié)約空間，僅給出引理4的具體證明。

引理3假設一個TypeⅠ攻擊者A1以不可忽略的概率贏得了Game 3的勝利，則存在一個算法C，以一個不可忽略的概率解決CDHP難題。

引理4假設一個TypeⅡ攻擊者A2以不可忽略的概率贏得了Game 4的勝利，則存在一個算法C，以一個不可忽略的概率解決CDHP難題。

證明假定一個TypeⅡ攻擊者A2以不可忽略的概率ε贏得了Game 4的勝利，需要構造一個算法C，利用A2解決CDHP難題。C收到一個CDHP難題實例(p, q, g, ga, gb)，目標是能夠計算出gab。C回答H1詢問、H2詢問和H3詢問，詢問與回答方式與引理1相同。其他詢問回答方式如下：

公鑰詢問C構建公鑰列表(IDU, wU, uU)。A1向C提出IDU的詢問，C以下面步驟進行回答：

(1) 如果C的公鑰列表中存在IDU，C向A1返回PKU= (wU, uU)。

秘密值提取A2向C提出IDU的詢問，C以下面方式進行回答：

(1) C以IDU為參數，運行公鑰查詢，在公鑰列表中得到(IDU, wU, uU)。

(2) 如果IDU≠ID*，C查找私鑰列表(IDU, zU, tU)，將zU返回給A2。

(3) 如果IDU=ID*，C返回“⊥”，并終止算法。

部分秘鑰提取A2向C提出IDU的詢問，C以下面方式進行回答：

(1) C以IDU為參數，運行公鑰查詢，在公鑰列表中得到(IDU, wU, uU)。

(2) C查找私鑰列表(IDU, zU, tU)，將tU返回給A2。

簽密C構建簽密列表(IDS, PKS, IDR, PKR, m,σ)。其中S為發(fā)送方身份，R為接收方身份。A2向C提出(IDA, PKA, IDB, PKB, m)的詢問，C以下面方式進行回答:

(1) 如果IDA≠ID*，C依據方案的簽密算法，計算σ= (R, s, c)，將結果添加到簽密列表，并將σ返回給A2。

解簽密A2向C提出(IDA, PKA, IDB, PKB,σ)的詢問，C以下面方式進行回答：

(1) 如果IDB≠ID*，C依據方案的解簽密算法，將m返回給A2。

(2) 如果IDB=ID*，且IDA≠ID*，C檢查是否有(IDA, PKA, IDB, PKB, *,σ)是否在簽密列表中，若存在C將對應的m返回給A2，否則返回“拒絕”。

如果對方案攻擊成功的概率ε是不可忽略，則C能夠以不可忽略的概率解決CDHP問題。所以，在計算CDHP困難和隨機諭言模型的假設下，改進方案在適應性選擇消息攻擊下是具有加密不可區(qū)分性。

5結語

對兩個無證書簽密方案進行了密碼分析，發(fā)現對于XZ方案，不僅使主密鑰泄露，而且在類型Ⅰ和類型Ⅱ敵手攻擊下是無法保證機密性和抗偽造性。對于GAO方案，類型Ⅰ敵手可以利用公鑰替換偽造任何用戶對任意消息的簽密。針對以上兩種方案的安全缺陷，分別進行了改進，并在隨機預言模型下證明了證明改進方案在適應性選擇消息攻擊下是具有不可偽造性和加密不可區(qū)分性。從目前研究進展來看，如何構造安全高效的無證書簽密仍然是一個亟待解決的問題。

參考文獻

[1] Zheng Y.Digital signcryption or how to achieve cost(signature & encryption)<

[2] Al-riyami S,Paterson K.Certificateless public key cryptography[C]//Proc of Asiacrypt 2003.Springer-Verlag,Berlin,2003:452-473.

[3] Barbosa M,Farshim P.Certificateless signcryption[C]//Proc of ACM Symposium on Infomation,Computer and Communications Secu-rity.New York:ACM Press,2008:369-372.

[4] Sharmila S,Deva S.Efficient certificateless online/offline signature with tight security[J].Journal ofinternet services and information security,2013,1(1/2):115-137.

[5] Selvi S,Vivek S S,Ragan C P.Certifieateless KEM and hybrid signcryption schemes revisited[C]//Proceeding of ISPEC 2010.LNCS 6047,Berlin:Springer-Verlag,2010:294-307.

[6] Xie W,Zhang Z.Certifieateless signcryption without pairing[EB/OL].2010-06-20.http://epfint.iacr.org/2010/187.

[7] 劉文浩,許春香.無雙線性配對的無證書簽密方案[J].軟件學報,2011,22(8):1918-1926.

[8] Shi W,Kumer N,Gong P,et al.Cryptanalysis and improvement of a certificateless signcryption scheme without bilinear pairing[J].Frontiers of Computer Science,2014,8(4):656-666.

[9] Zhou C,Zhou W,Dong X,et al.Provable certificateless generalized signcryption scheme[J].Designs,Codes and Cryptography,2014,71(2):331-346.

[10] Shi W,Neeraj K,Gong P,et al.On the security of a certificateless online/offline signcryption for Internet of Things[J].Peer-to-Peer Networking and Applications,2014,74(8):101-120.

[11] 夏昂,張龍軍.一種新的無雙線性對的無證書安全簽密方案[J].計算機應用研究,2014,31(2):532-535.

[12] 高鍵鑫,吳曉平,秦艷琳,等.無雙線性對的無證書安全簽密方案[J].計算機應用研究,2014,31(4):1195-1198.

收稿日期：2015-01-27。河南省高校青年骨干教師資助計劃項目；河南省科技攻關計劃基金項目(152102210193)；河南省高等學校重點科研項目(15A520091)。樊愛宛，副教授，主研領域：信息安全。潘中強，副教授。趙偉艇，教授。

中圖分類號TP309

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.070

CRYPTANALYSIS AND IMPROVEMENT OF TWO CERTIFICATELESS SIGNCRYPTION SCHEMES

Fan Aiwan1Pan Zhongqiang2Zhao Weiting1

1(SchoolofSoftware,PingdingshanCollege,Pingdingshan467002,Henan,China)2(CenterofNetworkandComputer,PingdingshanCollege,Pingdingshan467002,Henan,China)

AbstractApplying the cryptanalysis to two newly presented certificateless secure signcryption schemes, it is proved that both of them are insecure. For the first one, not only the master key can be disclosed, it cannot ensure the confidentiality and anti-forgery capability under the attacks made by type I and type II adversaries as well. For the second scheme, under the attack launched by Type I adversary, not just the public key can be used to replace and forge the signcryption by any user on arbitrary message, but the legitimate recipient can also be feigned to calculate the signcryption. We improved these two schemes separately by means of binding the public key and hash function, increasing the random numbers and participating in operation with public key pair. In random oracle model we proved the security of the improved schemes, they were demonstrated secure.

KeywordsCertificateless signcryptionConfidentiality attackForgery attackPublic key replacementRandom oracle model