基于QC-LDPC碼的M公鑰密碼體制及其性能研究*

陶忠君，卜 凡，史治平

（1.電子科技大學，四川 成都 610000；2.國網電力科學研究院有限公司,江蘇 南京 211000）

0 引言

隨著量子計算機的快速發展，目前使用的大多數公鑰密碼算法（如RSA 和ECC）都面臨著被量子攻擊的危險。基于編碼理論的McEliece 公鑰密碼體制是基于隨機線性碼的譯碼困難問題，是一個NP 完全問題。目前還沒有有效的量子計算方法對該體制進行攻擊，具有很高的安全性，能夠較好的抵抗量子攻擊。不僅如此，McEliece 公鑰密碼體制還具有較低的計算復雜度，比RSA 等加密算法快得多。盡管如此，McEliece 公鑰密碼體制還是很少被實際系統使用，主要是因為采用Goppa 碼的McEliece 體制密鑰體積大，系統傳輸速率低等因素影響了該體制的應用。準循環LDPC 碼（即QCLDPC 碼）的出現為McEliece 體制的應用提供了新的機會，可以明顯降低密鑰的大小，同時提高系統的傳輸速率。

1 M 公鑰密碼體制

基于糾錯編碼的密碼體制的安全性建立在矩陣分解困難問題和糾錯碼的譯碼問題上。在基于糾錯編碼的加解密體制中，編碼的過程同時也是加密的過程，譯碼的過程同時也是解密的過程。

1.1 基于Goppa 碼的M 公鑰密碼體制

1978 年，McEliece 將糾錯編碼與加解密體制結合，提出基于Goppa 碼的McEliece 體制，簡稱M體制[1]。1986 年，Niderreiter 提出基于Goppa 碼的Niderreiter 加解密體制，簡稱N 體制[2]。許多學者證明這兩種體制的安全性相同。M 體制用糾錯編碼的生成矩陣加密，N 體制用校驗矩陣加密。M 體制算法過程如下：

接收方選好n和t，先在GF(2m)上隨機選擇一個度是t的不可約多項式，再產生一個k×n階的Goppa 碼的生成矩陣G，矩陣G生成的Goppa 碼可以糾正t個錯誤，H是G對應的校驗矩陣，尺寸為(n-k)×n，滿足G·HT=0。然后隨機選擇一個k×k階稠密的非奇異矩陣S和一個n×n階置換矩陣P來隱藏矩陣G。最后用矩陣G′=S·G·P生成一個線性碼，G′生成的線性碼的最小距離與原碼相同。G，H，S和P是私鑰，G′和t是公鑰。

假設m是k比特明文向量，發送方利用接收方的公鑰G′對m運算如下：

式中，z是隨機產生的n比特錯誤向量，WH(z)=t，WH(z)表示z的漢明重量，c是n比特密文。

接收方收到的信息序列為r，其對r的解密步驟如下。

①用置換矩陣P對r做式（2）的運算。

②利用校驗矩陣H來譯碼。由于z的漢明重量是t，因此可以正確譯碼。由式（2）可知，譯碼可得到：

1.2 基于QC-LDPC 碼的M 公鑰密碼體制

基于Goppa 碼的M 體制自提出以來，許多密碼研究者研究分析該體制，目前該體制仍然很安全。但該體制中公鑰密鑰尺寸大、信息傳輸率比較低。2008 年，Baldi 在文獻[3]中提出一種基于QC-LDPC 碼的M 體制，并對其進行安全性分析，分析表明在相同的安全性下，密鑰存儲空間能大大降低。2018 年，Baldi 在文獻[4]中提出一種基于QC-LDPC 碼的N 體制的變體，并在文章中提出一種譯碼速度更快且譯碼性能優異的Q 譯碼器。基于QC-LDPC 碼的M 體制的加解密過程如下。

（1）Bob 生成密鑰。Bob 的私鑰H如下所示：

H由n0個循環塊矩陣組成。循環塊矩陣的階數是p。因此，H的尺寸是p×(n0·p)。每個循環塊矩陣的行重為dv。所以碼率為(n0-1)/n0。假定H的糾錯能力是t′。Bob 還需產生準循環n階可逆矩陣Q，行重為m，和準循環k階可逆陣S。Bob 公鑰如下所示：

（2）Alice 加密。Alice 使用Bob 的公鑰G′加密k比特消息u。加密表達式如下：

式中，e為隨機產生的二元錯誤向量，假設權重是t。由于H的糾錯能力限制，t需滿足t′≥t·m。Alice 加密消息u后，直接將密文x發送到接收端。

（3）Bob 解密。Bob 收到x后，執行以下操作：

①計算x′=x·Q=u·S-1·G·Q-1·Q+e·Q=u·S-1·G+e·Q

②計算H(x′)T=H(eQ)T=H(e(QT)T)T=s、根據S，QT和私鑰矩陣H，譯碼可得到e，再得到eQ。

③計算u·S-1·G=x′+eQ。由于G是系統生成矩陣，所以可得到u·S-1。

④最終將u·S-1右乘S，得到消息u。

2 QC-LDPC 碼M 公鑰密碼體制的安全性分析

M 體制的安全性主要由錯誤向量e和其漢明重量t決定，為使M 體制具有很高的計算安全性，t需足夠大，但同時要保證合法的接收方能夠糾正出所有的錯誤比特。對M 體制的攻擊方法有很多，包括枚舉攻擊、最小碼重攻擊、信息重發和信息相關攻擊、信息集譯碼攻擊等，這里主要介紹信息集譯碼攻擊的安全性分析。

信息集譯碼攻擊的思想是利用收集的密文分析出明文。在M 體制加密表達式中，x=u·G′+e。x為n比特密文向量，u為k比特明文向量。e為隨機產生的權重為t的向量。假設破譯者收集到了一個密文x。他在x中任意選擇k比特組成向量，即xk。理論上，xk滿足：

和在x中選擇的k個位置一致，Gk′是將相對應的k個列向量拼成的矩陣。同理，ek也是依據這k個位置得到的向量。由此可知u滿足：

若ek等于全零向量，u可表示成u=xk·(Gk′)-1，便能得到信息u。因為攻擊者也可以獲得x和G′。反之，如果ek不是全零向量，破譯者就無法破解得到明文。

破譯者每次在x中選擇k位，執行xk·(Gk′)-1。如果結果有意義，說明他選擇的ek正好為全零向量。執行的結果就是u。若執行的結果沒有意義，那么他選擇的是非全零向量ek，需要繼續選擇，直到破解得到u。

破譯者選擇的ek為全零向量的概率，即破解成功的概率如下：

那么，破譯成功需要的工作因子是：

根據式（11）可仿真分析出錯誤向量權重t和W（也稱為安全因子）的關系。當(n,k)參數設置為（16 128，12 096）時，QC-LDPC 碼的錯誤向量權重t和工作因子W的關系如圖1 所示。

圖1 錯誤向量權重t 對于工作因子W 的影響

密碼分析理論認為，當某攻擊算法的工作因子小于80 時，密碼體制是不安全的。相反，若大于或等于80，則足夠安全。因此，從圖1 可以發現，當錯誤向量的權重為25 時，工作因子約等于90，這種參數下密碼體制是足夠安全的。

3 基于QC-LDPC 碼的M 公鑰密碼體制密鑰量分析

M 體制的密鑰量指的是存儲公鑰需要的內存空間。內存空間用比特數來度量。對于(n，k)為（1 024，524）的Goppa 碼，基于它的M 體制的密鑰量是k×n=536 576；基于QC-LDPC 碼的M 體制，公鑰G′是準循環矩陣，其由幾個循環塊矩陣組成，循環塊矩陣可以由第一行循環移位得到，因此對于基于準循環碼的M 體制，只需要存儲公鑰矩陣中每個循環塊矩陣的第一行。例如碼的參數為n0=4、k0=3、p=4 032、n=n0·p=16 128、k=k0·p=12 096的QC-LDPC 的公開密鑰量等于p×k0×n0=48 384 bit。

在安全因子是80 的時候，[1 632，1 269]Goppa碼的公鑰量是1 269（1 632-1 269）=460 647 位（系統矩陣表示，t=33）[5]。QC-LDPC 碼的公鑰量是4×3×1 008=12 096，其中n0=4、k0=3、p=1 008[3]。可以發現，在安全參數為80 的情況下，QC-LDPC的密鑰量可以縮減到Goppa 碼的密鑰量的3%。

4 QC-LDPC 碼M 公鑰密碼體制的解密成功率分析

基于QC-LDPC 碼的M 體制的解密算法主要是BF 算法及其改進方案。

4.1 BF 解密算法

假定接收端接收到硬判決之后的向量是z=(z0,z1,…,zn-1)。H的維度是(m,n)，H中的第j行為hj=(hj,0,hj,1,…,hj,n-1)(1 ≤j≤m)。校正子s是：

s中的第j個分量是：

當s=0 時，z就是碼字，傳輸中沒有引入傳輸錯誤。反之，z則受到了噪聲干擾。假如給傳輸碼字造成噪聲干擾的錯誤向量為e=(e0,e1,…,en-1)。

s與e的關系如式（13）所示：

s中第j個分量是：

具體的譯碼迭代步驟如下所示。

（1）計算s，若s=0，就停止譯碼，并提示譯碼成功，并且返回正確的碼字。若達到了最大迭代次數，并且s ≠0，則結束譯碼，返回譯碼失敗。若不屬于這兩種情況，則進行步驟（2）。

（2）計算出向量z中每個比特所關聯的錯誤校驗方程的個數，得出f=[f0,f1,…,fn-1]。

（3）將向量f中最大的元素所對應的位置取出構成位置向量S。

（4）將向量z中對應于位置向量S的元素翻轉。并且跳轉到步驟（1）。

BF 算法要解決的譯碼問題是HeT=S，輸入H，S，輸出e。算法中采用的是迭代譯碼算法。首先設置初始值，令e=0，通過不停地循環，不停地迭代，使得最終的s為0 才停止。而且在循環過程中，每次都動態地更新e和s。具體看某一次循環：碼長是n，j表示j=0,…,n-1 中的某個值。hj表示矩陣H的第j列元素。|hj|表示第j列元素中1 的個數。vj表示接收的碼字中第j個變量節點，j=0,…,n-1。s是校正子，它的尺寸是1×(n-k)。s的含義是n-k個校驗方程對和錯的標志。如果s中第一個元素為1，那么表示第一個校驗方程出錯，如果為0，表示第一個校驗方程正確。如果s全0，表示所有校驗方程全部正確。那么此時碼字才是合法碼字，碼字中沒有錯誤。譯碼的過程，就是糾錯的過程，最后能夠得到合法的碼字。H矩陣可以用矩陣表示，也可以用tanner 圖來表示。|hj|也表示包含vj這個變量節點的校驗方程的個數。而s表示的是所有校驗方程的結果。因此，hj*s表示的含義是包含vj這個變量節點的錯誤的校驗方程的個數。那么它的個數最大不超過|hj|。將門限設置為|hj|，如果一個變量節點使得包含它的所有校驗方程都出錯了，那么這個變量節點一定是錯誤的，通過這一準則找到錯誤變量節點的位置。通過不斷迭代更新得到e的位置，最終使得HeT=S，從而找到了合適的e。

隨著p值的增大，即碼長的增加，糾錯能力會不斷上升。本文采用原始的BF 譯碼，碼長為1 899 bit，碼率為2/3 時，錯誤向量權重為3 bit 的譯碼成功率是94.5%，權重是4 bit 的譯碼成功率是93.07%，權重是5 bit 的譯碼成功率是86.87%。由于當碼長很長，大于10 000 時，計算矩陣Q的逆矩陣很耗費時間。文獻[6]中，Baldi 通過理論分析估算出了當矩陣Q的行重為7 時，BF 譯碼的糾錯能力，即是能糾正的錯誤向量e的最大權重數，如表1 所示。

表1 多種參數下BF 譯碼的糾錯能力

4.2 Q 譯碼器

為了提高BF 譯碼器的效率，文獻[4]給出了一種N 體制的Q 譯碼器方法。Q 譯碼器要解決的問題是H(eQT)=S，輸入H、Q、S、輸出e，e′=eQT，其實e′是由QT的一些行模二相加而成的，或者也可以說是由Q的一些列模二相加而成的。而e中1 的位置，也就是那些列的標號。比如e中第一個元素為1，說明相加的那些列包含Q的第一列。如果為0，說明不包含Q的第一列。簡而言之，e′是由Q的一些列組成的，那么e′就和Q有著一定的關系。文章中有一個定理，e′和參與組成它的那些Q的列的相關性要比沒有參與組成它的那些列要大。求相關性值的過程就是兩個向量求內積的過程，這個內積值越大，表示相關性值越大。首先，算法初始化e為全零向量。算法同樣執行迭代譯碼過程，不斷更新e，然后用這個更新的e來判斷是不是正確的錯誤向量。算法的第一步是計算S*H，在分析BF譯碼器時，S*hj的含義是包含vj這個變量節點的錯誤的校驗方程的個數。那么S*H的含義是所有變量節點對應的錯誤校驗方程的個數。錯誤的個數越大，則該位置上的變量節點越有可能出錯，也即e′位置越有可能為1，所以S*H和e′有很大的關系。再看算法的第二步，通過S*H算出來的相關性值和Q矩陣相乘，正如剛才分析的，其實類似于拿e′和Q矩陣相乘，前面也分析過，e′和Q中的組成它的列內積值更大，所以第二步算出的結果是e′和Q的每一列的相關性值。通過將最大的相關性值位置保存下來，這些位置根據之前的分析，也就是e中為1的位置。一次迭代可能不能找到e中所有的1，需要通過多次的迭代，最后得到e。

4.3 Q 譯碼器和BF 譯碼器的分析與比較

Q 譯碼器和BF 譯碼器的區別是Q 譯碼器利用錯誤向量和矩陣Q的列向量的相關性。在算法中，其算出了相關性向量R，它的元素之間都是相關的，元素越大，表示這個位置對應的列越有可能是組成e′的列，所以元素之間是有關系的。因此，把門限設置為這些元素的最大值。而在BF 算法中，錯誤向量是獨立的，沒有物理量與其相關，并且算法中S*H算出的向量中的元素之間沒有關系，每一個元素都表示對應的變量節點所連的錯誤校驗方程的個數，有n個變量節點，每個變量節點都獨立計算。所以門限就不能設置成向量中的最大值，而是設為矩陣H的列重，BF 譯碼器是將S*H向量中每一個元素和列重比較，找到等于列重的位置。Q 譯碼器相比較BF 譯碼器，雖然性能提升，但是譯碼復雜度提高了，譯碼所需的時延更大，算法需要經常與矩陣Q運算，而在BF 譯碼中，主要是和矩陣H運算。所以，BF 譯碼的時延更低。BF 和Q 譯碼器都需要計算S*H，即包含變量節點的錯誤校驗方程的個數。因為這反映了錯誤向量的信息。往往錯誤校驗方程的個數越多，該位置對應在錯誤向量中，越有可能為1。這兩個算法的關鍵在于門限值的選擇，現在有許多改進的BF 算法對門限值的選擇做了優化，很多研究者提出，門限值要隨著每一次迭代而發生變化，這樣性能會更好，但是時延會更大。本文還是采用固定門限值。另外，在實際仿真時，迭代次數不能設置過高，過高會影響譯碼速度。實驗中發現，很多碼字若在10 次內還未迭代成功，后面都不會成功。因此可以將最大迭代次數設置地小一點。例如20 次左右，這樣，不僅譯碼性能影響很小，也大大減少了譯碼的時延。v*H′=0vHeT=S。

4.4 QC-LDPC 碼的變體M 體制及其性能

為了提高M 體制的解密成功率，文獻[7]給出了一種利用Q 譯碼器的變體M 體制的加解密方法。

4.4.1 Bob 產生公私鑰

Bob 需產生兩個隨機的n階準循環矩陣Q1和Q2。其形式和參數與上文中M 體制中的一致。QCLDPC 碼的矩陣H和G的形式和參數與上文一致。矩陣S是k階的可逆準循環矩陣。Bob 的私鑰為Q1、Q2、S、G，公鑰為SGQ2與Q1T·Q2。Bob 將兩個公鑰發給Alice。

4.4.2 Alice 加密

加密表達式如下：

式中，e的權重為t。Alice 將密文c發送給Bob。

4.4.3 Bob 解密

Bob 收到密文c后，解密步驟如下所示：

①在c的右邊乘，得到

②通過矩陣H，計算通過Q 譯碼器，輸入H，s和Q1，譯碼得到e。

③計算e·Q1T，并將其與相加得到mSG，由于矩陣G前k列是單位陣，因此可直接得到mS。

④在mS右邊乘S-1，得到明文m。

在變體M 體制中，為了提高譯碼或解密的準確率，改變了M 體制算法，使譯碼的形式可以直接使用Q 譯碼器。仿真了碼長1 899，H的行權重為9，碼率2/3 的M 變體密碼體制，錯誤向量e的權重為3 bit 時，譯碼成功率為100%；錯誤向量e的權重為9 bit 時譯碼成功率為100%；錯誤向量的權重為12 bit 時，譯碼成功率為100%；錯誤向量權重為15 bit 時，譯碼成功率是99.83%。與BF 譯碼相比，該錯誤向量的權重提高了3 倍，譯碼成功率至少提高了5%。

5 結語

基于QC-LDPC 碼的M 公鑰密碼體制是目前基于糾錯編碼的密碼體制的重要方案之一，是抗量子攻擊的密碼方案的重要手段之一。本文從QCLDPC 碼的M 公鑰密碼體制的加解密過程、密碼體制的安全性、密鑰量的大小、解密成功率等方面進行了研究。QC-LDPC 碼的M 公鑰密碼體制相對于經典的Goppa 碼M 體制，密鑰體積小、信息傳輸效率高，是未來后量子密碼學發展的重要方向之一。