基于編碼的加密體制綜述

李 喆，韓益亮，李 魚，朱率率，楊曉元

(武警工程大學 密碼工程學院， 陜西 西安 710086)

2019年10月26日，第十三屆全國人大常委會第十四次會議通過了《中華人民共和國密碼法》，通過制度的形式把信息安全的重要性上升為國家意志?，F(xiàn)在社會中的銀行交易、無人駕駛、衛(wèi)星通信、指揮控制等方面，密碼學具有不可替代的作用。隨著科學技術(shù)的飛速發(fā)展，量子計算機逐漸進入人們的視野，其強大的計算能力備受青睞，量子計算機強大的計算能力在諸多方面帶來了極大的便利，但是其強大的計算能力也對經(jīng)典計算機(圖靈機)條件下基于數(shù)論的密碼體制帶來了嚴重的威脅。目前，大部分密碼體制都依賴于經(jīng)典計算機在多項式時間內(nèi)無法有效解決的兩個計算困難問題，即大整數(shù)分解和離散對數(shù)問題。Shor[1]提出了可以在多項式時間內(nèi)破解大整數(shù)問題和離散對數(shù)問題的量子算法，這一算法使得經(jīng)典的公鑰密碼方案極不安全，RSA[2]、離散橢圓曲線方案(Elliptic Curve Cryptography, ECC)[3]等密碼體制的安全性受到挑戰(zhàn)。因此，為了應(yīng)對量子計算機帶來的挑戰(zhàn)，許多密碼學者嘗試構(gòu)造可以抵御量子計算的新型密碼體制，即抗量子計算密碼體制(Post-Quantum Cryptography, PQC)。PQC主要有五種[4]：基于編碼的公鑰密碼體制、基于格的公鑰密碼體制、基于哈希樹的公鑰密碼體制、基于多變量的公鑰密碼體制、超奇異橢圓曲線同源密碼。

2015年，美國和歐盟分別推動抗量子密碼的標準化進程[5]。2018年，美國國家標準與技術(shù)研究院(National Institute of Standards and Technology, NIST)面向全球征集抗量子密碼，舉辦第一輪PQC算法征集會議，基于編碼的密碼體制占有很大的比例[6]。2019年，NIST評選第二輪后量子密碼算法，基于編碼的密碼方案依然具有很大的比重[7]。在未來的研究過程中，基于編碼的密碼體制依然是研究的熱點。

為了使我國后量子密碼算法同步推進，國家密碼局于2018年面向全國征求密碼算法，目前，全國密碼算法設(shè)計競賽第一輪算法評選結(jié)果已經(jīng)揭曉，第二輪算法評選正在進行中，預(yù)計于2022年左右開展抗量子密碼算法標準化工作。

基于編碼的密碼體制最初是由McEliece[8]提出的，其一般性譯碼問題屬于一般線性碼的非確定性多項式完全問題。到目前為止，原始的方案依然具有安全性。該體制采用Goppa碼，具有加解密速度快、計算復(fù)雜度低的優(yōu)點。但現(xiàn)實中沒有大量使用該體制的原因是，其密鑰儲存空間太大、碼率低。Niederreiter[9]提出了基于GRS碼的Niederreiter密碼體制，相較于McEliece體制，該體制密鑰存儲空間減少，但仍然不能投入到實際使用中。因此，許多學者為了減小密鑰的尺寸，推動提高密碼方案的實用化，改進McEliece體制，提出了用其他結(jié)構(gòu)更加緊湊的編碼代替Goppa碼，例如準循環(huán)低密度奇偶校驗碼(Quasi-Cyclic Low-Density Parity Check, QC-LDPC)碼[10]、Polar碼[11]、中密度奇偶校驗碼(Medium Density Parity Check, MDPC)碼[12]、Gabidulin碼[13]、低秩奇偶校驗(Low Rank Parity Check， LRPC)碼[14]，改進的密碼方案減少了密鑰長度，但容易受到攻擊[15]。

后來，基于編碼的方案進一步發(fā)展，一些學者對McEliece體制的結(jié)構(gòu)進行變型。Wang[16]在生成矩陣的每一列中都嵌入了隨機列并構(gòu)造了一種線性隨機碼的加密方案RLCE。Kim等[17]通過將McEliece和Niederreiter相結(jié)合，利用秩度量的編碼構(gòu)造了McNie密碼方案。劉相信等[18]通過隱藏明文的漢明重量，將校驗矩陣拆分構(gòu)造了一種新型密碼方案。Mostafa[19]通過利用錯誤向量的漢明重量大于編碼最小距離的性質(zhì)，構(gòu)造了一種不同的密碼方案。

本文根據(jù)編碼的性質(zhì)，總結(jié)了基于漢明度量編碼和基于秩度量的加密方案，歸納了目前發(fā)展的現(xiàn)狀，展望了未來的發(fā)展方向。介紹了目前基于McEliece方案進行結(jié)構(gòu)改變的新型密碼方案，為將來研究抗量子密碼方案提供了新的方向。綜述了目前對基于編碼的密碼方案主流的攻擊方法。

1 基于糾錯碼的密碼體制

1.1 McEliece加密體制

該密碼體制包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①隨機生成長度為n，維度為k的k×n階生成矩陣G，其中最小距離d≥2t+1；

②生成k×k階隨機非奇異可逆矩陣S；

③生成n×n階二元隨機置換矩陣P。

G左乘隨機非奇異可逆矩陣S，右乘隨機置換矩陣P，得到擾亂后的k×n階矩陣Gpub，Gpub=SGP。其中，公鑰為Gpub和t；私鑰為S、DC、P，DC是編碼C的譯碼算法。

2)加密過程如下：

①隨機選擇錯誤向量e∈Fn，其中，F(xiàn)n為有限域上的n維線性向量空間，wt(e)≤t；

②發(fā)送方利用接收方的公鑰Gpub對發(fā)送的消息m進行加密，得到密文c。c=mGpub⊕e，其中m∈Fk。

3)解密過程如下：

①接收方收到密文c，利用自己的私鑰對密文進行解密；

②cP-1=(mS)G⊕eP-1。

利用編碼的譯碼算法進行譯碼，mS=DC(cP-1)，m1=mS，m=m1S-1。

目前，這一方案的研究目標和發(fā)展方向主要有以下三類：

1)采用Goppa碼的原始方案，到目前為止都足夠安全，下一步的關(guān)注點是，在保證安全性的基礎(chǔ)上，分析目前存在的攻擊類型，合理選用參數(shù)，對Goppa碼進行變型，如交織Goppa碼；

2)進一步分析原始方案存在的攻擊，尤其是要關(guān)注側(cè)信道攻擊，在模擬仿真平臺上實現(xiàn)密碼方案，通過側(cè)信道攻擊檢驗方案的安全性；

3)分析McEliece密碼體制延展性以及消息重放攻擊，進一步研究方案保證其安全性。

1.2 Niederreiter密碼體制

Niederreiter采用McEliece的對偶形式提出了Niederreiter體制，與McEliece公鑰密碼體制不同的是，Niederreiter密碼體制采用一致校驗矩陣來構(gòu)造加密算法。同樣地，該密碼體制包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①系統(tǒng)參數(shù)：n,t∈N。

②生成M：(n-k)×(n-k)階可逆矩陣。

③生成H：糾正t個錯誤的編碼C的(n-k)×n階校驗矩陣。

④生成P：n×n階隨機置換矩陣。

⑤計算Hpub=MHP。

2)加密過程如下：

計算s=HpubeT，其中，e∈{0,1}n。

3)解密過程如下：

計算M-1s=HPeT，利用伴隨式譯碼算法恢復(fù)PeT，計算eT=P-1PeT。

McEliece體制的公鑰為k×nbit，Niederreiter公鑰體制的公鑰為(n-k)×nbit，采用這種對偶變型的密碼方案，可以有效減小密鑰長度。在McEliece體制中，攻擊者可以通過兩個被加密消息之間的關(guān)系來確定錯誤位置。而Niederreiter公鑰體制并不存在延展性，所以不會遭到密文的延展性攻擊和消息重放攻擊。

目前，這一方案的研究目標和發(fā)展方向主要有以下兩類：

1)研究重點逐漸聚焦在采用Niederreiter 密碼體制進行簽名方案的構(gòu)造；

2)研究改進Niederreiter 密碼體制在硬件上面的實現(xiàn)，提高效率和實用性。

1.3 研究現(xiàn)狀

目前關(guān)于McEliece密碼體制的研究大概分為兩類：

1)研究改進McEliece原始方案的結(jié)構(gòu)分析其原始方案的底層編碼，選擇性能更優(yōu)的碼字來替代原始方案的Goppa碼，達到減小密鑰長度的目的，使其投入到實際運用中；

2)研究分析McEliece原始方案及其變型的安全性，分析其存在安全性問題的原因，進一步完善密碼方案。

2 采用其他編碼改進的McEliece體制

2.1 基于漢明度量編碼的密碼方案

2.1.1 基于LDPC/MDPC碼的密碼方案

采用LDPC碼或MDPC碼代替原來的Goppa碼，LDPC碼或MDPC碼具有有效的迭代譯碼算法，可以明顯降低譯碼錯誤率，并且采用其循環(huán)結(jié)構(gòu)可以有效減小公鑰尺寸。MDPC碼奇偶校驗矩陣的行列密度比LDPC碼高。

Monico等[20]提出用LDPC碼代替原來的Goppa碼。Baldi等[10]提出基于QC-LDPC碼的McEliece體制，該體制可以減小密鑰大小，具有一定的安全性，采用比特迭代譯碼算法可以快速解碼。但其對偶碼存在低維數(shù)的漏洞，易被攻破。Baldi等[21]提出改進的QC-LDPC變型，其中可逆矩陣和置換矩陣都采用稀疏矩陣，提高了安全性，可以抵抗結(jié)構(gòu)化攻擊。Shooshtari等[22]指出，Baldi改進后的方案容易受到信息集譯碼攻擊(Information Set Decoding, ISD)，原因是改進后的QC-LDPC方案中，會出現(xiàn)循環(huán)矩陣的循環(huán)塊為偶數(shù)的情況。

Misoczki等[23]提出基于QC-MDPC碼的McEliece體制來抵御已知的對LDPC碼的攻擊，同時減小了密鑰量。Guo等[24]通過研究譯碼錯誤率與密鑰距離譜之間的聯(lián)系，對文獻[23]提出的QC-MDPC方案進行了密鑰恢復(fù)攻擊。Fab?i?等[25]同樣通過大量實驗尋找置換矩陣Q與譯碼錯誤率之間的關(guān)聯(lián)性，對密鑰進行恢復(fù)攻擊。

Moufek等[26]提出一種新的思路，將兩種奇偶校驗碼結(jié)合使用。該方案通過QC-LDPC碼和QC-MDPC碼的級聯(lián)使用，可以減少密鑰長度，采用偽隨機生成矩陣具有一定的安全性。Dragoi等[27]對文獻[26]改進的方案進行安全性分析，發(fā)現(xiàn)文獻[26]改進的方案存在極大的漏洞。

目前，這一方案的研究目標和發(fā)展方向主要有以下兩類：

1)研究QC-LDPC碼和QC-MDPC碼的性質(zhì)，進一步改進方案的譯碼算法，減小譯碼錯誤率，提高譯碼效率；

2)分析采用QC-LDPC碼和QC-MDPC碼密碼方案的結(jié)構(gòu)，研究低重量搜索攻擊對其密碼方案的影響，并對其安全性做進一步分析。

2.1.2 基于Polar碼的密碼方案

Polar碼是目前可以在理論上證明趨于Shannon限的編碼。Arikan提出Polar碼[28]，并深入研究Polar碼的性質(zhì)，后來眾多學者進一步研究了Polar碼的結(jié)構(gòu)及性能。

首先，Polar碼比Goppa碼等其他編碼糾錯能力更強；其次，極化碼的連續(xù)消除譯碼算法比Goppa碼的譯碼效率更高，降低了解密過程中的計算復(fù)雜度。通過研究極性碼的性質(zhì)，Mahdlavifar等嘗試把極化碼應(yīng)用到密碼學中，并取得了一定的進展[29]。Hooshmand 等[30]利用極化碼的性質(zhì)構(gòu)造對稱密碼體制。Hooshmand 等[31]為了避免主動攻擊和被動攻擊，通過分析有限長度極化碼的性質(zhì)，提出了基于物理層加密(Physical Layer Encryption, PLE)方案[32]，在合法的通信雙方建立安全可靠的保密通信。

Shrestha等[33]將Polar碼應(yīng)用到編碼密碼中，提出了基于Polar碼的McEliece密碼方案。Hooshmand等[34]在原有方案的基礎(chǔ)上，優(yōu)化了基于Polar碼的McEliece密碼方案，減少了密鑰存儲空間。但是，Bardet等[35]分析了文獻[34]中提出的基于Polar碼的McEliece密碼方案的結(jié)構(gòu)，提出了密鑰恢復(fù)攻擊的方法。這種攻擊方法可以獲得文獻[33]方案解密密文所需要的任何信息。楊超等[36]利用Polar碼譯碼算法的低復(fù)雜性構(gòu)造Niederreiter 公鑰密碼體制，并進行了仿真分析。Drǎgoi等[37]證明任何基于弱遞減單項式碼的密碼方案都有可能受到密鑰恢復(fù)攻擊，基于Polar碼的密碼方案也不例外。

目前，這一方案的研究目標和發(fā)展方向主要有四類：

1)進一步研究Polar碼，研究其極化現(xiàn)象的原因，提高中等長度碼字的編碼效率；

2)進一步研究其譯碼算法，分析連續(xù)消除算法，列表連續(xù)刪除譯碼算法，加入循環(huán)冗余檢驗位的列表連續(xù)刪除算法的性能，在提高譯碼正確率的同時提高譯碼效率；

3)把Polar碼的極化性質(zhì)應(yīng)用到簽名領(lǐng)域，把極化性質(zhì)與簽名有效結(jié)合，提高簽名的效率；

4)通過把Polar碼與其他性能好的碼字相級聯(lián)，克服了Polar碼在中等長度時性能差的缺點，總體上使密碼方案的效率與安全性達到最佳。

2.1.3 基于RS碼/GRS碼的密碼方案

該體制采用RS碼或GRS碼代替McEliece原始方案中的Goppa碼。GRS碼存在有效譯碼算法，可以有效減少公鑰長度。

基于GRS碼的Niederreiter體制變型被Silelnikov等完全攻破，當公鑰Hpub的列元素可以表示為支撐元素的多項式，利用各列元素的關(guān)系可求出支撐向量和常數(shù)向量[38]。Wieschebrink[39]提出用GRS碼與隨機碼并列的級聯(lián)碼避免了文獻[38]中提到的攻擊。Couvreur等[40]針對三種GRS變型，采用GRS碼的平方碼構(gòu)造與隨機碼相區(qū)分的區(qū)分器，進而采用密鑰恢復(fù)攻擊，能夠在多項式時間內(nèi)攻破文獻[39]所采用的級聯(lián)碼方案。

Márquez-Corbella等[41]提出用兩個GRS碼構(gòu)造“u/u+v”的變型。目前，這一方案的研究目標和發(fā)展方向主要有兩類。

1)進一步研究文獻[38]針對基于GRS碼的密碼體制提出的攻擊方法，分析這種攻擊是否會對McEliece體制原始方案的安全性造成影響；

2)進一步研究采用GRS碼的Niederreiter體制，利用Niederreiter體制可以抵抗反應(yīng)攻擊和延展性攻擊的優(yōu)點，深究其本質(zhì)，設(shè)計可以達到原始方案的新型密碼體制。

2.2 基于秩度量編碼

基于漢明度量的McEliece密碼，使用Goppa碼或MDPC碼，其缺點是有相對較大的密鑰。原始基于編碼的密碼方案是基于具有漢明度量的Goppa碼，實際上可以考慮基于秩度量的編碼。秩度量的特別之處在于譯碼問題的實際難度隨著參數(shù)的增大而迅速增大。在同樣安全級別下，基于秩度量的密碼方案比基于漢明度量的密碼方案更安全。與基于漢明度量的編碼相比，秩度量中已知的具有高效譯碼算法的碼族很少?？梢杂糜贛cEliece方案的兩大類秩度量編碼，即Gabidulin碼和LRPC碼。基于LRPC碼的密碼方案，因其低代數(shù)結(jié)構(gòu)，逐漸成為研究的熱點。

Kshevetskiy等對基于Gabidulin碼的原始方案進一步優(yōu)化參數(shù)，在保證安全性的同時進一步減少密鑰尺寸[42]。Overbeck[43]針對基于秩度量編碼的原始方案及其變型進行分析，提出一種有效的攻擊方法。該攻擊主要是對基于秩度量碼的密碼方案進行分析，發(fā)現(xiàn)Gabidulin碼包含一個巨大的向量空間不變作用下的弗羅貝尼烏斯自同構(gòu)。后來，許多學者試圖用其他擾亂矩陣來避免存在的已知其他攻擊，但是Gabidulin代碼自身存在的問題仍沒有消失[44]。換句話說，對編碼進行擾亂的生成器的一些核心部分仍然存在向量空間不變的問題，這就增加了系統(tǒng)的弱點。

為了抵御文獻[43]提及的攻擊，Loidreau[45]對維度等參數(shù)進行優(yōu)化，提出一種基于新型秩度量的編碼體制。Coggia等[46]對文獻[45]提出的密碼方案進行安全性分析，指出當λ=2時，攻擊者有超過50%的可能性用區(qū)分器把公共代碼和隨機碼區(qū)分開，利用這個區(qū)分器可以在多項式時間內(nèi)實現(xiàn)密鑰恢復(fù)攻擊。Aragon等[47]提出一種新的譯碼算法，該方法可以降低以往方案的譯碼錯誤概率。Aragon等[48]利用LRPC碼在選擇明文攻擊下的不可區(qū)分性(INDistinguishability-Chosen ciPhertext Attacks, IND-CPA)情況解密失敗條件下，采用一種代數(shù)方法對解密失敗發(fā)生的情況進行建模，然后根據(jù)攻擊者可以利用IND-CPA方案中發(fā)送給解密oracle的錯誤這一事實，對比文獻[24]中提出的對QC-MDPC碼密鑰恢復(fù)攻擊，Aragon等嘗試把這種攻擊應(yīng)用到基于秩度量的密碼方案。

與漢明度量相比，秩度量的優(yōu)勢比較明顯，在一定的參數(shù)選擇范圍下，通過搜索低重量攻擊的復(fù)雜度會明顯提升。

目前，這一方案的研究目標和發(fā)展方向主要有以下兩類：

1)分析研究LRPC碼的結(jié)構(gòu)，改進譯碼算法以減小LRPC碼的譯碼錯誤率；

2)尋找隱藏Gabidulin碼結(jié)構(gòu)的方法，使其能夠抵抗文獻[43]提及的攻擊。

3 McEliece加密方案結(jié)構(gòu)的變型

3.1 McNie方案

Kim等[17]提出將McEliece方案和Niederreiter方案結(jié)合的McNie加密方案，該方案采用4-循環(huán)低秩奇偶校驗碼，能夠抵抗目前已知的結(jié)構(gòu)化攻擊，減小了密鑰的大小。Lau等[49]針對McNie方案提出了一種密鑰恢復(fù)攻擊，能夠恢復(fù)McNie方案所有參數(shù)下的密鑰，進而提出了一種新的基于Gabidulin碼的McNie方案，該新方案不存在譯碼失敗率。Aragon等[48]對McNie方案采用消息恢復(fù)攻擊和改進的信息集譯碼攻擊，使McNie方案的安全級別減半。Kim等[50]在文獻[49]改進的基礎(chǔ)上，進一步提出了McNie2-Gabidulin方案，該方案具有IND-CPA安全性，密鑰尺寸小于其他沒有譯碼失敗概率的密碼方案。

1)密鑰生成過程如下：

①對于給定的參數(shù)n和r，產(chǎn)生下列矩陣:

G′：域Fqm上的信息數(shù)為k、最小距離l>n-k碼C的k×n階生成矩陣。

S：(n-k)×(n-k)階可逆矩陣。

H：一個能夠糾正r個錯誤的碼C的(n-k)×n階校驗矩陣。

P：n×n階隨機置換矩陣。

②計算矩陣F=G′P-1HTS。

公鑰：(G′,F)。

私鑰：(S,H,P)。

c1=mG′+e

(1)

c2=mF

(2)

3)解密過程如下：

S′=c1P-1HT-c2S-1=eP-1HT

(3)

接收者利用譯碼算法

φH(S′)=eP-1

(4)

c1-e=mG′

(5)

得到m。

把McNie體制和McEliece類比，則

G′=SGPF=G′P-1HTS=(SGP)P-1HTS

(6)

因為GHT=0，所以F=0，推出c2=0，c1=mG′+e，這就是McEliece體制的原始方案。

目前，這一方案的研究目標和發(fā)展方向主要有以下兩類：

1)分析研究McNie方案，找到McNie方案沒有入圍第二輪抗量子候選方案的原因；

2)尋找隱藏Gabidulin碼結(jié)構(gòu)的方法，使其能夠抵抗文獻[43]提及的攻擊。

3.2 改進版Niederreiter密碼方案

劉相信等[18]對錯誤向量e的重量進行了隱藏，提出的Niederreiter密碼方案改進版可以抵抗ISD攻擊。

1)密鑰生成過程如下：

①選擇二元(n,k,t)Goppa碼，糾錯能力為t，校驗矩陣為(n-k)×n，快速譯碼算法為βHt。

②將H隨機拆分成兩個矩陣H1、H2(H=H1+H2)，隨機選取三個階數(shù)為(n-k)×(n-k)可逆矩陣S1、S2、S3，選取一個n×n階的可逆置換矩陣P，分別計算H′=S1H1P，H″=S2H2P，H?=S3HP。

③公鑰：(H′,H″,H?,t)。

④私鑰：(S1,S2,S3,T,βHt)。

2)加密過程如下：

將明文m編碼成漢明重量t的向量e，并將e拆分為兩個向量e1、e2,且e=e1+e2，wt(e1)=t1，wt(e2)=t2(t≠t1≠t2)。計算

(7)

將(c1,c2,c3)發(fā)送給接收方。

3)解密過程：收到(c1,c2,c3)后，計算

(8)

(9)

(10)

因為H=H1+H2，e=e1+e2。所以

(11)

利用譯碼算法βHt進行譯碼可得ePT，再利用私鑰P，即可得到密文e=ePT(PT)-1。

目前，這一方案的研究目標和發(fā)展方向主要有兩類：

1)研究本方案的安全性，隱藏后的錯誤向量是否可以保證密碼方案的安全；

2)選擇其他編碼進一步減少密鑰長度，例如LRPC碼。

3.3 改進錯誤向量的密碼方案

Mostafa[19]在其博士論文中提出Mostafa Esmaeili方案，該方案在McEliece加密的基礎(chǔ)上，改變了McEliece的結(jié)構(gòu)，不再利用可逆矩陣和置換矩陣對生成的矩陣進行擾亂，主要利用漢明重量大于編碼最小距離的錯誤向量，構(gòu)造了新型的密碼方案。該密碼方案與McEliece方案構(gòu)造過程類似，包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①G：域F上的維度為k、最小距離d≥2t+1的碼C的k×n階生成矩陣。

②H：域F上的(n-k)×n階的校驗矩陣。

③S：(n-k)×(n-k)隨機非奇異可逆矩陣。

④公鑰：(G，S(H-1)T)。

⑤私鑰：HTS-1。

2)加密過程如下：

發(fā)送者選擇長度為l1的消息m，隨機選擇長度為l2的隨機比特串r(其中l(wèi)=l1+l2)，將隨機比特串r與明文m并聯(lián)，得到[r|m]。隨機選擇n-k位的向量s，計算sS(H-1)T，假如wt(sS(H-1)T)

發(fā)送者使用接收者的公鑰對并聯(lián)后的消息進行加密，得到

c=[r|m]G+sS(H-1)T

(12)

3)解密過程如下：

接收者收到密文c后，使用自己的私鑰對密文進行解密。

cHTS-1=([r|m]G+sS(H-1)T)HTS-1=s

(13)

接收者通過自己的私鑰對密文進行解密得到s，然后用向量s乘以公鑰S(H-1)T，得到sS(H-1)T，然后計算

[r|m]G=c+sS(H-1)T

(14)

利用譯碼算法對[r|m]G進行解密，得到[r|m]，把長度為l2的隨機比特串r丟棄，最后得到明文m。

目前，這一方案的研究目標和發(fā)展方向主要有三類：

1)研究編碼的性質(zhì)，尋找適合構(gòu)造本方案的編碼；

2)研究本密碼方案是否可以抵御其他類型的攻擊；

3)利用本方案中漢明重量大于編碼最小距離的錯誤向量這種新的思想，嘗試把這種新的思想應(yīng)用于簽名、密鑰交換、密鑰封裝等密碼學原語中。

4 安全性分析

對基于編碼密碼體制的攻擊，主要有密鑰恢復(fù)攻擊[51]和信息集譯碼攻擊[52]等。

1)密鑰恢復(fù)攻擊。原始McEliece體制采用的是Goppa碼，具有一些隨機碼的特征。Gpub=SGP，攻擊者只有找到擾亂矩陣S、置換矩陣P，才有可能恢復(fù)出生成矩陣G，最后才能通過Goppa碼的快速譯碼算法解碼密文。假如攻擊者找不到擾亂矩陣S、置換矩陣P，無法恢復(fù)出生成矩陣G，也就無法達到破譯密文的目的。事實上，可逆矩陣S、置換矩陣P的碼族非常大，通過找到可逆矩陣S、置換矩陣P這種方法來恢復(fù)生成矩陣G在理論上是不可行的。

3)區(qū)分器攻擊。當區(qū)分器攻擊密碼方案時，區(qū)分器利用公鑰矩陣不具有隨機性，則將公鑰矩陣和隨機二進制矩陣進行區(qū)分。Faugère 等[54]發(fā)現(xiàn)采用的編碼和密碼方案的秩具有一定的相關(guān)性。當采用的Goppa碼的碼率接近于1，攻擊者構(gòu)造了一個Goppa碼區(qū)分器，很容易將隨機碼和Goppa碼區(qū)分。區(qū)分器攻擊的基本思想就是利用公共碼和隨機碼的可區(qū)分性，區(qū)分密碼方案所采用的代碼是否為隨機碼，從而達到攻擊的目的。

4)側(cè)信道攻擊。側(cè)信道攻擊通過檢測密碼方案實現(xiàn)過程中的一些物理現(xiàn)象，例如軟件的運行時間或硬件的功耗來分析密碼方案，以達到攻擊的目的。Strenzke等[55]提出對McEliece公鑰體制的側(cè)信道攻擊，Strenzke指出在解密過程中采用Patterson譯碼算法，時間功耗攻擊是非常有效的，在密鑰生成時能量攻擊可以對校驗矩陣的構(gòu)造造成極大的破壞。如果編碼的支撐向量已知，則在密鑰生成過程中的奇偶校驗矩陣構(gòu)造中，通過分析不可約Goppa多項式的求值所帶來的功耗，可以得到不可約Goppa多項式。對Patterson譯碼算法的定時攻擊使用了錯誤定位多項式的次數(shù)恰好等于接收到單詞中的錯誤數(shù)量這一事實。因此，為了得到明文，可以嘗試請求對偽密碼文本進行解密。Shoufan等[56]在文獻[55]分析的基礎(chǔ)上，對原始攻擊做了進一步分析。Heyse等[57]分析了解密過程中可逆矩陣和置換矩陣的功耗攻擊。Molter等[58]用所測量的功耗軌跡圖峰值信息取代時序信息，對時序分析和錯誤注入相結(jié)合的攻擊方法進行了研究。Chen等[59]提出一種分析基于編碼的差分攻擊功率的新型方法，該攻擊采用的方法是計算硬件實現(xiàn)上選定的基于QC-MDPC碼單密文的特征值。Chen等[60]采用與校驗矩陣大小相同的Boolean的方法隱藏信息,進一步對密鑰和特征值進行優(yōu)化。Santini等[61]研究了基于稀疏對偶校驗碼的密碼方案,在采用循環(huán)校驗碼的情況下，通過新的側(cè)信道攻擊方法恢復(fù)出比目前已知的其他攻擊更多的信息。

5)其他攻擊。由于McEliece公鑰密碼體制存在延展性[62]，攻擊者可以通過觀察兩個密文之間的關(guān)聯(lián)性來確定錯誤向量。另外一種反應(yīng)攻擊[63]則是對密文加以修改，合法接收方收到修改密文，攻擊者觀察其反應(yīng)。消息在信道傳遞的過程中，攻擊者非法截取密文，然后對截取的密文添加更多的錯誤位，如果接收方譯碼失敗，表明修改的錯誤位在原來的錯誤向量e上。攻擊者利用這種方法，最多重復(fù)k次就能恢復(fù)一個沒有錯誤的信息。

5 展望

目前，基于編碼的體制主要采用兩類具有快速譯碼算法的碼：秩度量碼和漢明度量碼。其存在的共同問題是密鑰尺寸太大，為了減小密鑰尺寸，推動基于編碼加密體制的實用化進程，可以從以下幾方面完善密碼體制。

1)密碼體制中編碼理論方面還值得繼續(xù)研究，例如研究碼的結(jié)構(gòu)特征，尋找新的性能更優(yōu)、安全性更強的碼，將編碼理論中的碼應(yīng)用到密碼學中；改進譯碼算法，降低譯碼復(fù)雜度，提高譯碼效率；研究如何構(gòu)造隨機性更強的公鑰矩陣，使攻擊者不能在公鑰中得到生成矩陣或校驗矩陣。

2)嘗試在原有方案的基礎(chǔ)上對結(jié)構(gòu)進行改變，減少密鑰長度，提高密碼方案的實用化。

3)研究基于編碼加密方案的軟硬件實現(xiàn)，優(yōu)化算法的能耗，提高實現(xiàn)效率，做好抗量子密碼的實用化準備。

4)研究分析目前存在的攻擊的共性，預(yù)測還可能存在的攻擊，針對這些攻擊，設(shè)計更加完善的密碼方案。

6 結(jié)論

目前，后量子密碼標準化進程正穩(wěn)步推進，后量子密碼方案已完成第二輪評選，我國也有序推進后量子算法標準化進程，基于編碼的后量子密碼方案已成為研究的熱點。McEliece密碼方案是很早的基于編碼的方案，具有抗量子計算的優(yōu)點，在量子計算機大規(guī)模投入使用之前，亟待研究基于編碼的密碼方案。后量子密碼評選方案中包括公鑰加密、密鑰封裝、數(shù)字簽名和密鑰交換。本文綜述了基于漢明度量編碼和基于秩度量編碼加密方案的發(fā)展歷程及研究現(xiàn)狀，介紹了基于McEliece方案進行結(jié)構(gòu)改變的方案，分析了目前對基于編碼加密方案主流的攻擊類型。由于編碼種類的多樣性，本文僅對典型的編碼進行了介紹，還有許多其他類型的編碼沒有進行詳細概述。