一個(gè)基于橢圓曲線的可證明安全簽密方案

摘 要:簽密能夠在一個(gè)合理的邏輯步驟內(nèi)同時(shí)完成數(shù)字簽名和加密兩項(xiàng)功能。與實(shí)現(xiàn)信息保密性和認(rèn)證性的先簽名后加密方案相比，簽密具有較低的計(jì)算和通信代價(jià)。提出一個(gè)基于橢圓曲線的簽密方案，能夠同時(shí)完成數(shù)字簽名和加密兩項(xiàng)功能。基于可證明安全性理論，在GDH(gap Diffie-Hellman)問題難解的假設(shè)之下，該方案在隨機(jī)預(yù)言機(jī)模型中被證明是安全的。該方案能夠抵御自適應(yīng)選擇明文/密文攻擊。

關(guān)鍵詞:簽密; GDH問題; 隨機(jī)預(yù)言機(jī)模型; 可證明安全性

中圖分類號(hào):TP309 文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)03-1055-03

doi:10.3969/j.issn.1001-3695.2010.03.069

Provably secure signcryption scheme based on elliptic curves

WANG Tian-qin

(School of Computer Science Information Engineering， Henan University， KaifengHenan 475001， China)

Abstract:Signcryption can provide simultaneous digital signature and encryption at a low computational and communication overhead compared with the signature-then-encryption approach. This paper proposed a signcryption scheme based on elliptic curves. Based on the theory of provable security，proved this scheme to be secure under the GDH(gap Diffie-Hellman) assumption in the random oracle model. It is secure against adaptive chosen plaintext/ciphertext attack.

Key words:signcryption; GDH problem; random oracle model; provable security

簽密的概念是由Zheng[1]于1997年首次提出的。簽密能夠在一個(gè)合理的邏輯步驟內(nèi)同時(shí)完成數(shù)字簽名和加密兩項(xiàng)功能，而其計(jì)算和通信代價(jià)要低于先簽名后加密方案，因而它是實(shí)現(xiàn)既加密又認(rèn)證地傳輸和存儲(chǔ)信息的較為理想的方法。由于在電子商務(wù)、電子政務(wù)、密鑰管理等方面都需要既保密又認(rèn)證的信息傳輸，簽密有著廣闊的應(yīng)用范圍[2，3]。

由于橢圓曲線具有較好的密碼學(xué)特性，基于橢圓曲線的密碼算法能夠提供更好的加密強(qiáng)度、更快的執(zhí)行速度和更小的密鑰長(zhǎng)度，橢圓曲線在公鑰密碼學(xué)中有著廣泛的應(yīng)用。自20世紀(jì)80年代中期橢圓曲線密碼體制(ECC)被引入以來(lái)[4]，其逐漸成為一個(gè)令人感興趣的密碼學(xué)分支，進(jìn)而形成了一個(gè)研究熱點(diǎn)。許多實(shí)用的基于橢圓曲線的密碼算法被提出。

可證明安全性理論是在一定的敵手模型下用歸約的方法證明安全方案或協(xié)議能夠達(dá)到特定的安全目標(biāo)。20世紀(jì)90年代Bellare等人[5]著名的RO(randomoracle)模型方法論的提出，使得過去僅作為純理論研究的可證明安全性理論迅速在實(shí)際應(yīng)用領(lǐng)域取得了重大進(jìn)展[6]。其基本思想是把 hash函數(shù)看成隨機(jī)函數(shù)，首先形式化定義方案的安全性，假設(shè)一個(gè)概率多項(xiàng)式時(shí)間(PPT)的敵手能夠以不可忽略的概率破壞方案的安全性;然后模擬者為敵手提供一個(gè)與實(shí)際環(huán)境不可區(qū)分的模擬環(huán)境，回答敵手的所有詢問;最后利用敵手的攻擊結(jié)果解決基礎(chǔ)困難問題。

本文基于文獻(xiàn)[7]提出了一個(gè)基于橢圓曲線的簽密方案，并在RO模型中給出了安全性證明。與文獻(xiàn)[8]的可證明安全簽密方案相比，本文的方案能夠抵御攻擊能力更強(qiáng)的敵手，并且采用了不同的思路對(duì)方案的安全性予以證明。

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

本章簡(jiǎn)單地介紹了橢圓曲線群中的GDH(gap Diffie-Hellman)問題。本文提出的簽密方案的安全性依賴于GDH問題的困難性。

問題描述:給定橢圓曲線群(〈P〉， + )中的任意元素aP、bP，以及DDH(decisional Diffie-Hellman) Oracle ODDH(﹒，﹒，﹒，﹒)，找到Diffie-Hellman密鑰K=abP。其中ODDH的功能是: 對(duì)于輸入(P， Pu， Pv， z) ∈(〈P〉，〈P〉，〈P〉，〈P〉)， 判定是否有z=uvP 。

如果GDH問題從計(jì)算上說(shuō)不可解，則稱GDH假設(shè)成立。確切地說(shuō)，對(duì)于安全參數(shù)k和攻擊者AGDH，定義下述游戲:

GDHgame(k， AGDH)

{ a←RZ*q;b←RZ*q

K←AGDH(P ， aP， bP | ODDH(﹒，﹒，﹒，﹒))

if K==abP then return 1 else return 0

}

其中:←R表示從集合中隨機(jī)選取元素對(duì)變量賦值;

AGDH(P， aP， bP | ODDH(﹒，﹒，﹒，﹒))表示算法在執(zhí)行過程中可以對(duì)符號(hào)“|”之后的預(yù)言機(jī)作詢問。

定義SuccGDH=max Pr[GDHgame(k， AGDH)=1]

這里max指對(duì)所有可能的敵手取最大值。如果SuccGDH是關(guān)于k的可忽略函數(shù)，則稱GDH假設(shè)成立。

2 簽密方案的形式化定義

2.1 方案組成

簽密方案由以下幾個(gè)算法組成:

a)GC——系統(tǒng)初始化算法。輸入安全參數(shù)k，輸出系統(tǒng)公共參數(shù)cp 。

b)GK——密鑰生成算法。輸入系統(tǒng)參數(shù)cp，輸出用戶密鑰對(duì) (sk，pk) 。

c)SC——簽密算法。輸入系統(tǒng)參數(shù)cp，發(fā)送者的私鑰skA，接收者的公鑰pkB，明文m，輸出簽密C 。

d)USC——解簽密算法。輸入系統(tǒng)參數(shù)cp，接收者的私鑰skB，發(fā)送者的公鑰pkA，簽密C，輸出明文m或符號(hào)“⊥”表示解簽密失敗。

2.2 敵手模型

假定敵手為第三方，即只考慮外部攻擊，其目標(biāo)是從簽密信息中獲取部分明文信息或偽造簽密信息。假定敵手可以選擇任意接收者身份和明文對(duì)發(fā)送者的簽密預(yù)言機(jī)進(jìn)行詢問，也可以選擇任意發(fā)送者身份和密文對(duì)接收者的解簽密預(yù)言機(jī)進(jìn)行詢問。

2.3 安全性定義

定義1 密文不可區(qū)分性。設(shè)SCR=(GC， GK， SC， USC)為簽密方案，O為敵手。考慮以下游戲:

game(k， O， SCR)

{ cp←GC(k)(skA， pkA) ←RGK(cp)

(skB， pkB) ←RGK(cp)

(m0， m1) ←O(k， cp， find， pkA， pkB | SC(cp， skA，﹒，﹒)， USC(cp， skB，﹒，﹒))

i←R{0， 1}

C* ←SC(cp， skA， pkB，mi)

i′ ←O(k， cp， guess， pkA， pkB ， C* | SC(cp， skA，﹒，﹒)， USC(cp， skB，﹒，﹒))

if i′==i ∧ (pkA， C*) was never queried to USC(cp， skB，﹒，﹒)

then return 1 else return 0

｝

其中:SC(cp， skA，﹒，﹒)表示以任意接收者公鑰和明文對(duì)A作簽密詢問;USC(cp， skB，﹒，﹒)表示以任意發(fā)送者公鑰和密文對(duì)B作解簽密詢問。(下同)

O的優(yōu)勢(shì)定義為

AdvO=|2Pr[game(k，O，SCR)=1]-1|

以S0表示“game輸出為1”這一事件。如果沒有任何PPT敵手能夠以不可忽略的優(yōu)勢(shì)贏得游戲，則稱簽密方案SCR是密文不可區(qū)分的。

定義2 不可偽造性。設(shè)SCR=(GC， GK， SC， USC)為簽密方案，O為敵手。考慮以下游戲:

game-1(k，O，SCR)

{ cp←GC(k)

(skA， pkA) ←RGK(cp)

(C*， pkR) ←O(k， cp， pkA | SC(cp， skA，﹒，﹒))

if pkR is invalid then return 0

m*← USC(cp， skR， pkA， C*)

if m*≠“⊥”∧(pkR， m*) was never queried by O to SC(cp， skA，﹒，﹒)

then return 1 else return 0｝

定義SuccO=Pr[game-1(k，O，SCR)=1]

如果沒有任何PPT敵手能夠以不可忽略的優(yōu)勢(shì)贏得游戲，則稱簽密方案SCR是不可偽造的。

3 方案構(gòu)造

簽密方案SCR=(GC， GK， SC， USC)的細(xì)節(jié)描述如下:

GC(k)

隨機(jī)選取長(zhǎng)度為k的素?cái)?shù)q，G1為由點(diǎn)P生成的階為q的橢圓曲線循環(huán)乘法群，假定明文空間為{0， 1}k，選取兩個(gè)安全hash函數(shù)G: G1→{0， 1}k ， H: {0， 1}*→Zq ，cp=( G1， P， G， H)。

GK(cp)

對(duì)任意用戶i， 隨機(jī)選取秘密數(shù)si∈Z*q，令Pi=siP，用戶的公鑰pki=Pi，私鑰ski=si SC(cp， skA， pkB， m)

設(shè)skA=sA， pkA=PA，pkB= PB 。

x←RZ*q， K←x PB， t←G(K)， c←t⊕m， r←H(m， PA， PB， K)， s←x/(r+ sA)， C←(c， r， s)

USC(cp， skB， pkA， C)

設(shè)skB= sB， pkA= PA，pkB= PB， C=(c， r， s) 。

W←s(PA+rP)， K←sBW， t←G(K)， m ←t⊕c，

if H(m， PA， PB， K)==r then return m

else return “⊥”

4 安全性分析

1)保密性 關(guān)于方案的保密性，有以下定理。

定理1 如果GDH假設(shè)成立，則SCR在本文假定的安全模型下具有密文不可區(qū)分性。確切地說(shuō)，有

AdvSCR(qG ， qH， qSC，qUSC)≤2 SuccGDH+(qH +qSC+qUSC)/2k-1+ (qSC+qUSC)/2k-1+ qSC(qG +qH+qSC+qUSC)/2k -1

其中qG、qH、qSC、qUSC分別表示各預(yù)言機(jī)被詢問的次數(shù)。

證明 不失一般性，本文假設(shè)信息的發(fā)送者為A，接收者為B。設(shè)有模擬者M(jìn)模擬游戲game中的SCR與敵手O作游戲game-1，回答O所提出的詢問。游戲規(guī)則修改如下:

a)對(duì)于敵手O在find階段之后所生成的兩個(gè)長(zhǎng)度相等的明文m0、m1，M執(zhí)行下列操作:

t+←R{0， 1}k，i←R{0， 1}，c+←t+⊕mi ， r+←R Zq ，s+←R Z*q

回答C+←(c+， r+， s+)。

b)當(dāng)G在K+=s+(r++sA)PB被詢問時(shí)，直接返回t+之值。

c)當(dāng)H在(mi， PA， PB， K+=s+(r++sA)PB )被詢問時(shí)，直接返回r+之值。

d)假定SC oracle和USC oracle 都是完備的，即對(duì)于簽密詢問，運(yùn)用sA進(jìn)行簽密應(yīng)答;對(duì)于解簽密詢問，運(yùn)用sB進(jìn)行解簽密應(yīng)答。

以S1表示“game-1輸出為1”這一事件。

在敵手O看來(lái)，M所提供的模擬環(huán)境與實(shí)際環(huán)境類似，不同之處僅在于: 當(dāng)H 在find階段中在點(diǎn)(mi， PA， PB， K+ )被詢問時(shí)回答有區(qū)別(這是因?yàn)閙i只有在find階段結(jié)束時(shí)才確定)，H在該點(diǎn)被詢問的次數(shù)最多為qH+qSC+qUSC。因此有

| Pr[S1]-Pr[S0] | ≤ (qH+qSC+qUSC)/2k (1)

對(duì)game-1進(jìn)行修改，得游戲game-2。游戲規(guī)則修改如下:

規(guī)則a)和d)不變。b)G被詢問時(shí)，直接返回G oracle之值;c)H被詢問時(shí)，直接返回H oracle之值。

注意到， t+僅在計(jì)算密文c+時(shí)使用。由于t+的隨機(jī)性，僅有c+而區(qū)分m0和m1是不可能的，從而有

Pr[S2]=1/2(2)

與game-1相比，不同之處在于:如果G在K+被詢問或H在(mi， PA， PB， K+ )被詢問，回答可能有差別(game-1中分別以t+、r+應(yīng)答而game-2中均以隨機(jī)數(shù)應(yīng)答)。從而有

| Pr[S2]-Pr[S1] | ≤ Pr[G在K+被詢問或H在(mi， PA， PB， K+ )被詢問](3)

事件“G在K+被詢問或H在(mi， PA， PB， K+ )被詢問”可以分為三種情形:由敵手O直接詢問，用ask2表示該情形;通過SC oracle詢問;通過USC oracle詢問。則有

Pr[G在K+被詢問或H在(mi，PA， PB， K+ )被詢問]≤ Pr[ask2]+(qSC+qUSC)/2k(4)

進(jìn)一步，用G Sim、H Sim分別代替游戲game-2中的G oracle、H oracle，得游戲game-3。此時(shí)，M需要維護(hù)四張表GL1、GL2、HL1、HL2，用于跟蹤對(duì)各預(yù)言機(jī)的詢問，各表的初始狀態(tài)均為空表。模擬算法描述如下:

G Sim(K)

{if ODDH(P， W， PR， K)==1

for some (PR ||W||(?， t))∈GL2 then return t

else if (K， t) ∈GL1 then return t

else { t←R{0， 1}k ;Add (K， t ) to GL1;

return t }

}H Sim(m， PS， PR， K)

{if ODDH(P， W， PR， K)==1

for some (PR ||W||((m， PS， PR， ?)， r))∈HL2

then return r

else if ((m， PS， PR， K)， r) ∈HL1 then return r

else { r←RZq ;

add ((m， PS， PR， K)， r) to HL1;

return r }}

注意到，在此游戲中，GL2、HL2均為空表。從而有

Pr[ask3]= Pr[ask2](5)

進(jìn)一步，用SCSim、USCSim分別代替游戲game-3中的SC oracle、USC oracle，得游戲game-4。模擬算法描述如下:

SCSim(PA ， PR ， m)

{t←R{0， 1}k ;c=t⊕m ;r←RZq ;s←R Z*q

W=s(PA+rP)

add (PR ||W||(?， t)) to GL2

add (PR ||W||((m， PA， PR， ?)， r)) to HL2

C← (c， r， s)

return C

}

 USCSim(PB， PS， C)

{W=s(PS+rP)

ifODDH(P， W， PB， K)==1

for some (K， t) ∈GL1or

ODDH(W， W′， PR， PB)==1

for some (PR ||W’||(?， t))∈GL2

then m=t⊕c

else { t←R{0， 1}k ;

add (PB ||W||(?， t)) to GL2 ; m= t⊕c }

if ODDH(P， W， PB， K)==1

for some ((m， PS， PB， K)， h)∈HL1 or

ODDH(W， W′， PR， PB)==1 for some

(PR ||W′||((m， PS， PR， ?)， h))∈HL2

thenif h==r then return m

 else return “⊥”

else { h←RZq ;

add (PB ||W||((m， PS， PB，?)， h)) to HL2;

if h==r then return m

else return “⊥”

}}

注意到，僅當(dāng)SC oracle在點(diǎn)K+對(duì)G或H作過詢問并且(K+， t) ∈GL1 或 ((m， PA， PR， K+)， h) ∈ HL1 時(shí)，模擬結(jié)果才會(huì)有誤差。因此有

| Pr[ask4]-Pr[ask3] |≤qSC(qG+qH+qSC+qUSC)/2k  (6)

如果事件ask4發(fā)生，則說(shuō)明表中有K+=s+(r++sA)PB 存在。有abP=sAPB=(K+- s+r+PB)1/s+。進(jìn)一步，其值可以通過DDH oracle找到(即對(duì)于表中的分量K，首先計(jì)算(K- s+r+PB)1/s+)=v，然后借助ODDH(P， PA ， PB， v)找到正確的K值)。也就是說(shuō)，如果ask4發(fā)生，則可以解決GDH問題。從而有

Pr[ask4]≤SuccGDH(7)

由式(1)~(7)可得

AdvSCR(qG， qH， qSC， qUSC)/2=| Pr[S0]-1/2 |≤ SuccGDH+(qH +qSC+qUSC)/2k+ (qSC+qUSC)/2k+ qSC(qG +qH+qSC+qUSC)/2k

從而得到定理的結(jié)論。

關(guān)于算法的執(zhí)行時(shí)間，通過直接計(jì)算不難得到，敵手攻破SCR與解決GDH問題的時(shí)間多項(xiàng)式等價(jià)。

2)不可偽造性 關(guān)于方案的不可偽造性，有以下結(jié)論:如果CDH假設(shè)成立，則方案SCR在本文假定的安全模型下具有不可偽造性。運(yùn)用與定理1的證明過程類似的方法，可以得到具體不可偽造性的度量結(jié)果。

3)安全性比較 從安全性角度看，該方案能夠抵御敵手的自適應(yīng)選擇明文/密文攻擊。與文獻(xiàn)[8]中的方案相比，本文基于不同的計(jì)算假設(shè)，采用了不同的安全性證明思路。

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

本文提出了一個(gè)基于橢圓曲線的簽密方案，并在RO模型中給出了安全性證明。在GDH問題難解的假設(shè)之下，該方案被證明是安全的。從安全性角度看，該方案能夠抵御敵手的自適應(yīng)選擇明文/密文攻擊。與文獻(xiàn)[8]中的方案相比較，本文基于不同的計(jì)算假設(shè)，并且采用了不同的思路對(duì)方案的安全性予以證明。

參考文獻(xiàn):

[1]ZHENG Yu-liang.Digital signcryption or how to achieve cost(signatureencryption) << cost(signature)+cost(encryption)[C]//KALISKI J R B S.Proc of Advances in Cryptology-CRYPTO’97.Berlin:Springer-Verlag，1997:165-179.

[2]陳偉東，馮登國(guó).簽密方案在分布式協(xié)議中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，2005，28(9):1421-1430.

[3]CHEN Li-qun， LEE J M. Improved identity-based signcryption[C]//VAUDENAY S.Proc of Public Key Cryptography-PKC.Berlin:Springer-Verlag，2005:362-379.

[4]KOBLITZ N. Elliptic curve cryptosystem[J].Mathematics of Computation，1987，48(177): 203-209.

[5]BELLARE M， ROGAWAY P. Random oracles are practical:a paradigm for designing efficient protocols[C]//Proc of the 1st ACM Conference on Computer and Communications Security.New York: ACM Press，1993: 62-67.

[6]馮登國(guó).可證明安全性理論與方法研究[J].軟件學(xué)報(bào)，2005，16(10):1743-1756.

[7]BAEK J， STEINFELD R， ZHENG Yu-liang. Formal proofs for the security of signcryption[J]. Journal of Cryptology，2007，20(2):203-235.

[8]李發(fā)根，胡予濮，李剛.一個(gè)高效的基于身份的簽密方案[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(9):1641-1647.