王 眾,韓益亮

(武警工程大學(xué) 密碼工程學(xué)院,西安 710086)

0 概述

目前,人們的日常生活已經(jīng)離不開(kāi)復(fù)雜網(wǎng)絡(luò)與頻繁通信,在享受網(wǎng)絡(luò)通信帶來(lái)便利的同時(shí),網(wǎng)絡(luò)安全問(wèn)題日益突出,如何保障用戶的隱私、所發(fā)送信息的不可否認(rèn)性以及通信過(guò)程的安全性成為網(wǎng)絡(luò)通信領(lǐng)域的研究重點(diǎn)。密碼學(xué)中的簽密技術(shù)[1]可以提供簽名以及加密的功能,其原理是在簽密時(shí)用發(fā)送方的私鑰進(jìn)行簽名,用接收方的公鑰進(jìn)行加密,解簽密時(shí)用發(fā)送方的公鑰進(jìn)行簽名驗(yàn)證以保證信息的不可否認(rèn)性,用接收方的私鑰進(jìn)行解密以保證信息的機(jī)密性。雖然簽密技術(shù)能夠在一個(gè)邏輯步驟內(nèi)完成簽名與加密,為信息提供良好的安全保護(hù),但是,隨著量子技術(shù)的發(fā)展以及量子計(jì)算機(jī)研究的不斷推進(jìn),基于經(jīng)典數(shù)論問(wèn)題的公鑰密碼方案,如RSA公鑰加密算法、橢圓曲線密碼(Elliptic Curves Cryptography,ECC)和屬性基密碼等,未來(lái)將無(wú)法再為復(fù)雜龐大的網(wǎng)絡(luò)通信提供可靠的安全保證。

近年來(lái),量子技術(shù)在密鑰安全領(lǐng)域得到應(yīng)用[2]。現(xiàn)有能夠抵御量子計(jì)算攻擊的密碼體制有基于編碼的密碼體制[3]、基于格的密碼體制LWE(Learning With Errors)[4]、基于Hash函數(shù)的密碼體制[5]以及基于多變量的密碼體制[6]。上述密碼體制均是在困難問(wèn)題的基礎(chǔ)上而建立,量子計(jì)算機(jī)與電子計(jì)算機(jī)在面對(duì)這些問(wèn)題時(shí)都不能在有限的資源條件下將其攻破,因此,這類(lèi)密碼體制可以有效抵抗量子計(jì)算攻擊。其中,基于編碼的密碼體制具有易于操作以及計(jì)算效率較高的特性,因此備受學(xué)者們的青睞,該密碼體制所依賴的困難問(wèn)題是碼字的譯碼問(wèn)題,較早的基于編碼的公鑰密碼算法由文獻(xiàn)[7]所編造,其私鑰主要為一個(gè)二元即約Goppa碼的生成矩陣,相對(duì)應(yīng)的公鑰為該矩陣被隨機(jī)處理之后的矩陣。另外一個(gè)經(jīng)典的編碼密碼算法Niederreiter由文獻(xiàn)[8]提出,該算法為文獻(xiàn)[7]算法的對(duì)偶體制,兩者的安全性完全相同,但Niederreiter算法在傳信率方面具有一定的優(yōu)勢(shì)。截止目前,仍沒(méi)有能夠有效攻擊這2種算法的方法。編碼密碼仍在不斷發(fā)展之中,為了保證編碼密碼的安全性、實(shí)用性并降低方案的密鑰尺寸,由較早的Goppa碼、Reed-Solomon碼[9],到現(xiàn)在的準(zhǔn)循環(huán)中密度奇偶校驗(yàn)(QC-MDPC)碼[10]、低密度奇偶校驗(yàn)(LDPC)碼[11]以及準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(QC-LDPC)碼[12]等,通過(guò)優(yōu)化碼字的選擇來(lái)不斷減少編碼密碼的公鑰量,但是,其安全性并未得到實(shí)質(zhì)上的提升。

雙公鑰加密技術(shù)是公鑰加密算法中有效提高算法安全性的手段之一,有較多學(xué)者將編碼密碼與雙公鑰加密思想相結(jié)合。文獻(xiàn)[13]利用雙公鑰對(duì)文獻(xiàn)[7]算法進(jìn)行改進(jìn),安全性有較好的提升,但是其通過(guò)雙公鑰的方式加密,增加了密鑰量,實(shí)用性不高。文獻(xiàn)[14]提出基于QC-LDPC碼的雙公鑰Niederreiter密碼方案,由于采用了QC-LDPC碼,使得雙公鑰方案的密鑰量有所下降,安全性有較高提升,但是,該方案的密鑰量和安全性仍有較大的提升空間。文獻(xiàn)[15]提出基于改進(jìn)Niederreiter密碼體制的雙公鑰加密方案,該方案可以有效抵抗ISD攻擊并采用雙公鑰加密的方式進(jìn)一步提升安全性,但采用系統(tǒng)碼避免雙公鑰加密的方式降低了運(yùn)行效率。本文通過(guò)對(duì)Xinmei簽名方案[16]與基于改進(jìn)Niederreiter密碼的雙公鑰加密方案進(jìn)行研究,提出一種抗量子簽密方案,通過(guò)采用系統(tǒng)碼的方式在增加方案安全性的同時(shí)保證其有效性與實(shí)用性。

1 相關(guān)知識(shí)

1.1 SDP問(wèn)題

1.2 基于改進(jìn)Niederreiter的雙公鑰加密方案

王眾等提出的基于改進(jìn)Niederreiter的雙公鑰加密方案[15],在第2步加密時(shí)對(duì)錯(cuò)誤向量e的重量進(jìn)行了隱藏,使得該方案可以較好地抵抗ISD攻擊,且其采用雙公鑰的加密方式提高了安全性。該方案具體步驟如下:

3)解密過(guò)程。當(dāng)接收者收到密文(x1,x2,x3)后,進(jìn)行以下解密操作:

(1)運(yùn)用私鑰A、B、C、Q以及譯碼算法β2Ht(),進(jìn)行第1步解密:

(1)

(2)

(3)

(2)完成第1步解密得到c1后,第2步解密就是普通的Niederreiter密碼體制的譯碼解密。運(yùn)用私鑰S、T和碼G1的譯碼算法β1Ht()進(jìn)行解密,具體如下:

(4)

1.3 Xinmei簽名方案修正

王新梅教授于1990年在編碼密碼的基礎(chǔ)上提出Xinmei簽名方案[16],隨后又有許多學(xué)者提出了對(duì)該方案的攻擊以及改進(jìn)方法,王新梅根據(jù)這些攻擊方法在2000年提出了針對(duì)Xinmei簽名方案的修正版[18],以使其可以對(duì)選擇性明文攻擊(簡(jiǎn)稱(chēng)AW攻擊)等進(jìn)行有效的防御。

設(shè)用戶在有限域GFq上選擇一個(gè)(n,k,t)二元即約Goppa碼,該碼的校驗(yàn)矩陣H的維度為(n-k)×n,生成矩陣G為k×n維,其中,t代表錯(cuò)誤向量所允許的最大譯碼漢明重量。用戶再選擇2個(gè)可逆置換矩陣P與T,其中,P為k×k維,T為n×n維。Xinmei簽名方案修正版的具體過(guò)程如下:

2)簽名過(guò)程。待簽名信息為kbit的向量m,隨機(jī)生成一個(gè)nbit的向量z,z的漢明重量滿足wt(z)≤t,h為Hash函數(shù),發(fā)送方進(jìn)行如下簽名:

E(m)=(z+h(z,m)PG)T=c

(5)

簽名后產(chǎn)生簽密文c,并將(m,c)發(fā)送給接收方。

3)解簽名過(guò)程。當(dāng)接收方收到(m,c)后,進(jìn)行如下的簽名驗(yàn)證過(guò)程:

(1)右乘公鑰矩陣V:

D1(c)=cV=[(z+h(z,m)PG)T]T-1HT=

zT-1HT

(6)

(2)運(yùn)用譯碼算法Y對(duì)D1(c)進(jìn)行譯碼得到z。需要注意的是,若wt(z)>t,則說(shuō)明傳輸過(guò)程有誤,無(wú)法正確譯碼,需要發(fā)送方重新發(fā)送。

(3)右乘公鑰矩陣J:

(7)

(4)根據(jù)上述結(jié)果再進(jìn)行如下運(yùn)算:

D3(c)=D2(c)+zW=h(z,m)°

(8)

當(dāng)且僅當(dāng)h(z,m)°=h(z,m)時(shí),簽名驗(yàn)證過(guò)程成功。

1.4 安全模型

根據(jù)文獻(xiàn)[19-20],本文提出基于編碼密碼的簽密方案的安全模型。

定義2若在下述機(jī)密性游戲中,攻擊者在任何多項(xiàng)式時(shí)間中贏得游戲的優(yōu)勢(shì)是可以忽略的,則說(shuō)明該簽密方案滿足選擇明文攻擊下的不可區(qū)分性,也即IND-CPA安全。

設(shè)多項(xiàng)式時(shí)間內(nèi)的攻擊者為α,α贏得下述游戲的優(yōu)勢(shì)為Advα,該機(jī)密性攻擊游戲包括以下步驟:

1)挑戰(zhàn)者選擇合適參數(shù)并運(yùn)行系統(tǒng),產(chǎn)生發(fā)送者以及接收者的公私鑰對(duì)(pkS,skS)、(pkR,skR),然后將發(fā)送方與接收方的公鑰(pkS,pkR)以及發(fā)送方的私鑰skS發(fā)送給攻擊者α。

2)攻擊者產(chǎn)生2個(gè)明文(m0,m1),并將該明文對(duì)以及公鑰對(duì)(pkS,pkR)發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者投擲一枚均勻的硬幣,選擇(m0,m1)中的一個(gè)mb,將公鑰對(duì)(pkS,pkR)與mb發(fā)送給簽密預(yù)言機(jī),簽密預(yù)言機(jī)將產(chǎn)生的簽密文返回給挑戰(zhàn)者,由挑戰(zhàn)者返回至攻擊者α。

3)攻擊者收到返回的簽密文后,輸出1 bit 的b1。當(dāng)b=b1時(shí),攻擊者α贏得游戲,該獲勝優(yōu)勢(shì)定義為:

(9)

定義3若在下述不可偽造性攻擊游戲中,攻擊者在任何多項(xiàng)式時(shí)間中贏得游戲的優(yōu)勢(shì)是可以忽略不計(jì)的,則說(shuō)明本文簽密方案在適應(yīng)性選擇消息攻擊下滿足不可偽造性安全,也即EUF-CMA安全。

設(shè)多項(xiàng)式時(shí)間內(nèi)的攻擊者為η,η贏得下述游戲的優(yōu)勢(shì)為Advη,該不可偽造性游戲包括以下步驟:

1)挑戰(zhàn)者選擇參數(shù)并運(yùn)行系統(tǒng),產(chǎn)生發(fā)送者S以及接收者R的公私鑰對(duì)(pkS,skS)、(pkR,skR),然后將接收方的(pkR,skR)與pkS發(fā)送給攻擊者η,并把發(fā)送者的公私鑰對(duì)(pkS,skS)發(fā)送給簽密預(yù)言機(jī)。

2)攻擊者可進(jìn)行簽密詢問(wèn),并驗(yàn)證簽密文的合法性。

3)攻擊者提交挑戰(zhàn)信息m以及偽造的簽密文n,并把接收方與發(fā)送方的公鑰對(duì)(pkS,pkR)提交給挑戰(zhàn)者,攻擊者提交信息(m,n,pkS,pkR)給挑戰(zhàn)者。挑戰(zhàn)者知道發(fā)送方的私鑰skS,對(duì)簽密文n進(jìn)行解簽密運(yùn)算,產(chǎn)生明文m。針對(duì)m,若攻擊者之前未對(duì)其進(jìn)行過(guò)簽密詢問(wèn),則說(shuō)明攻擊者挑戰(zhàn)成功,對(duì)明文進(jìn)行了偽造。

攻擊者η的優(yōu)勢(shì)可以表示如下:

pkR,m),skR,pkS)]

(10)

2 基于改進(jìn)Niederreiter雙公鑰加密的簽密方案

2.1 簽密方案構(gòu)造

本文基于改進(jìn)Niederreiter雙公鑰加密方案與Xinmei簽名方案修正版進(jìn)行簽密方案構(gòu)造,具體的參數(shù)選擇、公私鑰生成以及簽密解簽密過(guò)程如下:

(2)c=(z+f(r||m)PAG1A)TA。

(3)FB·c→(x1,x2,x3)。

(4)Output (x1,x2,x3)。

3)解簽密過(guò)程,具體計(jì)算如下:

(3)Y(D1(c),t1)→z

Whilewt(z)≤t1continue

Else Receive error occurred,sender A resend

(5)D3(c)=D2(c)+zW=f(r||m)。

Outputm。

Else output⊥。

2.2 正確性分析

當(dāng)接收者收到簽密文(x1,x2,x3)后,首先需要使用自己的私鑰對(duì)其進(jìn)行解密,解密成功后得到向量c,由簽密步驟2可知,c的產(chǎn)生是由Xinmei簽名算法對(duì)函數(shù)f的結(jié)果f(r||m)進(jìn)行簽名所得,其中,隨機(jī)向量z是由隨機(jī)向量r和明文m通過(guò)安全Hash函數(shù)所產(chǎn)生。

3 安全性分析

3.1 不可偽造性

Pr[B]=Pr[X1∩X2∩X3]≤1/(qf+qSC+qH)·

(11)

其中,qSC、qDSC、qH、qf分別代表攻擊者η所能進(jìn)行的簽密詢問(wèn)、解簽密詢問(wèn)以及對(duì)預(yù)言機(jī)H和f詢問(wèn)的最大次數(shù),分別設(shè)立4個(gè)詢問(wèn)列表Hlist、flist、SClist、DSClist來(lái)對(duì)詢問(wèn)進(jìn)行記錄。

1)預(yù)言機(jī)H詢問(wèn)。攻擊者η進(jìn)行H詢問(wèn),向H預(yù)言機(jī)中輸入r||m,首先查詢表中是否有相應(yīng)記錄,存在記錄則返回給攻擊者;不存在則生成z,將其記錄在表Hlist中并返回給攻擊者。

2)預(yù)言機(jī)f詢問(wèn)。攻擊者η進(jìn)行f詢問(wèn),向f預(yù)言機(jī)中輸入r||m,首先查詢表中是否有相應(yīng)記錄,存在記錄則返回給攻擊者;不存在則生成v,將其記錄在表flist中并返回給攻擊者。

4)解簽密詢問(wèn)(DSC)。向解簽密預(yù)言機(jī)進(jìn)行詢問(wèn)時(shí),輸入簽密文n,首先查看表DSClist中是否有相應(yīng)記錄m,若存在則返回給詢問(wèn)者,否則執(zhí)行解簽密算法得到r,通過(guò)r的值,在表Hlist、flist中進(jìn)行查詢得到明文m。

不可偽造性攻擊游戲的過(guò)程如下:

1)運(yùn)行簽密系統(tǒng),生成必要參數(shù)。

2)攻擊者進(jìn)行預(yù)言機(jī)H詢問(wèn)和預(yù)言機(jī)f詢問(wèn)。

3)攻擊者提交明文m與偽造的簽密文n,并對(duì)n進(jìn)行解簽密詢問(wèn),若詢問(wèn)返回結(jié)果為m,并且沒(méi)有對(duì)其進(jìn)行過(guò)簽密詢問(wèn),則說(shuō)明攻擊者成功贏得游戲。

證明在簽密詢問(wèn)時(shí),首先查詢表SClist中是否有相應(yīng)記錄,若存在相應(yīng)記錄則返回給詢問(wèn)者,否則需要產(chǎn)生對(duì)應(yīng)的結(jié)果。在沒(méi)有記錄的情況下,要調(diào)用預(yù)言機(jī)H與f來(lái)產(chǎn)生相應(yīng)的z與v的值,若H與f中已經(jīng)存在對(duì)應(yīng)于m的z或v的值,則說(shuō)明模擬過(guò)程失敗,需要預(yù)言機(jī)SC、H與f對(duì)同一明文進(jìn)行成功的詢問(wèn),這樣才能完成簽密詢問(wèn),將此記為事件X1,其發(fā)生的概率為:

Pr[X1]=1/(qf+qSC+qH)

(12)

在解簽密時(shí),輸入簽密文n,首先查看表DSClist中是否有相應(yīng)記錄m,若存在則返回給詢問(wèn)者,不存在則執(zhí)行解簽密算法得到r,由r的值在表Hlist、flist中進(jìn)行查詢找到相應(yīng)的明文m,若沒(méi)有相應(yīng)的記錄,則說(shuō)明模擬失敗。將通過(guò)r的值可在表Hlist、flist中進(jìn)行查詢找到明文m記為事件X2,其發(fā)生的概率為:

Pr[X2]=(qH/22n)·(qf/22n)=(qH·qf)/22n

(13)

(14)

由上述分析可知,攻擊算法B需要在以上3個(gè)相互獨(dú)立的事件都成立的前提下才可以成功,其優(yōu)勢(shì)表示如下:

Pr[B]=Pr[X1∩X2∩X3]≤1/(qf+qSC+qH)·

綜上,本文簽密方案滿足EUF-CMA安全。

3.2 機(jī)密性

證明將本文簽密方案所涉及的SDP問(wèn)題實(shí)例交由攻擊算法K嘗試解決,攻擊算法K作為攻擊者α在游戲中的挑戰(zhàn)者,而α作為攻擊算法K的子程序。具體步驟如下:

1)攻擊算法B得到SDP問(wèn)題實(shí)例中發(fā)送方以及接收方的公私鑰對(duì)(pkS,skS)、(pkR,skR),然后將發(fā)送方與接收方的公鑰(pkS,pkR)以及發(fā)送方的私鑰skS發(fā)送給攻擊者α。

2)攻擊者產(chǎn)生2個(gè)明文(m0,m1),并將該明文對(duì)以及公鑰對(duì)(pkS,pkR)發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者投擲一枚均勻的硬幣,選擇(m0,m1)中的一個(gè)mb,將公鑰對(duì)(pkS,pkR)與mb發(fā)送給簽密預(yù)言機(jī),簽密預(yù)言機(jī)將產(chǎn)生的簽密文返回給挑戰(zhàn)者,由挑戰(zhàn)者返回至攻擊者α。

3)攻擊者收到返回的簽密文后,輸出1 bit 的b1作為猜測(cè)。

(15)

因此,本文簽密方案滿足IND-CPA安全。

3.3 相關(guān)攻擊分析

針對(duì)編碼密碼體制,目前較為有效的攻擊手段包括直接譯碼攻擊和信息集譯碼攻擊(ISD)等。

本文簽密方案采用基于改進(jìn)Niederreiter的雙公鑰加密方案實(shí)現(xiàn)加密功能,在機(jī)密性上能夠?yàn)楹灻芊桨柑峁┹^好的保障。

4 效率分析

4.1 加密方案優(yōu)勢(shì)

本文簽密方案通過(guò)基于改進(jìn)Niederreiter的雙公鑰加密方案實(shí)現(xiàn)加密功能,其采用系統(tǒng)碼進(jìn)行構(gòu)造,以雙公鑰加密方式進(jìn)行加密,密鑰量會(huì)有所增加但仍在可接受的范圍內(nèi),安全性得到較大提升。將文獻(xiàn)[14-15]中的2種方案進(jìn)行比較,結(jié)果如表1所示?；诟倪M(jìn)Niederreiter的雙公鑰加密方案在第2步加密時(shí)采用了改進(jìn)版Niederreiter方法,對(duì)重量t有隱藏功能,允許其選擇維度較小的碼字而達(dá)到與普通Niederreiter同樣的安全級(jí)別。

表1 文獻(xiàn)[14-15]方案中的第2步加密密鑰尺寸對(duì)比

從表1可以看出,在達(dá)到282bit安全級(jí)別時(shí),文獻(xiàn)[14]方案的密鑰尺寸為20 904 bit,而文獻(xiàn)[15]方案為5 040 bit,密鑰尺寸有明顯下降,在2128bit安全級(jí)別下兩者具有同樣的效果,即隱藏重量t能夠顯著提升本文簽密方案的效率。

4.2 密鑰與密文量分析

在有限域GFq上選取二元系統(tǒng)碼G1、G2,維度分別為(120,40)、(80,40),進(jìn)行如表2所示的對(duì)比。由表2可以看出,本文簽密方案在私鑰量與密文量方面相比先簽名后加密的方法有較大的提升。私鑰量下降是因?yàn)樵诤灻芊桨笜?gòu)造時(shí),其中n×n維的矩陣T在簽名以及加密中共用,從而減少了一個(gè)n×n維的矩陣,也即14 400 bit的私鑰量。在密文量方面,先簽名后加密或者先加密后簽名的方法會(huì)產(chǎn)生簽名以及密文,而本文簽密方案是對(duì)簽名進(jìn)行加密,只有對(duì)簽名進(jìn)行正確驗(yàn)證后才可以得到相應(yīng)的明文信息,簽密方案的簽密文即對(duì)簽名進(jìn)行加密后的密文(x1,x2,x3),由1.2節(jié)對(duì)加密方案的描述可知該簽密文的大小為120 bit,即本文方法的密文量相比先簽名后加密的方法減少了50%。

表2 4種方案的密鑰與密文分析

Table 2 Key and ciphertext analysis of four schemes bit

方案公鑰量私鑰量密文量文獻(xiàn)[15]方案1120032000120Xinmei簽名方案1600019200120先簽名后加密方案2720051200240本文簽密方案2720036800120

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

本文通過(guò)對(duì)Niederreiter密碼體制進(jìn)行研究,采用基于改進(jìn)Niederreiter的雙公鑰加密方案來(lái)構(gòu)造抗量子簽密方案。相比改進(jìn)Niederreiter方案以及基于QC-LDPC碼的雙公鑰Niederreiter密碼方案,該加密方案在安全性方面得到較大的提升,且其采用系統(tǒng)碼來(lái)保證雙公鑰的加密方式不會(huì)帶來(lái)過(guò)大的密鑰量。在此基礎(chǔ)上,本文將基于改進(jìn)Niederreiter的雙公鑰加密方案與Xinmei簽名方案相結(jié)合,提出一種基于編碼密碼的簽密方案。分析結(jié)果表明,該方案能夠滿足EUF-CMA與IND-CPA安全,相比先簽名后加密或者先加密后簽名的方案,其私鑰量和密文量均較低,在后量子時(shí)代具有良好的使用前景。下一步嘗試在該簽密方案中增加如混合簽密、代碼簽密等功能,以適應(yīng)更加復(fù)雜的網(wǎng)絡(luò)環(huán)境。