一種新的基于橢圓曲線碼的子域子碼的McEliece密碼系統

趙鴻伯 錢路雁 金玲飛，2

1(復旦大學計算機科學技術學院 上海 201203) 2(東南大學移動通信國家重點實驗室 江蘇 南京 210096)

0 引 言

1994年，Shor提出了能夠在多項式時間復雜度內解決整數分解問題和離散對數問題的量子算法[1]，這意味著在可實用的量子計算機出現的背景下，現今被廣泛使用的RSA公鑰密碼系統及橢圓曲線公鑰密碼系統將不再安全。因此，密碼學界開始研究能夠抵抗量子計算機攻擊的后量子密碼系統，基于編碼理論的密碼系統便是后量子密碼系統中的一類。

第一個基于編碼理論的密碼系統是由McEliece在1978年提出的基于二元Goppa碼的McEliece公鑰密碼系統[2]。這一密碼系統與現今使用的公鑰密碼系統相比擁有更快的加解密速度。到目前為止，尚沒有有效的針對基于Goppa碼的密碼系統的攻擊方法。

在后續的研究中，學者們嘗試使用其他的糾錯碼來構造新的McEliece密碼系統。2005年，Gaborit提出使用QC-BCH碼來構造新的McEliece密碼系統[3]。2007年，Baldi等[4]提出了基于QC-LDPC碼的McEliece密碼方案。2009年，Berger等[5]介紹了使用QC-alternant碼構造的McEliece密碼方案。2013年，Misoczki等[6]構造了基于QC-MDPC碼的McEliece密碼系統。2018年，NIST舉行的后量子密碼學標準競賽上，多個基于編碼理論的密碼系統進入第一輪競爭，Aragon等[7]提出了基于QC-MDPC碼的BIKE密碼系統，Melchor等[8]學者提出的基于QC碼的HQC密碼系統等。

上述的部分密碼方案被證明存在弱點。2010年，Otmani等[9]提出了針對Gaborit和Baldi提出的基于QC-BCH碼和QC-LDPC碼的McEliece密碼系統的攻擊方法。同一年，Faugère等[10]提出了針對Berger等人設計的基于QC-alternant碼的McEliece密碼方案的攻擊方法。2016年，Guo等[11]提出了針對Misoczki等人構造的基于QC-MDPC碼的McEliece密碼方案的攻擊方法。

除了上述方案外，1996年，Janwa和Moreno提出代數幾何碼及其子碼可以作為構造McEliece密碼系統的一種選擇[12]。雖然基于代數幾何碼及其子碼的McEliece密碼系統已經被證明不安全[13]。但目前尚沒有針對基于代數幾何碼的子域子碼的McEliece密碼系統的有效的攻擊方法，代數幾何碼的子域子碼仍然可以作為構造McEliece公鑰密碼方案的一個選擇。

本文的主要貢獻在于構造了一個新的基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統。

1 預備知識

1.1 線性碼基礎知識

1.2 代數幾何碼

Goppa于1977年發現了編碼理論與代數幾何之間的理論聯系，并在1981年提出了代數幾何碼的構造方法[14]。

(1)

這個賦值映射的像就是一個從曲線X上構造的代數幾何碼，記為CL(X,P,E)。CL(X,P,E)的碼長n等于有理點的個數，即n=|P|。CL(X,P,E)維數k等于L(E)的維數，即k=dim(L(E))。CL(X,P,E)的碼距d由曲線X的虧格g決定，滿足條件n-k-g+1≤d≤n-k+1[16]。

1989年，Justesen等學者提出了構造基于有限域上的光滑不可約仿射曲線的代數幾何碼的簡易方法[17]。根據單項式基底F(x)和曲線的一個有理點集P，可以構造出曲線上的代數幾何碼的生成矩陣：

(2)

1.3 McEliece密碼系統

初始的McEliece密碼系統是基于Goppa碼構建的。該密碼系統由密鑰生成、加密算法和解密算法三個部分構成。

1.3.1 密鑰生成

1) 在有限域F2m上隨機選取一個度數為t的不可約多項式。根據這一多項式構造一個參數[n,k,d]Goppa碼的生成矩陣G，其中n=2m,d=2t+1。

2) 隨機選擇一個k×k的可逆矩陣S和一個n×n的置換矩陣P。

3) 計算公鑰Gpub=SGP。

4) 將集合(S,φ,P)作為私鑰保存，其中φ代表二元Goppa碼的快速譯碼算法。

1.3.2 加密算法

令m代表一個長度為k的消息向量。加密算法的執行過程如下：

1) 隨機生成一個長度為n的錯誤向量e，滿足wt(e)≤t。

2) 計算密文c=mGpub+e。

1.3.3 解密算法

對于獲得的密文c，解密算法的執行過程如下：

1) 消除置換矩陣的影響：計算x=cP-1=mSG+eP-1。

2) 使用譯碼算法φ清除錯誤向量：u=φ(x)。

3) 計算消息向量：m=uS-1。

2 基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統

2.1 基本思路

與其他代數幾何碼的子域子碼相比，橢圓曲線碼的子域子碼擁有更長的碼距。同時，2.4節中介紹了針對橢圓曲線碼的子域子碼的快速譯碼算法。這使得橢圓曲線碼的子域子碼成為構造McEliece公鑰密碼系統的一個選擇。

本節將介紹基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統。與初始的McEliece公鑰密碼系統類似，基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統也由密鑰生成、加密算法和解密算法三個部分組成。

2.2 密鑰生成

2.2.1 構造橢圓曲線碼

2) 隨機選擇X上的n個有理點P(α,β)構成有理點集P={P1,P2,…,Pn}。

4) 將F(x,y)按照V(f1)≤V(f2)≤…≤V(fn-t-1)順序排列，其中V(f)=2i+3j。

5) 使用F(x,y)的前k個單項式Fk(x,y)和有理點集P構造橢圓曲線碼的生成矩陣Ge。構造的橢圓曲線碼的參數為[n,k,d]，其中d=n-k。

2.2.2 構造橢圓曲線碼的子域子碼

1) 根據Ge計算橢圓曲線碼的校驗矩陣He。

3) 橢圓曲線碼的子域子碼的生成矩陣G是H2的零空間的一個基底。構造的子域子碼的參數為[N,K,D]，其中N=n,K≥mk-(m-1)n,D≥d。

2.2.3 生成密鑰

1) 隨機挑選一個F2上的k×k可逆矩陣S，一個n×n轉置矩陣P。

2) 計算公鑰Gpub=SGP。

3) 將有理點集P，可逆矩陣S和轉置矩陣P作為私鑰保存。

2.3 加密算法

對一個消息向量m的加密過程如下：

1) 隨機生成一個長度為n的錯誤向量e且wt(e)≤t。

2) 生成密文r=mGpub+e。

2.4 解密算法

2.4.1 橢圓曲線碼的子域子碼的快速譯碼算法

1) 構造兩個多項式A(x,y)、B(x,y)：

A(x,y)=a1f1+a2f2+…+an-t-1fn-t-1

(3)

B(x,y)=b1f1+b2f2+…+bn-t-k-1fn-t-k-1

(4)

其中，ai,bi∈q,fi∈F(x,y)。

2) 構造方程組A(Pi)+B(Pi)f(Pi)=0，找到A、B的一個非零解:

(5)

4) 糾錯后的碼字為{d(P1),d(P2),…,d(PPn)}。

2.4.2 快速譯碼算法證明

本節將證明橢圓曲線碼的子域子碼的快速譯碼算法的正確性。

1) 證明多項式A(x,y)、B(x,y)的存在性：將ai、bj看作是未知數，則式(5)是一個包含n個齊次線性方程的齊次方程組。其中未知數的個數為2(n-t-1)-k

2) 證明糾錯后的碼字等于{d(P1),d(P2),…,d(Pn)}。不妨設收到的碼字mGpub等于(f(P1),f(P2),…，f(Pn))，其中V(f)≤k。由1)知，至少有n-t個有理點Pi使得A(Pi)+B(Pi)f(Pi)=0。又由V(A+Bf)

2.4.3 解密算法

根據上文介紹的橢圓曲線碼的子域子碼的快速譯碼算法，對收到的密文r=mSGP+e={r1,r2,…,rn}，解密算法過程如下：

1) 消除置換矩陣P的影響：r′=rP-1=mSG+e′。

2) 清除錯誤位：m′=Φ(r′)=mS。

3) 恢復消息向量：m=m′S-1。

3 安全性能分析

目前，針對McEliece密碼系統主要存在兩類攻擊方法。第一類攻擊嘗試從密文中恢復明文信息的信息恢復攻擊，信息集譯碼攻擊算法是這一類攻擊算法的代表，3.2節中討論了信息集譯碼攻擊算法對提出的密碼方案的安全性的影響。第二類是根據選取的編碼的性質，試圖從公鑰中恢復私鑰的密鑰恢復攻擊。目前，尚沒有直接針對基于橢圓曲線碼的子域子碼的McEliece密碼系統的密鑰恢復攻擊方法。由于橢圓曲線碼是構建在虧格為1的代數曲線上的代數幾何碼，因此3.4節中討論了針對基于代數幾何碼的McEliece密碼系統的密鑰恢復攻擊對提出的密碼系統的影響。最終證明，在現有的攻擊方法下，本文中提出的密碼系統是安全的。

3.1 窮搜攻擊

窮搜攻擊的基本思路是根據公鑰矩陣的信息，通過遍歷搜索所有可能的k×k可逆矩陣，n×n置換矩陣以及使用的有理點集的方法，恢復出私鑰(S,P,P)。在2上，k×k可逆矩陣的個數為置換矩陣的個數為在q上，不同構的橢圓曲線的個數約為|X|≈2q[19]。橢圓曲線上的有理點的數量區間為橢圓曲線上基數為n的有理點集|P|的數量區間為

基于上述分析，攻擊者成功實施窮搜攻擊的可能性為1/|S||P||P||X|。當n、k取較大值時，設計的密碼系統能夠有效抵御窮搜攻擊。

3.2 信息集譯碼攻擊

1962年，Prange針對一般線性碼的譯碼問題提出了信息集譯碼算法[20]。

定義1令G代表一個[n,k]線性碼C的生成矩陣，I代表{1,2,…,n}的一個基數為k的子集。選擇G中以I為索引的列構成一個k×k矩陣GI。若GI可逆，則稱I為G的一個信息集。

下面是信息集譯碼算法的一個簡單例子。

令I代表q上的一個線性碼C的生成矩陣G的一個信息集，y代表上的一個向量，c代表C的一個碼字，且d(y,c)=w,w≠0。令yI和cI代表按I索引的y和c的子集。若yI=cI，則可以計算碼字

表1 信息集譯碼攻擊算法的時間復雜度

3.3 消息重傳攻擊

1997年，Berson和Thomas證明McEliece公鑰密碼系統在消息重傳場景下是不安全的[26]。

令m代表一個明文向量。假設存在兩個由m生成的密文c1=mGpub+e1和c2=mGpub+e2其中e1≠e2。由McEliece密鑰方案的初始定義可知c1-c2=e1-e2。根據這一關系，攻擊者可以快速的找到一個信息集I使得cI=mI，從而恢復出明文m。

和初始的McEliece密鑰方案相同，基于橢圓曲線碼的子域子碼的McEliece密鑰方案在消息重傳場景下也是不安全的。

為了使McEliece密碼系統達到CCA-2安全級別。有學者提出了可用于基于編碼理論的密碼系統的具有CCA-2安全級別的加密方案[27-28]。

3.4 針對基于代數幾何碼的McEliece公鑰系統的密鑰恢復攻擊

目前，尚沒有針對基于代數幾何碼的子域子碼的McEliece密碼系統的攻擊方法。由于選擇的編碼是代數幾何碼的一類子碼，本節將分析針對基于代數幾何碼的McEliece密鑰系統的攻擊方法對提出的密鑰系統的安全性能的影響。

3.4.1 Faure的攻擊算法

2007年，Faure和Minder提出了針對基于橢圓曲線碼的McEliece密鑰系統的攻擊算法[29]。這一算法的基本思路是，根據橢圓曲線上所有有理點構成的阿貝爾群，攻擊者能夠找到一條與選擇的曲線同構的橢圓曲線，并最終根據兩條曲線間的映射來恢復所選用的橢圓曲線。

為了從公開信息中構造所選用的橢圓曲線的所有有理點構成的阿貝爾群，攻擊者需要找到所選用的橢圓曲線碼的一個具有最小漢明重量的碼字。

定義2對于一個[n,k,d]橢圓曲線碼，其碼字的最小漢明重量等于它的碼距d=n-k。

橢圓曲線碼的子域子碼的碼距大于等于其原碼的碼距。在實際構造中，當橢圓曲線碼所在的有限域大于26時，總能構造出碼距大于原碼碼距的子域子碼。比如，參數為[64,54,10]的橢圓曲線碼的子域子碼的參數為[64,10,16]，參數為[128,113,15]的橢圓曲線碼的子域子碼的參數為[128,23,36]。

無法從子域子碼中獲得原碼的一個具有最小漢明重量的碼字使得Faure的攻擊算法對提出的密碼方案無效。

3.4.2 Couvreur的攻擊算法

2017年，Couvreur等人提出了針對基于代數幾何碼及其子碼的McEliece系統的攻擊算法。但Couvreur等在論文中闡明，這一攻擊算法并不適用于基于代數幾何碼的子域子碼的McEliece密碼系統[13]。

3.5 公鑰體積及推薦參數

與最初的McEliece密碼方案相同。提出的基于橢圓曲線碼的子域子碼的McEliece密碼系統的公鑰是一個大小為n×k比特的矩陣。合適的具有CCA-2安全級別的加密方案能夠在保持安全性能的同時，將密鑰方案的公鑰轉變為一個大小為(n-k)×k比特的標準形式矩陣[30]。

4 結 語

本文的主要貢獻在于構造了一個新的基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統。并使用針對McEliece公鑰密碼系統的攻擊算法及針對基于代數幾何碼的McEliece密碼系統的攻擊算法對提出系統的安全性能進行分析。分析證明，在現有的攻擊下，本文提出的基于橢圓曲線碼的子域子碼的公鑰密碼系統是安全的。

未來該方案可作為基于編碼理論的密碼系統的一個備選方案，在數字簽名、零知識證明等方面展開進一步的研究。