一種具有CDH問題安全性基于身份的簽名方案

陳輝焱, ,

(1.北京電子科技學院 信息安全系,北京 100070; 2.西安電子科技大學 通信工程學院,西安 710071)

0 概述

在實踐中使用公鑰密碼學,最主要的問題是如何提供一種安全的方式將用戶與他們的公鑰連接起來。目前,解決上述問題的方案是建立一個公鑰基礎設施,其中由可信實體頒發證書來確定公鑰屬于某個確定的用戶,證書通常包括用戶的身份、公鑰以及可信的實體簽名。若需要安全的通信,2個用戶間首先要交換證書。為了減少實際應用中對用戶證書的需求,文獻[1]提出基于身份密碼學的觀點,其思想是用戶的公鑰可以從任意字符串(郵件地址、連接用戶姓名的IP地址、社會安全號等)中導出,它以一種明確的方式來驗證其身份。這種密碼體系需要一種被稱為私鑰生成器(Private Key Generator,PKG)的可信機構來完成,PKG的任務是從用戶的身份信息中計算用戶的私鑰。

1984年以來,許多基于身份的簽名(Identity-based Signature,IBS)方案[2-3]被提出。目前,有兩種通用的IBS構造方法:一種由文獻[4]提出,它表明之前提出的大量方案都是其通用構造的實例;另外一種由文獻[5]提出,對于簽名知識的證明,該方法需要有效的零知識協議,這使得其構造僅僅適用于一部分方案,如RSA-FDH和BLS[6]。

IBS的安全證明一般都是通過演示一個規約來進行,這種規約證明了如果攻擊者A能夠有效地破解某個IBS,那么就可以構造出一種算法來破解這種困難問題,這種評估安全性的技術就是安全性規約。規約質量由敵手抗IBS方案破解潛在的棘手問題成功的概率決定。當敵手在時間t內運行成功的概率大約等于相同時間內解決潛在困難問題的概率時,則認為安全規約是嚴格的,否則就認為它是近似規約。

嚴格的安全證明需要較短的安全參數和更高的效率。針對那些在隨機預言機模型下是安全的密碼方案或由它們變形[7-8]所得的一些密碼方案,為其提供新的安全證明,以及利用嚴格的安全規約構造新的方案[9-10],已經成為可證明安全領域的一個研究熱點。然而,目前在設計具有嚴格安全規約的IBS方案方面還沒有明顯的進步。文獻[11]在Diffie-Hellman假設下對方案在嚴格安全規約范圍內通過Pointcheval和斯特恩分叉引理給出了證明。文獻[12-13]在Diffie-Hellman假設下對方案在嚴格安全規約范圍內通過文獻[14]的“ID規約技術”給出了證明。文獻[4]針對IBS方案的大家族定義了一個框架來提供安全性證明,但是該框架不能提供嚴格的安全界。文獻[5]演示了從任何滿足確定條件的數字簽名方案到IBS方案的轉換,并對所得的IBS方案給出安全性證明,盡管該安全性證明避免了分叉技術的使用,但它的規約條件仍然比較寬松。

盡管可計算的Diffie-Hellman (Computational Diffie-Hellman,CDH)假設在技術上比離散對數假設強,但對于各種已被研究的密碼群來說,目前并不知道如何通過解決離散對數問題[15]來更快地解決Diffie-Hellman問題。此外,一些理論表明在某些群中CDH假設與離散對數假設[15]等價。

基于以上問題,本文提出一種新的IBS方案IDSSTR。該方案的簽名過程是確定的:用戶使用他的部分密鑰通過Schnorr[16]簽名方案在消息上計算簽名。在隨機預言機模型下,IDSSTR的安全性與CDH假設密切相關。此外,不需要額外的信息將IDSSTR轉換成離線/在線版本。為縮短簽名消息的總長度,本文也給出具有消息恢復功能的IDSSTR修改版本。

1 預備知識

1.1 IBS方案

IBS方案由下列4個步驟組成:

1)系統參數建立。該算法通過PKG運行,輸入安全參數,生成方案的公共參數params和主密鑰。PKG公布公共參數,自己保存主密鑰。

2)私鑰提取。給出身份ID、主密鑰和公共參數params,該算法生成ID的私鑰dID。主實體將使用該算法針對參與方案的所有實體來生成私鑰,并通過安全渠道將私鑰分發給其主人。

3)簽名。給出消息m、身份ID、私鑰dID和公共參數params,該算法在m上生成ID的簽名σ。具有身份ID的實體將使用該算法用于簽名。

4)驗證。給出簽名σ、消息m、身份ID和公共參數params,如果σ對于身份ID在m上是有效的簽名,則該算法輸出“接受”;否則,輸出“拒絕”。

IBS方案安全性已知的最普遍概念是在自適應性選擇消息攻擊時存在偽造安全,在該模型中,敵手可以讓簽名者簽署除了輸出以外的任何消息,如果敵手最終輸出一對有效的消息和簽名,則敵手贏得游戲。

敵手和挑戰者之間的游戲如下:

1)系統參數建立。挑戰者運行系統參數建立算法,得到公共參數params和主私鑰sk。敵手可以得到公共參數params,但主私鑰sk由挑戰者保管。

2)查詢。敵手自適應地制作大量不同的查詢給挑戰者。每個查詢可以是下列中的一種:

(1)哈希查詢:挑戰者針對請求的輸入計算哈希函數值并將該值發送給敵手。

(2)私鑰提取查詢:敵手可以詢問任何身份ID的私鑰。挑戰者通過運行私鑰提取算法生成與ID對應的私鑰dID,將dID作為應答發送給敵手。

(3)簽名查詢:敵手可以針對身份ID和某個消息m對挑戰者進行簽名查詢。挑戰者首先運行私鑰提取算法產生與ID對應的私鑰dID,再利用dID運行簽名算法生成消息m的簽名σ,將σ作為應答發送給敵手。

3)偽造。敵手最終對消息m*和身份ID*輸出一個偽造的簽名σ*。如果下列條件均成立,則敵手成功:

(1)Verify(params,ID*,m*,σ*)=accept。

(2)敵手在ID*上沒有制造提取查詢。

(3)敵手在(ID*,m*)上沒有制造簽名查詢。

在上面的游戲中敵手A的優勢被定義為:

AdvSigA=Pr[A succeeds]

(1)

其中,概率是挑戰者和敵手在各種能遇到的情況下得到的。

定義1如果敵手在時間t內最多制造qs個簽名查詢,qH個哈希函數查詢,qe個私鑰提取查詢,且AdvSigA至少為ε,則敵手就可以破解該簽名方案。如果一個簽名方案在可適應選擇消息條件下沒有偽造者可以破解它,則認為該簽名方案是不可偽造的。

1.2 雙線性配對和復雜性假設

為簡單起見,令G1=G2。對于條件G1=G2,可以修改結合超級橢圓曲線的Weil和Tate配對來創造這樣的雙線性。

定義3如果不存在一個概率多項式時間算法在時間t內,以至少ε的概率解決群G上的CDH問題,則認為(t,ε)-CDH假設成立。

CDH問題的困難性被廣泛地認為與離散對數問題的困難性密切相關。此外,對于離散對數問題是困難的一類群來說,通過文獻[15]的結果,可以直接將本文方案與離散對數問題的困難性相聯系。

1.3 密碼哈希函數

密碼哈希函數是具有特定安全屬性的哈希函數,適合在各種信息安全應用中作為原語使用,例如身份驗證和消息完整性。對于密碼哈希函數H,存在與密碼觀點相關的3個基本屬性。

1)原像抵抗性。給出一個哈希值h,很難找到一個消息m使得H(m)=h。缺乏這種屬性的密碼哈希函數對于原像攻擊是很脆弱的。

2)第二原像抵抗性。給出一個輸入m1,很難找到不同的輸入m2使得H(m2)=H(m1)。缺乏這種屬性的密碼哈希函數對于第2種原像攻擊是很脆弱的。

3)抗碰撞性。很難找到2條不同的消息m1和m2使得H(m1)=H(m2),如m1和m2這樣的一對值被稱為密碼哈希碰撞。

2 具有嚴格安全性規約的IBS

本文的簽名方案IDSSTR運行過程如下:

1)系統參數建立。給出安全參數n,算法運行如下:

2)私鑰提取。給定用戶的身份ID∈{0,1}*,算法運行如下:

(2)計算h=H(v,ID)和f=hx。

(3)計算r=H0(f,ID)。

(4)計算y=t+rxmodp。

(5)將對應身份ID的私鑰dID設置為dID=(f,y)。

3)簽名。給出身份ID、dID和消息m∈{0,1}*,算法運行如下:

(2)計算c=H1(v0,m)和w=gy。

(3)計算s=k+cymodp。

(4)消息m和身份ID上的簽名σ=(f,w,s,c)。

4)驗證。給出身份ID和消息m上的簽名σ=(f,w,s,c),算法運行如下:

(1)計算r=H0(f,ID)。

(2)計算h=H(wu-r,ID)。

2.1 安全性證明

首先,證明不可偽造性。

定理1假設H1是密碼哈希函數,它具有原像抵抗性,H和H0作為隨機預言機。如果階為素數p的群G上的CDH假設成立,則該方案在自適應選擇消息攻擊下是安全的,如果在qH個隨機預言機查詢、qe個提取預言機查詢和qs個簽名預言機查詢的條件下滿足:

ε≤ε′+(qsig+qe)(qH+qH0+2qe+2qs)/p+

(2+qH+qe+qs)/p

(2)

t≈t′-O(4qe+6qs+qH)T

(3)

則該簽名方案是不可偽造的。其中,T是G中求冪的最大時間。

證明:F是一個偽造者,(t,qH,qH0,qe,qs,ε)破壞本文的構造。

構造一個模擬算法S,它可以將(G,g,p)和(ga,gb)作為輸入。算法S使用F算法在t′步內以ε′的概率計算CDHg,p(ga,gb)函數,其中:

ε≤ε′+(qs+qe)(qH+qH0+2qe+2qs)/p+

(2+qH+qe+qs)/p

(4)

t≈t′-O(4qe+6qs+qH)T

(5)

算法S對偽造者F模擬運行上述簽名方案。算法S回答F的哈希函數查詢、私鑰提取查詢、簽名預言機查詢,并將F可能的偽造(m,σ)轉化為CDHg,p(ga,gb)函數的答案。算法S通過提供(G,g,p)開始模擬,公鑰u=ga作為F的輸入。算法S回應F的查詢如下:

(1)S檢查L。如果存在條目(v,ID,d)∈L,S返回gbgd到F。

(2)否則,S檢查L′。L′通過提取預言機和簽名預言機生成。如果存在條目(v,ID,d)∈L′,S返回gd到F。

(1)S檢查L0。如果存在條目(f,ID,r)∈L0,S返回r到F。

(2)否則,S檢查L0′。L0′通過提取預言機和簽名預言機生成。如果存在條目(f,ID,r)∈L0′,S返回r到F。

(1)S檢查LE,如果存在條目(ID,f,y)∈LE,S返回(f,y)到F。

4)簽名查詢。假設偽造者F要求身份ID∈{0,1}*和消息m∈{0,1}*上的簽名,算法S在不知道主密鑰的情況下必須創建一個有效的簽名組。在這個過程中,S定義了哈希函數H和H0的若干值并為簽名查詢生成了一些私鑰。因此,算法S得到列表LE、L′和L0′。模擬過程如下:

(1)S檢查LE。如果存在條目(ID,f,y)∈LE,S跳到過程(5)。

(4)設置H(v,ID)=h,H0(f,ID)=r。如果H(v,ID)或H0(f,ID)已經被設置,則S終止;否則,在身份ID上生成私鑰dID=(f,y),并分別將(f,ID,y)、(v,ID,d)、(f,ID,r)放到LE、L′和L0′中。

(6)S計算c=H1(v0,m)和s=k+cy,生成一個有效的簽名σ=(f,w,s,c)并將其返回到F。

5)偽造。A輸出(m*,ID*,σ*=(f*,w*,s*,c*))使得σ*在消息m*和身份ID*上是一個有效的簽名,要求(m*,ID*)未曾在之前的簽名預言機查詢中被查詢過,ID*未曾在之前的提取預言機查詢中被查詢過。其中,如果H0(f*,ID*)沒有被攻擊者查詢到H0預言機中或通過簽名預言機和提取預言機設置,則模擬查詢到H0預言機自身。如果r*=H0(f*,ID*),H(w*u-r*)沒有被攻擊者查詢到H預言機中或通過簽名預言機和提取預言機設置,則模擬查詢到H預言機自身。

需要注意的是,S為F提供模擬器,它的分布與F在含有簽名者的真實交互中的分布相同。為了更清楚地說明這點,本文給出下列解釋:

1)H0預言機和H預言機的模擬器較好。

解決CDH問題時假設偽造者F返回一個有效的消息、身份和簽名組(m*,ID*,σ*=(f*,w*,s*,c*)),(m*,ID*)和ID*都未曾在之前的私鑰提取查詢和簽名查詢中被查詢過。在有效的偽造簽名(m*,ID*,σ*=(f*,w*,s*,c*))中,需要考慮下列情形:

情形1ID*出現在簽名預言機查詢中,但存在滿足(ID*,f′,gy′)=(ID*,f*,w*)的(ID*,f′,gy′)∈LE。假設A選擇gk并計算c*=H1(gk,m*),為了得到s*,A必須計算DLg(gk(w*)c*)。假設A選擇c*,為了生成一個有效的偽造簽名(m*,ID*,σ*=(f*,w*,s*,c*)),A必須找到滿足H1(gs*(w*)c*,m*)=c*的s*。如果s*以不可忽略的概率被找到,則密碼哈希函數H1就會很容易受到原像攻擊,這與原像抵抗性的概念發生矛盾。因此,這種情況下A生成有效偽造簽名的概率是可以忽略的。

情形2ID*出現在簽名預言機查詢中,但存在滿足(ID*,f′,gy′)≠(ID*,f*,w*)的(ID*,f′,y′)∈LE。假設r*=H0(f*,ID*),r′=H0(f′,ID*),可以得到w*ur*≠w′ur′。否則,通過w*ur*=w′ur′得到h*=H(w*ur*,ID*)=H(w′ur′,ID*)=h′,f*=(h*)a=(h′)a=f′,r*=H0(f*,ID*)=H0(f′,ID*)=r′,w*=w′。因此,在這種情況下,(w*ur*,ID*,h*)不能出現在L′中。

綜上所述,ID*不能出現在簽名預言機查詢中。

如果上面的情況均不發生,則(v*,ID*)存儲在L中并且h*=H(v*,ID*)=gbgd對于模擬器S中的某些d成立。

用算法S解決CDH問題的概率計算過程如下:

3)NH0代表偽造者F不能在(f*,ID*)上查詢H0預言機這一事件,NH0是偽造者的一部分輸出。NH代表偽造者F不能在(v*,ID*)上查詢H預言機這一事件,NH是偽造者的一部分輸出。其中r*=H0(f*,m*),v*=H0(w*u-r*)。計算概率Pr[NH∨NH0]的上界(Pr[NH∨NH0]=Pr[NH∧NH0]+Pr[NH0])過程如下:

(1)Pr[NH∧NH0]的上界:假設r*=H0(f*,m*),計算v*=w*u-r*。如果模擬器在(v*,ID*)上查詢H預言機本身并得到h=H(v*,ID*),h滿足ha=f*的概率最多為1/p。

(2)Pr[NH0]的上界:模擬器S在(f*,ID*)上查詢H0預言機本身并得到r*=H0(f*,ID*),H(v*,ID*)的概率被設置為最大(qH+qe+qs)/p,其中v*=w*u-r*。如果H(v*,ID*)的概率沒有被設置,它將通過模擬器被查詢且模擬器得到h=H(v*)。h滿足ha=f*的概率為1/p,則Pr[NH0]的概率最大值為(1+qH+qe+qs)/p。

將上面的概率相加,得出模擬器S最小以ε-(qs+qe)(qH+qH0+2qe+2qs)/p-(2+qH+qe+qs)/p的概率解決CDH問題。

2.2 效率分析

表1 2種方案在循環群G上的計算成本比較

2.3 離線/在線分析

本質上通過做離線的所有工作有可能使得上述方案瞬間在線簽名。本文的簽名方案主要分為以下2步:

(2)計算w=gy。

(3)輸出(v0,m)。

2)在線簽名。給出簽名消息m∈{0,1}*。

(1)計算c=H1(v0,m)。

(2)計算s=k+cymodp。

(3)簽名為σ=(f,w,s,c)。

驗證過程與前述相同。這一屬性較有用,因為它允許簽名者重新計算f進而快速地在線簽名,即通過一個模乘運算和模加運算就可以運行一個哈希函數。

3 有限的消息恢復

在帶寬有限的環境中,縮短原始消息M附加簽名σ的總長度是可行的。縮短簽名消息總長度的通用技術是在簽名過程中只對消息的一部分進行編碼,利用這種技術得到的方案稱為具有消息恢復功能的簽名方案。現有的具有消息恢復功能的數字簽名可以分為2種:基于RSA的方案[14]和基于離散對數的方案[18]。本節給出IDSSTR的一種修改版本,并根據文獻[18]提出的技術使其具有消息恢復功能。

IDSSTR修改版本構造過程如下:

1)系統參數建立。給出安全參數n,算法運行如下:

2)私鑰提取。對于給出的身份串ID∈{0,1}*,算法運行如下:

(2)計算h=H(v,ID)和f=hx。

(3)計算r=H0(f,ID)。

(4)計算y=t+rxmodp。

(5)將對應身份ID的私鑰dID設置為dID=(f,y)。

3)簽名。給出身份ID、dID和消息m∈{0,1}l,算法運行如下:

(2)計算m′=F1(m)‖F2(F1(m))⊕m和w=gy。

(3)計算c=H1(v0)⊕m′。

(4)計算c′=H2(c)。

(5)計算s=k+c′ymodp。

(6)消息m和身份ID上的簽名σ=(f,w,s,c)。

4)驗證。給出身份ID和消息m上的簽名σ=(f,w,s,c),算法運行如下:

(1)計算r=H0(f,ID)。

(2)計算h=H(wu-r,ID)。

(3)計算c′=H2(c)。

(4)計算v0=gsw-c′。

(5)計算m′=H1(v0)⊕c。

(6)計算m=[m′]l⊕F2([m′]l)。

其中,[m′]l表示m′中最重要的l位,[m′]l表示m′中次重要的l位,a⊕b表示字符串a和b的異或計算(XOR)。

備注 為了在身份ID上簽名一個較長的消息m(|m|>l),m應該分為m1和m2兩部分,且|m2|=l,m=m1‖m2,m1‖m2表示字符串m1和m2的級聯。

簽名者生成(f,w,s,c)過程如下:

2)計算m′=F1(m2)‖F2(F1(m2))⊕m2和w=gy。

3)計算c=H1(v0)⊕m′。

4)計算c′=H2(c‖m1)。

5)計算s=k+c′ymodp。

6)消息m和身份ID上的簽名σ=(f,w,s,c)。

對于上面的方案,假設H1、H2、F1、F2是密碼哈希函數,H和H0是可以給出類似于IDSSTR安全證明的隨機預言機。

4 結束語

本文提出一種具有嚴格安全性規約的IBS新方案IDSSTR。IDSSTR在線時自然有效,離線階段不需要額外的條件,驗證過程也不變。為了縮短原消息M和附加簽名σ的總長度,本文同時也提出了一種具有部分消息恢復功能的IDSSTR修改版本。因為CDH問題的困難性被廣泛地認為與離散對數問題的困難性密切相關,因此,本文提出的IDSSTR為其提供了安全保證。下一步將對一些基于身份的密碼方案提供新的安全證明以及利用嚴格的安全規約來構造更實用的方案。

[1] ADI S.Identity-based cryptosystems and signature schemes[J].Lecture Notes in Computer Science,1984,21(2):47-53.

[2] XUN Yi.An identity-based signature scheme from the weil pairing[J].IEEE Communications Letters,2003,7(2):76-78.

[3] BARRETO P S L M,MCCULLAGH N,QUISQUATER J J.Efficient and provably-secure identity-based signatures and signcryption from bilinear maps[C]//Proceedings of International Conference on Theory and Application of Cryptology and Information Security.Washington D.C.,USA:IEEE Press,2005:515-532.

[4] BELLARE M,NAMPREMPRE C,NEVEN G.Security proofs for identity-based identification and signature schemes[M].Berlin,Germany:Springer,2004.

[5] KUROSAWA K,HENG S H.From digital signature to ID-based identification/signature[C]//Proceedings of International Workshop on Public Key Cryptography.Berlin,Germany:Springer,2004:248-261.

[6] DAN B,BEN L,HOVAV S.Short signatures from the weil paring[J].Journal of Cryptology,2004,17(4):297-319.

[7] CORON J S.Optimal security proofs for PSS and other signature schemes[C]//Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2002:272-287.

[8] GE S.Tight proofs for signature schemes without random Oracles[C]//Proceedings of International Conference on Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2011:189-206.

[9] 盧 超,錢海峰.標準模型下的在線/離線多簽名方案[J].計算機應用研究,2010,27(9):3514-3517.

[10] 胡國政,洪 帆.標準模型中可證安全的簽名方案[J].武漢理工大學校報,2009,31(15):130-134.

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

[12] 劉振華,張襄松,田緒安,等.標準模型下基于身份的具有部分消息恢復功能的簽名方案[J].北京工業大學學報,2010,36(5):654-658.

[13] WANG Z,CHEN H.Emerging directions in embedded and ubiquitous somputing[M].Berlin,Germany:Springer,2007.

[14] BELLARE M,ROGAWAY P.The exact security of digital signatures:how to sign with RSA and Rabin[C]//Proceedings of International Conference on Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,1996:399-416.

[15] MAURER U M,WOLF S.The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms[J].SIAM Journal on Computing,1998,28(5):1689-1721.

[16] SCHNORR C P.Efficient identification and signatures for smart cards[M].Berlin,Germany:Springer,1989.

[17] LIBERT B,QUISQUATER J J.The exact security of an identity based signature and its applications[EB/OL].[2016-11-25].https://eprint.iacr.org/2004/102.pdf.

[18] ABE M,OKAMOTO T.A signature scheme with message recovery as secure as discrete logarithm[J].IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences,2001,84(1):197-204.