趙宗渠,黃鸝娟,范 濤,馬少提

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 概述

認(rèn)證密鑰交換(Authenticated Key Exchange,AKE)協(xié)議可使通信方在有主動敵手的信道上建立安全的共享會話密鑰,同時(shí)實(shí)現(xiàn)彼此身份的相互認(rèn)證,在后續(xù)的對稱密碼中能夠保證數(shù)據(jù)的完整性和真實(shí)性。目前多數(shù)AKE協(xié)議的安全性依賴于大整數(shù)分解和離散對數(shù)的Diffie-Hellman[1]困難問題,隨著量子計(jì)算技術(shù)的發(fā)展,此類問題在多項(xiàng)式時(shí)間算法下是可解的,這將給現(xiàn)有協(xié)議帶來安全威脅。格上構(gòu)造的公鑰密碼體制因其運(yùn)算簡單、可并行性和抗量子攻擊的優(yōu)點(diǎn),將在后量子時(shí)代成為最有效的解決方案之一,基于格的AKE協(xié)議因此成為學(xué)術(shù)界的研究熱點(diǎn)。

基于格的AKE協(xié)議[2-4]可以抵抗量子攻擊,解決經(jīng)典困難問題下協(xié)議的安全性問題,但不能降低通信復(fù)雜度并實(shí)現(xiàn)認(rèn)證。文獻(xiàn)[5]在標(biāo)準(zhǔn)模型下構(gòu)造高效的口令認(rèn)證密鑰交換協(xié)議,但該協(xié)議不能抵抗量子攻擊。文獻(xiàn)[6]基于LWE構(gòu)造了無環(huán)密鑰交換協(xié)議,雖然該協(xié)議可以抵抗量子攻擊,但無法實(shí)現(xiàn)客戶和服務(wù)器的相互認(rèn)證。文獻(xiàn)[7]提出一個(gè)基于理想格的密鑰交換協(xié)議,使通信方以顯著概率計(jì)算得到一個(gè)相同的會話密鑰,然而該協(xié)議提取的會話密鑰只具有高熵,并不是均勻分布的,雖然通信方可以利用隨機(jī)提取器得到均勻分布的共同比特,但這會降低協(xié)議的效率。文獻(xiàn)[8]提出一種基于理想格的密鑰封裝機(jī)制(Key Encapsulation Mechanism,KEM),文獻(xiàn)[9]在此基礎(chǔ)上結(jié)合一種簡單的低帶寬協(xié)調(diào)技術(shù)提出一種變形的錯(cuò)誤協(xié)調(diào)機(jī)制,結(jié)合環(huán)LWE困難問題構(gòu)造密鑰交換協(xié)議,使加密方案的密文長度縮短了近兩倍,通信方可以直接得到均勻的共同比特。

文獻(xiàn)[10]結(jié)合Peikert式錯(cuò)誤協(xié)調(diào)機(jī)制構(gòu)造了適用于TLS協(xié)議的Diffie-Hellman式密鑰交換協(xié)議,并給出具體的實(shí)現(xiàn)參數(shù),其中會話密鑰能達(dá)到較高的量子安全級別,但錯(cuò)誤協(xié)調(diào)機(jī)制模數(shù)較大,使得通信量較大,降低了協(xié)議的效率。文獻(xiàn)[11]基于R-LWE困難問題,利用格解碼算法結(jié)合中心二項(xiàng)分布提出了NewHope密鑰交換協(xié)議,優(yōu)化了文獻(xiàn)[10]的密鑰交換協(xié)議,擴(kuò)大了可容忍的錯(cuò)誤范圍,減少了模數(shù),節(jié)省了通信量。文獻(xiàn)[12]提出的NewHopeSimple方案,使用加密的構(gòu)造方法代替調(diào)和技術(shù),降低了協(xié)議的計(jì)算復(fù)雜度。文獻(xiàn)[13]基于加密的構(gòu)造方法提出抗選擇密文攻擊安全的Kyber系列密鑰封裝算法,其采用密鑰壓縮技術(shù)對需要發(fā)送的公鑰和密文進(jìn)行壓縮,降低了通信量。

隨著格密碼的快速發(fā)展,密鑰交換協(xié)議的效率已得到大幅提高,但目前多數(shù)協(xié)議都是Diffie-Hellman式密鑰交換協(xié)議[7,10,14-16],只能提供被動安全性,不能實(shí)現(xiàn)相互認(rèn)證,也不能抵抗中間人攻擊,而實(shí)際應(yīng)用中必須要考慮網(wǎng)絡(luò)上的主動攻擊者。因此,構(gòu)造認(rèn)證密鑰交換協(xié)議來抵御主動攻擊是研究趨勢所向,而基于KEM方案構(gòu)造認(rèn)證密鑰交換協(xié)議是一種可行的方法。

文獻(xiàn)[17]在NTRU格Diffie-Hellman式密鑰交換協(xié)議的基礎(chǔ)上,結(jié)合帶消息恢復(fù)功能的簽名算法與KEM方案實(shí)現(xiàn)協(xié)議的認(rèn)證性。與傳統(tǒng)簽名算法相比,該方案既增加了安全性又提高了通信效率。文獻(xiàn)[18]將具有CCA安全和CPA安全的KEM方案相結(jié)合,提出了適用于格的可認(rèn)證密鑰交換協(xié)議的通用架構(gòu),即GC協(xié)議,其將KEM方案作為基本的設(shè)計(jì)原語,在CK+模型下是可證明安全的。文獻(xiàn)[19]提出的CCA安全的密鑰封裝機(jī)制,可由基本的CPA安全的密鑰封裝機(jī)制獲得,使用這一方法,Kyber構(gòu)造了具有認(rèn)證性的密鑰交換協(xié)議Kyber.AKE。文獻(xiàn)[20]設(shè)計(jì)了格上基于R-LWE的三方PAKE協(xié)議,實(shí)現(xiàn)了通信方的顯式認(rèn)證,可避免兩方認(rèn)證密鑰交換協(xié)議的局限性,但該協(xié)議存在會話密鑰的不一致性問題。

為實(shí)現(xiàn)Diffie-Hellman式密鑰交換協(xié)議的認(rèn)證性并使其能夠抵抗量子攻擊,本文結(jié)合帶消息恢復(fù)功能的簽名算法,基于R-LWE構(gòu)造一個(gè)KEM方案。在協(xié)議執(zhí)行時(shí)采樣隨機(jī)種子生成協(xié)議雙方的公共參數(shù),防止攻擊者利用固定公共參數(shù)攻擊協(xié)議,以保證前向安全性。發(fā)送方選擇定比特長的隨機(jī)字符串,每4個(gè)元素使用Encode函數(shù)[12]編碼其中的一個(gè)比特,編碼后的環(huán)元素可容忍更大的錯(cuò)誤,從而降低模數(shù),縮減通信量。此外,在保證密文恢復(fù)完整性的前提下對密文元素使用Compress壓縮函數(shù)進(jìn)行壓縮,減輕服務(wù)器的傳輸負(fù)荷,同時(shí)利用帶有消息恢復(fù)功能的簽名算法實(shí)現(xiàn)協(xié)議的認(rèn)證性。

1 相關(guān)知識

1.1 密文壓縮算法

密文壓縮技術(shù)是減少用戶通信量的有效方法,其對密文元素進(jìn)行壓縮,丟掉密文元素的低位比特,即部分噪音信息。在保證密文恢復(fù)完整性的前提下,有效減少通信量,減輕服務(wù)器的傳輸負(fù)荷。將密文元素從q映射到2d上,其中d

定義1一個(gè)密文壓縮算法包括2個(gè)多項(xiàng)式時(shí)間算法,即壓縮算法Compressq(x,d)和解壓縮算法Decompressq(x,d)。

1)壓縮函數(shù):

Compressq(x,d)=?(2d/q)·x」mod+2d

2)解壓縮函數(shù):

Decompressq(c,d)=「(q/2d)·c?

1.2 帶消息恢復(fù)的簽名算法

文獻(xiàn)[14]提出帶消息恢復(fù)的簽名算法,其中每一個(gè)用戶都有一對密鑰,即一個(gè)需要公開的公鑰和一個(gè)需要秘密保存的私鑰。當(dāng)用戶需要對某個(gè)消息m進(jìn)行簽名產(chǎn)生對應(yīng)的數(shù)字簽名Sig時(shí),即需要使用自己的私鑰和消息m=(m1‖m2)進(jìn)行簽名運(yùn)算,運(yùn)算結(jié)果就是簽名值。簽名值只需要消息m中的部分消息m2表示。任何人都可以使用該用戶的公鑰來恢復(fù)消息和驗(yàn)證簽名是否正確,并且沒有人能夠在用戶私鑰未知的前提下偽造出一個(gè)合法的消息簽名對。此算法可解決簽名消息過長的問題。

定義21個(gè)帶消息恢復(fù)的簽名算法包括3個(gè)多項(xiàng)式時(shí)間算法,即簽名密鑰生成算法SigKeyGen(1λ)、簽名算法Sig((f,g),m=(m1‖m2))和驗(yàn)證算法Ver(h,σ=(s1,s2,m2))。

1)簽名密鑰生成算法SigKeyGen(1λ):{f,g←Df,h←f/gmodq}得到(Ks,Kv)=(g,h)。

2)簽名算法Sig((f,g),m=(m1‖m2)):{t=(m1+F(H′(m)) modq‖H′(m))s1,s2←Ds滿足(f/g)s1+s2=tmodq,得到σ=(s1,s2,m2)。

3)驗(yàn)證算法Ver(h,σ=(s1,s2,m2)):(t1‖t2)←hs1+s2modq,m1←t1-F(t2)modq,若(s1,s2)‖

1.3 Encode函數(shù)與Decode函數(shù)

定義3[10]用戶A選取v∈{0,1}n環(huán)元素k,即每4個(gè)q元素中編碼v的一個(gè)比特,用戶B根據(jù)收到的k′,取在{0,1,…,q-1}范圍中的4個(gè)系數(shù)減去?q/2」,累積它們的絕對值,若得到的結(jié)果小于q則vi取1,否則取0?？扇萑谈蟮腻e(cuò)誤,從而降低了模數(shù),縮減了通信量。Encode函數(shù)和Decode函數(shù)的具體描述如下:

Encode(v∈{0,1}n)

輸入k

對于i從0到n-1循環(huán)執(zhí)行:

ki←vi·?q/2」;

ki+n←vi·?q/2」;

ki+2n←vi·?q/2」;

輸出k

輸入k′,對于i從0到n-1循環(huán)執(zhí)行:

若t

否則k′i←0;

輸出k′

1.4 AKE協(xié)議安全模型

模型中會話密鑰的安全性通過模擬者和攻擊者之間的游戲定義。首先攻擊者A選擇一定數(shù)量的誠實(shí)參與者,通過提供攻擊者以下查詢來建模攻擊者的能力:

3)Corrupt(i)。攻擊者A通過此查詢來腐化參與者i。要求被詢問的協(xié)議參與者返回參與者i的長期私鑰,同時(shí)稱參與者i被腐化(Corrupted)。

通過模擬一個(gè)挑戰(zhàn)者與攻擊者之間的游戲定義AKE協(xié)議的安全性。游戲分為以下4個(gè)階段:

第1階段攻擊者A可以進(jìn)行任意除Test以外的查詢,預(yù)言機(jī)并給出相應(yīng)答案。

第4階段攻擊者A結(jié)束游戲,輸出猜測值b′。

對于任意攻擊者A,如果A贏得上述游戲的優(yōu)勢AdvA=|2Pr[b′=b]-1|是可忽略的,則稱該認(rèn)證密鑰協(xié)商協(xié)議是安全的。

2 算法設(shè)計(jì)及方案構(gòu)造

認(rèn)證密鑰交換協(xié)議包括2個(gè)階段,即系統(tǒng)建立階段Setup和會話密鑰的協(xié)商階段KeyExchange。

2.1 系統(tǒng)建立階段

H1和H2分別是在{0,1}l1和{0,1}l2上的抗碰撞哈希函數(shù),通信雙方分別使用帶消息恢復(fù)功能的簽名算法,選取{f,g←Df,h←f/gmodq},生成自己的簽名密鑰對:

SigKeyGen(1λ)→(KSA,KVA)=(gA,hA)

SigKeyGen(1λ)→(KSB,KVB)=(gB,hB)

2.2 會話密鑰的協(xié)商階段

用戶UA和用戶UB通過交換公共信息來協(xié)商出一個(gè)共享的會話密鑰,具體過程如下:

若按照上述協(xié)議執(zhí)行,最終交易雙方得到相同的會話密鑰,即SKA=SKB,具體的交換過程如圖1所示。

圖1 格上基于KEM的AKE協(xié)議交換過程

3 安全性分析

3.1 正確性證明

若用戶UA和用戶UB誠實(shí)地運(yùn)行協(xié)議,那么雙方獲得相同的密鑰SKA=SKB成立。

3.2 安全性證明

證明:通過一系列得模擬游戲,證明通信內(nèi)容不會泄露秘密的信息,并證明通信雙方交換的密鑰與隨機(jī)數(shù)不可區(qū)分。設(shè)sid*表示測試會話標(biāo)示符,攻擊者A嘗試區(qū)分會話密鑰SK和均勻隨機(jī)密鑰SK′,定義攻擊者A贏得游戲的優(yōu)勢為:

Adv(A)=|Pr[b′=1|b=1]-Pr[b′=1|b=0]|

在簽名方案的強(qiáng)不可偽造性下,此修改不會改變攻擊者A的優(yōu)勢。一旦偽造文件被發(fā)現(xiàn),不需要運(yùn)行完整個(gè)協(xié)議,簽名方案立即被破壞。同時(shí),c的分布與其他一般分布不可區(qū)分,所以,猜測出c=bs′b+e″b+a×k的概率可以忽略。因?yàn)閏=a(sas′b+k)+e″b+ea,根據(jù)引理2可知,sas′b+k的分布與χα的分布小于4ε,基本可以忽略,則游戲G1中c的分布接近游戲G0中c的分布,即A無法區(qū)分。若RLWEq,χ是困難問題,則:

|AdvG1(A)-AdvG0(A)|≤negl(n)

定義標(biāo)記CorrectGuess來表示是否sk→⊥解密失敗或者sk1←sk2解密成功,模擬器P不會顯式地計(jì)算CorrectGuess的值。有:

標(biāo)記CorrectGuess對游戲G5的比特b′無影響,這兩個(gè)事件是獨(dú)立的:AdvG5(A)=AdvG4(A)/2。

在最后的游戲中,測試會話的會話密鑰是真實(shí)隨機(jī)的,因此與隨機(jī)的情況沒有區(qū)別:AdvG7(A)=0。

通過以上游戲,可知攻擊者A的優(yōu)勢是可忽略的。證畢。

4 性能分析

本節(jié)對所提出的格上基于KEM的認(rèn)證密鑰交換協(xié)議方案進(jìn)行性能分析,性能主要體現(xiàn)在3個(gè)方面:

1)發(fā)送方選擇定比特長的隨機(jī)字符串,將這個(gè)隨機(jī)字符串中每4個(gè)元素使用Encode函數(shù)編碼其中的一個(gè)比特,編碼后的環(huán)元素可容忍更大的錯(cuò)誤,從而降低了模數(shù),縮減了通信量。

2)使用Compress壓縮函數(shù),對密文元素進(jìn)行壓縮,在保證密文恢復(fù)完整性的前提下,有效減少通信量,減輕服務(wù)器的傳輸負(fù)荷。 3)利用帶消息恢復(fù)功能的簽名算法,對方案中發(fā)送消息進(jìn)行簽名,在發(fā)送的過程中,用戶雙方只需要發(fā)送消息的部分值,有效降低了傳輸過程中的通信量。

表1 AKE協(xié)議效率分析與對比

本文方案和所對比的方案均為標(biāo)準(zhǔn)模型下構(gòu)造。由表1可以看出,在通信量方面,本文方案采用Encode函數(shù)和Compress壓縮函數(shù),大幅縮短了密文的尺寸,有效降低了通信代價(jià),同時(shí)使用帶消息恢復(fù)功能的簽名算法,在保證協(xié)議認(rèn)證性的同時(shí),也降低了通信量,與文獻(xiàn)[10]方案相比,本文協(xié)議不但可實(shí)現(xiàn)相互認(rèn)證,降低了通信量同時(shí)避免使用計(jì)算復(fù)雜的調(diào)和機(jī)制而使用計(jì)算簡單的加密機(jī)制,方案計(jì)算更加簡潔高效。本文協(xié)議的封裝和解封裝采用R-LWE困難假設(shè),與文獻(xiàn)[6]相比,解決了密文尺寸過長的問題。

綜上可知,與同類方案相比,本文方案具有較低的通信量,計(jì)算復(fù)雜度也在可接受范圍內(nèi)。因此,從方案的效率參數(shù)和計(jì)算效率分析,本文協(xié)議更具有實(shí)際應(yīng)用價(jià)值。

5 結(jié)束語

認(rèn)證密鑰交換協(xié)議被廣泛應(yīng)用于互聯(lián)網(wǎng)安全協(xié)議和傳輸層安全協(xié)議中,可有效提高實(shí)體間的通信效率。本文基于R-LWE困難假設(shè),以加密的構(gòu)造方法代替Peikert錯(cuò)誤協(xié)調(diào)機(jī)制,提出一種基于KEM的認(rèn)證密鑰交換協(xié)議。將KEM和帶消息恢復(fù)功能的數(shù)字簽名相結(jié)合,實(shí)現(xiàn)協(xié)議的認(rèn)證性,同時(shí)降低需要發(fā)送的簽名密文長度,大幅減少通信量。利用格上基于R-LWE問題構(gòu)造的密碼系統(tǒng)具有密鑰、密文尺寸小的優(yōu)點(diǎn),可提高AKE協(xié)議效率,并且有效抵抗量子攻擊。本文方案基于R-LWE困難假設(shè)構(gòu)造,而LWE的安全性較R-LWE更為穩(wěn)健,下一步將考慮在維持較低通信量的情況下,基于LWE構(gòu)造強(qiáng)安全的認(rèn)證密鑰交換方案。