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

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

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

0 引言

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

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

1 預備知識

1.1 安全性假設

定義3 雙線性映射。設G1是循環加法群，G2是循環乘法群，它們的階同為安全大素數q，群G1和G2中的離散對數問題是困難問題，則稱映射e:G1×G1→G2為滿足以下性質的雙線性映射。

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

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

1.2 代理簽名定義

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

2)密鑰對生成：系統密鑰生成中心KGC，輸入用戶身份ID和系統公開參數params，輸出用戶私鑰xID和公鑰yID。

3)代理授權：輸入系統公開參數params、原始簽名人A密鑰對和授權文件w，輸出代理授權證書W。其中：w包含了原始簽名人和代理簽名人的身份信息、授權關系的描述、允許簽署的消息范圍及期限等。

4)代理授權驗證：輸入系統公開參數params、原始簽名人A身份IDA和代理授權證書W，驗證者驗證W是否為一個有效的代理授權證書。

5)代理密鑰生成：代理簽名人B輸入系統公開參數params、代理授權證書W，輸出xAB作為代理簽名私鑰。

6)代理簽名：輸入系統公開參數params、代理授權文件W、代理簽名私鑰xAB和待簽名消息m，輸出簽名信息S。

7)代理簽名驗證：輸入系統公開參數params、原始簽名人A身份IDA、代理簽名人B身份IDB、授權證書W和簽名信息S，返回“1”說明驗證通過，返回“0”說明驗證失敗。

1.3 敵手模型

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

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

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

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

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

1.4 安全模型

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

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

2 簽名方案構造

簽名方案構造的步驟如下：

4)代理授權驗證：代理簽名人B接收到授權許可后，輸入系統公開參數params，驗證e(dAB,g)=e(h1,yA+R)是否成立，如果等式成立則接受授權許可。

5)代理密鑰生成。代理簽名人B，根據系統公開參數params，計算xAB=dAB+xBh1，輸出xAB作為代理簽名密鑰。

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

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

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

7)簽名驗證。對給定的消息/簽名對(m,S)，通過以下步驟進行驗證：

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

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

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

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

3 方案分析

3.1 正確性分析

授權許可正確性分析如下：

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

e(h1,yA+R)

簽名驗證等式正確性分析如下：

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 針對第二類攻擊者，在隨機預言機模型以及k-CAA困難問題假設下，本文方案是存在性不可偽造的。

為敘述簡便，假設A2不會對預言機作相同的詢問，而且在進行簽名詢問和偽造簽名時已經作了H1和H2詢問，所有的記錄列表初始化為空。C允許A2作以下適應性詢問：

3)H2詢問：C維護一個記錄結構為數組(IDA,IDB,m,R,h2)的列表LH2。當A2提交一個關于(IDA,IDB,m,R)的H2詢問時，C檢查列表LH2是否已經存在詢問對應值(IDA,IDB,m,R,h2)，存在則返回相應的h2給A2；否則均勻地隨機選擇h2∈Ω返回給A2同時將(IDA,IDB,m,R,h2)記錄到列表LH2。顯然這里h2∈E的概率為k/qH2，h2∈F的概率為(qH2-k)/qH2。

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

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

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

值得注意的是，如果h2∈E，構造的代理簽名能夠通過驗證等式，其合理性由以下等式保證：

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*)作為對困難問題的解答，從而C解決了k-CAA問題的實例。

以下分析C成功解決困難問題需要的時間和優勢：

當A2沒有作H2詢問而偽造一個有效簽名其發生的概率為1/2λ，所以C在游戲中的優勢估計滿足：

運行時間滿足：

t′

因此C以不可忽略的優勢ε′在多項式時間t′內成功地解決了一個k-CAA問題的實例，這與k-CAA問題困難性矛盾。所以本文方案針對于第二類敵手是存在性不可偽造的。

定理2 針對第三類攻擊者，在隨機預言機模型以及CDH困難問題假設下，本文方案是存在性不可偽造的。

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

為敘述簡便，假設A3不會對預言機作相同的詢問，且在進行簽名詢問和偽造簽名時已經作了H1和H2詢問，所有的記錄列表初始化為空。C允許A3作以下適應性詢問：

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

構造的代理簽名能夠通過驗證等式，其合理性由以下等式保證：

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

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

所以C可以成功計算：

以下分析C成功解決困難問題需要的時間和優勢：

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

當A3沒有詢問H1而偽造一個有效簽名時，這種模擬是存在漏洞的,其發生的概率為1/2λ，所以C在游戲中的優勢滿足：

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

運行時間滿足：

t′

因此C以不可忽略的優勢ε′在多項式時間t′內成功地解決了一個CDH問題的實例，這與CDH問題困難性矛盾。所以本文方案針對于第三類敵手是存在性不可偽造的。

4 方案實現與效率分析

4.1 方案實現

本文方案是以PBC(Pairing-Based Cryptography library)[14]為基礎，在操作系統為 Windows 7旗艦版 64位，處理器為 Intel i3-4170 3.70 GHz,主板為華碩B85M-F PLUS,內存為威剛 DDR3 1 600 MHz 8 GB的實驗基準測試環境中，通過Visual Studio 2012開發平臺，進行了方案實現。

其具體實現的核心代碼如下：

pairing_tpairing;

//初始化雙線性對

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

printf("pairing init failed");

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

//1)系統參數建立

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

//2)密鑰對生成

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);

//計算yA=xA*g

element_mul(yB,xB,g);

//計算yB=xB*g

//3)代理授權

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

element_mul(R,r,g);

//計算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)代理授權驗證

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);

//授權驗證左邊：e(dAB,g)

element_pairing(Lp,dAB,g);

// 授權驗證右邊：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);

//計算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)代理簽名驗證

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);

//計算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("驗證成功! ");

如圖3所示，為根據簽名生成等式S=xAB/(h2+xB)，對長度為71 B的消息m進行簽名的結果,整個簽名生成耗時為0.014 s。

圖3 簽名結果Fig. 3 Signature result

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

圖4 驗證結果Fig. 4 Verification result

4.2 計算效率分析

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

4.3 運行效率分析

在相同的實驗測試基準環境下，對本文方案和現有幾個代理簽名方案進行了實現，并將多次運行后的運行效率進行比較，結果如表2所示。

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

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

5 結語

針對無線設備應用中存在的計算能力和傳輸能力較弱的問題，本文提出了一個代理短簽名方案。然后，在CDH困難問題假設和隨機預言機模型下證明了本文方案的安全性。最后，對本文方案進行了實現和實驗比較，實驗結果和分析表明本文方案計算量小、效率較高，能較好地適用于計算能力較弱和傳輸能力受限的應用場景。在下一步的研究中，將在利用短簽名構造安全傳輸協議的思想[20]上，基于本文代理短簽名方案設計出一套適用于移動端應用軟件在線版權保護的安全認證協議。