周華靜，劉二根，左黎明

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

?

對(duì)一個(gè)高效的基于證書(shū)簽名方案的分析和改進(jìn)

周華靜1,2，劉二根1，左黎明1,2

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

摘要：在發(fā)現(xiàn)第一類(lèi)攻擊者容易攻破一個(gè)高效的基于證書(shū)簽名方案后，對(duì)原方案進(jìn)行改進(jìn)，并在逆Diffie-Hellman和計(jì)算Diffie-Hellman困難性假設(shè)下，利用隨機(jī)預(yù)言機(jī)模型證明了改進(jìn)方案在適應(yīng)性選擇消息和身份下具有不可偽造性。同時(shí)，將改進(jìn)后方案的效率，與已有基于證書(shū)簽名方案效率相比，發(fā)現(xiàn)該方案是高效的。

關(guān)鍵詞：公鑰密碼學(xué)；數(shù)字簽名；基于證書(shū)；隨機(jī)預(yù)言機(jī)模型

Gentry[1]在歐洲密碼學(xué)會(huì)第一次提出了基于證書(shū)公鑰密碼系統(tǒng)(Certificate-Based Public Key Cryptography，CB-PKC)的概念?；谧C書(shū)公鑰密碼體制下的用戶(hù)證書(shū)，不僅具備傳統(tǒng)公鑰證書(shū)的所有功能，而且可以用來(lái)生成簽名和解密密鑰，同時(shí)解決了基于身份密碼體制下固有的密鑰托管問(wèn)題。隨后，Kang等[2]首次將基于證書(shū)公鑰密碼系統(tǒng)應(yīng)用到數(shù)字簽名的領(lǐng)域，提出了基于證書(shū)數(shù)字簽名(Certificate-Based Signature，CBS)的概念，給出其安全性定義，同時(shí)，給出了兩個(gè)具體的基于證書(shū)的數(shù)字簽名方案；Liu等[3]給出兩個(gè)基于證書(shū)的簽名方案；Wu等[4]給出了由無(wú)證書(shū)簽名(Certificateless Signature，CLS)生成基于證書(shū)簽名的一般性方法；王雯娟等[5]提出一個(gè)基于計(jì)算Diffie-Hellman問(wèn)題(CDHP)下的，利用Schnorr簽名思想構(gòu)造的一個(gè)新型高效基于證書(shū)數(shù)字簽名方案；最近，陳江山等[6]也給出了一個(gè)高效的基于證書(shū)數(shù)字簽名方案。通過(guò)對(duì)文獻(xiàn)[6]方案進(jìn)行安全性分析時(shí)發(fā)現(xiàn)其對(duì)于類(lèi)型I攻擊者的攻擊并不安全，因此在原方案的基礎(chǔ)上提出改進(jìn)方案，修補(bǔ)了原方案的漏洞，并對(duì)其進(jìn)行安全性分析。

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

設(shè)G1為加法循環(huán)群，G2為乘法循環(huán)群，且群的階均為素?cái)?shù)p。設(shè)一個(gè)映射e∶G1×G1→G2且滿(mǎn)足下面3個(gè)性質(zhì)：

2)非退化性：存在P,Q∈G1，滿(mǎn)足

e(P,Q)≠1；

3)可計(jì)算性：對(duì)于任意的P,Q∈G1，存在有效的多項(xiàng)式時(shí)間算法可以算出e(P,Q)。

則稱(chēng)該映射為雙線(xiàn)性映射。

定義1逆Diffie-Hellman問(wèn)題(Inv-DHP):設(shè)P為乘法循環(huán)群G的生成元，給定aP，計(jì)算a-1P。

定義2計(jì)算Diffie-Hellman問(wèn)題(CDHP):設(shè)P為加法循環(huán)群G的生成元，給定aP，bP，計(jì)算abP。

假設(shè)1計(jì)算逆Diffie-Hellman困難性假設(shè)：如果不存在一個(gè)概率多項(xiàng)式時(shí)間算法(PPT)，使得在時(shí)間t內(nèi)，以至少ε的概率解群G上的Inv-DHP，則稱(chēng)(t,ε)-Inv-DHP困難假設(shè)在該群上成立。

假設(shè)2計(jì)算Diffie-Hellman困難性假設(shè)：如果不存在PPT算法，使得在時(shí)間t內(nèi)，以至少ε的概率解群G上的CDHP，則稱(chēng)(t,ε)-CDHP困難假設(shè)在該群上成立。

定義3基于證書(shū)數(shù)字簽名方案由下面6個(gè)算法構(gòu)成：

1)系統(tǒng)參數(shù)建立：輸入系統(tǒng)安全參數(shù)1k，輸出系統(tǒng)公開(kāi)參數(shù)params及系統(tǒng)主私鑰sk，主公鑰pk；

2)用戶(hù)密鑰生成：輸入系統(tǒng)主公鑰pk及公開(kāi)參數(shù)params，輸出用戶(hù)A的個(gè)人私鑰SKA和公鑰PKA；

3)證書(shū)生成：輸入系統(tǒng)主私鑰sk、公開(kāi)參數(shù)params和用戶(hù)A的公鑰PKA，輸出對(duì)應(yīng)的用戶(hù)公鑰證書(shū)CA；

4)簽名密鑰生成：輸入用戶(hù)證書(shū)CA、用戶(hù)A的私鑰SKA和公開(kāi)參數(shù)params，輸出用戶(hù)A的簽名密鑰SA；

5)簽名：輸入消息m∈{0,1}*、用戶(hù)A的簽名密鑰SA和公開(kāi)參數(shù)params，輸出消息m的簽名σ；

6)驗(yàn)證：輸入消息簽名對(duì)(m,σ)、用戶(hù)A的公鑰PKA和系統(tǒng)主公鑰pk，輸出0或者1(0表示簽名無(wú)效，1表示簽名有效)。

一個(gè)安全的基于證書(shū)數(shù)字簽名方案，必須滿(mǎn)足下面的正確性和不可偽造性。

定義4(正確性)如果一個(gè)基于證書(shū)的數(shù)字簽名方案是由簽名人嚴(yán)格按照簽名算法的步驟產(chǎn)生的，那么該簽名能夠通過(guò)驗(yàn)證等式，即該簽名方案滿(mǎn)足正確性。

下面定義基于證書(shū)數(shù)字簽名的不可偽造性：

定義5(攻擊模型)[7]在基于證書(shū)的簽名方案中存在兩種類(lèi)型的攻擊者：類(lèi)型I攻擊者AI和類(lèi)型II攻擊者AII。

類(lèi)型I攻擊者AI：AI模擬用戶(hù)進(jìn)行攻擊，即試圖以用戶(hù)的身份偽造簽名。AI知道用戶(hù)的私鑰，可以任意替換用戶(hù)的公鑰，但不知對(duì)應(yīng)的公鑰證書(shū)。

類(lèi)型II攻擊者AII：AII模擬認(rèn)證中心進(jìn)行攻擊，即不誠(chéng)實(shí)的證書(shū)授權(quán)中心試圖偽造簽名。AII知道系統(tǒng)主私鑰，可以生成任意用戶(hù)的公鑰證書(shū)，但他不知道對(duì)應(yīng)用戶(hù)的私鑰，不能替換用戶(hù)公鑰。

基于證書(shū)簽名的存在性不可偽造可通過(guò)攻擊者A∈{AI,AII}和挑戰(zhàn)者C之間的游戲來(lái)定義：

游戲1(AI和C參與游戲)

1)初始化：輸入系統(tǒng)安全參數(shù)1k，C執(zhí)行系統(tǒng)參數(shù)建立算法，生成系統(tǒng)公開(kāi)參數(shù)params、主私鑰sk和公鑰pk，并將params和pk發(fā)送給AI。

2)詢(xún)問(wèn)：攻擊者AI可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行下列適應(yīng)性的詢(xún)問(wèn)：

①密鑰詢(xún)問(wèn)：

AI可以對(duì)任意用戶(hù)進(jìn)行公私鑰詢(xún)問(wèn)；

②Hash詢(xún)問(wèn)：

AI可以對(duì)任意輸入的Hash值進(jìn)行詢(xún)問(wèn)；

③證書(shū)詢(xún)問(wèn)：

AI可以對(duì)任意用戶(hù)的證書(shū)進(jìn)行詢(xún)問(wèn)；

④簽名詢(xún)問(wèn)：

AI可以對(duì)任意消息對(duì)應(yīng)的簽名進(jìn)行詢(xún)問(wèn)。

3)偽造：AI輸出身份為ID*，對(duì)應(yīng)消息為m*的簽名σ*。

如果AI輸出的偽造簽名σ*可以通過(guò)驗(yàn)證等式，且AI沒(méi)有詢(xún)問(wèn)過(guò)身份為ID*的用戶(hù)證書(shū)和對(duì)應(yīng)的簽名，則AI贏得游戲1。

游戲2(AII和C參與游戲)

1)初始化：輸入系統(tǒng)安全參數(shù)1k，C執(zhí)行系統(tǒng)參數(shù)建立算法，生成系統(tǒng)公開(kāi)參數(shù)params、主私鑰sk和公鑰pk，并將params，pk及sk發(fā)送給AII。

2)詢(xún)問(wèn)和偽造與游戲1中的相同。

如果AII輸出的簽名σ*可以通過(guò)驗(yàn)證等式，且AII沒(méi)有詢(xún)問(wèn)過(guò)身份為ID*私鑰和對(duì)應(yīng)的簽名，則AII贏得游戲2。

定義6(不可偽造性)如果不存在一個(gè)PPT算法能夠以不可忽略的概率借助攻擊者AI和AII贏得游戲，則稱(chēng)該基于證書(shū)數(shù)字簽名方案在適應(yīng)性選擇消息和身份下是存在性不可偽造的。

定義7(安全性)若一個(gè)基于證書(shū)數(shù)字簽名方案滿(mǎn)足正確性且在適應(yīng)性選擇消息和身份攻擊下是存在性不可偽造的，則稱(chēng)該方案滿(mǎn)足安全性。

2原始方案分析

2.1 方案回顧

原方案[6]是一個(gè)基于證書(shū)的數(shù)字簽名方案，具體描述如下。

Step3證書(shū)生成：CA計(jì)算簽名者A的證書(shū)為CA=sPA=sH1(PKC,PKA,IDA，i)，其中IDA為A的身份，并將證書(shū)CA發(fā)送給A；

Step4簽名密鑰生成：簽名者A計(jì)算簽名密鑰為SA=CA+xPA，并作預(yù)運(yùn)算f=e(SA,PKC)=e(PA,PKA2)；

Step6驗(yàn)證：驗(yàn)證者先計(jì)算f=e(PA,PKA2)，再驗(yàn)證等式h=H2[m,e(V,PKC)fh]是否成立。如果等式成立則接受簽名，否則拒絕簽名。

2.2方案中的缺陷

分析上述方案，發(fā)現(xiàn)類(lèi)型I攻擊者可以偽造簽名并能通過(guò)驗(yàn)證等式。具體攻擊過(guò)程如下。

由于類(lèi)型I攻擊者AI已知用戶(hù)私鑰x，而在原方案簽名密鑰生成過(guò)程中f=e(PA,PKA2)=

3改進(jìn)方案

在原方案基礎(chǔ)上，利用雙線(xiàn)性對(duì)映射構(gòu)造了一個(gè)改進(jìn)的基于證書(shū)的簽名方案，包含3個(gè)參與者，分別是證書(shū)生成中心(CertificateGenerateCenter，CGC)、簽名者和驗(yàn)證者。具體描述如下。

Step3證書(shū)生成：證書(shū)生成中心計(jì)算CA=

sPA=sH1(PKC‖PKA‖IDA)，其中IDA表示用戶(hù)A的身份信息，將CA發(fā)送給用戶(hù)A作為其證書(shū)；

Step4簽名密鑰生成：用戶(hù)A計(jì)算簽名密鑰

S=CA+xPA，再作預(yù)運(yùn)算f=e(S,PKC)e(PA,PKC)；

T=ft，h=H2(m‖T)，生成簽名σ=(V,h)，其中V=(t-h)(S+PA)；

Step6驗(yàn)證：驗(yàn)證者先計(jì)算f=e(PA,X2)，再驗(yàn)證h=H2[m,e(V,PKC)fh]是否成立。如果成立則輸出1，表示接收簽名；否則輸出0，表示拒絕簽名。

4安全性分析

定理1改進(jìn)后的基于證書(shū)的簽名方案是正確的。

證明e(V,PKC)fh=e[(t-h)(S+PA),PKC]fh=

e(S+PA,PKC)t-hfh=

e(S+PA,PKC)t=ft=T

即驗(yàn)證等式成立。

定理2(類(lèi)型I攻擊下的不可偽造性)改進(jìn)后的基于證書(shū)簽名方案在適應(yīng)性選擇消息攻擊下能抵抗類(lèi)型I攻擊者的攻擊，否則Inv-DHP可解。

證明若挑戰(zhàn)者C想解決Inv-DHP，那么問(wèn)題實(shí)例為已知aP，計(jì)算a-1P。假設(shè)類(lèi)型I攻擊者AI能以不可忽略的概率成功偽造上述簽名方案，則看挑戰(zhàn)者C如何利用AI解決Inv-DHP。C通過(guò)維護(hù)一些列表來(lái)模擬回答AI的詢(xún)問(wèn)，這些列表為PK-List，H1-List，H2-List，CA-List，Sig-List格式分別為(IDi，PKi，xi)，(PKC，PKi，IDi,h1i)，(mi,Ti,h2i)，(PKC,PKi,IDi,Ci)，(m,t,σi)且都初始化為空。

首先，C運(yùn)行系統(tǒng)參數(shù)建立算法，產(chǎn)生公開(kāi)參數(shù)params={k,q,e,G1,G2,H1,H2,P},隨機(jī)選取

1≤j≤qH1，其中qH1為AI對(duì)H1作的最大詢(xún)問(wèn)次數(shù)，令PKC=aP；

H2詢(xún)問(wèn)：AI對(duì)H2-List進(jìn)行詢(xún)問(wèn)，若存在(mi,T,h2i)，則返回h2i給AI，否則C隨機(jī)選擇

證書(shū)詢(xún)問(wèn)：AI對(duì)CA-List進(jìn)行詢(xún)問(wèn)(假設(shè)AI已進(jìn)行過(guò)H1-List詢(xún)問(wèn)，否則可以先進(jìn)行H1詢(xún)問(wèn))，當(dāng)i≠j時(shí)C檢查H1-List，返回Ci=h1iP給AI；當(dāng)i=j時(shí)詢(xún)問(wèn)終止；

簽名詢(xún)問(wèn)：AI對(duì)Sig-List進(jìn)行詢(xún)問(wèn)，C選擇

偽造：AI經(jīng)過(guò)以上詢(xún)問(wèn)訓(xùn)練輸出消息為m，身份為ID的有效偽造簽名σ1=(V1,h1)，由分叉引理[3]知，AI可生成消息m的另一個(gè)有效偽造簽名σ2=(V2,h2)。

由(V1-V2)=(h2-h1)(S+PA)，則(h2-h1)-1(V1-V2)=S+PA=a-1yP+xyP+yP，即a-1P=y-1(h2-h1)-1(V1-V2)-xP-P。

因此挑戰(zhàn)者C成功解決了Inv-DHP困難問(wèn)題。

下面計(jì)算挑戰(zhàn)者C解決Inv-DHP困難問(wèn)題的概率。設(shè)AI最多進(jìn)行qH1次H1詢(xún)問(wèn)和qUK次公鑰詢(xún)問(wèn)，AI輸出有效偽造簽名的概率為ε，則在對(duì)H1-List的詢(xún)問(wèn)中未詢(xún)問(wèn)身份IDi的概率為(1-1/qH1)qH1，輸出有效偽造簽名(m,ID,σ)中ID=IDi的概率至少為1/qUK，因此C解決困難問(wèn)題的概率≥ε(1-1/qH1)qH1/qUK=O(ε)。即如果攻擊者AI可以在多項(xiàng)式時(shí)間內(nèi)以不可忽略的概率ε贏得游戲1，那么C就能以不低于O(ε)的概率解決Inv-DHP問(wèn)題。

定理3改進(jìn)后的基于證書(shū)簽名方案在適應(yīng)性選擇消息攻擊下能夠抵抗類(lèi)型II攻擊者的攻擊，否則CDH問(wèn)題可解。

證明挑戰(zhàn)者C想解決CDHP，則問(wèn)題實(shí)例為已知aP,bP，計(jì)算abP。假設(shè)類(lèi)型II攻擊者AII能以不可忽略的概率攻破上述簽名方案，則看挑戰(zhàn)者C如何利用AII解決CDHP。

證書(shū)詢(xún)問(wèn)：AII對(duì)H1-List進(jìn)行詢(xún)問(wèn)，C檢索列表，從列表中找出(PKC,PKi,IDi,h1i)，并返回證書(shū)Ci=sPAi發(fā)送給AII；

偽造：經(jīng)過(guò)上述詢(xún)問(wèn)訓(xùn)練，攻擊者AII輸出消息為m*，身份為ID*的簽名σ*=(V*,h*)，又由分叉引理AII還可以偽造另一個(gè)有效簽名σ*1=(V*′,h*′)。

因此，V*-V*′=(h′*-h*)(SA+PA)，則有(h*′-h*)-1(V*-V*′)=SA+PA=sbP+abP+bP，即abP=(h*′-h*)-1(V*-V*′)-sbP-bP。

因此挑戰(zhàn)者C成功解決了CDH問(wèn)題。計(jì)算C解決CDH問(wèn)題的時(shí)間概率與定理2中的類(lèi)似。

5效率分析

將已有的基于證書(shū)數(shù)字簽名方案與改進(jìn)方案相比較，分析各方案的效率，發(fā)現(xiàn)改進(jìn)方案僅比原始方案多了一次乘法運(yùn)算。設(shè)P表示一次雙線(xiàn)性對(duì)運(yùn)算，E表示一次有限域上的模冪運(yùn)算，M表示群G1上的標(biāo)量乘運(yùn)算，S表示群G上的形如aP+bQ的同時(shí)乘運(yùn)算。比較結(jié)果如表1。

表1　4個(gè)基于證書(shū)方案效率比較

6結(jié)束語(yǔ)

在已有基于證書(shū)簽名方案的基礎(chǔ)上提出了一個(gè)改進(jìn)的方案，并在隨機(jī)語(yǔ)言機(jī)模型下，證明了方案在適應(yīng)性選擇消息下可抗公鑰替換攻擊和CA攻擊。將改進(jìn)方案與現(xiàn)有基于證書(shū)數(shù)字簽名方案比較、分析，發(fā)現(xiàn)改進(jìn)方案在效率和安全性方面都是可行的。

參考文獻(xiàn):

[1] C. Gentry. Certificate-based encryption and the certificate revocation problem[C]. LNCS 2656: EUROCRPTY [l9], Berlin: Springer-Verlag, 2003: 272-293.

[2] B. Kang, J. Park, S. Hahn. A certificate-based signature scheme[C]. CT-RSA LNCS 964, Berlin: Springer-Verlag, 2004: 99-111.

[3] J.K.Liu, M.H.Au, W. Susilo. 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，ACM Press, New York: 2007: 302-311.

[4] Wu Wei, Mu Yi. Certificate-based signatures: new definitions and a generic construction from certificateless signatures[C]. LNCS 5379: WISA, Berlin: Springer-Verlag, 2009: 99-114.

[5] 王雯娟, 黃振杰, 郝艷華. 一個(gè)高效的基于證書(shū)數(shù)字簽名方案[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(6): 89-92.

[6] 陳江山, 黃振杰. 一個(gè)高效的基于證書(shū)簽名方案[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(30): 98-102.

[7] Li Jiguo, Huang Xinyi, Mu Yi, et al.. Certificate-based signature: security model and efficient construction[C].Proc. of EuroPKI’07. Palma de Mallorca, Spain: Springer-Verlag, 2007:444-453.

[9] 李志敏, 徐馨, 李存華. 高效的基于證書(shū)數(shù)字簽名設(shè)計(jì)方案[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(4): 1430-1433, 1444.

[10] 楊波, 肖自碧. 基于證書(shū)的簽名方案[J]. 北京郵電大學(xué)學(xué)報(bào), 2012, 35(5): 73-76.

[11] 吳晨煌, 郭瑞景, 陳智雄. 高效的基于證書(shū)短簽名方案[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2013, 22(2): 129-132.

Analysis and Improvement of an Efficient Certificate-Based Signature Scheme

ZHOU Hua-jing, LIU Er-gen, ZUO Li-ming

(1. College of Science of East China Jiaotong University, Nanchang, Jiangxi 330013, China;2. Institute of Engineering and Cryptography of East China Jiaotong University, Nanchang, Jiangxi 330013, China)

Abstract:From the study of an efficient certificate-based signature we find that the first adversaries can attack the scheme easily. As a consequence, we propose an improved scheme on the basis of original scheme, and prove that the scheme is existentially unforgeable against adaptive chosen message and identity attacks under random oracle model based on the inverse Diffie-Hellman Problem and Compute Diffie-Hellman assumption. In this paper we also analyze the efficiency of the scheme, compare with the existing schemes, find that this scheme is effective.

Key words:public key cryptography, digital signature, base on certificate, random oracle mod

文章編號(hào)：1007-4260(2016)01-0047-05

中圖分類(lèi)號(hào)：TP309

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.13757/j.cnki.cn34-1150/n.2016.01.014

作者簡(jiǎn)介：周華靜，女，安徽天長(zhǎng)人，華東交通大學(xué)理學(xué)院碩士研究生，研究方向?yàn)樾畔踩?。E-mail: 642578515@qq.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金(11361024,11261019),江西省高?？萍悸涞赜?jì)劃(KJLD12067),江西省教育廳科研項(xiàng)目(GJJ13339)和華東交通大學(xué)校立科研基金(11JC04)。

*收稿日期：2015-06-04

網(wǎng)絡(luò)出版時(shí)間：2016-03-15 17:05網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.014.html