趙鴻伯 錢(qián)路雁 金玲飛，2

1(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203) 2(東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室 江蘇 南京 210096)

0 引 言

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

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

在后續(xù)的研究中，學(xué)者們嘗試使用其他的糾錯(cuò)碼來(lái)構(gòu)造新的McEliece密碼系統(tǒng)。2005年，Gaborit提出使用QC-BCH碼來(lái)構(gòu)造新的McEliece密碼系統(tǒng)[3]。2007年，Baldi等[4]提出了基于QC-LDPC碼的McEliece密碼方案。2009年，Berger等[5]介紹了使用QC-alternant碼構(gòu)造的McEliece密碼方案。2013年，Misoczki等[6]構(gòu)造了基于QC-MDPC碼的McEliece密碼系統(tǒng)。2018年，NIST舉行的后量子密碼學(xué)標(biāo)準(zhǔn)競(jìng)賽上，多個(gè)基于編碼理論的密碼系統(tǒng)進(jìn)入第一輪競(jìng)爭(zhēng)，Aragon等[7]提出了基于QC-MDPC碼的BIKE密碼系統(tǒng)，Melchor等[8]學(xué)者提出的基于QC碼的HQC密碼系統(tǒng)等。

上述的部分密碼方案被證明存在弱點(diǎn)。2010年，Otmani等[9]提出了針對(duì)Gaborit和Baldi提出的基于QC-BCH碼和QC-LDPC碼的McEliece密碼系統(tǒng)的攻擊方法。同一年，F(xiàn)augère等[10]提出了針對(duì)Berger等人設(shè)計(jì)的基于QC-alternant碼的McEliece密碼方案的攻擊方法。2016年，Guo等[11]提出了針對(duì)Misoczki等人構(gòu)造的基于QC-MDPC碼的McEliece密碼方案的攻擊方法。

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

本文的主要貢獻(xiàn)在于構(gòu)造了一個(gè)新的基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統(tǒng)。

1 預(yù)備知識(shí)

1.1 線性碼基礎(chǔ)知識(shí)

1.2 代數(shù)幾何碼

Goppa于1977年發(fā)現(xiàn)了編碼理論與代數(shù)幾何之間的理論聯(lián)系，并在1981年提出了代數(shù)幾何碼的構(gòu)造方法[14]。

(1)

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

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

(2)

1.3 McEliece密碼系統(tǒng)

初始的McEliece密碼系統(tǒng)是基于Goppa碼構(gòu)建的。該密碼系統(tǒng)由密鑰生成、加密算法和解密算法三個(gè)部分構(gòu)成。

1.3.1 密鑰生成

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

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

3) 計(jì)算公鑰Gpub=SGP。

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

1.3.2 加密算法

令m代表一個(gè)長(zhǎng)度為k的消息向量。加密算法的執(zhí)行過(guò)程如下：

1) 隨機(jī)生成一個(gè)長(zhǎng)度為n的錯(cuò)誤向量e，滿足wt(e)≤t。

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

1.3.3 解密算法

對(duì)于獲得的密文c，解密算法的執(zhí)行過(guò)程如下：

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

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

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

2 基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統(tǒng)

2.1 基本思路

與其他代數(shù)幾何碼的子域子碼相比，橢圓曲線碼的子域子碼擁有更長(zhǎng)的碼距。同時(shí)，2.4節(jié)中介紹了針對(duì)橢圓曲線碼的子域子碼的快速譯碼算法。這使得橢圓曲線碼的子域子碼成為構(gòu)造McEliece公鑰密碼系統(tǒng)的一個(gè)選擇。

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

2.2 密鑰生成

2.2.1 構(gòu)造橢圓曲線碼

2) 隨機(jī)選擇X上的n個(gè)有理點(diǎn)P(α,β)構(gòu)成有理點(diǎn)集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個(gè)單項(xiàng)式Fk(x,y)和有理點(diǎn)集P構(gòu)造橢圓曲線碼的生成矩陣Ge。構(gòu)造的橢圓曲線碼的參數(shù)為[n,k,d]，其中d=n-k。

2.2.2 構(gòu)造橢圓曲線碼的子域子碼

1) 根據(jù)Ge計(jì)算橢圓曲線碼的校驗(yàn)矩陣He。

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

2.2.3 生成密鑰

1) 隨機(jī)挑選一個(gè)F2上的k×k可逆矩陣S，一個(gè)n×n轉(zhuǎn)置矩陣P。

2) 計(jì)算公鑰Gpub=SGP。

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

2.3 加密算法

對(duì)一個(gè)消息向量m的加密過(guò)程如下：

1) 隨機(jī)生成一個(gè)長(zhǎng)度為n的錯(cuò)誤向量e且wt(e)≤t。

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

2.4 解密算法

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

1) 構(gòu)造兩個(gè)多項(xiàng)式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) 構(gòu)造方程組A(Pi)+B(Pi)f(Pi)=0，找到A、B的一個(gè)非零解:

(5)

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

2.4.2 快速譯碼算法證明

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

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

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

2.4.3 解密算法

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

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

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

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

3 安全性能分析

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

3.1 窮搜攻擊

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

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

3.2 信息集譯碼攻擊

1962年，Prange針對(duì)一般線性碼的譯碼問(wèn)題提出了信息集譯碼算法[20]。

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

下面是信息集譯碼算法的一個(gè)簡(jiǎn)單例子。

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

表1 信息集譯碼攻擊算法的時(shí)間復(fù)雜度

3.3 消息重傳攻擊

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

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

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

為了使McEliece密碼系統(tǒng)達(dá)到CCA-2安全級(jí)別。有學(xué)者提出了可用于基于編碼理論的密碼系統(tǒng)的具有CCA-2安全級(jí)別的加密方案[27-28]。

3.4 針對(duì)基于代數(shù)幾何碼的McEliece公鑰系統(tǒng)的密鑰恢復(fù)攻擊

目前，尚沒(méi)有針對(duì)基于代數(shù)幾何碼的子域子碼的McEliece密碼系統(tǒng)的攻擊方法。由于選擇的編碼是代數(shù)幾何碼的一類子碼，本節(jié)將分析針對(duì)基于代數(shù)幾何碼的McEliece密鑰系統(tǒng)的攻擊方法對(duì)提出的密鑰系統(tǒng)的安全性能的影響。

3.4.1 Faure的攻擊算法

2007年，F(xiàn)aure和Minder提出了針對(duì)基于橢圓曲線碼的McEliece密鑰系統(tǒng)的攻擊算法[29]。這一算法的基本思路是，根據(jù)橢圓曲線上所有有理點(diǎn)構(gòu)成的阿貝爾群，攻擊者能夠找到一條與選擇的曲線同構(gòu)的橢圓曲線，并最終根據(jù)兩條曲線間的映射來(lái)恢復(fù)所選用的橢圓曲線。

為了從公開(kāi)信息中構(gòu)造所選用的橢圓曲線的所有有理點(diǎn)構(gòu)成的阿貝爾群，攻擊者需要找到所選用的橢圓曲線碼的一個(gè)具有最小漢明重量的碼字。

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

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

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

3.4.2 Couvreur的攻擊算法

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

3.5 公鑰體積及推薦參數(shù)

與最初的McEliece密碼方案相同。提出的基于橢圓曲線碼的子域子碼的McEliece密碼系統(tǒng)的公鑰是一個(gè)大小為n×k比特的矩陣。合適的具有CCA-2安全級(jí)別的加密方案能夠在保持安全性能的同時(shí)，將密鑰方案的公鑰轉(zhuǎn)變?yōu)橐粋€(gè)大小為(n-k)×k比特的標(biāo)準(zhǔn)形式矩陣[30]。

4 結(jié) 語(yǔ)

本文的主要貢獻(xiàn)在于構(gòu)造了一個(gè)新的基于橢圓曲線碼的子域子碼的McEliece公鑰密碼系統(tǒng)。并使用針對(duì)McEliece公鑰密碼系統(tǒng)的攻擊算法及針對(duì)基于代數(shù)幾何碼的McEliece密碼系統(tǒng)的攻擊算法對(duì)提出系統(tǒng)的安全性能進(jìn)行分析。分析證明，在現(xiàn)有的攻擊下，本文提出的基于橢圓曲線碼的子域子碼的公鑰密碼系統(tǒng)是安全的。

未來(lái)該方案可作為基于編碼理論的密碼系統(tǒng)的一個(gè)備選方案，在數(shù)字簽名、零知識(shí)證明等方面展開(kāi)進(jìn)一步的研究。