可證明安全的無對的無證書簽名方案研究

王 寧，王亞飛

（1. 黃河水利職業(yè)技術(shù)學(xué)院,河南 開封 475004；2.平頂山學(xué)院,河南 平頂山 467000）

0 引言

數(shù)字簽名在公鑰密碼學(xué)中有著非常重要的地位。 在正常的網(wǎng)絡(luò)活動中，它能保證用戶網(wǎng)絡(luò)活動的合法性和安全性。 簽名可以在傳統(tǒng)的公鑰基礎(chǔ)設(shè)施（Public Key Infrastructure，簡稱PKI）和基于身份的公鑰密碼學(xué)下實現(xiàn)[1]。 傳統(tǒng)的PKI 密碼學(xué)面臨著復(fù)雜的證書管理問題，而基于身份的密碼學(xué)存在與生俱來的密鑰托管問題，即密鑰生產(chǎn)中心（key generator center，簡稱KGC）知道用戶的私鑰。 有了用戶的私鑰，惡意的KGC 就可以很容易模仿用戶對消息進行簽名等操作。 為了解決以上問題，2003 年，Al-Riyami 等[2]提出了無證書公鑰密碼學(xué)。 在無證書公鑰密碼學(xué)中，用戶的私鑰由兩部分構(gòu)成，一部分是KGC利用系統(tǒng)的主密鑰產(chǎn)生的用戶部分私鑰，另一部分是由用戶自己選擇的秘密值。 此外，用戶的公鑰是由用戶自己選取的秘密值所導(dǎo)出的，無需PKI 證書。因此，無證書密碼學(xué)避免了證書管理和密鑰托管問題。

在無證書密碼學(xué)應(yīng)用中，一些研究者提出了基于雙線性對的無證書數(shù)字簽名方案[3～7]。 雙線性對運算開銷較大，一個對運算至少是橢圓曲線上點乘運算的20 倍[10]。 因此，人們又提出了一些基于指數(shù)運算的無對的無證書數(shù)字簽名[8～9]。 然而，一個指數(shù)運算至少是橢圓曲線上點乘運算的10 倍[10]。為了進一步提高效率，利用ECDSA 和Schnorr 簽名的思想，筆者提出一個無對的無證書簽名方案。 新的方案沒有雙線性對運算和指數(shù)運算，方案效率要比其他現(xiàn)有

的無證書簽名方案更高。

1 基本理念模型

1.1 困難問題假設(shè)

令E/Fq表示定義在有限素域Fq上的橢圓曲線E:y2=x3+ax+bmodq，其中a，b∈Fq，q＞3，4a3+27b2≠0modq。 E/Fq上的點和一個 “無窮遠點”O(jiān) 組成一個群：G={(x,y):x,y∈Fq,E(x,y)=0}U{O}。

令群G 的階為n。在如下的加運算下，G 形成一個加法循環(huán)群：

令P,Q∈G，l 是過點P 和Q 的直線（若P=Q，則l 是過點P 的切線），R 是l 與E/Fq相交的第3 個點。過點R 作垂線交E/Fq于點R'（另一個交點為O），則P+Q=R'。與此相應(yīng)，可以定義群G 上的乘法運算為：tP=P+L+P(t 次，t∈￠*q)。

在橢圓曲線加法群上，困難問題是，多項式時間算法不能解決它。

橢圓曲線離散對數(shù)問題(ECDLP)：給定兩個元素P，Q∈G，求整數(shù)a∈￠*q，使得P=aQ 成立。

1.2 無證書數(shù)字簽名的定義

一個無證書數(shù)字簽名方案[3]由以下6 個算法構(gòu)成：

（1）系統(tǒng)建立（Setup）。 輸入安全參數(shù)l，返回系統(tǒng)公共參數(shù)params 和系統(tǒng)主密鑰s。 KGC 運行該算法，建立了一個無證書系統(tǒng)。

（2）部分私鑰提取(Extract-Partial-Private-Key)。輸入params，系統(tǒng)主密鑰和用戶的身份ID，輸出部分私鑰DID。 KGC 運行該算法，產(chǎn)生用戶的部分私鑰，并通過安全信道發(fā)給相應(yīng)的用戶。

（3）秘密值建立(Set-Secret-Value)。 輸入params和用戶的身份ID，輸出用戶的秘密值xID。 系統(tǒng)中每個用戶均執(zhí)行該算法，產(chǎn)生各自的秘密值。

（4）公鑰建立(Set-Public-Key)。輸入params 和用戶的秘密值xID，輸出用戶公鑰pkID。 系統(tǒng)中每個用戶執(zhí)行該算法，產(chǎn)生各自的公鑰，并公開公鑰。

（5）簽名（Sign）。 這是無證書簽名算法。 輸入params、待簽消息m、用戶（簽名人）的身份ID、公鑰pkID、部分私鑰DID以及秘密值xID，該算法輸出簽名σ。

（6）驗證(Verify)。 這是一個確定的簽名驗證算法。 輸入params，簽名人的身份ID、公鑰pkID、消息m 以及簽名σ，返回“1”，說明該簽名有效，返回“0”說明該簽名無效。

1.3 無證書數(shù)字簽名的安全模型

在無證書密碼系統(tǒng)中，有兩種類型具備不同能力的敵手A1，A2。 假設(shè)A1模擬的是一個不誠實的用戶，而A2是一個惡意但被動的KGC。

類型 I 的敵手A1：A1不知道系統(tǒng)主密鑰及用戶的部分私鑰，但可以代替任意用戶的公鑰。 因為在無證書密碼系統(tǒng)中，公鑰和持有者之間沒有認證存在。

類型II 的敵手A2：A2掌握系統(tǒng)主密鑰，知道用戶的部分私鑰，但它不能替換目標用戶的公鑰。

Huang[3]將（類型I/類型II）敵手按能力從弱到強分 成 了3 類：Normal 敵 手、Strong 敵 手 和Super 敵手。對于Super 敵手，即使其在替換用戶公鑰時不提供該公鑰對應(yīng)的秘密值，也能得到在替換后的公私鑰下有效的消息——簽名對。 方案如果能夠抵抗住Super 敵手的攻擊，便能抵抗住Strong 敵手和Normal敵手的攻擊。

2 新方案的設(shè)置規(guī)劃

本文提出的無對的無證書簽名方案由以下6個算法構(gòu)成（本方案所計算的整數(shù)均需要mod q）。

2.1 系統(tǒng)建立

（1）給定安全參數(shù)l，KGC 選擇l 比特的大素數(shù)q，定義1.1 節(jié)所要求的{Fq;E/Fq;G;P}。

（2）選擇主密鑰s∈￠*q，并計算Ppub=sP。 選擇Hash函數(shù)H1:{0,1}*×G→Z*q、H1:{0,1}*×G×Z*q→Z*q和H3,H4:{0,1}*×{0,1}*×G3→c*q。

（3）公開系統(tǒng)參數(shù)params={Fq,E/Fq,G,P,Ppub,H1,H2}，秘密保存主密鑰s。

2.2 部分私鑰提取

（1） 輸入用戶的身份ID 后，KGC 隨機選取r0,r1∈￠*q, 計算R0=rop，d0=(r0+H1(ID,R0)s)-1。

（2）計算R1=r1P，并將R1的x 軸坐標，取整求余為x1，然后計算d1=r-11(sx1+H2(ID,R0,x1)。

（3）設(shè)置d0為用戶的部分私鑰，{R0,x1,d1}為用戶的部分公鑰。

2.3 秘密值建立

身份為ID 的用戶隨機選取ZID∈￠*q作為自己的秘密值。

2.4 公鑰建立

身份為ID 的用戶計算ZID=zIDP， 并設(shè)置PKID={ZID,R0,x1,d1}為自己的公鑰。

2.5 簽名

身份為ID 的用戶對消息m∈(0，1)*簽名如下：（1）隨機選取k∈￠*q，計算K=kp。 （2）計算u=H3(m,ID,K,PKID)，w=H4(m,ID,K,PKID)。 （3）計算v=k+ud-10+wziID。 則簽名者對消息m 的簽名σ=(u,v,w)。

2.6 驗證

給定params。 簽名者的身份ID 以及對應(yīng)的公鑰PKID ={ZID,R0,x1,d1}。 驗 證 者 收 到(m,σ)后，計算Q=d-11x1·Ppub+d-11H2(ID,R0,x1)·P，K'=vp-u[R0+H1(ID,R0)·Ppub]-wZID，將Q 的x 軸坐標為xQ。然后，驗證等式xQ=x1和u=H2(ID,m,K',PKID)是否成立。 如果兩個等式成立，則輸出“接受”，否則，輸入“拒絕”。

3 新方案的安全性證明和協(xié)議條件比較

3.1 安全性證明

以下在隨機預(yù)言機模型下，證明新方案的安全性。

定理1：在ECDLP 和隨機預(yù)言機模型下，所提方案在適應(yīng)性選擇消息和身份攻擊下，是抗存在性偽造的。

上述定理可以由下面的引理1 和引理2 推導(dǎo)出。

引理1：在ECDLP 和隨機預(yù)言機模型下，對于Super 類型I 敵手A1，新方案在適應(yīng)性選擇消息攻擊下是抗存在性偽造的。

證明： 假定給算法X 一個離散對數(shù)問題的實例：(P,β=aP∈G1)，X 的任務(wù)是計算和輸出該問題的解a。

X 運行Setup 算法，產(chǎn)生系統(tǒng)參數(shù)params={Fq;E/Fq;G;P;Ppub,H1,H2}，其中Ppub=sP。 X 隨機挑選IDI(1≤I≤qH1, 是Super 敵手A1訪問H1預(yù)言機的最大次數(shù)) 作為這次游戲的挑戰(zhàn)者,發(fā)送系統(tǒng)參數(shù)params 給A1。

A1執(zhí)行以下詢問：

Create(IDi)：X 維持一個包含元組(IDi,{Ri,d1i,xi,Zi},{d0i,zi})的列表Lcreate。

如果IDi≠IDI，X 隨機選擇zi∈c*q， 計算Zi=ziP；隨機選擇d0i,h1i∈c*q，計算Ri=(d0i)-1P-hoiPpub，令h1i=H1(IDi,Ri)；隨機選擇ri,h2i∈￠*q，記riP 的x 軸坐標為xi, 計算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

否則，X 隨機選擇Zi∈￠*q，計算Zi=ziP；隨機選擇hi∈c*q，doi=⊥,計算Ri=aP-hiPpub, 令hi=H1(IDi,Ri)；隨機選擇ri,h2i∈c*q，記riP 的x 軸坐標為xi, 計算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

在列表Lcreate 中記錄 (IDi,{Ri,d1i,xi,Zi},{d0i,zi}),在列表LH1記錄(IDi,Ri,h1i),在列表LH2中記錄(IDi,Ri,xi,h2i)。

不失一般性，我們假定A1在執(zhí)行以下詢問之前已經(jīng)執(zhí)行有關(guān)ID 的Create 詢問。

H1-詢問：X 模擬H1隨機預(yù)言機，維持列表LH1，記錄元組(IDi,Ri,h1i)。 如果列表中存在，返回h1i，否則隨機選擇h1i∈c*q返回給A1，并添加到列表LH1中。

H2-詢問：X 模擬H2隨機預(yù)言機，維持列表LH2，記錄元組(IDi,Ri,h2i)。 如果列表中存在，返回h2i，否則隨機選擇h2i∈c*q返回給A1，并添加到列表LH2中。

H3-詢問：X 模擬H3隨機預(yù)言機，維持列表LH3，記錄元組(IDi,m,Ki,PKi,h3i)。 如果列表中存在，返回h3i，否則隨機選擇h3i∈c*q返回給A1，并添加到列表LH3中。

H4-詢問：X 模擬H3隨機預(yù)言機，維持列表LH4，記錄元組(IDi,m,Ki,PKi,h4i)。 如果列表中存在，返回h3i，否則隨機選擇h4i∈c*q返回給A1，并添加到列表LH4中。

Extract-Partial-Private-Key(IDi)：如 果IDi=IDI，則X 中止；否則X 查找列表Lcreate 中對應(yīng)于IDi的元組(IDi,{Ri,d1i,xi,Zi},{d0i,zi})，返回部分私鑰d0i。

Secret-Value-Extract(IDi)：X 查找列表Lcreate中對應(yīng)于IDi的元組(IDi,{Ri,d1i,xi,Zi},{d0i,zi})，返回秘密值zi。

Public-Key-Replace(IDi,PK'i=(R'i,d1'i,x'i,W'i)：X 首先計算Qi=(d1'i)-1x'i·Ppub+(d1'i)-1H2(IDi,r'i,x'i)·P，Qi的x 軸坐標為xQi。然后驗證等式xQi=xi是否成立。如果不成立，則拒絕替換；如果成立，則查找列表Lcreate中對應(yīng)于IDi的元組(IDi,{Ri,d1i,xi,Zi},{d0i,zi}), 將{Ri,d1i,xi,Zi}替換為{R'i,d1'i,x'i,W'i}。這里需要說明的是，由于{d1i,xi})是符合橢圓曲線數(shù)字簽名算法ECDSA 的簽名，而ECDSA 是不可偽造的， 所以對于任何IDi來說，其Ri，d1i,xi是不可能被敵手替換的， 只有Zi可能被替換。

Public-Key-Request(IDi)：C 查找列表Lcreate中對應(yīng)于IDi的元組(IDi,Ri,Zi,di,xi)，返回(Ri,Zi)。

Super-Sign 詢問： 假設(shè)A1作出簽名詢問(IDi,m)。

如果IDi≠IDI且對應(yīng)IDi的公鑰未被替換，X 知道用戶的秘密值和部分私鑰，則按照這些私鑰產(chǎn)生簽名。 否則，X 隨機選取ui,vi,wi∈c*q作為簽名， 令ui=H3(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi)，并將(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi,ui)添加到列表LH3中，X 返回一個無碰撞的ui作為H2的輸出內(nèi)容，并傳送給A1。

偽造：模擬結(jié)束后，最終A1以一個不可忽略的概率輸出一個有效簽名。如果ID*≠IDI，則X 停止模擬。 否則，由分叉引理，存在算法可以在PPT 時間內(nèi)生成兩個有效簽名(IDi,m,K,u1,v1,w1)和(IDi,m,K,u2,v2,w1)，且u1≠u2。 則有以下等式成立：

K=v1P-u1(RI+H1(IDI,RI)Ppub)-w1ZI

K=v2P-u2(RI+H1(IDI,RI)Ppub)-w1ZI

由這兩個式子得： (v1-v2)P=(u1-u2)aP

所以有a=(v1-v2)/(u1-u2)， 從而X 解決了ECDLP的一個實例。

引理2：在ECDLP 和隨機預(yù)言機模型下，對于Super 類型II 敵手A2， 所提方案在適應(yīng)性選擇消息攻擊下是抗存在性偽造的。

證明： 假定給算法X 一個離散對數(shù)問題的實例：(P，β=aP∈G1)，X 的任務(wù)是計算和輸出該問題的解a。

X 隨機選取s∈c*q作為系統(tǒng)主密鑰，計算Ppub=sP，然 后 產(chǎn) 生 系 統(tǒng) 參 數(shù)params={Fq；E/Fq；G；P；Ppub，H1，H2}。 X 隨機挑選IDI(1≤I≤qH1，是Super 敵手A2訪問H1預(yù)言機的最大次數(shù)) 作為這次游戲的挑戰(zhàn)者，發(fā)送系統(tǒng)參數(shù)params 和s 給A2。 由于A2知道s，它不再詢問Extract-Partial-Private-Key。

A2執(zhí)行以下詢問：

Create(IDi)：X 維持一個包含元組(IDi,{Ri,d1i,xi,Zi},{d0i,zi})的列表Lcreate。

X 隨機選擇roi,h1i∈￠*q， 計算Ri=r0iP 和d0i=(roi+shoi)-1,令h1i=H1(IDi,Ri)；隨機選擇ri,h2i∈￠*q，記riP 的x 軸坐標為xi。 計算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

如果IDi≠IDI，X 隨機選擇Zi∈￠*q，計算Zi= ziP；否則，X 令zi=⊥，計算Zi=β=aP；

最后，在列表Lcreate中記錄(IDi,{Ri,d1i,xi,Zi},{d0i,zi}),在列表LH1中記錄(IDi,Ri,h1i),在列表LH2中記錄(IDi,Ri,xi,h2i)。

Hi-詢問(i=1,2,3,4)同引理1。

Secret-Value-Extract(IDi)：如果IDi=IDI，則X 中止； 否則，X 查找列表Lcreate中對應(yīng)于IDi的元組(IDi,{Ri,D1i,xi,Zi}, {doi,zi})，返回秘密值zi。

Public-Key-Replace(IDi)：如果IDi=IDI，則X 中止；否則，X 按照引理1 中的Public-Key-Replace 詢問進行判斷和回答。

Super-Sign 詢問： 假設(shè)A2作出簽名詢問(IDi,m)。 X 隨機選取ui，vi，wi∈￠*q作為簽名，令ui=H3(IDi,m，viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi)，并將(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi,ui)添 加 到 列 表LH3中，X 返回一個無碰撞的ui，作為H2的輸出內(nèi)容，并傳送給A2。

偽造：模擬結(jié)束后，最終A2以一個不可忽略的概率輸出一個有效簽名(ID*,m,σ*=(u*,v*)。 如果ID*≠IDI，則X 停止模擬。 否則，由分叉引理，存在算法可以在PPT 時間內(nèi)生成兩個有效簽名(IDi,m,K,u1,v1,w1)和(IDi,m,K,u2,v2,w1)，且u1≠u2。 則有以下等式成立：

由這兩個式子得： (v1-v2)P=(w1-w2)aP

所以有a=(v1-v2)/(w1-w2)， 從而X 完成了解決ECDLP 問題的一個實例。

3.2 協(xié)議條件比較

本節(jié)從配對運算（P）、指數(shù)運算（E）、點乘運算（M）這3 個運算來進行效率比較。

表1 無證書簽名方案比較Table 1 Non-certificate signature plan comparison

在同等安全級別下（橢圓曲線上160 bit 的群元素等同于1024 bit RSA 安全級別）， 運行一次雙線性對所需的時間約為有限域上指數(shù)運算的10 倍左右。 由表1 可知，所提方案的協(xié)議具有較高的效率和較強的安全性。

4 結(jié)語

本文提出的無對的無證書簽名方案，由于不含雙線性對和指數(shù)運算，計算開銷明顯降低，效率較高。在安全性方面，它在橢圓曲線離散對數(shù)問題假設(shè)下，它能夠抵抗住無證書簽名的最強攻擊類型。因此，安全性較強。

[1] A. Shamir. Identity-based Cryptosystems and Signature Schemes [M]. Advances in Cryptology-Crypto'84, LNCS 196, Berlin: Springer-Verlag, 1985：47-53.

[2] S. Al-Riyami, K. Paterson. Certificateless public key cryptography [M]. ASIACRYPT 2003, LNCS 2894,Berlin: Springer-Verlag, 2003：452-473.

[3] X. Huang, Y. Mu, W. Susilo, D. Wong, and W. Wu.Certificateless signature revisited [M]. ACISP 2007,LNCS 4586, Berlin: Springer-Verlag, 2007：308-322.

[4] H. Du，Q.Wen，Efficient and provably-secure certificateless short signature scheme from bilinear pairings[J]. Computer Standards and Interfaces, 2009,31(2): 390-394.

[5] L. Zhang, F. Zhang, A new provably secure certificateless signature scheme. ICC 2008, IEEE Communications Society.

[6] B. Hu，D. Wong，Z. Zhang，et al.Certificateless signature:a new security model and an improved generic construction[J]. Design, Codes and Cryptography,2007,42:109-126.

[7] K. Choi，J. Park，J. Hwang, et al. Efficient certificateless signature schemes. ACNS'2007[M]. LNCS 4521, Berlin: Springer-Verlag, 2007:443-458.

[8] A. Ge，S. Chen，X. Y. Huang. A concrete certificateless signature scheme without pairings. The 2009 International Conference on Multimedia Information Networking and Security [J]. IEEE Computer Society, 2009(2):374-377.

[9] J. Zhang，J. Mao. An efficient RSA-based certificateless signature scheme [J]. The Journal of Systems and Software(2011)，2011(09):36.

[10] X. Cao，W. Kou，X. Du. A pairing-free identity-based authenticated key agreement protocol with minimal message exchanges [J]. Information Sciences, 2010，180(15)：2895-2903.