Niederreiter公鑰密碼方案的改進(jìn)

劉相信，楊曉元

(網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室(武警工程大學(xué))，西安 710086)(*通信作者電子郵箱1125424226@qq.com)

0 引言

基于編碼的密碼方案具有抗量子的特性和簡(jiǎn)單的加解密過程，是當(dāng)今抗量子密碼方案的佼佼者。1978年，Berlekamp等[1]證明了隨機(jī)線性碼的譯碼問題是一個(gè)非確定性多項(xiàng)式完全困難(Non-deterministic Polynomial Complete, NPC)問題，為基于編碼的公鑰密碼方案的設(shè)計(jì)奠定了理論基礎(chǔ)，同年McEliece[2]利用此困難問題提出第一個(gè)基于Goppa碼的公鑰密碼方案——McEliece公鑰密碼方案。該方案可抗量子攻擊、加解密速度快、實(shí)現(xiàn)簡(jiǎn)單。方案中錯(cuò)誤向量的漢明重量固定且公開，易導(dǎo)致密文對(duì)明文信息的泄露，所以必須選取較大的公鑰尺寸來保證計(jì)算安全性，因此該方案公鑰尺寸過大，實(shí)用性差。1986年，Niederreiter[3]對(duì)McEliece公鑰密碼方案進(jìn)行了改進(jìn)，提出了一種Niederreiter公鑰密碼方案，該方案從另一個(gè)角度利用了隨機(jī)線性碼的譯碼困難問題，McEliece公鑰密碼方案隱藏的是Goppa碼的生成矩陣，而該方案隱藏的是Goppa碼的校驗(yàn)矩陣，此時(shí)公鑰尺寸有所變小，但還是沒有達(dá)到實(shí)用要求。為了降低方案的密鑰尺寸、提高方案的性能，同時(shí)保持方案的安全性，學(xué)者們紛紛利用一些具有較好性質(zhì)的線性碼來代替原方案的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)碼、代數(shù)幾何碼等，這些方案雖然具有較好的性能，但是這些好的性能是以犧牲原始McEliece和Niederreiter方案的安全性為代價(jià)的。

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

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

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

1 基礎(chǔ)知識(shí)

1.1 編碼理論中的NPC問題

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

1.2 Niederreiter密碼方案

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

1.2.1 密鑰生成

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

1.2.2 加密過程

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

1.2.3 解密過程

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

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

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

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

2.1 密鑰生成

(n-k)×n階矩陣H為二元(n,k,d)GRS碼的校驗(yàn)矩陣，其糾錯(cuò)能力為t，快速譯碼算法ΨH(t)。隨機(jī)將H拆分為兩個(gè)矩陣H1和H2，使得H=H1+H2。隨機(jī)選取三個(gè)(n-k)×(n-k)階可逆矩陣A、B和C，隨機(jī)選取一個(gè)n×n可逆矩陣Q且其列重最大值為w(無需公開)。分別計(jì)算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 解密過程

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

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

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

3 安全性分析

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

3.1 區(qū)分攻擊

區(qū)分攻擊的思想是將一個(gè)隨機(jī)矩陣與公開碼字的生成矩陣或者校驗(yàn)矩陣(即公鑰)區(qū)分開來，針對(duì)不同的方案可以實(shí)施具體的區(qū)分操作，進(jìn)行密鑰恢復(fù)攻擊，且其花費(fèi)的代價(jià)較小，如文獻(xiàn)[9-11，19]。

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

3.2 ISD

4 性能分析

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

5 結(jié)語(yǔ)

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