彭　程，楊鄧奇

(1.云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，昆明　650091；2.大理學(xué)院 數(shù)學(xué)與計算機學(xué)院，云南　大理　671003)

?

基于ElGamal體制的無需配對無證書簽名方案

彭程1，楊鄧奇2

(1.云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，昆明650091；2.大理學(xué)院 數(shù)學(xué)與計算機學(xué)院，云南大理671003)

ElGamal簽名體制；無證書簽名；無雙線性對

簽名是網(wǎng)絡(luò)系統(tǒng)安全的必要元素，目前的簽名技術(shù)如RSA、ECDSA等在實現(xiàn)公鑰管理時主要是基于PKI技術(shù)；然而，基于PKI技術(shù)的公鑰管理需要復(fù)雜的證書管理，系統(tǒng)實現(xiàn)比較復(fù)雜。2001年，文獻[1]提出基于身份的密碼系統(tǒng)(IBC)，旨在消除傳統(tǒng)公鑰證書密碼體制中煩瑣的公鑰管理過程。但是基于身份的密碼系統(tǒng)存在密鑰托管問題。文獻[2]提出了無證書公鑰密碼系統(tǒng)(CL-PKC)以解決基于身份密碼系統(tǒng)中的密鑰托管問題，同時去除傳統(tǒng)公鑰證書體制中煩瑣的證書管理過程，并提出了無證書密碼系統(tǒng)基于雙線對。雙線性對的運算是比較耗時的運算，文獻[3]指出，進行一次雙線性對運算、指數(shù)運算和哈希運算所需的計算量分別至少是橢圓曲線標量乘法的21倍、3倍和1倍。文獻[4]首次提出無需配對的無證書密碼系統(tǒng)，該系統(tǒng)存在大量的指數(shù)運算，并給出了一個無證書加密方案，沒有給出相應(yīng)的簽名方案。2006-2011年期間，提出了諸多無證書簽名方案及其變體[5-10]，但這些方案都需要進行多次雙線性對的運算。2012年，文獻[11]提出無雙線性對的無證書簽名方案，該方案在簽名和驗證階段都不需要雙線性對運算，其主要運算為橢圓曲線上的標量乘法(后文簡稱標量乘法)，具有較高的計算效率。但該方案用戶密鑰生成階段存在一個問題，即在用戶獲得由KGC為其提供的部分私鑰后，可以惡意地選擇多個秘密值進行計算，使一個部分私鑰對應(yīng)多個秘密值，即一個用戶、一個部分私鑰對應(yīng)多個公私鑰對，這對系統(tǒng)安全造成了嚴重威脅。此外，該方案在驗證的效率并不是只需2次標量懲罰和1次哈希運算，而是需要4次標量乘法和1次哈希運算。

1　預(yù)備知識

1.1困難問題及假設(shè)

1.2通用的無證書簽名方案

一般來講，無論是基于雙線性對還是無需配對的無證書簽名方案，通常包括7個算法[2]。

1)系統(tǒng)初始化算法:由KGC執(zhí)行，輸入安全參數(shù)k，輸出系統(tǒng)主密鑰s和參數(shù)Params，其中主密鑰s由KGC保密，而參數(shù)Params公開。

2)用戶秘密值生成算法:在用戶端執(zhí)行，輸入系統(tǒng)參數(shù)Params和用戶ID，輸出用戶秘密值xID和對應(yīng)的公開值XID。

3)用戶部分密鑰生成算法:在KGC上執(zhí)行，輸入系統(tǒng)參數(shù)Params、系統(tǒng)主密鑰s、用戶身份(ID)和公開值XID，輸出用戶部分私鑰DID和對應(yīng)的部分公鑰PID。

4)用戶私鑰生成算法:在用戶端運行，輸入系統(tǒng)參數(shù)Params、用戶部分密鑰DID和用戶秘密值xID，輸出用戶私鑰SKID。

5)用戶公鑰生成算法:在用戶端運行，輸入系統(tǒng)參數(shù)Params、公開值XID和用戶部分公鑰PID，輸出用戶公鑰PKID。

6)簽名算法:由簽名用戶運行，輸入系統(tǒng)參數(shù)Params、用戶私鑰SKID、用戶ID和消息M，輸出消息M的簽名。

7)驗證算法:由驗證用戶運行，輸入系統(tǒng)參數(shù)Params、用戶公鑰PKID、用戶ID和簽名。若驗證通過，輸出1；否則，輸出0。

1.3安全模型

無證書密碼系統(tǒng)考慮兩類攻擊者[2]，令A(yù)I和AII分別表示第一類攻擊者和第二類攻擊者。AI可以任意替換合法用戶的公鑰，但不能查詢系統(tǒng)主密鑰。AII可以訪問主密鑰，但不能替換目標用戶公鑰。假設(shè)C是挑戰(zhàn)者，AI為第一類攻擊者，AII是第二類攻擊者，則無證書簽名方案的安全性可以用攻擊者AI和AII與挑戰(zhàn)者C之間交互的兩個游戲來定義[2](兩個游戲中，挑戰(zhàn)者存儲所有的查詢歷史)。

1.3.1定義1 游戲一(第一類攻擊者與挑戰(zhàn)者之間的交互)

Phase I-1:挑戰(zhàn)者C運行Setup()建立系統(tǒng)參數(shù)，包括需要保密的主密鑰s和公開參數(shù)params={p，q，G，P，P0，H1，H2}。

PhaseI-2:AI可以向挑戰(zhàn)者C發(fā)出一系列以下查詢:

Hash查詢:AI選擇一字符串，C返回該字符串的Hash值給AI。

部分私鑰查詢:AI選擇一個用戶ID，C根據(jù)系統(tǒng)參數(shù)及部分密鑰生成算法，計算ID對應(yīng)的部分私鑰DID，并返回給AI。

秘密值查詢:AI選擇一個用戶ID，C根據(jù)系統(tǒng)參數(shù)及秘密值生成算法，計算ID對應(yīng)的秘密值xID，并返回給AI。

公鑰查詢:AI選擇一個用戶ID，C根據(jù)系統(tǒng)參數(shù)及公鑰生成算法，計算ID對應(yīng)的公鑰PKID，并返回給AI。

簽名查詢:AI選擇用戶ID和消息m發(fā)送給C，C計算用戶ID的私鑰SKID，并用SKID該私鑰對消息m進行簽名，生成Sign(ID，m，SKID)并將其返回給AI。

簽名驗證查詢:AI發(fā)送Sign(ID，m，PKID，result)給C，C驗證簽名有效性，若簽名有效，則設(shè)置result=1；否則，設(shè)置result=0，并返回result值給AI。

PhaseI-3:AI偽造一個簽名，輸出四元組(m*，s*，ID*，PK*)，稱AI在游戲中獲勝，當(dāng)且僅當(dāng):

1)s*是關(guān)于ID*、PK*和m*的一個有效簽名；

2)AI從未執(zhí)行過身份為ID*用戶的部分私鑰查詢；

3)AI從未執(zhí)行過關(guān)于ID*、PK*和m*的簽名查詢。

1.3.2定義2 游戲二(第二類攻擊者與挑戰(zhàn)者C之間的交互)

Phase I-1:挑戰(zhàn)者C運行Setup()建立系統(tǒng)參數(shù)，包括需要保密的主密鑰s和公開參數(shù)params={p，q，G，P，P0，H1，H2}。

Phase I-2:AII可以向挑戰(zhàn)者C發(fā)出定義1中Phase I-2所定義的查詢。

Phase I-3:AII偽造一個簽名，輸出四元組(m*，s*，ID*，PK*)，稱AII在游戲中獲勝，當(dāng)且僅當(dāng):

1)s*是關(guān)于ID*、PK*和m*的一個有效簽名；

2)AII從未執(zhí)行過身份為ID*用戶的秘密值查詢或公鑰替換查詢；

3)AII從未執(zhí)行過關(guān)于ID*、PK*和m*的簽名查詢。

1.3.3定義3(適應(yīng)性選擇消息攻擊不可偽造性)

一個無證書簽名方案在適應(yīng)性選擇消息攻擊下是不可偽造的，當(dāng)且僅當(dāng)，任何多項式時間受限攻擊者不能以不可忽略的優(yōu)勢贏得上述兩個游戲。

本文中，安全的簽名方案指簽名方案在適應(yīng)性選擇消息攻擊下存在不可偽造性。

2　無需配對的無證書簽名方案

本論文基于ElGamal簽名體制和無證書簽名方案[4，11]，設(shè)計無需配對的無證書簽名方案如下:

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

KGC生成兩個素數(shù)p、q，使得q|p-1，P為安全橢圓曲線上循環(huán)加法群G中一個階為q的生成元，選擇Hash函數(shù)H1:{0，1}*×G×G|→Zq*。KGC選擇主密鑰s∈Zq*，并計算系統(tǒng)公鑰P0=sP，公開系統(tǒng)參數(shù)params={p，q，G，P，P0，H1，H2}，保密主密鑰s。

2.2用戶秘密值生成

用戶IDi隨機選擇xi∈Zq*作為其長期私鑰，并計算Xi=xiP，將Xi發(fā)給KGC。

2.3用戶部分私鑰生成

KGC收到用戶IDi發(fā)送的Xi后，隨機選擇一個ri∈Zq*，計算IDi的部分公鑰Ri=riP，計算IDi的部分私鑰Di=ri+sH1(IDi，Ri，Xi)，通過安全信道將Di返回給用戶IDi。

2.4用戶密鑰生成

用戶IDi收到Di后，通過計算判斷等式Ri+H1(IDi，Ri，Xi)P0=DiP是否成立來判斷KGC分配給自己的部分私鑰是否有效。若有效，則用戶IDi設(shè)置自己的私鑰為SKIDi=〈xi，Di〉，公鑰為PKIDi=〈Xi，Ri〉。

2.5簽名過程

用戶IDi隨機選取αZq*且α0，計算Ti=αP，γ=H1(IDi，Ti，Xi)，e=SHA-x(m)，σ=(e+γxi+γDi)/α，生成簽名(σ，γ)并發(fā)送給節(jié)點A。

2.6驗證過程

當(dāng)收到(σ，γ)后，節(jié)點A計算，h1=H1(IDi，Ri，Xi)，e=SHA-x(m)，u1=e/σ，u2=γ/σ，Q=u1P+u2(Ri+Xi+h1P0) ，并驗證H1=(IDi，Q，Xi)=γ是否成立，若成立，輸出1；否則輸出0。

驗證過程正確性:

所以H1(IDi，Q，Xi)=H1(IDi，Ti，Xi)=γ

3　安全與效率

3.1安全性分析

3.1.1密鑰生成階段的安全性

首先，本文所提的方案中，不存在文獻[11]中一個部分私鑰可以對應(yīng)多個公私鑰對的問題。因為，KGC在為用戶生成其部分私鑰之前，用戶先選擇秘密值xA，并將其對應(yīng)的XA發(fā)送給KGC，由KGC負責(zé)將XA、部分公鑰RA及IDA綁定。因此，有效地防止文獻[11]中用戶A通過生成多個XA來生成多個PK=〈XA，RA〉及SK=〈xA，rA〉的情況。

3.1.2簽名方案安全性證明

本節(jié)對本文所提的簽名方案的安全性進行證明。

定理1(無證書簽名方案在AI攻擊下存在不可偽造性):在隨機預(yù)言模型(ROM)中，若群G上的離散對數(shù)問題(DL)是困難的，那么上述的無證書簽名方案在敵手AI的攻擊下是安全的。

證明:假設(shè)C想解決G上的DL問題，其DL問題的輸入為(dP，P)，其目標是計算出d。假設(shè)AI能以不可忽略的優(yōu)勢攻破我們的簽名方案，下面利用AI來解決群G上的DL問題。首先，C設(shè)置P0=dP，生成系統(tǒng)參數(shù)params={p，q，P，P0，H1，H2}并將其發(fā)給AI。C創(chuàng)建并維持列表L1，LD，LSK，LPK，LS分別用于跟蹤AI對預(yù)言機H1、部分私鑰、秘密值、公鑰和簽名查詢。開始時每個列表均為空，假設(shè)以下AI的詢問都是不同的。

H1查詢:列表L1每一項格式為(ID，R，X，h1)，假設(shè)AI最多能做q1次H1查詢，C在[1，q1]中隨機選取一個值K。當(dāng)C收到AI對H1(IDi，Ri，Xi)查詢時，C隨機選擇h1∈Zq*，返回h1給AI，并將H1(IDi，Ri，Xi，h1)添加到列表L1中。

秘密值查詢:列表LSK中每一項格式為(ID，X，x)，當(dāng)C收到對(IDi，Xi，xi)時，若(IDi，Xi，xi)在列表LSK中存在則返回相應(yīng)的xi給AI；否則，隨機選擇xi∈Zq*，返回給AI，計算Xi=xiP并將(IDi，Xi，xi)添加到列表LSK中。

簽名查詢:當(dāng)C收到關(guān)于身份IDi，公鑰為(Ri，Xi)對消息m的簽名查詢時，C隨機選擇σ，γ，計算，設(shè)置H1(IDi，Q，Xi)=γ，返回(σ，γ)給AI。

定理2(無證書簽名方案在AII攻擊下存在不可偽造性):在隨機預(yù)言模型(ROM)中，若群G上的離散對數(shù)問題(DL)是困難的，那么上述的無證書簽名方案在敵手AII的攻擊下是安全的。

證明:假設(shè)C想解決G上的DL問題，其DL問題的輸入為(dP，P)，其目標是計算出d。假設(shè)AII能以不可忽略的優(yōu)勢攻破我們的簽名方案，下面利用AII來解決群G上的DL問題。首先，C生成系統(tǒng)參數(shù)params={p，q，P，P0，H1，H2}并將其發(fā)給AII。C創(chuàng)建并維持列表L1，LD，LSK，LPK，LS分別用于跟蹤AII對預(yù)言機H1、部分私鑰、私鑰、公鑰和簽名查詢。開始時，每個列表均為空，并假設(shè)以下AII的查詢都是不同的。

H1查詢:列表L1每一項格式為(ID，R，X，h1)，當(dāng)C收到AII對H1(IDi，Ri，Xi)查詢時，C隨機選擇h1∈Zq*，返回h1給AII，并將H1(IDi，Ri，Xi，h1)添加到列表L1中。

秘密值查詢:列表LSK中每一項格式為(ID，X，x)，當(dāng)C收到AII關(guān)于身份為IDi用戶的秘密值查詢(IDi，Xi，xi)時，若IDi=IDK，則C終止；否則，若(IDi，Xi，xi)在列表LSK中存在則返回相應(yīng)的xi給AII，若xi=，則表示關(guān)于身份IDi對應(yīng)的公鑰經(jīng)被替換；若(IDi，Xi，xi)不在列表LSK中，則隨機選擇xi∈Zq*，返回給AII，計算Xi=xiP并將(IDi，Xi，xi)添加到列表LSK中。

3.2效率分析

將本文提出的簽名方案的效率與文獻[11]所提的無證書簽名方案進行比較如表1所示，其中H表示一個哈希運算，S表示橢圓曲線點群G上的標量乘法，Z1表示Zq*中證書的長度。

表1　計算量和簽名長度比較

在簽名階段，計算TA=P需要一次標量乘法，計算h時需要一次哈希運算[11]。在驗證階段，計算h1y需要一次標量乘法，計算hP需要一次標量乘法，計算s1(RA+XA+h1y+hP)和s2(RA+XA+h1y+hP)各需至少一次標量乘法，因此，驗證階段共計計算量4S+1H。本文所提方案，在簽名階段，計算Ti=αP需要一次標量乘法，計算h時需要一次哈希運算。驗證階段，計算u1P需要一次標量乘法，計算h1P0需要一次標量乘法，計算u2(Ri+Xi+h1P0)需要一次標量乘法；計算h1需要一次哈希運算，因此，驗證階段共計計算量3S+1H。驗證階段的效率提高了20。在簽名長度方面，本文提出的方案簽名長度比文獻[11]的簽名長度減少了33.3.

4　結(jié)束語

論文基于ElGamal簽名體制的思想，提出一種新的無需配對的無證書簽名方案，并用隨機預(yù)言模型證明了簽名方案的安全性。方案解決了文獻[11]中利用方案缺陷使得用戶可以在獲得一個部分私鑰的情況下，惡意生成多個公私鑰對的問題，同時，在效率方面也有所提高。

[1]BONEH D，F(xiàn)RANKLIN M K，Identity-based encryption from the weil pairing[C]//Advances in Cryptology-CRYPTO2001.USA:[s.n.]，2001：213-229.

[2]Al-RIYAMI S S，PATERSON K.Certificateless public key cryptography[J].Springer-Verlag，2003：452-473.

[3]CHEN L，CHENG Z，SMART N P.Identity-based key agreement protocols from Pairings[J].Int J Inf Secur，2007，6(4):213-241.

[4]BAEK J，SAFAVI-NAINI R，SUSILO W.Certificateless public key encryption without pairing[M].Heidelberg:Springer，2005，3650:13-148.

[5]DUAN S.Certificateless undeniable signature scheme[J].Information Sciences，2008，178(3):742-755.

[6]ZANG L，ZANG F，QIN B，et al.Provably-secure electronic cash based on certificateless partially-blind signatures[J].Electron Comm Res，2011，10(5):545-552.

[7]JIN Z，WEN Q.Certificateless multi-proxy signature[J].Compute Commun，2011，34(3):344- 352.

[8]ZHANG Z，WONG D，XU J，et al.Certificateless public-key signature:security model and efficient construction[C]//Springer-Verlag.2006：293-308.

[9]CHOI K Y，PARK J H，HWANG J，et al.Efficient certificateless signature schemes[C].Springer-Verlag，2007:443-458.

[10]ZHANG LEI,ZHANG Futai.A method to construct a class of cerificateless signature schemes[J].Chinese Journal of Computers,2009，32(5)：940-945.

[11]WANG Shengbao,LIU Wenhao.Certificateless signature scheme without bilinear pairings[J].Journal on Communications,2012，33(4):93-98.

[12]POINTCHEVAL D,STERN J.Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,12(3):361-369.

Certificateless Signature Scheme without Paring Based on ElGamal Scheme

PENG Cheng1，YANG Dengqi2

(1.School of Mathematics and Statistics，Yunnan University，Kunming 650091，China;2.School of Mathematics and Computer，Dali University，Dali 671003，China)

ElGamal; certificateless signature; without paring

2014-12-22；修改日期: 2015-01-30

國家自然科學(xué)基金(11464049)。

彭程(1980-)，男，碩士，實驗師，主要從事網(wǎng)絡(luò)安全、并行算法方面的研究。

TN918.1；G642.0

A

10.3969/j.issn.1672-4550.2016.01.019