一個安全高效的無證書簽名方案的分析和改進

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

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

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

1 預備知識

1.1 困難問題及假設

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

假設1離散對數困難性假設：如果不存在一個概率多項式時間（PPT）的算法，在時間t內，以一個大于0的概率ε解得群G上的DL問題，則稱離散對數困難性假設成立。

1.2 攻擊者類型［2］

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

2 文獻［9］方案分析

2.1 方案回顧

文獻［9］提出一個改進的無證書簽名方案。方案由系統參數生成、秘密值生成、公鑰生成、私鑰生成、簽名及驗證這6個算法組成，方案具體描述如下。

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

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

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

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

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

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

2.2 安全性與效率分析

通過對上述方案的分析，發現存在如下缺陷。

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

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

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

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

3 方案改進

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

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

2）用戶個人密鑰生成：簽名者A隨機選取xA∈Zq*作為用戶個人私鑰，計算XA=xAP作為對應的公鑰，公開XA，保密xA。

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

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

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

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

4 新方案的安全性分析

4.1 抗類型Ⅰ攻擊者的攻擊

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

證明因為類型Ⅰ攻擊者可以任意替換用戶公鑰，但是在改進的新方案中，由于在KGC生成的部分私鑰中利用哈希運算將用戶個人公鑰進行綁定，因此攻擊者無法替換用戶公鑰。即新方案可以抵抗類型Ⅰ攻擊者的攻擊。

4.2 抗類型Ⅱ攻擊者的攻擊

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

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

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

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

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

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

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

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

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

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

1）如果IDi≠ID*，Ω 查詢列表L1，Ls，Lk分別得到相應的h1i，xi及Di的值（假設在此之前已經進行過H1詢問，用戶個人密鑰詢問及部分密鑰詢問，不然可以先進行詢問），直接計算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，并隨機選取ki∈RZq*，計算Vi=SKi-1(ki+h2i)，返回給AⅡ；如果IDi=ID*且mi=m*，Ω 查詢列表L2，得到h2i的值，隨機選取ki∈RZq*，計算Ki=kiP，再計算Vi=(Ki+h2iP)PKA-1，將Vi返回給AⅡ。

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

由于AⅡ輸出的2個偽造簽名都是有效的，因此滿足驗證等式

聯立式（2）式（3）得V*PK*-h*P=-，因此

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

5 效率比較

將改進后的新方案與其他簽名方案進行效率比較，其中P表示雙線性對運算，H表示哈希運算，E表示指數運算，M表示標量乘運算，結果如表1所示。

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

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

6 結束語

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

[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]樊睿,王彩芬,藍才會,等.新的無證書代理簽名方案[J].計算機應用,2008,28(4):915-917.

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

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

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

[9]劉倩,范安東,張麗娜,等.一個高效的無證書簽名方案分析與改進[J].河南科技大學學報:自然科學版,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]王麗莎,張建中.一種高效安全的無證書數字簽名方案[J].計算機工程與應用,2012,48(15):70-73.

[12]張磊,張福泰.一類無證書簽名方案的構造方法[J].計算機學報,2009,32(5):940-945.

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