一個(gè)安全高效的無證書簽名方案的分析和改進(jìn)

劉二根，周華靜，2，王 霞，2，郭紅麗，2

（華東交通大學(xué)1.理學(xué)院；2.系統(tǒng)工程與密碼學(xué)研究所，江西 南昌330013）

數(shù)字簽名是現(xiàn)代密碼學(xué)的一個(gè)重要領(lǐng)域，最早的數(shù)字簽名是基于證書的，而基于證書的密碼學(xué)體制存在著證書的頒發(fā)，存儲(chǔ)，撤銷等問題。因此，解決此類問題成為密碼學(xué)領(lǐng)域的重要研究方面。1985年，Shamir［1］第一次提出基于身份的密碼學(xué)體制，在該體制下，用戶密鑰生成完全依賴密鑰生成中心（KGC），因此，又不可避免地存在密鑰托管問題。隨著密碼學(xué)的日益發(fā)展，2003年，Al-Riyami等［2］提出的無證書密碼體制，既解決了傳統(tǒng)的基于證書密碼體制下繁瑣的證書管理問題，也解決了基于身份密碼體制下的密鑰托管問題?；跓o證書密碼體制的種種優(yōu)點(diǎn)，該體制一經(jīng)提出便得到學(xué)者們的廣泛關(guān)注。2005年，Huang等［3］首次比較詳細(xì)地給出無證書簽名方案安全模型的定義，并提出一個(gè)具體的基于無證書的簽名方案。2007年，Liu等［4］也提出一個(gè)無證書簽名方案。在接下來的幾年里，無證書簽名不斷發(fā)展，學(xué)者們先后提出各種無證書簽名方案。2008年，樊睿等［5］提出一個(gè)效率較高的無證書代理簽名方案。2010年，李明祥等［6］提出一個(gè)高效的無證書部分盲簽名方案。2014年，樊愛宛等［7］提出一個(gè)強(qiáng)安全的無證書簽名方案，同年又提出另一個(gè)無證書簽名方案［8］。隨后，劉倩等［9］對(duì)一個(gè)無證書簽名方案進(jìn)行安全性分析，發(fā)現(xiàn)其對(duì)于兩類攻擊者的攻擊并不安全，因此提出改進(jìn)方案。通過對(duì)文獻(xiàn)［9］的分析，發(fā)現(xiàn)仍然存在公鑰替換攻擊且效率不高，在此基礎(chǔ)上進(jìn)行改進(jìn)，提出新的無證書簽名方案。并對(duì)改進(jìn)后的方案進(jìn)行安全性證明和效率分析。

1 預(yù)備知識(shí)

1.1 困難問題及假設(shè)

定義1離散對(duì)數(shù)問題（DLP）：設(shè)G是一個(gè)橢圓曲線群，已知aP∈G，a∈Z*q，其中P為G的生成元，求解a的問題稱為離散對(duì)數(shù)問題。

假設(shè)1離散對(duì)數(shù)困難性假設(shè)：如果不存在一個(gè)概率多項(xiàng)式時(shí)間（PPT）的算法，在時(shí)間t內(nèi)，以一個(gè)大于0的概率ε解得群G上的DL問題，則稱離散對(duì)數(shù)困難性假設(shè)成立。

1.2 攻擊者類型［2］

在無證書密碼體制中存在兩種類型的攻擊者AⅠ和AⅡ，分別具有不同的能力。①類型Ⅰ攻擊者AⅠ：AⅠ不知道系統(tǒng)主密鑰，但是可以任意替換用戶公鑰；②類型Ⅱ攻擊者AⅡ：AⅡ知道系統(tǒng)主密鑰，但是不知道用戶個(gè)人私鑰，也不能替換用戶公鑰。

2 文獻(xiàn)［9］方案分析

2.1 方案回顧

文獻(xiàn)［9］提出一個(gè)改進(jìn)的無證書簽名方案。方案由系統(tǒng)參數(shù)生成、秘密值生成、公鑰生成、私鑰生成、簽名及驗(yàn)證這6個(gè)算法組成，方案具體描述如下。

1）系統(tǒng)參數(shù)生成：設(shè)置系統(tǒng)安全參數(shù)為k，KGC（Key Generator Center）選取階為q的加法循環(huán)群G1和乘法循環(huán)群G2，其中q≤2k且為素?cái)?shù)。雙線性對(duì)映射為e:G1×G1→G2，選取群G1的一個(gè)生成元為P∈G1，并隨機(jī)選取s∈RZ*q作為系統(tǒng)主密鑰，計(jì)算Ppub為系統(tǒng)公鑰，g為公鑰參數(shù)。選擇兩個(gè)安全哈希函數(shù)H1:{0,1}*×G1→G1，H2:{0,1}*×{0,1}*×G1×G1×G1→Z*q，則系統(tǒng)公開參數(shù)可表示為params={q,e,g,G1,G2,P,Ppub,H1,H2}，公開params，保密主密鑰s。

2）秘密值生成：簽名者A隨機(jī)選取xA∈Z*q作為自己的秘密值并保存。

3）公鑰生成：簽名者A計(jì)算PKA=xAP作為自己的公鑰，將其公開。

4）私鑰生成：①部分私鑰：設(shè)簽名者A的身份為IDA，KGC 計(jì)算DA=sQA=sH1(IDA)∈G1，將DA作為簽名者A的部分私鑰，通過秘密信道發(fā)送給A；②完整私鑰：簽名者A收到DA后，計(jì)算SA=DA=xA·H1(IDA，PKA)∈G1，則用戶完整私鑰為SA。

5）簽名：簽名者A的身份為IDA，簽名私鑰為SA，待簽名消息為m∈{0,1}*，由A執(zhí)行簽名算法。A隨機(jī)選取一個(gè)隨機(jī)數(shù)r∈RZ*q，計(jì)算R=gr∈G2，h=H2(m｜｜IDA｜｜R｜｜PKA)∈Z*q，V=r·P+h·SA∈G1，則簽名為σ=(h,V)。

6）驗(yàn)證：驗(yàn)證者收到簽名后首先計(jì)算h=H2(m｜｜IDA｜｜R｜｜PKA)，如果等式e(V,P)e(QA,Ppub+PKA)-h=R成立，則說明簽名有效，接受簽名，輸出1；否則，拒絕，輸出0。

2.2 安全性與效率分析

通過對(duì)上述方案的分析，發(fā)現(xiàn)存在如下缺陷。

缺陷一：該方案存在公鑰替換攻擊，存在一個(gè)類型Ⅰ的攻擊者F，可以替換用戶公鑰，具體攻擊為：

攻 擊 者F將 簽 名 者A的 公 鑰 替 換 為PK′A=P-Ppub，并 隨 機(jī) 選 取 隨 機(jī) 數(shù) 為r′∈RZq*，則R′=gr′，h′=H2(m｜｜IDA｜｜R′｜｜PKA)∈Zq*，計(jì)算簽名為V′=r′P+h′QA。返回簽名σ′=(h′,V′)給驗(yàn)證者。下面證明由攻擊者偽造的該簽名V′可以通過驗(yàn)證等式

因此，簽名可以通過驗(yàn)證等式，也就是說攻擊者F將簽名者A的公鑰替換后偽造的簽名σ′=(h′,V′)是有效的。即方案不能抵抗公鑰替換攻擊。

缺陷二：通過對(duì)方案的效率分析，可以看出上述方案在簽名的驗(yàn)證階段使用了兩次雙線性對(duì)運(yùn)算，而雙線性對(duì)運(yùn)算的時(shí)間復(fù)雜度和計(jì)算復(fù)雜度都比哈希運(yùn)算和指數(shù)運(yùn)算的要高的多。因此，使用雙線性對(duì)運(yùn)算會(huì)使方案效率下降。

3 方案改進(jìn)

針對(duì)上述方案中安全性及效率上的缺陷，提出一個(gè)可抗公鑰替換攻擊且效率更高的無證書簽名方案。方案包括系統(tǒng)初始化（Setup）、用戶個(gè)人密鑰生成（UserKeyGen）、部分私鑰生成（PartKeyGen）、簽名密鑰生成（SignKey）、簽名（Sign）及驗(yàn)證（Verify）這6個(gè)算法。方案描述如下。

1）系統(tǒng)初始化：設(shè)系統(tǒng)安全參數(shù)為1k，KGC選取一個(gè)大素?cái)?shù)q≤2k，并生成以q為階的加法循環(huán)群G1和乘法循環(huán)群G2，選取群G1的一個(gè)生成元P∈G1，并隨機(jī)選取s∈RZ*q作為系統(tǒng)主密鑰，計(jì)算Ppub=sP作為系統(tǒng)主公鑰。作雙線性對(duì)映射e:G1×G1→G2，選取兩個(gè)安全哈希函數(shù)分別為：H1：{0,1}*×G1→Zq*，H2：{0,1}*×{0,1}*×G1→Zq*。系統(tǒng)公開參數(shù)為params={q,e,G1,G2,P,Ppub,H1,H2}，KGC公開params，保密s。

2）用戶個(gè)人密鑰生成：簽名者A隨機(jī)選取xA∈Zq*作為用戶個(gè)人私鑰，計(jì)算XA=xAP作為對(duì)應(yīng)的公鑰，公開XA，保密xA。

3）部分私鑰生成：此算法由KGC 執(zhí)行，KGC 隨機(jī)選取yA∈Zq*，計(jì)算DA=s+yA+H1(IDA,XA)作為用戶的部分私鑰，并通過安全信道發(fā)送給A。

4）簽名密鑰生成：簽名者A收到DA后，計(jì)算SKA=DA+xAH1(IDA,XA)作為簽名密鑰，對(duì)應(yīng)的簽名公鑰為PKA=SKAP。

5）簽名：設(shè)待簽名消息為m∈{0,1}*，簽名者A隨機(jī)選取隨機(jī)數(shù)k∈Zq*，計(jì)算K=kP，h=H2(m,IDA,K)，V=SKA-1(k+h)，則消息m對(duì)應(yīng)的簽名對(duì)為σ=(m,K,h,V)。

6）驗(yàn)證：驗(yàn)證者收到消息m的簽名對(duì)σ=(m,K,h,V)后，對(duì)其進(jìn)行驗(yàn)證，如果等式K=VPKA-hP成立，則說明簽名有效，輸出1；否則，簽名無效，輸出0。

4 新方案的安全性分析

4.1 抗類型Ⅰ攻擊者的攻擊

定理1新方案可以抵抗類型Ⅰ攻擊者的公鑰替換攻擊。

證明因?yàn)轭愋廷窆粽呖梢匀我馓鎿Q用戶公鑰，但是在改進(jìn)的新方案中，由于在KGC生成的部分私鑰中利用哈希運(yùn)算將用戶個(gè)人公鑰進(jìn)行綁定，因此攻擊者無法替換用戶公鑰。即新方案可以抵抗類型Ⅰ攻擊者的攻擊。

4.2 抗類型Ⅱ攻擊者的攻擊

定理2新方案對(duì)于類型Ⅱ攻擊者的適應(yīng)性選擇消息和身份攻擊，在隨機(jī)預(yù)言機(jī)模型下是存在性不可偽造的。

證明設(shè)一個(gè)類型Ⅱ攻擊者AⅡ。如果在多項(xiàng)式有界的時(shí)間t內(nèi)，AⅡ能夠以一個(gè)不可忽略的概率ε偽造一個(gè)有效的簽名，只需證明，存在一個(gè)概率多項(xiàng)式時(shí)間的挑戰(zhàn)算法Ω 可以利用AⅡ成功解決DL問題，問題實(shí)例為，已知(P,aP)，求解a。在下面的證明中，Ω 模擬密鑰生成中心，回答AⅡ的一系列適應(yīng)性詢問，用a模擬簽名私鑰，設(shè)目標(biāo)用戶身份為ID*，對(duì)應(yīng)的待簽名消息為m*。AⅡ向Ω 進(jìn)行如下適應(yīng)性詢問：哈希詢問、用戶個(gè)人密鑰詢問、部分密鑰詢問、簽名密鑰詢問、簽名詢問，而Ω 通過維護(hù)一些列表模擬對(duì)AⅡ的回答。

H1詢問：對(duì)應(yīng)的列表格式為L1(IDj,Xj,h1j)，AⅡ向Ω 進(jìn)行用戶身份為IDi的H1詢問。Ω 首先檢查列表L1，如果列表中存在(IDi,Xi,h1i)的項(xiàng)，則直接返回h1i給AⅡ；否則，列表中不存在(IDi,Xi,h1i)的項(xiàng)，Ω 隨機(jī)選取h1i∈RZ*q，返回給AII，并將(IDi,Xi,h1i)添加到列表。H2詢問：對(duì)應(yīng)的列表格式為L2(mj,IDj,Kj,h2j)，AⅡ向Ω 進(jìn)行消息為mi，用戶身份為IDi的H2詢問。Ω檢查列表L2，如果列表中存在(mi,IDi,Ki,h2i)的項(xiàng)，直接返回h2i給AⅡ；否則，Ω 隨機(jī)選取h2i∈RZ*q，并返回給AⅡ，將(mi,IDi,Ki,h2i)添加到列表。

用戶個(gè)人密鑰詢問：每一項(xiàng)列表的格式為Ls(IDj,xj,Xj)，AⅡ向Ω 進(jìn)行用戶身份為IDi的簽名密鑰詢問。Ω 先查詢列表Ls，如果列表中已經(jīng)存在(IDi,xi,Xi)的項(xiàng)，直接返回(xi,Xi)給AⅡ。否則：

1）如果IDi≠ID*，Ω 隨機(jī)選取xi∈RZ*q，計(jì)算Xi=xiP，并將(xi,Xi)返回給AⅡ，同時(shí)將(IDi,xi,Xi)添加到列表Ls中。

2）如果IDi=ID*，即AⅡ詢問的是目標(biāo)用戶的個(gè)人密鑰，Ω 拒絕回答，返回(⊥,Xi)給AⅡ，并將(IDi,⊥,Xi)添加到列表Ls中。

部分密鑰詢問：對(duì)應(yīng)的列表中每項(xiàng)的格式為Lk(IDj,Dj)，AⅡ向Ω 進(jìn)行用戶身份為IDi的部分密鑰詢問。Ω 檢查列表Lk，如果列表中存在(IDi,Di)的項(xiàng)，直接返回Di給AⅡ。否則：

1）如果IDi≠ID*，Ω 首先查詢列表L1（假設(shè)在此之前已經(jīng)進(jìn)行過H1詢問，否則可以先進(jìn)行H1詢問），得到h1i，隨機(jī)選取yi，計(jì)算Di=s+yi+h1i，并返回給AⅡ，將(IDi,Di)添加到列表。

2）如果IDi=ID*，Ω 拒絕回答，詢問終止。

簽名密鑰詢問：相應(yīng)的列表格式為Lsk(IDj,SKj,PKj)，AⅡ向Ω 詢問身份為IDi的用戶的簽名密鑰。Ω 檢查列表，如果列表中存在(IDi,SKi,PKi)的項(xiàng)，直接返回(SKi,PKi)給AⅡ。否則

1）如果IDi≠ID*，Ω 查詢列表L1，Ls，Lk分別得到相應(yīng)的h1i，xi及Di的值（假設(shè)在此之前已經(jīng)進(jìn)行過H1詢問，用戶個(gè)人密鑰詢問及部分密鑰詢問，不然可以先進(jìn)行詢問），直接計(jì)算SKi=Di+xih1i，PKi=SKi·P，將(SKi,PKi)返回給AⅡ，并將(IDi,SKi,PKi)添加到列表Lsk中。

2）如果IDi=ID*，Ω 拒絕回答，詢問終止。

簽名詢問：AⅡ向Ω 詢問用戶身份為IDi，待簽名消息為mi的簽名詢問。如果IDi≠ID*，Ω 查詢列表L2和Lsk，得到h2i及SK，并隨機(jī)選取ki∈RZq*，計(jì)算Vi=SKi-1(ki+h2i)，返回給AⅡ；如果IDi=ID*且mi=m*，Ω 查詢列表L2，得到h2i的值，隨機(jī)選取ki∈RZq*，計(jì)算Ki=kiP，再計(jì)算Vi=(Ki+h2iP)PKA-1，將Vi返回給AⅡ。

攻擊與挑戰(zhàn)：最后，經(jīng)過若干輪的詢問，AⅡ可以成功偽造出目標(biāo)用戶ID*對(duì)于消息m*的簽名σ*=(m*,K*,h*,V*) ，根據(jù)Forking 引理［10］知，通過對(duì)哈希運(yùn)算進(jìn)行分叉，AⅡ還可以輸出另一個(gè)有效簽名，下面看算法Ω 利用AⅡ解決困難問題。

由于AⅡ輸出的2個(gè)偽造簽名都是有效的，因此滿足驗(yàn)證等式

聯(lián)立式（2）式（3）得V*PK*-h*P=-，因此

也就是說，挑戰(zhàn)者Ω 成功解決了離散對(duì)數(shù)困難問題，這與困難性假設(shè)矛盾。因此，對(duì)于類型Ⅱ攻擊者，在適應(yīng)性選擇消息和身份攻擊下滿足存在性不可偽造。

5 效率比較

將改進(jìn)后的新方案與其他簽名方案進(jìn)行效率比較，其中P表示雙線性對(duì)運(yùn)算，H表示哈希運(yùn)算，E表示指數(shù)運(yùn)算，M表示標(biāo)量乘運(yùn)算，結(jié)果如表1所示。

表1 各方案效率比較Tab.1 The efficiency comparison of each scheme

由于雙線性對(duì)運(yùn)算的時(shí)間復(fù)雜度和計(jì)算復(fù)雜度都較高，一次雙線性對(duì)運(yùn)算的計(jì)算復(fù)雜度分別是指數(shù)運(yùn)算和哈希運(yùn)算的7倍和21倍；時(shí)間復(fù)雜度是指數(shù)運(yùn)算的10倍［5］。從表1可以看出，本文方案全文沒有使用雙線性對(duì)運(yùn)算，效率較高。

6 結(jié)束語

通過對(duì)文獻(xiàn)［9］的分析和研究，發(fā)現(xiàn)文獻(xiàn)［9］中的方案在安全性和效率方面都存在漏洞，因此對(duì)其進(jìn)行改進(jìn)，并在隨機(jī)語言機(jī)模型下證明了改進(jìn)方案滿足存在不可偽造性。將本文方案與已有無證書簽名方案進(jìn)行效率比較，發(fā)現(xiàn)本文方案在效率上具有優(yōu)勢(shì)。

[1]SHAMIR A.Identity-Based Cryptosystem and Signature Scheme[C]//Advances in Cryptology-Crypto′84.Berlin: Springer-Verlag,1984:47-53.

[2]AL-RIYAMI S,PATERSON K G.Certificateless Public Key Cryptography[C]//Advances in Cryptology-ASIACRYPT′03.Berlin:Springer-Verlag,2003:452-473.

[3]HUANG X,SUSILO W,MU Y,et al.On the security of a certificateless signature Schemes from Asia Crypt′03[C]//Proceedings of CANS′05.Berlin:Springer-Verlag,2005:13-25.

[4]LIU J K, AU M H, SUSILO W.Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model [C]// Proc ACM Symposium on Information, Computer and Communications Security.New York:ACM Press,2007:302-311.

[5]樊睿,王彩芬,藍(lán)才會(huì),等.新的無證書代理簽名方案[J].計(jì)算機(jī)應(yīng)用,2008,28(4):915-917.

[6]李明祥,杜光輝,羅新方.高效的無證書部分盲簽名方案[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(22):4817-4819.

[7]樊愛宛,楊照峰,謝麗明.強(qiáng)安全無證書簽名方案的安全性分析和改進(jìn)[J].通信學(xué)報(bào),2014,35(5):118-123.

[8]樊愛宛,申遠(yuǎn),趙偉艇.無證書簽名方案的安全性分析與改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2014,34(8):2342-2344,2349.

[9]劉倩,范安東,張麗娜,等.一個(gè)高效的無證書簽名方案分析與改進(jìn)[J].河南科技大學(xué)學(xué)報(bào):自然科學(xué)版,2014,35(4):49-53.

[10]POINTCHEVAL D,STERN J.Security Proofs for Signature Schemes[C]//Proceedings of the EUROCRYPT′96.Spain:Saragossa,1996:387-398.

[11]王麗莎,張建中.一種高效安全的無證書數(shù)字簽名方案[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):70-73.

[12]張磊,張福泰.一類無證書簽名方案的構(gòu)造方法[J].計(jì)算機(jī)學(xué)報(bào),2009,32(5):940-945.

[13]陳玲玲,亢保元,張磊.一種高效的基于身份的代理盲簽名方案[J].華東交通大學(xué)學(xué)報(bào),2008,25(1):113-116.