應對反應攻擊的級聯(lián)中密度準循環(huán)奇偶校驗碼公鑰方案

巫光福，戴子恒

（江西理工大學信息工程學院，江西贛州 341000）

0 引言

當今，世界各國都在如火如荼地研究著量子計算。量子計算機具有超強的計算能力，能在相對較短的時間內(nèi)處理大量的數(shù)據(jù)，這給基于計算復雜度的現(xiàn)代公鑰密碼學（Public Key Cryptography，PKC）的安全帶來了巨大挑戰(zhàn)。為應對量子計算帶來的威脅，后量子密碼學［1］應運而生。目前，美國國家標準技術研究所（National Institute of Standards and Technology，NIST）正制定新一代的后量子密碼方案標準［2］，其主要分為基于格、基于編碼、基于多變量和基于哈希這四類構造方法。

McEliece 型的加密方案［3］是基于編碼的公鑰密碼中最經(jīng)典的方案，而采用中密度準循環(huán)奇偶校驗（Quasi-Cyclic Moderate-Density Parity-Check，QC-MDPC）碼來代替原始Goppa 碼所構造出的變型方案是有希望達到密鑰量與安全性相對平衡的優(yōu)良方案。1962 年，Gallager［4］提出了低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼，它是一類具有稀疏校驗矩陣的線性分組碼，譯碼復雜度低。2000年，Monico等［5］利用LDPC 碼來代替Goppa碼，構造了新的McEliece 公鑰密碼方案。2007 年，Baldi 等［6］將低密度準循環(huán)奇偶校驗（Quasi-Cyclic Low-Density Parity-Check，QC-LDPC）碼應用于McEliece 公鑰密碼方案中。但上述這些方案不久便被證明是不安全的，易受到譯碼攻擊和結構攻擊。2013 年，Misoczki等［7］在前人工作的啟發(fā)下，提出了基于中密度準循環(huán)奇偶校驗碼的McEliece 公鑰密碼方案。該方案已被證明能抵抗QCLDPC碼公鑰方案所受到的相關攻擊，在保證一定安全性的同時具有較小的密鑰量。但在2016 年，Guo 等［8］提出了針對該方案的一種反應攻擊：密鑰恢復攻擊（key recovery attack），簡稱GJS（Guo，Johansson and Stankovski）攻擊。在最近NIST 所征集的相關QC-MDPC 碼的公鑰方案中，能否抵抗GJS 攻擊已成為判斷方案好壞的一項基本準則。因此，找尋更多更好的方法來解決現(xiàn)有面臨的GJS 攻擊，是研究關于QC-MDPC 碼公鑰密碼方案的一個重要方向。

將噴泉碼級聯(lián)到QC-MDPC 碼公鑰密碼方案中便是本文對于抵抗GJS 攻擊的設想。1998 年，Byers 等［9］首次提出了數(shù)字噴泉（Digital Fountain）的概念，但并沒有給出現(xiàn)實可行的方案。2002 年，Luby［10］提出了一種可實際應用的噴泉碼，被稱為LT 碼。2006年，Shokrollahi［11］在LT 碼的基礎上繼續(xù)提出了新的噴泉碼，被稱為Raptor 碼。Raptor 碼實際上是LT 碼和分組碼的級聯(lián)碼，因此本文采用LT 碼和QC-MDPC 碼級聯(lián)來構成一種類Raptor碼，是具有一定可行性的。目前，數(shù)字噴泉碼技術常應用于無線多媒體廣播和分布式存儲等領域，將噴泉碼結合到公鑰密碼學中是其應用前景的一個新構想，因此噴泉碼作為一種前向糾錯技術在信息安全方面的研究是值得深入探討的。

1 相關工作

1.1 QC-MDPC碼McEliece公鑰方案

中密度準循環(huán)奇偶校驗（QC-MDPC）碼中，中密度是指該碼的奇偶校驗矩陣的行重量相較于LDPC 碼略高；準循環(huán)是指該碼的奇偶校驗矩陣的每行可由第一行循環(huán)移位不同數(shù)量的碼字得到；奇偶校驗是指該碼是由其奇偶校驗矩陣所表示的。LDPC 碼的校驗矩陣行重量一般不大于10，而中密度奇偶校驗（Moderate Density Parity Check，MDPC）碼的校驗矩陣行重量為O()的數(shù)量級。由于QC-MDPC碼的校驗矩陣使用了準循環(huán)結構，生成該矩陣的第一行便能得到校驗矩陣，因此在實際中只需存儲第一行碼長，提升了存儲空間的利用率。如圖1 所示是一個（56，32，14）-QC-MDPC 碼的校驗矩陣H。

圖1 QC-MDPC碼的校驗矩陣HFig.1 Check matrix H of QC-MDPC code

QC-MDPC 碼一般由四個參數(shù)表示，即(n，k，w，t)-QCMDPC 碼。其中，n表示碼長；k表示碼的維度；w表示校驗矩陣固定行重量；t表示碼的糾錯能力。除此之外，n還表示校驗矩陣的列數(shù)，r(r=n-k)表示校驗矩陣的行數(shù)，被稱為余維度，且n=n0r。如表1 所示為現(xiàn)已提出的多個安全級別下QC-MDPC碼的相關參數(shù)［7］，其中n0=2。

表1 不同安全級別下的QC-MDPC碼參數(shù)Tab.1 Parameters of QC-MDPC code under different security levels

基于QC-MDPC 碼的McEliece 公鑰密碼方案由三部分組成：

1）密鑰生成。

生成一個能糾t個錯誤的(n，k，w)-QC-MDPC 碼的校驗矩陣H，H∈；根據(jù)校驗矩陣H來轉(zhuǎn)換得到生成矩陣G，G∈；將校驗矩陣H作為私鑰，生成矩陣G作為公鑰。

2）加密。

給定一個明文m∈，一個重量w(e) ≤t的噪聲變量e∈，密文通過計算得到：c←mG+e。

3）解密。

令φH是能糾t個錯誤的MDPC 碼譯碼算法，則明文通過計算得到：mG←φH(mG+e)，最后從mG前k個位置中提取明文m。

在密鑰生成中，校驗矩陣H是通過不斷循環(huán)位移得到。首先生成一個二進制字符串h0，來作為分塊矩陣的第一行；然后進行循環(huán)位移生成其他行來得到分塊矩陣H0；最后將分塊矩陣H0整體循環(huán)位移從而最終得到校驗矩陣H。生成矩陣G是通過分組碼中校驗矩陣與生成矩陣的關系轉(zhuǎn)換得到。關于解密中的譯碼算法，Gallager［4］最初提出了硬判決和軟判決兩類算法。硬判決算法稱為比特翻轉(zhuǎn)（Bit Flipping，BF）算法。軟判決算法又叫作概率解碼算法，目前來說性能最佳的概率解碼算法為置信傳播（Belief Propagation，BP）算法。根據(jù)研究現(xiàn)狀，QC-MDPC 碼的譯碼一般采用Misoczki 等［7］所改進的BF 算法。BF 算法的基本思想為：當譯碼接收到一個比特時，計算對應的校驗子（syndrome），并統(tǒng)計奇偶校驗方程（unsatisfied parity-check equations）不成立的總數(shù)，記為counter，若計數(shù)值counter超過閾值T（threshold），則翻轉(zhuǎn)該比特。比特翻轉(zhuǎn)后的碼字繼續(xù)重復上述過程，經(jīng)過一定的迭代輪次后，當校驗子的值為0 或迭代次數(shù)達到上限，則譯碼完成。

1.2 數(shù)字噴泉碼

數(shù)字噴泉碼是差錯控制中的一種前向糾錯編碼（Forward Error Correction，F(xiàn)EC）技術，即能在刪除信道中進行碼字糾刪。在通信傳輸時，信道難免會發(fā)生丟包或誤碼，因此在刪除信道中，接收端要么接收正確信息，要么接收錯誤信息對其丟棄。解決這一問題的一種方法可以是采用反饋重發(fā)（Automatic Repeat-reQuest，ARQ）技術［12］，即當接收端收到錯誤信息后，便對發(fā)送端進行反饋要求重發(fā)消息。ARQ 的技術原理相當簡單直觀，但其缺陷也較為明顯。當傳輸數(shù)據(jù)較大時，即使在一定誤碼率下，接收端進行的反饋重發(fā)量也會很大，這樣便增加了通信的負擔，也影響了傳輸效率，同時ARQ技術下的通信信道利用率并不高，會引起信道資源的浪費。因此，將ARQ 替換為對消息進行編碼來達到糾錯的目的，這便是信道編碼的優(yōu)勢。

LT 碼和Raptor 碼是噴泉碼中兩種典型碼型。LT 碼性能的好壞主要取決于度分布函數(shù)，其編碼步驟［10］如下：

1）將需要被發(fā)送的數(shù)據(jù)進行等長l分組得到n個數(shù)據(jù)包；

2）根據(jù)設計好的度分布函數(shù)f來隨機獲得一個度數(shù)δ；

3）在n個數(shù)據(jù)包中隨機選取δ個并對其全部進行異或運算來得到一個編碼包；

4）重復上述步驟來獲得足夠多的編碼包。

上述過程如圖2 所示。從該過程可以看出，為保證后續(xù)譯碼，生成的編碼包數(shù)量不少于n，且理論上生成的編碼包個數(shù)是不受限的。這也體現(xiàn)了噴泉碼的“無碼率性”，即在編碼過程中獲得的編碼包數(shù)量不固定，因此碼率就不固定，如同噴泉一樣源源不斷地向接收端傳輸。對于LT碼的編譯碼過程，實際上可看作為類似分組碼的矩陣變換：將分組的n個數(shù)據(jù)包記為P=(p1，p2，…，pn)，獲得的編碼包記為B=(b1，b2，…，bn)。那么由矩陣P變換到矩陣B的過程可表示為：B=P?F，同時譯碼過程即可表示為：P=B?F-1，其中F稱為編碼矩陣，F(xiàn)-1為編碼矩陣的求逆過程。顯然，編碼矩陣F的結構和度分布函數(shù)f密切相關，為了使譯碼復雜度較小，因此需要對度分布函數(shù)f精心設計。編碼矩陣的求逆過程，即譯碼可采用高斯消除算法或置信傳播算法來恢復數(shù)據(jù)，高斯消除算法有更優(yōu)的譯碼性能，置信傳播算法運算復雜度相對較低，根據(jù)綜合考慮，實際常采用置信傳播算法對LT 碼進行譯碼。

圖2 LT碼編碼示意圖Fig.2 Schematic diagram of LT code encoding

Raptor 碼是在LT 碼的基礎上發(fā)展而來的。由于LT 碼在編碼過程中選擇數(shù)據(jù)包進行異或操作具有隨機性，可能存在某個數(shù)據(jù)包從未被進行編碼，則接收端無法獲取該原始數(shù)據(jù)而導致譯碼失敗。因此在LT 編碼過程中會刻意選取較大度數(shù)來進行一定量的編碼，從而保證原始數(shù)據(jù)被完全覆蓋。但這樣會帶來過多的編譯碼過程中的異或操作，減小了譯碼過程中可譯集的大小，使得譯碼仍存在一定的失敗率。Raptor的設計很好地解決了上述問題。Raptor 是將分組碼和LT 碼進行級聯(lián)編碼得到，先使用分組碼對原始消息進行預編碼，然后使用LT 碼進行編碼得到編碼包進行發(fā)送［11］，如圖3 所示為Raptor 碼編碼過程。使用級聯(lián)編碼的好處在于對Raptor 碼進行譯碼時，若出現(xiàn)對LT 碼的譯碼失敗，那么可以利用分組碼的自糾能力繼續(xù)譯碼來消除失敗。因此，Raptor 碼中的LT 碼無須產(chǎn)生太多高連接度的編碼包，這樣既保證了數(shù)據(jù)被良好覆蓋，同時又具有較高的譯碼成功率和較低的編譯碼復雜度。

圖3 Raptor碼編碼示意圖Fig.3 Schematic diagram of Raptor code encoding

2 密鑰恢復攻擊

2016 年，Guo 等［8］提出了一種對QC-MDPC 碼下的McEliece 公鑰密碼方案的攻擊：密鑰恢復攻擊，簡稱GJS 攻擊。其通過對接收機解密是否成功這一反應，判斷并獲得私鑰的相關信息，從而來恢復方案的私鑰。

2.1 攻擊情景

假設Alice 為發(fā)送方，Bob 為接收方，Eve 為攻擊者。Alice首先利用QC-MDPC 碼McEliece 公鑰方案的公鑰對消息m加密生成密文c進行發(fā)送，Bob 接收到密文c后使用對應私鑰解密。若解密成功，則Bob 對Alice 回復確認或不作回復；若解密失敗，則Bob 對Alice 反饋要求重發(fā)消息。Eve 作為敵手，同樣對消息m使用公鑰加密生成密文c，但會選擇一種特定的錯誤圖樣e與密文c進行異或運算，得到密文ce進行發(fā)送。同樣Bob 接收后使用私鑰解密，當解密失敗后Bob 要求重發(fā)消息時，Eve 能截取到此反饋，經(jīng)過大量消息的傳輸后，Eve 便能統(tǒng)計獲得相應的譯碼失敗率。Eve 通過分析大量實驗下的譯碼失敗率和私鑰結構的關系后，最終恢復出私鑰。

2.2 攻擊原理

Eve發(fā)送的密文ce=mG+e被Bob接收后，根據(jù)比特翻轉(zhuǎn)算法的步驟，開始計算校驗子s=ceHT=mGHT+eHT=eHT，該結果表示計算校驗子實際上只和錯誤圖樣e有關，則對于第j位的奇偶校驗方程為：sj=。若sj≠0，那校驗方程不成立的個數(shù)增加一個，當計數(shù)（counter）達到一定值，即超過閾值時，那么密文c對應的第i位置的比特將會翻轉(zhuǎn)。因此，對于敵手設計的錯誤圖樣e，它會影響譯碼時變量節(jié)點是否發(fā)生比特翻轉(zhuǎn)的情況。同時，BF 是一種迭代算法，在一定的迭代次數(shù)下，若未正確地完成所有比特翻轉(zhuǎn)，那么譯碼失敗。所以，敵手可以通過多次的實驗來獲取譯碼失敗情況，找尋錯誤圖樣e和譯碼失敗的關系，這一關系表述為：若錯誤圖樣e中兩位1 之間的漢明距離也存在于校驗矩陣H的第一行向量h0的兩位1 之間，那么此時譯碼失敗率要比不存在情況時的小。根據(jù)該關系，敵手通過譯碼失敗的統(tǒng)計數(shù)據(jù)來得到向量h0中存在的漢明距離和重數(shù)，即距離譜D。利用距離譜進行深度優(yōu)先搜索恢復出向量h0，最后進行線性變換恢復出校驗矩陣H，即破解出私鑰。

2.3 攻擊結果

文獻［8］給出了在選擇明文攻擊（Chosen Plaintext Attack，CPA）和適應性選擇密文攻擊（Adaptive Chosen Ciphertext Attack，CCA2）兩種攻擊等級安全下實施GJS 攻擊的結果。在80-bit安全下，CPA 情景的參數(shù)如下：當t=84時，M=105，U=2400；當t=90 時，M=104，U=2400。其中，M為某特定錯誤圖樣e下一次實驗加解密傳輸?shù)南⒘?，U為選擇不同錯誤圖樣e所進行的實驗次數(shù)。在M×U的消息傳輸量下，GJS 攻擊能成功恢復私鑰。對于CCA2 情景，當t=84時，至少需要M×U=2.03× 108的消息傳輸量來恢復出私鑰，而最差情況下則需要M×U=3.56 × 108。由于CCA2 的安全級別更高，因此需要的代價較CPA 情景下更大，因此實驗所需的消息傳輸量更多。

3 類Raptor碼級聯(lián)QC-MDPC碼公鑰方案

密鑰恢復攻擊的特點在于它是一類反應攻擊，即攻擊者利用接收端譯碼失敗時的反應來恢復出私鑰，因此通信傳輸中反饋信道是進行密鑰恢復攻擊的必要條件。若對反饋信道進行加密處理或直接用其他方式代替反饋信道，那密鑰恢復攻擊的實施復雜度將會極大增加。噴泉碼便是十分契合抵抗密鑰恢復攻擊的設計，在基于QC-MDPC 碼的McEliece 公鑰方案中級聯(lián)LT 碼，得到一種類Raptor 碼的公鑰方案。在該方案下當譯碼失敗時，接收端無須反饋重發(fā)，而是繼續(xù)接收源源不斷的編碼包直到譯碼成功。本文提出的類Raptor 碼級聯(lián)QCMDPC碼的公鑰方案由密鑰生成、加密和解密三個部分組成。

3.1 密鑰生成

根據(jù)QC-MDPC 碼和LT 碼的級聯(lián)過程，首先生成QCMDPC碼的McEliece公鑰方案中的公鑰：生成矩陣G，私鑰：校驗矩陣H。然后通過LT碼的編碼過程來獲得編碼矩陣F。最后將G'=GF作為方案的公鑰，將H和F(F-1)作為方案的私鑰。其中

3.2 加密

對明文m∈使用公鑰進行級聯(lián)碼加密：mG'。然后考慮信道中加入的錯誤圖樣e，其重量不大于整個級聯(lián)碼的糾錯能力，得到最終的密文c=mG'+e。

3.3 解密

解密為加密的逆過程，先對密文c進行級聯(lián)過程中LT 碼的譯碼：mG=φF-1(mG'+e)，其中φF-1表示為置信傳播算法。然后進行對QC-MDPC碼的譯碼：m=φH(mG)，其中φH表示為比特翻轉(zhuǎn)算法。最終解密獲得明文m。

4 參數(shù)與效率分析

4.1 參數(shù)分析

根據(jù)方案描述，在級聯(lián)碼中，QC-MDPC 碼需考慮的是相關參數(shù)(n，k，w，t)，方案仍采用QC-MDPC碼McEliece公鑰密碼方案。LT 碼需考慮編碼矩陣F所對應度分布函數(shù)f中的相關參數(shù)x和δ，其中：x表示生成的編碼包個數(shù)，即編碼分組數(shù)；δ表示度數(shù)。而編碼包長參數(shù)l，由于其不會影響LT 碼譯碼性能，為了方便分析，方案確定l=1。對于設計優(yōu)良的LT碼，需要盡可能生成少的編碼分組來保證譯碼開銷較小，同時還需要盡量小的編碼符號平均度數(shù)來保證編譯碼代價較小。這兩點也符合了本文方案的設計要求：較少的編碼分組數(shù)意味著較小的密鑰量以便存儲，較小的編碼符號平均度數(shù)意味著方案運行效率相對更高。

在LT 碼中，譯碼開銷用參數(shù)ε表示，是指當輸入符號數(shù)為n時，接收到的編碼分組數(shù)為x且能以高概率1-γ成功譯出這n個符號，那么x=(1+ε)n，即ε=-1。編譯碼代價是指生成編碼包和恢復原始數(shù)據(jù)的編譯碼操作數(shù)，即編譯碼復雜度。文獻［10］中給出了度分布函數(shù)的幾種選擇，如表2所示。

表2 三種度分布函數(shù)的比較Tab.2 Comparison of three degree distribution functions

文獻［10］分析了這三種度分布函數(shù)并得出采用魯棒孤子分布是最優(yōu)選擇的結論。從編碼分組數(shù)可以看出，魯棒孤子分布所需要的譯碼開銷相較于度一分布要小很多，但無法達到理想孤子分布的最優(yōu)情況。不過魯棒孤子分布改善了理想孤子分布存在的問題：可譯的度數(shù)為1 的編碼包不夠多會容易導致譯碼失敗。從平均度數(shù)上看，魯棒孤子分布需要的編譯碼操作數(shù)大致接近理想孤子分布。綜合考慮，魯棒孤子分布的性能最佳。根據(jù)具體的信道特點，新的度分布函數(shù)也被研究者們不斷提出，但本文方案暫不考慮度分布的設計，選擇魯棒孤子分布作為LT碼分布函數(shù)已達到方案的安全要求。

上述單從LT碼分析了其譯碼開銷，但對于本文方案級聯(lián)碼的譯碼開銷來說，ε并不確定。由于QC-MDPC 碼具有一定的自糾能力，因此LT碼在譯碼時未完全譯出也可能最終解密成功，此時εR≤εLT。同時使用BF對QC-MDPC 譯碼時可能會出現(xiàn)失敗，則此時εR>εLT。而級聯(lián)碼的譯碼開銷決定了編碼分組數(shù)x的取值。最優(yōu)情形為x=n時，消息便能成功譯出；最壞情形為x=(1+εm)n，其中εm表示對任意消息都能以1的概率成功解密時的譯碼開銷。因此方案在確定編碼矩陣F的大小時，x的取值應考慮最壞情形，即x=(1+εm)n。

4.2 密鑰量和復雜度分析

本文方案的公鑰為G'=GF。矩陣G'的大小為k×x，即公鑰密鑰量為(n-r)x比特。而在QC-MDPC 碼的原始方案中，矩陣G為準循環(huán)結構且可化為系統(tǒng)矩陣，其密鑰量為(n0-1)r比特。本文方案由于對矩陣G右乘了矩陣F，公鑰的準循環(huán)結構被認作消失，因此兩者對比密鑰量相差了x倍。本文方案的私鑰為H和F(F-1)。矩陣H同為準循環(huán)結構，其密鑰量為n0r比特。而矩陣F(F-1)更多是作為一種私鑰形式，表現(xiàn)為LT碼的譯碼算法，因此實際中無須對其進行存儲。

方案的復雜度圍繞密鑰生成、加解密過程分析。在密鑰生成階段，矩陣G和F相乘獲得G'需要(2n-1)kx次比特操作，該復雜度大于QC-MDPC 碼方案下生成公鑰G時的復雜度，但仍小于QC-LDPC 碼方案下生成公鑰G2=S-1GQ-1時的復雜度。在加密階段，明文m與公鑰G'進行矩陣相乘運算，需要(2k-1)x次比特操作。在解密階段，對LT 碼和QCMDPC 碼的解碼分別采用置信傳播算法和比特翻轉(zhuǎn)算法。BP譯碼算法復雜度為O(nlnn)，而LT 碼的另一譯碼算法高斯消除算法復雜度為O(xn2)，兩種算法相較BP 復雜度更適合本文方案。BF譯碼算法復雜度為O(nwI)，I為迭代次數(shù)。

5 抵抗GJS攻擊

基于糾錯碼的公鑰密碼方案一直以來面臨著兩類攻擊的安全挑戰(zhàn)：譯碼攻擊和結構攻擊。譯碼攻擊是直接破解得到明文，結構攻擊則是破解方案的私鑰。Misoczki等［7］提出的基于QC-MDPC 碼的McEliece 公鑰密碼方案已被證明能抵抗消息集譯碼攻擊（Information Set Decoding Attack），在80-bit安全下，攻擊實現(xiàn)的復雜度為O(281.04)，因此可以達到該比特安全性。同時該方案還能抵抗找尋原碼對偶碼的低重量碼字的結構攻擊［13］。但Guo 等［8］提出了一種新的結構攻擊——GJS 攻擊，是目前對于QC-MDPC 碼公鑰方案最具威脅的攻擊之一，本文提出的級聯(lián)碼公鑰方案能有效抗擊GJS 攻擊。根據(jù)Raptor 碼的實現(xiàn)流程來得到方案的具體實現(xiàn)，并考慮GJS 攻擊在此情景下的影響進而分析抗擊效果。

5.1 Raptor碼系統(tǒng)流程

基于Raptor 碼的編譯碼系統(tǒng)流程如圖4 所示。從圖4 中可以看出，此過程中存在反饋系統(tǒng)，同時結合了噴泉碼具有的FEC 機制，使得整體上采用了混合自動重傳請求（Hybrid Automatic Repeat-reQuest，HARQ）［14］技術。接收端在對一次消息成功譯碼后，會向?qū)Ψ椒答佉粋€確認信息（ACKnowledge，ACK），讓其停止發(fā)送編碼包；當譯碼失敗時，接收端不會作任何反饋，而是等待對方發(fā)送更多的編碼包直至譯碼成功?？梢钥闯稣麄€過程對譯碼失敗的相關信息具有一定的隱藏能力。

圖4 Raptor碼的編譯碼系統(tǒng)流程Fig.4 Flow chart of Raptor code encoding/decoding system

但本文方案無法直接采用上述系統(tǒng)，因為不能達到完全匹配，同時還存在一些缺陷：由于HARQ 機制的存在，那么發(fā)接收端需要進行一定的同步，即通過接收端的反饋來控制發(fā)送LT 碼編碼時編碼包的量。而本文方案是直接由矩陣運算完成級聯(lián)碼加密，采用上述動態(tài)過程是不現(xiàn)實的。除此之外，過程中的反饋系統(tǒng)仍是一個安全隱患。雖然為正向反饋，但攻擊者仍可能利用該反饋系統(tǒng)進行攻擊，如利用旁道攻擊（Side-Channel Attack）中的計時攻擊（Timing Attack）。文獻［15］提出了一種在GJS 攻擊上改進的計時攻擊，若攻擊者能獲取QC-MDPC 碼進行BF 譯碼時的迭代次數(shù)，那么攻擊者同樣能得到私鑰H的距離譜和迭代次數(shù)的關系圖，并通過大量樣本實驗來恢復出私鑰H。而迭代次數(shù)實際上是通過譯碼運行時間來體現(xiàn)的，所以何時收到反饋信息便是攻擊者計算譯碼時長的途徑，從而有可能對本文方案實施類似的計時攻擊。因此，本文方案的實現(xiàn)情景需要在Raptor 碼的編譯碼系統(tǒng)流程的基礎上進行修改。

5.2 方案情景與抗擊效果

本文方案的實現(xiàn)情景如圖5 所示。該情景刪除了Raptor碼系統(tǒng)流程中的反饋系統(tǒng)，同樣能達到抵抗GJS 攻擊的效果。其分析如下：

圖5 本文方案實現(xiàn)流程Fig.5 Realization flow chart of proposed scheme

當敵手準備GJS 攻擊時，首先對消息進行本文方案的級聯(lián)編碼，即使用公鑰G'對消息加密。然后選擇特定錯誤圖樣e，得到密文c∈。公鑰G'對于原始方案的公鑰G來說，只是矩陣略大一些，面對敵手其在形式上是一樣的，因此敵手對特定錯誤圖樣e仍按照原方法構造且e∈。

GJS 攻擊的本質(zhì)是利用特定錯誤圖樣e來影響B(tài)F 譯碼效果，通過大量實驗結果來反映出距離譜D信息從而恢復出私鑰H。因此在原方案中生成mG+e是GJS 攻擊成功的前提，但本文方案由于加入了LT 碼的編碼，所以生成的是mGF+e，編碼矩陣F將mG隱藏起來，此時e主要影響的是F，這意味著錯誤圖樣只是改變了LT 碼編碼時度數(shù)δ的大小，即數(shù)據(jù)的連接度情況。當方案的參數(shù)x足夠大，即譯碼開銷具有合適大小時，便能生成足夠多的編碼包來保證LT 碼在BP譯碼時都能成功譯出消息，因此在本文方案下GJS 攻擊生成的錯誤圖樣e無法影響QC-MDPC碼的譯碼結果。

除此之外，方案將F作為了私鑰，因此敵手很難通過G'恢復出G，進一步加大了攻擊難度。同時方案還考慮了譯碼時的最壞情況，保證加解密過程中始終能譯碼成功，因此便無須反饋系統(tǒng)，從根本上阻止了反應攻擊。綜上分析，本文方案在抵抗GJS攻擊上是十分有效的。

5.3 仿真分析

本文分析了GJS 攻擊的內(nèi)在過程，并提出了相應理論上的應對措施。對于本文方案能否抵抗GJS 攻擊的關鍵在于確定合適的譯碼開銷值大小。根據(jù)本文方案在GJS 攻擊下的情景，可對參數(shù)選擇合適數(shù)值后進行模擬仿真。隨機選取待加密明文m，其長度為480比特，QC-MDPC碼長n為960比特，碼率為0.5。LT 碼的度分布函數(shù)采用魯棒孤子分布，其參數(shù)為α=0.03，γ=0.5。信道錯誤圖樣e引起的刪除概率為0.1。對一次消息加解密實驗重復進行1000次，最終獲得方案級聯(lián)碼的性能如圖6所示。

圖6 方案譯碼開銷與譯碼成功率關系Fig.6 Relation between decoding overhead and decoding success rate

由圖6 中仿真結果可以看出，私鑰F需確定的參數(shù)x=(1+εm)n≈1.65n。為了方便模擬，QC-MDPC碼選擇的參數(shù)為原方案參數(shù)大小的1/10。而在LT 碼的譯碼時，其碼長會影響譯碼效果，即碼長越長，譯碼效果在低冗余時提升越明顯［16］。因此實際中若使用QC-MDPC 碼原方案，譯碼開銷εm或?qū)陀?.65。不過值得注意的是，上述仿真理想化了QC-MDPC碼的譯碼，未考慮其存在一定譯碼失敗的情況。那么綜合分析得出，εm至少為0.65來保證最壞情況時的譯碼成功。

確定了較好數(shù)值大小的譯碼開銷εm后，對于方案在實際應用中，可以保證存儲中的密鑰量不會過大。而在安全性上，由于實際因素復雜，理想情況中的譯碼百分之百成功難以達到。但根據(jù)抵抗GJS 攻擊中比特安全性定義：對于a-bit 安全級別，若方案的譯碼失敗率小于2-a，那么方案能抵抗相關攻擊。因此方案在較小譯碼失敗率下仍可保持應用中抵抗GJS攻擊的效果，所以選擇了優(yōu)良數(shù)值的譯碼開銷εm后，便保證了譯碼失敗率可以忽略。

6 不同方案的對比分析

本文提出的基于QC-MDPC 碼級聯(lián)碼的公鑰密碼方案能有效抵抗GJS 攻擊，對本文方案與已有的能抵抗GJS 攻擊的方案進行了比較。

6.1 本文方案的公鑰密鑰量

根據(jù)上述分析可知本文方案的公鑰密鑰量為(n-r)x，其略大于MDPC 碼生成矩陣G參數(shù)(n-r)r。但MDPC 碼是不具有公鑰設計價值的：根據(jù)MDPC 碼與其他碼型方案的比較，若將MDPC 碼的生成矩陣作為公鑰，其密鑰量甚至大于原始的McEliece 方案的公鑰量。密鑰量這么大的原因在于MDPC碼不存在準循環(huán)（Quasi-Cyclic，QC）結構，因此需存儲整個矩陣而不是矩陣中的某一行。本文方案同樣面臨這樣的問題，若要讓方案的公鑰密鑰量減少，那么需要保證公鑰G'具有一定的循環(huán)結構。由于G'=GF，其中G可化為系統(tǒng)形式并具有準循環(huán)結構，那么F便是保證G'循環(huán)性的決定因素。因此，如何改良設計LT碼編碼時的度分布函數(shù)f就成為了本文方案的改進目標。

關于對矩陣F的考慮，最直觀的是使其成為準循環(huán)結構，但這樣可能會導致一定的安全問題，這點下文將會分析。不過可以降低對G'的循環(huán)性要求，即無須達到準循環(huán)，而讓G'的每行或列之間存在某種規(guī)律，同樣也能達到減少密鑰量的效果。除此之外，根據(jù)文獻［17］提出的相關方案，表明存在非準循環(huán)結構的F也能保證G'的準循環(huán)性，而滿足這種條件的F有多少個也是今后需要進一步驗證的。

6.2 本文方案的抗攻擊性能

本文主要分析了所提出的公鑰密碼方案對GJS 攻擊的抗擊效果，需要對QC-LDPC/MDPC 碼易遭受的其他攻擊進行討論，來綜合分析方案的安全性能。

消息集譯碼攻擊［13］是利用公鑰G和錯誤圖樣e來構造出一個可逆矩陣G1從而恢復明文，即m=cG1-1=(mG+e)G1-1=mGG-1+ee-1。而消息集譯碼算法如Stern 算法和MMT（May，Meurer and Thomae）算法［18］，其時間復雜度都是指數(shù)級別的，約為O(20.05n)，本文方案和原始QC-MDPC 碼的公鑰密碼方案在參數(shù)n上相同，即80-bit 安全級別下攻擊復雜度約為O(2480)。顯然本文方案是能抵抗此攻擊的。

搜尋公鑰對偶碼的低重量碼字的結構攻擊［13］，是利用QC-LDPC 碼的McEliece 公鑰密碼方案的私鑰H進行實施的，其基本原理是針對私鑰H的稀疏性特點，即行重量太小進行攻擊。而本文方案仍以QC-MDPC 碼為基礎，則私鑰H的密度足夠大，因此能抵抗此攻擊。

2010 年，OTD（Otmani，Tillich and Dallot）攻擊［19］是針對公鑰形式為G2=S-1GQ-1的QC-LDPC 碼的McEliece 變型方案而進行實施的，其中，S和Q分別為非奇異加擾矩陣和非奇異變換矩陣且都稀疏。本文方案的公鑰G'=GF與上述條件明顯不符，因此該攻擊對本文方案無效。

一種尋找弱密鑰的密鑰恢復攻擊［20］，其攻擊點為原始的QC-MDPC 碼McEliece 公鑰密碼方案，即利用公鑰G來恢復私鑰H。本文方案將G進行了隱藏同時還存在其他矩陣作為私鑰，因此該攻擊不可行。

FHP（Fab?i?，Hromada and Paul stankovski）攻擊［21］是一種對本文方案安全性有威脅的反應攻擊，與GJS 攻擊十分相似。其攻擊點為QC-LDPC 碼McEliece 公鑰密碼方案，即利用公鑰G2=S-1GQ-1且構造特定的錯誤圖樣e來觀測譯碼結果。在此情景下，加密為c=mS-1GQ-1+e，解密先對c右乘Q得到c'=mS-1G+eQ，最后利用譯碼算法糾錯eQ得到mS-1并恢復出明文m=mS-1S。由此看出，影響譯碼結果的為eQ，所以FHP攻擊便會利用Q的循環(huán)且低密度特性來獲取距離譜與譯碼結果的聯(lián)系，從而恢復私鑰。本文方案的公鑰形式也存在對G右乘矩陣F，根據(jù)上述密鑰量的分析，F(xiàn)若為循環(huán)結構雖有利于公鑰存儲，但這樣也有可能利于FHP 攻擊的實施。不過本文方案在解密時為級聯(lián)碼的分步譯碼，在LT碼譯碼時很大程度上消除了錯誤圖樣，并且方案刪去了反饋系統(tǒng)，所以在理論上是能抵抗FHP攻擊的。

6.3 各類抵抗GJS攻擊方案對比

一些代表性研究根據(jù)GJS 攻擊的特點也提出了抗擊方案。本文方案與這些方案的特性對比如表3 所示，各方案的具體介紹如下。

表3 不同抵抗GJS攻擊方案的特性比較Tab.3 Characteristic comparison of different schemes against GJS attack

Eaton等［15］提出了使用“靜態(tài)密鑰”進行密鑰封裝的方案：ParQ 加密方案（Parallelized QC-MDPC KEM）。該方案的抗擊原理為：首先生成QC-MDPC 碼的McElicec 方案的公鑰G和私鑰H，令par為平行數(shù)，取值范圍為3～12。然后將公鑰G通過ParQ 加密算法來獲得par個平行公鑰，利用平行公鑰對明文進行加密得到封裝密文C=(c1，c2，…，cP-1，cP)。最后通過ParQ 解密算法對封裝密文C解密，即通過私鑰H來對密文c解密，當且僅當P個密文c譯碼失敗時，才記作ParQ 解密失敗，否則解密成功。根據(jù)該方案的描述，可以看出其原理與本文方案十分相似，都是對原McEliece 方案的公私鑰進行改造來降低譯碼成功率，使其達到能抵抗GJS 攻擊的安全標準。而改造后的公私鑰相對更大，因此在某種程度上是通過密鑰量來換取方案的安全性。

Barreto 等［22］提出了CAKE（Code-based Algorithm for Key Encapsulation）。該算法的抗擊原理為：方案采用臨時密鑰，即動態(tài)密鑰，進行密鑰封裝，當完成一次明文的加解密后，使用過的“密鑰對”便會更新。由于每次解密所使用的私鑰是不斷變化的，因此恢復私鑰便沒有意義，GJS 攻擊便完全失效。不過CAKE 并非McEliece 型，而是基于ElGamal 型的公鑰密碼。其特點表現(xiàn)為：算法將私鑰矩陣乘以隨機循環(huán)密度矩陣來隱藏私鑰的結構，其不同于McEliece 型對私鑰右乘公鑰來隱藏私鑰結構的特點。在NIST 所征集的一類基于編碼的密碼方案即BIKE（BIt flipping Key Encapsulation）方案［23］中，第一種算法BIKE-1 為CAKE 的改進，并在最新的BIKE 方案中，提升了譯碼算法的性能，獲得了更優(yōu)的譯碼器即Backflip Decoder［24］。該譯碼器可以讓方案在靜態(tài)密鑰下，使譯碼失敗率足以忽略，從而實現(xiàn)更高的安全性。

7 結語

本文提出了一種類Raptor 碼的級聯(lián)碼公鑰密碼方案，該方案是QC-MDPC 碼McEliece 公鑰密碼方案基礎上的改進。分析結果表明，通過犧牲原方案在密鑰量和加解密復雜度上的一些優(yōu)勢，本文方案獲得了在安全性上的提升，其表現(xiàn)為能抵抗GJS 攻擊等一些反應攻擊和其他相關攻擊。但本文方案也存在一定的缺陷，如密鑰量的問題。同時方案還存在一些改進的方向，如對級聯(lián)碼能否提出更優(yōu)的整體譯碼方案來提升譯碼效率。這些都是未來需要進一步研究的方向。