基于ElGamal體制的無(wú)需配對(duì)無(wú)證書(shū)簽名方案

彭　程，楊鄧奇

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

?

基于ElGamal體制的無(wú)需配對(duì)無(wú)證書(shū)簽名方案

彭程1，楊鄧奇2

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

ElGamal簽名體制；無(wú)證書(shū)簽名；無(wú)雙線性對(duì)

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

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

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

1.2通用的無(wú)證書(shū)簽名方案

一般來(lái)講，無(wú)論是基于雙線性對(duì)還是無(wú)需配對(duì)的無(wú)證書(shū)簽名方案，通常包括7個(gè)算法[2]。

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

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

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

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

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

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

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

1.3安全模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Phase I-1:挑戰(zhàn)者C運(yùn)行Setup()建立系統(tǒng)參數(shù)，包括需要保密的主密鑰s和公開(kāi)參數(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偽造一個(gè)簽名，輸出四元組(m*，s*，ID*，PK*)，稱AII在游戲中獲勝，當(dāng)且僅當(dāng):

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

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

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

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

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

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

2　無(wú)需配對(duì)的無(wú)證書(shū)簽名方案

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

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

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

2.2用戶秘密值生成

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

2.3用戶部分私鑰生成

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

2.4用戶密鑰生成

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

2.5簽名過(guò)程

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

2.6驗(yàn)證過(guò)程

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

驗(yàn)證過(guò)程正確性:

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

3　安全與效率

3.1安全性分析

3.1.1密鑰生成階段的安全性

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

3.1.2簽名方案安全性證明

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

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

證明:假設(shè)C想解決G上的DL問(wèn)題，其DL問(wèn)題的輸入為(dP，P)，其目標(biāo)是計(jì)算出d。假設(shè)AI能以不可忽略的優(yōu)勢(shì)攻破我們的簽名方案，下面利用AI來(lái)解決群G上的DL問(wèn)題。首先，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對(duì)預(yù)言機(jī)H1、部分私鑰、秘密值、公鑰和簽名查詢。開(kāi)始時(shí)每個(gè)列表均為空，假設(shè)以下AI的詢問(wèn)都是不同的。

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

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

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

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

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

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

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

3.2效率分析

將本文提出的簽名方案的效率與文獻(xiàn)[11]所提的無(wú)證書(shū)簽名方案進(jìn)行比較如表1所示，其中H表示一個(gè)哈希運(yùn)算，S表示橢圓曲線點(diǎn)群G上的標(biāo)量乘法，Z1表示Zq*中證書(shū)的長(zhǎng)度。

表1　計(jì)算量和簽名長(zhǎng)度比較

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

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

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

[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

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

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

TN918.1；G642.0

A

10.3969/j.issn.1672-4550.2016.01.019