王 寧，王亞飛

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

0 引言

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

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

的無(wú)證書(shū)簽名方案更高。

1 基本理念模型

1.1 困難問(wèn)題假設(shè)

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

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

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

在橢圓曲線加法群上，困難問(wèn)題是，多項(xiàng)式時(shí)間算法不能解決它。

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

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

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

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

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

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

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

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

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

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

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

類(lèi)型 I 的敵手A1：A1不知道系統(tǒng)主密鑰及用戶的部分私鑰，但可以代替任意用戶的公鑰。 因?yàn)樵跓o(wú)證書(shū)密碼系統(tǒng)中，公鑰和持有者之間沒(méi)有認(rèn)證存在。

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

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

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

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

2.1 系統(tǒng)建立

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

（2）選擇主密鑰s∈￠*q，并計(jì)算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）公開(kāi)系統(tǒng)參數(shù)params={Fq,E/Fq,G,P,Ppub,H1,H2}，秘密保存主密鑰s。

2.2 部分私鑰提取

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

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

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

2.3 秘密值建立

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

2.4 公鑰建立

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

2.5 簽名

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

2.6 驗(yàn)證

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

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

3.1 安全性證明

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

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

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

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

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

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

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

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

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

否則，X 隨機(jī)選擇Zi∈￠*q，計(jì)算Zi=ziP；隨機(jī)選擇hi∈c*q，doi=⊥,計(jì)算Ri=aP-hiPpub, 令hi=H1(IDi,Ri)；隨機(jī)選擇ri,h2i∈c*q，記riP 的x 軸坐標(biāo)為xi, 計(jì)算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í)行以下詢問(wèn)之前已經(jīng)執(zhí)行有關(guān)ID 的Create 詢問(wèn)。

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

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

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

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

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

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

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

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

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

如果IDi≠I(mǎi)DI且對(duì)應(yīng)IDi的公鑰未被替換，X 知道用戶的秘密值和部分私鑰，則按照這些私鑰產(chǎn)生簽名。 否則，X 隨機(jī)選取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 返回一個(gè)無(wú)碰撞的ui作為H2的輸出內(nèi)容，并傳送給A1。

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

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

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

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

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

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

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

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

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

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

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

如果IDi≠I(mǎi)DI，X 隨機(jī)選擇Zi∈￠*q，計(jì)算Zi= ziP；否則，X 令zi=⊥，計(jì)算Zi=β=aP；

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

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

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

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

Super-Sign 詢問(wèn)： 假設(shè)A2作出簽名詢問(wèn)(IDi,m)。 X 隨機(jī)選取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 返回一個(gè)無(wú)碰撞的ui，作為H2的輸出內(nèi)容，并傳送給A2。

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

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

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

3.2 協(xié)議條件比較

本節(jié)從配對(duì)運(yùn)算（P）、指數(shù)運(yùn)算（E）、點(diǎn)乘運(yùn)算（M）這3 個(gè)運(yùn)算來(lái)進(jìn)行效率比較。

表1 無(wú)證書(shū)簽名方案比較Table 1 Non-certificate signature plan comparison

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

4 結(jié)語(yǔ)

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

[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.