陶忠君，卜 凡，史治平

（1.電子科技大學(xué)，四川 成都 610000；2.國(guó)網(wǎng)電力科學(xué)研究院有限公司,江蘇 南京 211000）

0 引言

隨著量子計(jì)算機(jī)的快速發(fā)展，目前使用的大多數(shù)公鑰密碼算法（如RSA 和ECC）都面臨著被量子攻擊的危險(xiǎn)?；诰幋a理論的McEliece 公鑰密碼體制是基于隨機(jī)線性碼的譯碼困難問(wèn)題，是一個(gè)NP 完全問(wèn)題。目前還沒(méi)有有效的量子計(jì)算方法對(duì)該體制進(jìn)行攻擊，具有很高的安全性，能夠較好的抵抗量子攻擊。不僅如此，McEliece 公鑰密碼體制還具有較低的計(jì)算復(fù)雜度，比RSA 等加密算法快得多。盡管如此，McEliece 公鑰密碼體制還是很少被實(shí)際系統(tǒng)使用，主要是因?yàn)椴捎肎oppa 碼的McEliece 體制密鑰體積大，系統(tǒng)傳輸速率低等因素影響了該體制的應(yīng)用。準(zhǔn)循環(huán)LDPC 碼（即QCLDPC 碼）的出現(xiàn)為McEliece 體制的應(yīng)用提供了新的機(jī)會(huì)，可以明顯降低密鑰的大小，同時(shí)提高系統(tǒng)的傳輸速率。

1 M 公鑰密碼體制

基于糾錯(cuò)編碼的密碼體制的安全性建立在矩陣分解困難問(wèn)題和糾錯(cuò)碼的譯碼問(wèn)題上。在基于糾錯(cuò)編碼的加解密體制中，編碼的過(guò)程同時(shí)也是加密的過(guò)程，譯碼的過(guò)程同時(shí)也是解密的過(guò)程。

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

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

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

假設(shè)m是k比特明文向量，發(fā)送方利用接收方的公鑰G′對(duì)m運(yùn)算如下：

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

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

①用置換矩陣P對(duì)r做式（2）的運(yùn)算。

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

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

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

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

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

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

式中，e為隨機(jī)產(chǎn)生的二元錯(cuò)誤向量，假設(shè)權(quán)重是t。由于H的糾錯(cuò)能力限制，t需滿足t′≥t·m。Alice 加密消息u后，直接將密文x發(fā)送到接收端。

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

①計(jì)算x′=x·Q=u·S-1·G·Q-1·Q+e·Q=u·S-1·G+e·Q

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

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

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

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

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

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

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

若ek等于全零向量，u可表示成u=xk·(Gk′)-1，便能得到信息u。因?yàn)楣粽咭部梢垣@得x和G′。反之，如果ek不是全零向量，破譯者就無(wú)法破解得到明文。

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

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

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

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

圖1 錯(cuò)誤向量權(quán)重t 對(duì)于工作因子W 的影響

密碼分析理論認(rèn)為，當(dāng)某攻擊算法的工作因子小于80 時(shí)，密碼體制是不安全的。相反，若大于或等于80，則足夠安全。因此，從圖1 可以發(fā)現(xiàn)，當(dāng)錯(cuò)誤向量的權(quán)重為25 時(shí)，工作因子約等于90，這種參數(shù)下密碼體制是足夠安全的。

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

M 體制的密鑰量指的是存儲(chǔ)公鑰需要的內(nèi)存空間。內(nèi)存空間用比特?cái)?shù)來(lái)度量。對(duì)于(n，k)為（1 024，524）的Goppa 碼，基于它的M 體制的密鑰量是k×n=536 576；基于QC-LDPC 碼的M 體制，公鑰G′是準(zhǔn)循環(huán)矩陣，其由幾個(gè)循環(huán)塊矩陣組成，循環(huán)塊矩陣可以由第一行循環(huán)移位得到，因此對(duì)于基于準(zhǔn)循環(huán)碼的M 體制，只需要存儲(chǔ)公鑰矩陣中每個(gè)循環(huán)塊矩陣的第一行。例如碼的參數(shù)為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 的時(shí)候，[1 632，1 269]Goppa碼的公鑰量是1 269（1 632-1 269）=460 647 位（系統(tǒng)矩陣表示，t=33）[5]。QC-LDPC 碼的公鑰量是4×3×1 008=12 096，其中n0=4、k0=3、p=1 008[3]?？梢园l(fā)現(xiàn)，在安全參數(shù)為80 的情況下，QC-LDPC的密鑰量可以縮減到Goppa 碼的密鑰量的3%。

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

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

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個(gè)分量是：

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

s與e的關(guān)系如式（13）所示：

s中第j個(gè)分量是：

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

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

（2）計(jì)算出向量z中每個(gè)比特所關(guān)聯(lián)的錯(cuò)誤校驗(yàn)方程的個(gè)數(shù)，得出f=[f0,f1,…,fn-1]。

（3）將向量f中最大的元素所對(duì)應(yīng)的位置取出構(gòu)成位置向量S。

（4）將向量z中對(duì)應(yīng)于位置向量S的元素翻轉(zhuǎn)。并且跳轉(zhuǎn)到步驟（1）。

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

隨著p值的增大，即碼長(zhǎng)的增加，糾錯(cuò)能力會(huì)不斷上升。本文采用原始的BF 譯碼，碼長(zhǎng)為1 899 bit，碼率為2/3 時(shí)，錯(cuò)誤向量權(quán)重為3 bit 的譯碼成功率是94.5%，權(quán)重是4 bit 的譯碼成功率是93.07%，權(quán)重是5 bit 的譯碼成功率是86.87%。由于當(dāng)碼長(zhǎng)很長(zhǎng)，大于10 000 時(shí)，計(jì)算矩陣Q的逆矩陣很耗費(fèi)時(shí)間。文獻(xiàn)[6]中，Baldi 通過(guò)理論分析估算出了當(dāng)矩陣Q的行重為7 時(shí)，BF 譯碼的糾錯(cuò)能力，即是能糾正的錯(cuò)誤向量e的最大權(quán)重?cái)?shù)，如表1 所示。

表1 多種參數(shù)下BF 譯碼的糾錯(cuò)能力

4.2 Q 譯碼器

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

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

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

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

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

4.4.1 Bob 產(chǎn)生公私鑰

Bob 需產(chǎn)生兩個(gè)隨機(jī)的n階準(zhǔn)循環(huán)矩陣Q1和Q2。其形式和參數(shù)與上文中M 體制中的一致。QCLDPC 碼的矩陣H和G的形式和參數(shù)與上文一致。矩陣S是k階的可逆準(zhǔn)循環(huán)矩陣。Bob 的私鑰為Q1、Q2、S、G，公鑰為SGQ2與Q1T·Q2。Bob 將兩個(gè)公鑰發(fā)給Alice。

4.4.2 Alice 加密

加密表達(dá)式如下：

式中，e的權(quán)重為t。Alice 將密文c發(fā)送給Bob。

4.4.3 Bob 解密

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

①在c的右邊乘，得到

②通過(guò)矩陣H，計(jì)算通過(guò)Q 譯碼器，輸入H，s和Q1，譯碼得到e。

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

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

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

5 結(jié)語(yǔ)

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