高效的可證安全短代理簽名方案

左黎明，陳祚松，夏萍萍，易傳佳

(1.華東交通大學(xué) 理學(xué)院，南昌 330013； 2.華東交通大學(xué) 系統(tǒng)工程與密碼學(xué)研究所，南昌 330013)(*通信作者電子郵箱limingzuo@126.com)

0 引言

1996年，Mambo等[1-2]首次提出了代理簽名的概念。在一個(gè)代理簽名方案中，包含了原始簽名人、代理簽名人和驗(yàn)證人，原始簽名人授權(quán)給代理簽名人后，代理簽名人可以代表原始簽名人生成一個(gè)有效的代理簽名，驗(yàn)證人驗(yàn)證時(shí)要同時(shí)驗(yàn)證代理簽名的有效性和原始簽名人的授權(quán)。這種方案很好地解決了特殊數(shù)字簽名權(quán)力的代理問(wèn)題，在分布式系統(tǒng)、電子商務(wù)、電子政務(wù)等領(lǐng)域有著廣泛的應(yīng)用。2012年，楊力等[3]針對(duì)可信計(jì)算組織 (Trusted Computing Group, TCG)的直接匿名證明方案不能實(shí)現(xiàn)跨域可信認(rèn)證的不足，提出了一個(gè)新的代理簽名方案，實(shí)現(xiàn)對(duì)移動(dòng)終端在多可信域之間漫游時(shí)的可信計(jì)算平臺(tái)認(rèn)證，并證明了方案能夠抵抗平臺(tái)偽裝攻擊和重放攻擊。2013年，Wen等[4]指出隨著計(jì)算機(jī)能力的增強(qiáng)，現(xiàn)有的電子支付系統(tǒng)將逐漸變得不安全，為此提出了一個(gè)基于量子代理盲簽名的銀行支付系統(tǒng)，與傳統(tǒng)的電子支付系統(tǒng)相比，不僅能夠保護(hù)用戶的匿名性，還可以實(shí)現(xiàn)電子支付的高安全性。2014年，Gao等[5]針對(duì)無(wú)線mesh網(wǎng)絡(luò)中存在的隱私泄漏隱患，提出了一個(gè)基于代理群簽名的匿名訪問(wèn)認(rèn)證方案，能在認(rèn)證過(guò)程中很好地保護(hù)用戶的隱私。2015年，Wang等[6]針對(duì)數(shù)據(jù)云存儲(chǔ)和共享服務(wù)中用戶組成員撤銷后，數(shù)據(jù)塊簽名更新過(guò)程復(fù)雜的問(wèn)題，提出了一個(gè)基于代理重簽名方案的公共審計(jì)機(jī)制，顯著地提高用戶撤銷的效率。2016年,張新鵬等[7]提出了一個(gè)較Wang等[6]方案通信開(kāi)銷和計(jì)算代價(jià)更低的單向代理重簽名方案，但當(dāng)用戶處于無(wú)線網(wǎng)絡(luò)環(huán)境下，用戶撤銷時(shí)的數(shù)據(jù)傳輸負(fù)荷仍然是很大的。2017年，Chiou等[8]提出了一個(gè)基于代理簽名方案的電子投票系統(tǒng)，并能夠在智能手機(jī)端通過(guò)該方案安全和方便地進(jìn)行投票。同年，Hong等[9]提出了一個(gè)基于屬性的代理簽名方案，能夠保證存儲(chǔ)在云中的數(shù)據(jù)的安全和實(shí)現(xiàn)細(xì)粒度的認(rèn)證。2018年，Xu等[10]提出了一個(gè)具有可重授權(quán)和重撤銷特性的代理簽名方案，并應(yīng)用到一個(gè)在線的車輛訂購(gòu)系統(tǒng)中，在保證系統(tǒng)安全的同時(shí)提高了系統(tǒng)的隨需應(yīng)變能力。

隨著無(wú)線網(wǎng)絡(luò)的普及，在無(wú)線網(wǎng)絡(luò)環(huán)境下，使用代理簽名實(shí)現(xiàn)各類數(shù)據(jù)完整性保護(hù)和身份認(rèn)證變得越來(lái)越普遍[11-13]，這也給如何降低網(wǎng)絡(luò)數(shù)據(jù)流量和避免網(wǎng)絡(luò)阻塞帶來(lái)了巨大的挑戰(zhàn)。而短簽名方案由于其簽名長(zhǎng)度短的優(yōu)勢(shì)，能夠很好地解決這些問(wèn)題。對(duì)此本文構(gòu)造了一個(gè)高效的短代理簽名方案，并在計(jì)算Diffie-Hellman(Computational Diffie-Hellman, CDH)困難問(wèn)題假設(shè)、k-碰撞攻擊算法(Collusion Attack Algorithm with k traitors, k-CAA)困難問(wèn)題假設(shè)和隨機(jī)預(yù)言機(jī)模型下證明了方案的安全性。

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

1.1 安全性假設(shè)

定義3 雙線性映射。設(shè)G1是循環(huán)加法群，G2是循環(huán)乘法群，它們的階同為安全大素?cái)?shù)q，群G1和G2中的離散對(duì)數(shù)問(wèn)題是困難問(wèn)題，則稱映射e:G1×G1→G2為滿足以下性質(zhì)的雙線性映射。

2)非退化性：e(P,P)≠1；

3)易計(jì)算性：?M,N∈G1,存在有效算法計(jì)算e(M,N)。

1.2 代理簽名定義

1)系統(tǒng)參數(shù)建立：系統(tǒng)密鑰生成中心(Key Generation Center,KGC)，輸入安全參數(shù)k，輸出系統(tǒng)公開(kāi)參數(shù)params。

2)密鑰對(duì)生成：系統(tǒng)密鑰生成中心KGC，輸入用戶身份ID和系統(tǒng)公開(kāi)參數(shù)params，輸出用戶私鑰xID和公鑰yID。

3)代理授權(quán)：輸入系統(tǒng)公開(kāi)參數(shù)params、原始簽名人A密鑰對(duì)和授權(quán)文件w，輸出代理授權(quán)證書(shū)W。其中：w包含了原始簽名人和代理簽名人的身份信息、授權(quán)關(guān)系的描述、允許簽署的消息范圍及期限等。

4)代理授權(quán)驗(yàn)證：輸入系統(tǒng)公開(kāi)參數(shù)params、原始簽名人A身份IDA和代理授權(quán)證書(shū)W，驗(yàn)證者驗(yàn)證W是否為一個(gè)有效的代理授權(quán)證書(shū)。

5)代理密鑰生成：代理簽名人B輸入系統(tǒng)公開(kāi)參數(shù)params、代理授權(quán)證書(shū)W，輸出xAB作為代理簽名私鑰。

6)代理簽名：輸入系統(tǒng)公開(kāi)參數(shù)params、代理授權(quán)文件W、代理簽名私鑰xAB和待簽名消息m，輸出簽名信息S。

7)代理簽名驗(yàn)證：輸入系統(tǒng)公開(kāi)參數(shù)params、原始簽名人A身份IDA、代理簽名人B身份IDB、授權(quán)證書(shū)W和簽名信息S，返回“1”說(shuō)明驗(yàn)證通過(guò)，返回“0”說(shuō)明驗(yàn)證失敗。

1.3 敵手模型

代理簽名方案主要存在以下三類攻擊者：

1)類型1：攻擊者A1同時(shí)知道原始簽名人的公鑰和代理簽名人的公鑰。

2)類型2：攻擊者A2不僅知道原始簽名人的公鑰和代理簽名人的公鑰，還知道原始簽名人的私鑰，但不知道代理簽名人的私鑰。

3)類型3：攻擊者A3不僅知道原始簽名人的公鑰和代理簽名人的公鑰，還知道代理簽名人的私鑰，但不知道原始簽名人私鑰。

從上述三類攻擊者所擁有的能力描述可知，當(dāng)代理簽名方案對(duì)于攻擊者A2和攻擊者A3是存在不可偽造的，那么，對(duì)于攻擊者A1也是存在不可偽造的。所以本文在后續(xù)的安全模型和安全證明中，僅考慮類型2的攻擊者A2和類型3的攻擊者A3。

1.4 安全模型

定義3 安全模型。如果不存在一個(gè)敵手可以在概率多項(xiàng)式時(shí)間內(nèi)以一個(gè)不可忽略的優(yōu)勢(shì)在圖1和圖2的游戲中獲勝(其中敵手的優(yōu)勢(shì)指其獲勝的概率)，則證明這個(gè)代理簽名方案是存在性不可偽造的。

圖1 攻擊者A2與挑戰(zhàn)者C之間的博弈Fig. 1 Game between attacker A2 and challenger C

2 簽名方案構(gòu)造

簽名方案構(gòu)造的步驟如下：

4)代理授權(quán)驗(yàn)證：代理簽名人B接收到授權(quán)許可后，輸入系統(tǒng)公開(kāi)參數(shù)params，驗(yàn)證e(dAB,g)=e(h1,yA+R)是否成立，如果等式成立則接受授權(quán)許可。

5)代理密鑰生成。代理簽名人B，根據(jù)系統(tǒng)公開(kāi)參數(shù)params，計(jì)算xAB=dAB+xBh1，輸出xAB作為代理簽名密鑰。

6)代理簽名： 代理簽名人B對(duì)給定消息m∈{0,1}*，進(jìn)行如下操作：

①計(jì)算h2=H2(IDA,IDB,m,R)；

②計(jì)算S=xAB/(h2+xB)，則S為代理簽名人B對(duì)消息m的簽名。

7)簽名驗(yàn)證。對(duì)給定的消息/簽名對(duì)(m,S)，通過(guò)以下步驟進(jìn)行驗(yàn)證：

①計(jì)算h1=H1(IDA,IDB,wAB,R)；

②計(jì)算h2=H2(IDA,IDB,m,R)；

③驗(yàn)證等式e(S,h2g+yB)=e(h1,yA+yB+R)是否成立，若等式成立，則簽名驗(yàn)證通過(guò)；若等式不成立，則簽名驗(yàn)證失敗。

圖2 攻擊者A3與挑戰(zhàn)者C之間的博弈Fig. 2 Game between attacker A3 and challenger C

3 方案分析

3.1 正確性分析

授權(quán)許可正確性分析如下：

e(dAB,g)=e((xA+r)h1,g)=e(h1,(xA+r)g)=

e(h1,yA+R)

簽名驗(yàn)證等式正確性分析如下：

e(S,h2g+yB)=e(S,(h2+xB)g)=

e(xAB/(h2+xB),(h2+xB)g)=

e((xA+xB+r)h1,g)=e(h1,yA+yB+R)

3.2 安全性證明

定理1 針對(duì)第二類攻擊者，在隨機(jī)預(yù)言機(jī)模型以及k-CAA困難問(wèn)題假設(shè)下，本文方案是存在性不可偽造的。

為敘述簡(jiǎn)便，假設(shè)A2不會(huì)對(duì)預(yù)言機(jī)作相同的詢問(wèn)，而且在進(jìn)行簽名詢問(wèn)和偽造簽名時(shí)已經(jīng)作了H1和H2詢問(wèn)，所有的記錄列表初始化為空。C允許A2作以下適應(yīng)性詢問(wèn)：

3)H2詢問(wèn)：C維護(hù)一個(gè)記錄結(jié)構(gòu)為數(shù)組(IDA,IDB,m,R,h2)的列表LH2。當(dāng)A2提交一個(gè)關(guān)于(IDA,IDB,m,R)的H2詢問(wèn)時(shí)，C檢查列表LH2是否已經(jīng)存在詢問(wèn)對(duì)應(yīng)值(IDA,IDB,m,R,h2)，存在則返回相應(yīng)的h2給A2；否則均勻地隨機(jī)選擇h2∈Ω返回給A2同時(shí)將(IDA,IDB,m,R,h2)記錄到列表LH2。顯然這里h2∈E的概率為k/qH2，h2∈F的概率為(qH2-k)/qH2。

4)代理簽名詢問(wèn)：當(dāng)A2提交關(guān)于(m,IDA,IDB,R)的代理簽名詢問(wèn)時(shí)，則C從列表LH1中獲取記錄(IDA,IDB,wAB,R,v,h1)，C從列表LH2中獲取相應(yīng)記錄(IDA,IDB,m,R,h2)，C從列表LR中獲取記錄(IDA,IDB,wAB,r,R)，然后：

①如果h2∈E，即存在ej=h2∈E,計(jì)算S=v(xA+r)g/(b+ej),將S返回給A2；

②如果h2∈F，返回“⊥”，記此事件為Event1，“⊥”表示空。

值得注意的是，如果h2∈E，構(gòu)造的代理簽名能夠通過(guò)驗(yàn)證等式，其合理性由以下等式保證：

e(S,h2g+yB)=e(v(xA+r)g/(b+ej),ejg+yB)=

e(vg,yA+yB+R);R=rg-yB

即輸出S*/((xA+r*)v*)作為對(duì)困難問(wèn)題的解答，從而C解決了k-CAA問(wèn)題的實(shí)例。

以下分析C成功解決困難問(wèn)題需要的時(shí)間和優(yōu)勢(shì)：

當(dāng)A2沒(méi)有作H2詢問(wèn)而偽造一個(gè)有效簽名其發(fā)生的概率為1/2λ，所以C在游戲中的優(yōu)勢(shì)估計(jì)滿足：

運(yùn)行時(shí)間滿足：

t′

因此C以不可忽略的優(yōu)勢(shì)ε′在多項(xiàng)式時(shí)間t′內(nèi)成功地解決了一個(gè)k-CAA問(wèn)題的實(shí)例，這與k-CAA問(wèn)題困難性矛盾。所以本文方案針對(duì)于第二類敵手是存在性不可偽造的。

定理2 針對(duì)第三類攻擊者，在隨機(jī)預(yù)言機(jī)模型以及CDH困難問(wèn)題假設(shè)下，本文方案是存在性不可偽造的。

引理2 假設(shè)敵手A3經(jīng)過(guò)有限次詢問(wèn)后在多項(xiàng)式時(shí)間t內(nèi)以不可忽略的優(yōu)勢(shì)ε攻破了本文方案，記qHi和tHi分別為敵手A3詢問(wèn)Hi(i=1,2)預(yù)言機(jī)的次數(shù)和一次詢問(wèn)所需時(shí)間，記qR和tR分別為授權(quán)識(shí)別碼詢問(wèn)次數(shù)和一次詢問(wèn)所需時(shí)間,記qS和tS分別為代理簽名詢問(wèn)次數(shù)和一次詢問(wèn)所需時(shí)間，δ∈(0,1/2)，則存在算法C，在概率多項(xiàng)式時(shí)間t′

為敘述簡(jiǎn)便，假設(shè)A3不會(huì)對(duì)預(yù)言機(jī)作相同的詢問(wèn)，且在進(jìn)行簽名詢問(wèn)和偽造簽名時(shí)已經(jīng)作了H1和H2詢問(wèn)，所有的記錄列表初始化為空。C允許A3作以下適應(yīng)性詢問(wèn)：

4)代理簽名詢問(wèn)。當(dāng)A3提交關(guān)于(m,IDA,IDB,R,xAB)的代理簽名詢問(wèn)時(shí)，則C從列表LH2中獲取相應(yīng)記錄h2，C從列表LR中獲得(IDA,IDB,wAB,c,r,R)。若c=0則計(jì)算S=(xB+r)vbg/(xB+h2)，將S返回給A3；否則，返回“⊥”，記此事件為Event1。

構(gòu)造的代理簽名能夠通過(guò)驗(yàn)證等式，其合理性由以下等式保證：

e(S,h2g+yB)=e((xBvbg+rvbg)/(xB+h2),h2g+yB)=

e(vg,yA+yB+R);R=rg-yA

所以C可以成功計(jì)算：

以下分析C成功解決困難問(wèn)題需要的時(shí)間和優(yōu)勢(shì)：

2)只有當(dāng)模擬階段Event1和Event2一直都不發(fā)生時(shí)，則C能解決CDH問(wèn)題的一個(gè)實(shí)例。Event1一直不發(fā)生的概率為(1-δ)qs，Event2不發(fā)生的概率為δ，則可得Event1、Event2都不發(fā)生的概率為：

當(dāng)A3沒(méi)有詢問(wèn)H1而偽造一個(gè)有效簽名時(shí)，這種模擬是存在漏洞的,其發(fā)生的概率為1/2λ，所以C在游戲中的優(yōu)勢(shì)滿足：

ε′≥δ(1-δ)qs(ε-1/2λ)

運(yùn)行時(shí)間滿足：

t′

因此C以不可忽略的優(yōu)勢(shì)ε′在多項(xiàng)式時(shí)間t′內(nèi)成功地解決了一個(gè)CDH問(wèn)題的實(shí)例，這與CDH問(wèn)題困難性矛盾。所以本文方案針對(duì)于第三類敵手是存在性不可偽造的。

4 方案實(shí)現(xiàn)與效率分析

4.1 方案實(shí)現(xiàn)

本文方案是以PBC(Pairing-Based Cryptography library)[14]為基礎(chǔ)，在操作系統(tǒng)為 Windows 7旗艦版 64位，處理器為 Intel i3-4170 3.70 GHz,主板為華碩B85M-F PLUS,內(nèi)存為威剛 DDR3 1 600 MHz 8 GB的實(shí)驗(yàn)基準(zhǔn)測(cè)試環(huán)境中，通過(guò)Visual Studio 2012開(kāi)發(fā)平臺(tái)，進(jìn)行了方案實(shí)現(xiàn)。

其具體實(shí)現(xiàn)的核心代碼如下：

pairing_tpairing;

//初始化雙線性對(duì)

if (pairing_init_set_buf(pairing,eparam, strlen(eparam)))

printf("pairing init failed");

element_txA,yA,xB,yB,g,r,R,h1,h2;

//1)系統(tǒng)參數(shù)建立

element_init_G1(g,pairing);element_random(g);

//2)密鑰對(duì)生成

element_init_Zr(xA,pairing);

element_init_G1(yA,pairing);

element_init_Zr(xB,pairing);

element_init_G1(yB,pairing);

element_mul(yA,xA,g);

//計(jì)算yA=xA*g

element_mul(yB,xB,g);

//計(jì)算yB=xB*g

//3)代理授權(quán)

element_init_G1(R,pairing);element_init_Zr(r,pairing);

element_mul(R,r,g);

//計(jì)算R=r*g

element_init_G1(h1,pairing);

element_from_hash(h1,IDA,strlen(IDA));

element_ttemp1,dAB;

element_init_Zr(temp1,pairing);

element_add(temp1,xA,r);

element_init_G1(dAB,pairing);

element_mul(dAB,temp1,h1);

//dAB=(xA+r)h1

//4)代理授權(quán)驗(yàn)證

element_tLp,Rp,yA_R;

element_init_GT(Lp,pairing);

element_init_GT(Rp,pairing);

element_init_G1(yA_R,pairing);

element_mul(yA_R,temp1,g);

//授權(quán)驗(yàn)證左邊：e(dAB,g)

element_pairing(Lp,dAB,g);

// 授權(quán)驗(yàn)證右邊：e(h1,yA+R)

element_pairing(Rp,h1,yA_R);

if(element_cmp(Lp,Rp)) return 0;

//5)代理密鑰合成

element_txAB,temp3;

element_init_Zr(temp3,pairing);

element_add(temp3,xB,temp1);

element_init_G1(xAB,pairing);

element_mul(xAB,temp3,h1);

//計(jì)算xAB

//6)代理簽名生成

charm[100]="sign_message_czs";

strcat(m,IDA);strcat(m,IDB);

strcat(m,WAB);element_init_Zr(h2,pairing);

element_from_hash(h2,m,strlen(m));

element_tS,temp4,temp5;

element_init_G1(S,pairing);

element_init_Zr(temp4,pairing);

element_init_Zr(temp5,pairing);

element_add(temp4,xB,h2);

element_invert(temp5,temp4);

element_mul(S,temp5,xAB);

//(h2+xB)^(-1)*xAB

//7)代理簽名驗(yàn)證

element_tleft,right,temp6,temp7;

element_init_GT(left,pairing);

element_init_GT(right,pairing);

element_init_G1(temp6,pairing);

element_mul(temp6,temp4,g);

//h2g+yB

element_pairing(left,S,temp6);

//e(S,h2g+yB)

element_init_G1(temp7,pairing);

element_mul(temp7,temp3,g);

//計(jì)算yA+yB+R

element_pairing(right,h1,temp7);

//e(h1,yA+yB+R)

element_printf("e(S,h2g+yB)= %B ",left);

element_printf("e(h1,yA+yB+R)= %B ",right);

if (!element_cmp(left,right))

printf("驗(yàn)證成功! ");

如圖3所示，為根據(jù)簽名生成等式S=xAB/(h2+xB)，對(duì)長(zhǎng)度為71 B的消息m進(jìn)行簽名的結(jié)果,整個(gè)簽名生成耗時(shí)為0.014 s。

圖3 簽名結(jié)果Fig. 3 Signature result

圖4為根據(jù)相應(yīng)參數(shù)和代理簽名驗(yàn)證等式e(S,h2g+yB)=e(h1,yA+yB+R)對(duì)消息m的簽名進(jìn)行驗(yàn)證的結(jié)果。由圖4中可知，代理簽名驗(yàn)證過(guò)程只需要0.028 s，并且方案的整體耗時(shí)為0.127 s，能夠較高效地實(shí)現(xiàn)消息的代理簽名和驗(yàn)證簽名。

圖4 驗(yàn)證結(jié)果Fig. 4 Verification result

4.2 計(jì)算效率分析

表1 不同方案的計(jì)算效率和簽名長(zhǎng)度比較Tab. 1 Comparison of computation efficiency and signature length of different schemes

4.3 運(yùn)行效率分析

在相同的實(shí)驗(yàn)測(cè)試基準(zhǔn)環(huán)境下，對(duì)本文方案和現(xiàn)有幾個(gè)代理簽名方案進(jìn)行了實(shí)現(xiàn)，并將多次運(yùn)行后的運(yùn)行效率進(jìn)行比較，結(jié)果如表2所示。

表2 不同方案運(yùn)行50次平均耗時(shí)比較 sTab. 2 Average time consumption comparison of different schemes with running 50 times s

從表2可知，本文方案簽名平均耗時(shí)為0.014 s，簽名驗(yàn)證平均耗時(shí)為0.029 s，方案平均總耗時(shí)為0.129 s。本文方案與文獻(xiàn)[15]方案相比方案平均總耗時(shí)減少了約28.7%，與文獻(xiàn)[16]方案相比方案平均總耗時(shí)減少了約33.8%，與文獻(xiàn)[17]方案相比方案平均總耗時(shí)減少了約9.8%，與文獻(xiàn)[18]方案相比方案平均總耗時(shí)減少了約27.9%，與文獻(xiàn)[19]方案相比方案平均總耗時(shí)減少了約17.8%。從以上分析可知，本文方案不僅簽名長(zhǎng)度短、理論計(jì)算效率高，而且在實(shí)際運(yùn)行效率上也優(yōu)于文獻(xiàn)[15-19]方案。

5 結(jié)語(yǔ)

針對(duì)無(wú)線設(shè)備應(yīng)用中存在的計(jì)算能力和傳輸能力較弱的問(wèn)題，本文提出了一個(gè)代理短簽名方案。然后，在CDH困難問(wèn)題假設(shè)和隨機(jī)預(yù)言機(jī)模型下證明了本文方案的安全性。最后，對(duì)本文方案進(jìn)行了實(shí)現(xiàn)和實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果和分析表明本文方案計(jì)算量小、效率較高，能較好地適用于計(jì)算能力較弱和傳輸能力受限的應(yīng)用場(chǎng)景。在下一步的研究中，將在利用短簽名構(gòu)造安全傳輸協(xié)議的思想[20]上，基于本文代理短簽名方案設(shè)計(jì)出一套適用于移動(dòng)端應(yīng)用軟件在線版權(quán)保護(hù)的安全認(rèn)證協(xié)議。