典型抗量子公鑰加密算法實(shí)現(xiàn)

◆喻文韜

（東南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 江蘇 210023）

1 緒論

量子計(jì)算機(jī)的概念是最早是由英國(guó)牛津大學(xué)物理學(xué)家David Deutsch 和美國(guó)科學(xué)家Richard Feynman 于20 世紀(jì)80 年代共同提出。量子理論中定義了一個(gè)粒子同時(shí)可具有數(shù)個(gè)不同狀態(tài)。若我們采用這種具備不同狀態(tài)的粒子進(jìn)行數(shù)學(xué)運(yùn)算，那么在同一時(shí)間就可以完成對(duì)多種狀態(tài)的結(jié)果的運(yùn)算。假設(shè)采用1 個(gè)粒子就可以表示0 和1 兩種不同狀態(tài)，那么采用128 個(gè)這樣的粒子就可以完成在同一時(shí)間計(jì)算出2128種狀態(tài)的結(jié)果。

量子計(jì)算機(jī)一旦現(xiàn)世，其計(jì)算量與現(xiàn)在市面上存在的超級(jí)計(jì)算機(jī)的計(jì)算量完全不在一個(gè)數(shù)量級(jí)，因此現(xiàn)代密碼體系中的各種加密算法如RSA 公鑰加密算法（基于大整數(shù)分解數(shù)學(xué)問題的困難性），ECC公鑰加密算法（基于橢圓曲線的離散對(duì)數(shù)問題）完全可以采用量子計(jì)算機(jī)來進(jìn)行暴力破解，現(xiàn)代密碼體系的安全性即將遭受重大威脅。

簡(jiǎn)單來說，這是因?yàn)榱孔佑?jì)算機(jī)能夠幫助黑客更快闖過算法陷門這道難關(guān)。與各個(gè)比特只能處于1 或0 狀態(tài)的經(jīng)典計(jì)算機(jī)不同，量子計(jì)算機(jī)可以使用能夠同時(shí)代表1與0的多種可能狀態(tài)的量子比特——這就是所謂疊加現(xiàn)象。另外，通過所謂糾纏現(xiàn)象，各個(gè)量子比特之間也能夠在遠(yuǎn)距離條件下相互影響。

在這些現(xiàn)象的作用之下，只需要添加少數(shù)額外的量子比特，我們就能夠讓計(jì)算機(jī)的處理能力呈指數(shù)級(jí)上升。擁有300 個(gè)量子比特的量子計(jì)算機(jī)就可以表達(dá)比可觀察宇宙中全部原子總數(shù)更多的值。假設(shè)量子計(jì)算機(jī)能夠克服其自身特性帶來的某些固有限制，那么其最終完全有可能在相對(duì)較短的時(shí)間之內(nèi)測(cè)試加密密鑰的所有潛在排列。

抗量子加密是一種新的加密方法探索方向，其能夠利用現(xiàn)有經(jīng)典計(jì)算機(jī)實(shí)現(xiàn)，但卻具有足以抵御未來量子攻擊的能力。其中一種防御方式在于進(jìn)一步增加數(shù)字密鑰的大小，以便持續(xù)提升黑客利用算力進(jìn)行暴力破解時(shí)所需要搜索的總體排列數(shù)量。舉例來說，如果將密鑰的大小從128 位加倍至256 位，將能夠快速增加使用Grover 算法時(shí)量子計(jì)算機(jī)所需要搜索的全部可能排列數(shù)量。另一種方法則涉及更為復(fù)雜的陷門函數(shù)，這意味著即使是像Shor 這樣的算法也很難幫助量子計(jì)算機(jī)成功破解密鑰內(nèi)容。研究人員正在探索各種各樣的方法，包括基于格子的密碼學(xué)以及超奇異同構(gòu)密鑰交換等相當(dāng)新奇的實(shí)現(xiàn)途徑無論具體方法如何，新方法的目標(biāo)都在嘗試將一種或者幾種能夠廣泛采用的方法歸為一類。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院于2016 年啟動(dòng)了一項(xiàng)流程，旨在制定政府使用的后量子加密標(biāo)準(zhǔn)。其目前已經(jīng)將最初的69 個(gè)提案縮小至26 個(gè)，并表示初步標(biāo)準(zhǔn)草案可能會(huì)在2022 年前后正式公布。由于加密技術(shù)需要被深深嵌入眾多不同的系統(tǒng)當(dāng)中，所以標(biāo)準(zhǔn)制定面臨著巨大的壓力，找到可行途徑并實(shí)現(xiàn)新的技術(shù)也可能需要投入大量時(shí)間。去年，美國(guó)國(guó)家科學(xué)院研究報(bào)告指出，以往業(yè)界花了十多年時(shí)間才全面推出一種能夠廣泛部署的加密方法——但其中仍然存在缺陷?？紤]到量子計(jì)算的發(fā)展速度，我們的世界也許已經(jīng)沒那么多時(shí)間用來應(yīng)對(duì)這一波新的安全威脅。

2017 年5 月3 日，世界上第一臺(tái)光量子計(jì)算機(jī)誕生。這臺(tái)計(jì)算機(jī)是真正“中國(guó)制造”，它是由中國(guó)科技大學(xué)、中國(guó)科學(xué)院-阿里巴巴量子計(jì)算實(shí)驗(yàn)室、浙江大學(xué)、中國(guó)科學(xué)院物理所等單位協(xié)同完成研發(fā)。2020 年12 月4 日，中國(guó)科學(xué)技術(shù)大學(xué)宣布該校潘建偉等人成功構(gòu)建76 個(gè)光子的量子計(jì)算原型機(jī)“九章”。“九章”是中國(guó)科學(xué)技術(shù)大學(xué)潘建偉團(tuán)隊(duì)與中科院上海微系統(tǒng)所、國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心合作，成功構(gòu)建76 個(gè)光子的量子計(jì)算原型機(jī)，求解數(shù)學(xué)算法高斯玻色取樣只需200 秒。這一突破使我國(guó)成為全球第二個(gè)（第一個(gè)為IBM的Q System One）實(shí)現(xiàn)“量子優(yōu)越性”（國(guó)外稱“量子霸權(quán)”）的國(guó)家。

2 NTRU 加密算法原理

在量子計(jì)算機(jī)現(xiàn)世之后仍能夠保持機(jī)密性而不被其暴力破解，即能夠抵御出破譯依舊存活的密碼稱為后量子密碼（Post-Quantum Cryptography）。NTRU（Number Theory Research Unit）加密算法便是后量子公鑰加密算法中最為典型的算法。

20 世紀(jì)90 年代，美國(guó)的三名數(shù)學(xué)家及密碼學(xué)家J.Hoffstein，J.Pipher 和J.H.Silverman 共同首先提出了NTRU 公鑰加密算法。NTRU 公鑰加密算法不僅能夠抵御可能出現(xiàn)的量子計(jì)算機(jī)的暴力破譯，而且在密碼算法所基于的數(shù)學(xué)問題上比現(xiàn)在市面上大多數(shù)采用的RSA 及ECC 橢圓曲線算法更難以破解。從現(xiàn)階段的研究來看，NTRU公鑰加密算法所基于的數(shù)學(xué)困難問題是難以被量子計(jì)算機(jī)所暴力破解的。不僅如此，在加解密的速度方面，NTRU 因?yàn)榱鞒滔鄬?duì)簡(jiǎn)單，步驟簡(jiǎn)潔，其運(yùn)算速度比現(xiàn)有的大多數(shù)加密算法更勝一籌，公鑰系統(tǒng)也相對(duì)容易實(shí)現(xiàn)。總的來說，我們有理由相信后量子公鑰加密算法（NTRU）完全有可能在未來的公鑰密碼體系中占有主導(dǎo)地位。

1.1 NTRU算法參數(shù)

NTRU 公鑰加密算法中的關(guān)鍵參數(shù)為三個(gè)整數(shù)參數(shù)（N，p，q），以及四個(gè)N-1 次整數(shù)系多項(xiàng)式的集合。該算法的加密以及解密過程均是在多項(xiàng)式截?cái)喹h(huán)R=Z[X]/（XN-1）上運(yùn)算。對(duì)于整數(shù)p 和q，他們不需要是素?cái)?shù)，但必須滿足gcd（p，q）=1，且q 必須遠(yuǎn)遠(yuǎn)大于p。我們?cè)O(shè)：L（d1，d2）意味著對(duì)于多項(xiàng)式F 屬于R，多項(xiàng)式中共有d1個(gè)系數(shù)為1，d2個(gè)系數(shù)為1，則剩余的系數(shù)均為0，可以得到以下多項(xiàng)式的集合：

1.2 密鑰的生成

在NTRU 公鑰加解密的過程中，絕大部分的運(yùn)算都是發(fā)生在多項(xiàng)式截?cái)喹h(huán)R=Z[X]/（XN-1）上。通過了解該加密算法的加解密流程，我們可以得知加密時(shí)需要用多項(xiàng)式h 和多項(xiàng)式r 想乘，而在解密時(shí)需要用私鑰f 與密文多項(xiàng)式e 相乘得多項(xiàng)式a，且還原明文時(shí)會(huì)用到私鑰f 模p 的逆Fp與多項(xiàng)式a 相乘得到解密后得明文m 我們不妨設(shè)私鑰f 多項(xiàng)中系數(shù)-1 和系數(shù)+1 的個(gè)數(shù)相等均為d，這樣在使用擴(kuò)展歐幾里得算法時(shí)就可以很簡(jiǎn)單的得出私鑰f 模p 的逆 Fp=1。通過設(shè)置私鑰f 的多項(xiàng)式中正負(fù)一系數(shù)的個(gè)數(shù)就可以提高NTRU 加密算法的運(yùn)算速率。

我們隨機(jī)生成兩個(gè)次數(shù)不高于N-1 次的多項(xiàng)式f 和g 分別屬于Lf和Lg，F(xiàn)p，F(xiàn)q分別為多項(xiàng)式f 模算法參數(shù)p 和q 的逆。我們需要用擴(kuò)展歐幾里得算法來對(duì)Fp和Fq是否存在進(jìn)行驗(yàn)證。

對(duì)于擴(kuò)展歐幾里得算法：

設(shè)存在整數(shù)a，b，則一定存在整數(shù)x，y 滿足：

當(dāng)b=0 時(shí)存在x 與y 為最后一組解，而每一組的解均可以根據(jù)最后一組求得。所以第一組的解x與y必定存在，這時(shí)可用遞歸算法，求得b=0 時(shí)返回x=1，y=0。再根據(jù)x1=y2，y1=x2-k*y2 可得當(dāng)層的解，由此不斷返回可得原解。

將整數(shù)a，b 擴(kuò)展為多項(xiàng)式則可以得到

設(shè)存在多項(xiàng)式a（x），b（x），則一定存在u（x），v（x）滿足

在這種前提下，我們不妨設(shè)私鑰多項(xiàng)式f 為a（x）且b（x）=（xN-1）=（x-1）（xN-1+xN-2+……+x+1）代入即可算出第一層的多項(xiàng)式為私鑰f 模p 和q 的逆元。

在此的基礎(chǔ)上我們可以合理推測(cè)，若存在gcd（f，xN-1）=1 mod 2；

那么也就存在多項(xiàng)式u（x）與多項(xiàng)式v（x），滿足：

其中多項(xiàng)式u（x）即為私鑰f 在多項(xiàng)式截?cái)喹h(huán)Z2[X]/（XN-1）求出的逆元。

隨后我們可以將私鑰f 在多項(xiàng)式截?cái)喹h(huán)Z2[X]/（XN-1）上的逆元一步步提升模的數(shù)值，使得最后提升至模q。且由于Fq是私鑰f在模2 情況下的逆元，即Fq*f=1 mod 2。

對(duì)于Fq*f=2k+1，進(jìn)行賦值并帶入新的私鑰，進(jìn)行如下運(yùn)算：

即可計(jì)算出私鑰f 模4，16，256 等數(shù)值的逆元，由由于q 一般選為2n，則可以推出若私鑰q 模2 存在逆元，那么模q 一定也存在相應(yīng)的逆元。

綜上可得公鑰為多項(xiàng)式h（x）=Fq*g mod p，私鑰為多項(xiàng)式f（x）。

1.3 明文加密

先隨機(jī)產(chǎn)生一個(gè)明文消息多項(xiàng)式m（x），該明文多項(xiàng)式屬于Lm，且該明文系數(shù)不超過N-1 次，隨后隨機(jī)產(chǎn)生一個(gè)多項(xiàng)式r（x），且該r（x）多項(xiàng)式次數(shù)不超過N-1 次。隨后進(jìn)行計(jì)算e（x）=h（x）*r（x）+m（x）mod q，計(jì)算出的多項(xiàng)式e（x）則為明文加密之后產(chǎn)生的密文。

1.4 密文解密

在得到密文多項(xiàng)式e（x）后，我們用私鑰f 進(jìn)行計(jì)算得出多項(xiàng)式a=f*e mod q，隨后計(jì)算 Fq*a mod p 計(jì)算值得到明文m。

多項(xiàng)式a 其系數(shù)需要限制再區(qū)間[-p/2，p/2]內(nèi)，因此這個(gè)多項(xiàng)式在所有參數(shù)模q 的情形下都不會(huì)改變，即可得正確的密文解密。

3 NTRU 算法具體實(shí)現(xiàn)

量子計(jì)算機(jī)的發(fā)展，對(duì)目前廣泛應(yīng)用的RSA、ECC 等公鑰密碼體制構(gòu)成了嚴(yán)重的威脅，面臨量子計(jì)算機(jī)的挑戰(zhàn)，國(guó)際上掀起了抗量子計(jì)算公鑰密碼的研究熱潮。一種方案是采用量子密碼、DNA 密碼等基于非數(shù) 學(xué)難題的新型密碼。這些極具潛力的新型密碼的研究還處于初級(jí)階段，有待我們深入系統(tǒng)地研究完善。另一種方案是采用基于數(shù)學(xué)難題的、能夠抗量子計(jì)算攻擊的密碼。基于量子計(jì)算機(jī)不擅長(zhǎng)計(jì)算的數(shù)學(xué)問題構(gòu)造密碼，便可以抗量子計(jì)算的攻擊。

3.1 公私密鑰生成

在生成NTRU 的公私密鑰時(shí)，我們需要先進(jìn)行參數(shù)選擇，方便起見已將df，dg，dr 都定義為d。

void KeyGeneration（int Lf[]，int U[]，int g[]，int h[]）函數(shù)為密鑰生成函數(shù)。通過輸入的Lf，U，以及多項(xiàng)式g，來生成私鑰f，公鑰h。要保證私鑰f 多項(xiàng)式中系數(shù)-1 和1 的個(gè)數(shù)相同，則f*Fq=1 mod 2。

在NTUR 算法原理中可以得知若f mod 2 的逆元存在，那么f mod q 的逆元必定也的得出。因此在密鑰生成函數(shù)中需不斷提高f 模的值大小來完成密鑰生成。

3.2 明文加密過程

void Encryption（int h[]，int Lr[]，int m[]，int e[]）通過該函數(shù)我們可以實(shí)現(xiàn)對(duì)輸入明文消息多項(xiàng)式m 的加密。通過具體的e=r*h+m mod q 算法得到密文e。

3.3 密文解密過程

void Decryption（int e[]，int Lf[]，int a[]，int Fp[]）通過該函數(shù)可以實(shí)現(xiàn)對(duì)加密后的密文e 的解密。在運(yùn)行該函數(shù)時(shí)我們首先需要先進(jìn)行a=f*e mod q 運(yùn)算，并且使得該多項(xiàng)式系數(shù)位于[-p/2，p/2]之間，隨后計(jì)算a mod 結(jié)果得明文m。

3.4 實(shí)現(xiàn)界面

選取參數(shù)N，p，q 分別為11，3，32，加解密結(jié)果如圖1 所示。

圖1 輸入關(guān)鍵參數(shù)

以下分別為公鑰、私鑰、明文、密文以及解密后得到的正確明文。

圖2 公鑰

圖3 私鑰

圖4 明文

圖5 密文

由圖6 可以看出成功進(jìn)行了明文的加密以及密文的解密。

圖6 解密密文得到的消息

當(dāng)我們選擇了不互素的多項(xiàng)式Lf，Lg 和Lr 時(shí)則會(huì)出現(xiàn)圖7 結(jié)果。

圖7 輸入多項(xiàng)式不符合要求

4 總結(jié)

對(duì)于多項(xiàng)式模運(yùn)算中的求逆元運(yùn)算，直接選擇模q 運(yùn)算較為困難，代碼實(shí)現(xiàn)起來也很復(fù)雜，會(huì)使得密鑰生成的速度不夠快捷，因此可以選擇從模2 求逆一步步提升到模q 求逆元（q 取值一般為，n 為正整數(shù)），這樣使得密鑰生成能夠更為快捷的完成，提升了整個(gè)算法實(shí)現(xiàn)的高效性。

對(duì)于截?cái)喽囗?xiàng)式環(huán)上的多項(xiàng)式運(yùn)算，直接在外部進(jìn)行運(yùn)算是比較耗費(fèi)時(shí)間的，因此將環(huán)R=Z[X]/（XN-1）上的兩個(gè)多項(xiàng)式運(yùn)算（例如多項(xiàng)式模加，模乘以及模逆運(yùn)算）直接分解為具體的功能函數(shù)，從而簡(jiǎn)化了算法具體加解密實(shí)現(xiàn)的流程，體現(xiàn)了該算法實(shí)現(xiàn)的高效性。

NTRU 加密算法并不是十全十美的，它依舊存在著解密錯(cuò)誤的問題。通過不斷選擇合適參數(shù)測(cè)試出錯(cuò)概率，可以看出參數(shù)N，q 均對(duì)于解密的成功性具有一定影響。在具體代碼實(shí)現(xiàn)NTRU 加解密的過程中，由于我個(gè)人能力的不足，編程水平有限，并不能夠特別明顯優(yōu)化該算法的實(shí)現(xiàn)過程，但我相信，隨著人們對(duì)于該領(lǐng)域不斷探索學(xué)習(xí)，未來一定會(huì)出現(xiàn)更為高效的加解密實(shí)現(xiàn)方式。對(duì)于典型后量子公鑰加密算法中的NTRU 加密算法具備著重大的潛力，并且能夠抵抗量子計(jì)算機(jī)的量子分析，未來一定會(huì)成為公鑰加密算法體系的一大熱點(diǎn)。