基于Niederreiter編碼的混合加密方案的改進(jìn)

劉相信 ，楊曉元

(1.武警工程大學(xué)密碼工程學(xué)院，西安710086; 2.網(wǎng)絡(luò)與信息安全武警部隊重點實驗室，西安710086)(*通信作者電子郵箱1125424226@qq.com)

0 引言

1978年，Berlekamp等［1］證明了隨機(jī)線性碼的譯碼問題是一個非確定性多項式完全(Non-deterministic Polynomial Complete，NPC)問題，為基于糾錯碼的公鑰密碼方案的設(shè)計奠定了理論基礎(chǔ)。同年，McEliece［2］利用此困難問題提出第一個基于Goppa碼的公鑰密碼方案——McEliece公鑰密碼方案;該方案可抗量子攻擊、加解密速度快、實現(xiàn)簡單。方案中錯誤向量的漢明重量固定且公開，導(dǎo)致密文對明文信息的泄露，所以必須選取較大的公鑰尺寸來保證計算安全性，由此導(dǎo)致方案公鑰尺寸過大，實用性差。1986年，Niederreiter［3］對McEliece公鑰密碼方案進(jìn)行了改進(jìn)，提出了一種Niederreiter公鑰密碼方案，該方案從另一個角度利用了隨機(jī)線性碼的譯碼困難問題，McEliece公鑰密碼方案隱藏的是Goppa碼的生成矩陣，該方案隱藏的是Goppa碼的校驗矩陣，此時公鑰尺寸有所變小，但還是沒有達(dá)到實用要求。現(xiàn)有基于編碼的方案沒有改變Niederreiter方案的基本框架，著重在方案的安全性、密鑰量和傳信率之間的平衡作研究，如文獻(xiàn)［4－6］。不可否認(rèn)的是Niederreiter方案并非完美，存在公鑰尺寸大、無法抵抗信息集譯碼攻擊的缺點。

2013 年，Persichetti［7］設(shè)計了第一個基于 Niederreiter編碼的混合加密方案，該方案達(dá)到了選擇密文攻擊不可區(qū)分(INDistinguishability under Chosen Ciphertext Attack，INDCCA)安全，推動了基于編碼的密碼方案實用化，具有重大意義，其缺點是用于加密收發(fā)雙方共享秘密密鑰的公鑰尺寸較大。2016年，von Maurich等［8］利用準(zhǔn)循環(huán)中密度奇偶校驗(Quasi-Cyclic Medium-Density Parity-Check，QC-MDPC)碼的準(zhǔn)循環(huán)的特點，對上述方案進(jìn)行了優(yōu)化，此時的公鑰尺寸也較大，在80比特的安全級下，公鑰為4801比特。在128比特的安全級下，公鑰為9857比特。

現(xiàn)有基于Niederreiter編碼的混合加密方案通過選取較大的公鑰尺寸來保證其安全性，如Maurich方案。本文對Niederreiter編碼方案進(jìn)行了改進(jìn)，使得其能抵抗信息集譯碼攻擊，提高其安全性，以此降低方案的公鑰尺寸。經(jīng)分析，改進(jìn)后的Niederreiter編碼方案可以抵抗信息集譯碼攻擊，改進(jìn)的基于Niederreiter編碼的混合加密方案具有較小的公鑰尺寸。改進(jìn)的基于Niederreiter編碼的混合加密方案的公鑰尺寸小于Maurich方案的公鑰尺寸:在80比特的安全級下，該方案的公鑰從原方案的4801比特降低到240比特;在128比特的安全級下，該方案的公鑰從原方案的9 857比特降低到384比特。其存儲代價和計算代價變小，方案的實用性更強。

1 基礎(chǔ)知識

1.1 編碼理論中的NPC問題

1978年，Berlekamp等［1］證明了陪集重量問題和子空間重量問題是NPC問題，為基于糾錯碼的公鑰密碼方案的設(shè)計奠定了理論基礎(chǔ)。

難題1 陪集重量問題。已知域Fq上一個k×n階矩陣G，k維向量 c=(c1，c2，…，ck) 以及正整數(shù) t，是否存在向量x=(x1，x2，…，xn)，滿足 wt(x) ≤ t，且 c=xGT。

利用隨機(jī)線性碼的校驗矩陣H代替難題1中的矩陣G，則有:

難題2 伴隨子譯碼問題。已知一個(n，k)線性碼的最小距離d，校驗矩陣H，伴隨子s和整數(shù)t，且d=2t+1，是否能在找到漢明重量小于t的錯誤向量e，滿足s=eHT。

1.2 Niederreiter編碼方案

設(shè)(n－k)×n階矩陣H為二元(n，k，d)Goppa碼的校驗矩陣，其中 n=2a，d=2t+1，k=n － at。快速譯碼算法ΨH(t)。

1.2.1 密鑰生成

隨機(jī)選取GF(2)上的(n－k)×(n－k)階可逆矩陣A和n×n階置換矩陣P，計算H'=AHP，將A、H、P作為私鑰保存，H'作為公鑰公開。

1.2.2 加密過程

明文m∈GF(2n)的漢明重量為t。密文:c=mH'T。

1.2.3 解密過程

接收方收到密文 c后，計算 c A－1T=mH'TA－1T=mPTHTATA－1T=mPTHT，利用Goppa碼的快速譯碼算法可得m'=mPT，進(jìn)而得 m=m'(PT)－1。

1.3 信息集譯碼攻擊

信息集譯碼攻擊［9］是對Niederreiter編碼方案最經(jīng)典最有效的攻擊方法，而且這種攻擊方法在不斷地優(yōu)化應(yīng)用［10－15］。目前，現(xiàn)有編碼方案只要選取較大的密鑰尺寸，使得用信息集譯碼攻擊方案的代價達(dá)到280或者2128即認(rèn)為設(shè)計的方案是安全的。攻擊過程如下:

對于明文 m=(m1，m2，…，mn)、方程 c=m1×n，攻擊者刪除m中k個元素，相應(yīng)地刪除HT中的k行，于是有c=m，若可逆，則可求得m=1×(n－k)n－k)×(n－k)1×(n－k)c·(n－k)×(n－k))－1，若此時 wt(c·(n－k)×(n－k))－1) =t，則破譯成功，添加k個零元素即可得明文m。

1.4 基于Niederreiter編碼的混合加密方案

基于Niederreiter編碼的混合加密方案由Persichetti［7］首次提出，該方案具有IND-CCA安全，可以處理任意長度的明文信息，實用性較強。該方案包含兩個部分::

1)密鑰封裝機(jī)制。Bob利用Niederreiter編碼方案產(chǎn)生自己的公鑰;Alice將需要共享的對稱密鑰用Bob公開的公鑰加密，并將其發(fā)送給Bob，Bob收到密文后利用自己的私鑰解密得到共享密鑰。

2)數(shù)據(jù)封裝機(jī)制。Alice和Bob利用共享的對稱密鑰進(jìn)行秘密通信。

2 Niederreiter編碼方案的改進(jìn)

由第1章可知，Niederreiter編碼方案中的錯誤向量e(明文m)的漢明重量固定且公開，而Berlekamp等［1］陳述的隨機(jī)線性碼的譯碼困難問題中e的漢明重量小于等于線性碼的糾錯能力t。很明顯，Niederreiter編碼方案所依賴的困難問題不同于Berlekamp等［1］陳述的隨機(jī)線性碼的譯碼困難問題。

下面對Niederreiter編碼方案進(jìn)行改進(jìn):

設(shè)(n－k)×n階矩陣H為二元(n，k，d)Goppa碼的校驗矩陣，其中 n=2a，d=2t+1，k=n － at。快速譯碼算法ΨH(t)。

2.1 密鑰生成

隨機(jī)將H拆分為兩個矩陣H1和H2，使得H=H1+H2。隨機(jī)產(chǎn)生三個(n－k)×(n－k)階可逆矩陣A、B和C，分別計算 H'=AH1、H″=BH2、H =CH 將(H'，H″，H ，t) 公開，(A－1T，B－1T，C－1T，ΨH(t)) 秘密保存。

2.2 加密過程

明文m是GF(2)上漢明重量為t(t≤J)的n維向量，發(fā)送方隨機(jī)將m拆分成兩個n維向量m1和m2，使得m=m1+m2，且 wt(m1)=t1，wt(m2)=t2，重量關(guān)系 t≠ t1≠ t2。將明文分量 m1用 H'、H″加密產(chǎn)生密文 c1∈、c2∈，明文分量m2用H 加密產(chǎn)生密文c3∈。即密文c1=m1H'T，c2=m1H″T，c3=m2HT，將密文(c1，c2，c3) 發(fā)送給接收方。

2.3 解密過程

當(dāng)接收方收到密文(c1，c2，c3)后，進(jìn)行下列運算:

由于 m=m1+m2、H=H1+H2，此時有 c1A－1T+c2B－1T+c3C－1T=mHT，運行Maurich等［8］優(yōu)化的BF譯碼算法 ΨH(t)對c1A－1T+c2B－1T+c3C－1T進(jìn)行譯碼即可得到明文m。

2.4 安全性分析

本文對Niederreiter編碼方案進(jìn)行了改進(jìn)，將明文進(jìn)行了隨機(jī)拆分，使得明文空間和密文空間隨機(jī)化，實際用于加密的信息的漢明重量t1、t2只有發(fā)送方自己知道，很好地遵從了前文提到的一般線性分組碼的譯碼問題中錯誤向量e的漢明重量未知這個條件(關(guān)于錯誤向量e的漢明重量:伴隨子譯碼問題陳述為wt(e)≤w，本文方案為wt(ei)=?)。同時攻擊者在沒有私鑰的情況下，無法對密文c1、c2和c3進(jìn)行有效的變換組合來獲取有效的信息。此時，攻擊者在沒有t1、t2和私鑰的情況下，無法進(jìn)行有效的破譯分析，從而彌補了現(xiàn)有方案的缺陷。

本方案中m1和m2的漢明重量t1(1≤t1≤n)、t2(1≤t2≤n)只有發(fā)送方自己知道，此時，在密文c1=m1H'T，c2=mH″T，c=mHT已知的情況下，攻擊者無法判定132wt(c·()－1) =t1，2，只能通過窮舉的方法逐一嘗試。由于具有漢明重量ti的n維向量m=(m1，m2，…mn)左乘一個n×(n－k)階矩陣HT，其效果相當(dāng)于在矩陣HT中選取相應(yīng)位置的ti行，故用信息集譯碼攻擊本方案的代價為C1n++ … ++=2n－ 1。

3 Niederreiter編碼的混合加密方案的改進(jìn)

3.1 密鑰封裝機(jī)制

Bob隨機(jī)選取 GF(2) 上的二元(n，r，ν)QC-MDPC 碼，r×n 階校驗矩陣形式為H= ［H0|H1|…|Hn0－1］，行重為ν，糾錯能力為 J，Hi為 r×r階循環(huán)矩陣，n=n0r，譯碼方法為ΨH(t)。隨機(jī)將H拆分為兩個r×n階具有分塊循環(huán)性質(zhì)的矩陣H1和H2，使得H=H1+H2。隨機(jī)產(chǎn)生三個r×r階非奇異循環(huán)矩陣 A、B 和 C，分別計算 H'=AH1、H″=BH2、H =CH。Bob 將(H'，H″，H ，t) 公開，(A－1T，B－1T，C－1T，ΨH(t))秘密保存。

3.1.1 Alice 共享密鑰的產(chǎn)生

Alice隨機(jī)選取的x是GF(2)上漢明重量為t(t≤J)的n維向量，并隨機(jī)將x拆分成兩個n維向量x1和x2，使得x=x1+x2，且 wt(x1)=t1，wt(x2)=t2，重量關(guān)系 t≠ t1≠ t2。將x1用 H'、H″加密產(chǎn)生密文 c1∈、c2∈，x2用H 加密產(chǎn)生密文 c3∈。即密文 c1=x1H'T，c2=x1H″T，c3=x2HT，將密文(c1，c2，c3)發(fā)送給Bob。同時Alice利用SHA-256算法產(chǎn)生共享密鑰，即 k=(k1‖k2)=SHA-256(x)，k1、k2均為128比特。

3.1.2 Bob 共享密鑰的產(chǎn)生

當(dāng) Bob收到密文 (c1，c2，c3) 后，利用自己的私鑰(A－1T，B－1T，C－1T，ΨH(t))，進(jìn)行下列運算:

由于 x=x1+x2、H=H1+H2，此時有 c1A－1T+c2B－1T+c3C－1T=xHT，運行Maurich等［8］優(yōu)化的BF譯碼算法ΨH(t)對c1A－1T+c2B－1T+c3C－1T進(jìn)行譯碼即可得到x。此時 Bob利用SHA-256算法產(chǎn)生共享密鑰，即 k=(k1‖k2)=SHA-256(x)，k1、k2均為128 比特。

3.2 數(shù)據(jù)封裝機(jī)制

3.2.1 Alice 數(shù)據(jù)發(fā)送過程

任意長度數(shù)據(jù)m用密鑰k1在密碼分組鏈接(Cipher-Block Chaining，CBC)模型下用高級加密標(biāo)準(zhǔn)128(Advanced Encryption Standard-128，AES-128)算法加密，即T=AES-128-CBCenc，k1(I，m)，I為初始化隨機(jī)向量。產(chǎn)生數(shù)據(jù) 認(rèn) 證 碼(MessageAuthentication Code，MAC):τ =AES-128-CMACk2(T)。此時Alice發(fā)送給Bob的數(shù)據(jù)包為c=(T‖τ‖I)。

3.2.2 Bob 數(shù)據(jù)接收過程

Bob收到數(shù)據(jù)包c=(T‖τ‖I)時，利用共享密鑰k=(k1‖k2) 計 算 AES-128 CMACk2(T)。 若 此 時AES-128-CMACk2(T)=τ，說明數(shù)據(jù)包正確，進(jìn)而利用k1恢復(fù) 出 數(shù) 據(jù) m = AES-128-CBCdec，k1(I，T)。 若 此 時AES-128-CMACk2(T)≠τ，則丟棄數(shù)據(jù)包。

3.3 性能分析

改進(jìn)的方案沒有改變原方案的框架，保持了原方案的選擇密文攻擊不可區(qū)分(IND-CCA)安全。

Maurich等［8］改進(jìn)的方案公鑰尺寸較大，在80比特的安全級下，公鑰為4 801比特;在128比特的安全級下，公鑰為9857比特。由安全性分析知，利用信息集譯碼攻擊本方案的代價為++…+=2n－1，即:在80比特的安全級下，本方案的n取80即可;在128比特的安全級下本方案的n取128即可;依次類推。由于QC-MDPC碼具有準(zhǔn)循環(huán)的特點，故只需公開公鑰(H'，H″，H ，t)中的首行即可，即本文方案的公鑰尺寸為3n，改進(jìn)方案的密鑰尺寸與Maurich方案［8］的密鑰尺寸比較如表1所示。

表1 本文方案與Maurich方案［8］密鑰尺寸比較 bitTab.1 Comparison of key size between the proposed scheme and Maurich scheme［8］ bit

由改進(jìn)過程可知，在密鑰封裝機(jī)制中，本文方案對產(chǎn)生收發(fā)雙方共享秘密密鑰的隨機(jī)向量x進(jìn)行了拆分，且實施了3次加密操作。雖然密鑰共享的過程比Maurich方案［8］復(fù)雜，但是本文方案的n遠(yuǎn)小于Maurich方案［8］，其存儲代價也遠(yuǎn)小于Maurich方案［8］;由于Niederreiter編碼的實現(xiàn)過程是利用線性移位寄存器來進(jìn)行明文與公鑰的二進(jìn)制加，本方案的n遠(yuǎn)小于Maurich方案［8］，故其計算代價也遠(yuǎn)小于Maurich方案［8］。

4 結(jié)語

基于編碼的公鑰密碼方案作為抗量子方案的備用方案之一，具有較高的安全性和較好的性能，很有可能成為量子計算機(jī)時代下保障數(shù)據(jù)安全的關(guān)鍵技術(shù)。本文在Maurich等［8］改進(jìn)的基礎(chǔ)上，對基于Niederreiter編碼的混合加密方案作了進(jìn)一步的改進(jìn)，保持了Maurich方案［8］的選擇密文攻擊不可區(qū)分(IND-CCA)安全，降低了方案的密鑰尺寸，使其更加實用。下一個研究目標(biāo)是在不同的應(yīng)用場景下來考察基于Niederreiter編碼的混合加密方案的性能。