Niederreiter公鑰密碼方案的改進

劉相信，楊曉元

(網絡與信息安全武警部隊重點實驗室(武警工程大學)，西安 710086)(*通信作者電子郵箱1125424226@qq.com)

0 引言

基于編碼的密碼方案具有抗量子的特性和簡單的加解密過程，是當今抗量子密碼方案的佼佼者。1978年，Berlekamp等[1]證明了隨機線性碼的譯碼問題是一個非確定性多項式完全困難(Non-deterministic Polynomial Complete, NPC)問題，為基于編碼的公鑰密碼方案的設計奠定了理論基礎，同年McEliece[2]利用此困難問題提出第一個基于Goppa碼的公鑰密碼方案——McEliece公鑰密碼方案。該方案可抗量子攻擊、加解密速度快、實現簡單。方案中錯誤向量的漢明重量固定且公開，易導致密文對明文信息的泄露，所以必須選取較大的公鑰尺寸來保證計算安全性，因此該方案公鑰尺寸過大，實用性差。1986年，Niederreiter[3]對McEliece公鑰密碼方案進行了改進，提出了一種Niederreiter公鑰密碼方案，該方案從另一個角度利用了隨機線性碼的譯碼困難問題，McEliece公鑰密碼方案隱藏的是Goppa碼的生成矩陣，而該方案隱藏的是Goppa碼的校驗矩陣，此時公鑰尺寸有所變小，但還是沒有達到實用要求。為了降低方案的密鑰尺寸、提高方案的性能，同時保持方案的安全性，學者們紛紛利用一些具有較好性質的線性碼來代替原方案的Goppa碼，例如RM(Reed Muller)碼、LDPC(Lower Density Parity Check)/MDPC(Moderate Density Parity Check)碼、RS(Reed-Solomon)/GRS(Generalized RS)碼、QC(Quasi-Cyclic)/QD(Quasi-Dyadic)/QM(Quasi-Monoidic)碼、代數幾何碼等，這些方案雖然具有較好的性能，但是這些好的性能是以犧牲原始McEliece和Niederreiter方案的安全性為代價的。

隨著最新研究的推進，大量的改進方案均被證實存有漏洞。文獻[4-7]是近幾年出現對于QC密碼方案的攻擊，指出現有QC-LDPC(Quasi-Cyclic Low-Density Parity-Check)編碼密碼方案和QC-MDPC(Quasi-Cyclic Medium-Density Parity-Check)編碼密碼方案均存有漏洞。文獻[8]指出通過Goppa碼或者交替碼的子族來生成緊湊公鑰的方案是存有漏洞的，即現有QC/QD/QM編碼密碼方案是存有漏洞的。文獻[9-10]指出采用Goppa碼的原McEliece方案在某些參數下存有與隨機碼相區分的區分器，并對其進行了密鑰恢復攻擊。文獻[11]采用GRS碼的平方碼構造與隨機碼相區分的區分器，對一些GRS碼的變形方案進行了多項式時間的密鑰恢復攻擊。特別強調的是，現有的編碼密碼方案均無法抵抗信息集攻擊(Information Set Decoding, ISD)，且這種攻擊方法在不斷的優化和應用[12-17]。

2016年，Baldi等[18]從一個嶄新的角度對McEliece密碼方案進行了改進，將現有McEliece密碼方案中的置換矩陣P改為Q=R+T，前者為稠密的，后者為稀疏的，以提高密鑰隱藏能力，設計的方案在某些參數下可以抵抗區分攻擊，但是無法抵抗ISD。

本文認同Baldi等[18]的觀點，即單純地用置換矩陣去隱藏密鑰的方法是不能夠真正地隱藏密鑰信息，產生的公開碼字與原秘密碼字是置換等價的。為此本文對Niederreiter密碼方案中的置換矩陣P進行改進，使P為隨機矩陣，唯一的要求是其列重的最大值固定。需要注意的是，在線性碼糾錯能力有限的情況下，這樣改進的同時會大幅度降低錯誤向量e的漢明重量，進而指數級地降低ISD的代價。為此本文對置換矩陣P改進的同時，對錯誤向量e也進行了隨機拆分，使其漢明重量變大且未知(也可能超過線性碼的糾錯能力)，以抵抗ISD，由此實現對Niederreiter密碼方案的改進。GRS碼具有靈活的參數選取方法和有效的譯碼方法，本文借鑒文獻[18]的方法，用GRS碼測試方案的性能；結果表明，改進Niederreiter密碼方案可以抵抗區分攻擊和ISD，表現出較好的性能，在量子時代下的生存力增強。

1 基礎知識

1.1 編碼理論中的NPC問題

1978年，Berlekamp等[1]證明了隨機線性碼的譯碼問題是NPC問題，為基于編碼的公鑰密碼方案的設計奠定了理論基礎。其表述如下：

1.2 Niederreiter密碼方案

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

1.2.1 密鑰生成

隨機選取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后，計算cA-1T=mH′TA-1T=mPTHTATA-1T=mPTHT，利用Goppa碼的快速譯碼算法可得m′=mPT，進而得m=m′(PT)-1。

在此本文對Niederreiter密碼方案進行如下闡述說明:第一，方案中的公鑰H′=AHP通過私鑰H左乘可逆矩陣A和右乘置換矩陣P得到；由矩陣的性質可知，矩陣的左乘相當于對矩陣的行作變換，故私鑰H左乘可逆矩陣A并不能改變線性碼的性質，因此無法真正地隱藏私鑰H；矩陣的右乘相當于對矩陣的列作變換，私鑰H通過右乘置換矩陣P得到HP，其作用僅僅是對其進行了簡單的置換，校驗矩陣HP與校驗矩陣H生成的碼字是置換等價的，因此也無法真正地將私鑰H隱藏；即公鑰H′沒有真正地將私鑰H的信息完全隱藏，這是現有編碼密碼方案容易遭受區分攻擊的根本原因。第二，方案中的明文信息的漢明重量固定且公開，這是現有編碼密碼方案容易遭受ISD的根本原因。

2 Niederreiter密碼方案的改進

本文從兩方面對Niederreiter密碼方案進行改進：第一，對方案中的置換矩陣P進行改進，使P為隨機矩陣，唯一的要求是其列重的最大值固定；第二，對錯誤向量e進行改進，隱藏其漢明重量。方案如下。

2.1 密鑰生成

(n-k)×n階矩陣H為二元(n,k,d)GRS碼的校驗矩陣，其糾錯能力為t，快速譯碼算法ΨH(t)。隨機將H拆分為兩個矩陣H1和H2，使得H=H1+H2。隨機選取三個(n-k)×(n-k)階可逆矩陣A、B和C，隨機選取一個n×n可逆矩陣Q且其列重最大值為w(無需公開)。分別計算H′=AH1Q、H″=BH2Q、H?=CHQ、ts=?t/w」。將(H′,H″,H?,ts)公開，(A-1T,B-1T,C-1T,Q-1T,ΨH(t))秘密保存。

2.2 加密過程

2.3 解密過程

當接收方收到密文(c1,c2,c3)后，進行下列運算：

c3C-1T=e2H?TC-1T=e2QTHTCTC-1T=e2QTHT

因為e=e1+e2、H=H1+H2，故c1A-1T+c2B-1T+c3C-1T=eQTHT；此時，wt(eQT)=ts·w=?t/w」·w≤t，故在GRS碼的糾錯能力之內，因此利用GRS碼的譯碼算法ΨH(t)對c1A-1T+c2B-1T+c3C-1T進行譯碼可得到eQT，進而得到e=eQT·Q-1T，解碼即可得到明文m。

3 安全性分析

目前對于Niederreiter密碼方案的攻擊方法有兩類：區分攻擊和ISD。前者試圖將公鑰與隨機矩陣區分開來，進一步實施密鑰恢復攻擊；后者旨在從獲取的密文直接恢復明文。

3.1 區分攻擊

區分攻擊的思想是將一個隨機矩陣與公開碼字的生成矩陣或者校驗矩陣(即公鑰)區分開來，針對不同的方案可以實施具體的區分操作，進行密鑰恢復攻擊，且其花費的代價較小，如文獻[9-11，19]。

在改進的Niederreiter密碼方案中，本文將私鑰矩陣H右乘了一個隨機矩陣Q，得到的矩陣HQ已經不再是某個線性碼的校驗矩陣，具有隨機性，且攻擊者不知道密文中e1和e2的漢明重量；此時攻擊者無法將公鑰中的(H′,H″,H?)與隨機矩陣區分開來，無法進行密鑰恢復攻擊，進而無法構造等價碼進行解碼操作，所以本方案可以抵抗區分攻擊。

3.2 ISD

4 性能分析

表1 兩種方案的密鑰尺寸比較(F2)

5 結語

基于編碼的公鑰密碼方案作為抗量子方案的備用方案之一，具有較高的安全性和較好的性能，很有可能成為量子計算機時代下保障數據安全的關鍵技術。本文對Niederreiter密碼方案進行了深入的闡述，對現有研究現狀作了歸納總結；結合Baldi等[18]的最新研究成果，并受其啟發，對原Niederreiter密碼方案中的置換矩陣和錯誤向量進行了改進，對改進Niederreiter密碼方案的安全性進行了深入細致的分析，利用GRS碼測試了方案的性能。分析表明，改進Niederreiter密碼方案可以抵抗區分攻擊和ISD；測試表明，改進方案表現出較好的性能，在量子時代下的生存力增強。需要注意的是，改進方案從理論上證明了其優越性，在具體的應用場景下，應根據具體的需求靈活地選取合適的線性碼和參數。