典型抗量子公鑰加密算法實現

◆喻文韜

（東南大學網絡空間安全學院 江蘇 210023）

1 緒論

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

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

簡單來說，這是因為量子計算機能夠幫助黑客更快闖過算法陷門這道難關。與各個比特只能處于1 或0 狀態的經典計算機不同，量子計算機可以使用能夠同時代表1與0的多種可能狀態的量子比特——這就是所謂疊加現象。另外，通過所謂糾纏現象，各個量子比特之間也能夠在遠距離條件下相互影響。

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

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

2017 年5 月3 日，世界上第一臺光量子計算機誕生。這臺計算機是真正“中國制造”，它是由中國科技大學、中國科學院-阿里巴巴量子計算實驗室、浙江大學、中國科學院物理所等單位協同完成研發。2020 年12 月4 日，中國科學技術大學宣布該校潘建偉等人成功構建76 個光子的量子計算原型機“九章”?！熬耪隆笔侵袊茖W技術大學潘建偉團隊與中科院上海微系統所、國家并行計算機工程技術研究中心合作，成功構建76 個光子的量子計算原型機，求解數學算法高斯玻色取樣只需200 秒。這一突破使我國成為全球第二個（第一個為IBM的Q System One）實現“量子優越性”（國外稱“量子霸權”）的國家。

2 NTRU 加密算法原理

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

20 世紀90 年代，美國的三名數學家及密碼學家J.Hoffstein，J.Pipher 和J.H.Silverman 共同首先提出了NTRU 公鑰加密算法。NTRU 公鑰加密算法不僅能夠抵御可能出現的量子計算機的暴力破譯，而且在密碼算法所基于的數學問題上比現在市面上大多數采用的RSA 及ECC 橢圓曲線算法更難以破解。從現階段的研究來看，NTRU公鑰加密算法所基于的數學困難問題是難以被量子計算機所暴力破解的。不僅如此，在加解密的速度方面，NTRU 因為流程相對簡單，步驟簡潔，其運算速度比現有的大多數加密算法更勝一籌，公鑰系統也相對容易實現?？偟膩碚f，我們有理由相信后量子公鑰加密算法（NTRU）完全有可能在未來的公鑰密碼體系中占有主導地位。

1.1 NTRU算法參數

NTRU 公鑰加密算法中的關鍵參數為三個整數參數（N，p，q），以及四個N-1 次整數系多項式的集合。該算法的加密以及解密過程均是在多項式截斷環R=Z[X]/（XN-1）上運算。對于整數p 和q，他們不需要是素數，但必須滿足gcd（p，q）=1，且q 必須遠遠大于p。我們設：L（d1，d2）意味著對于多項式F 屬于R，多項式中共有d1個系數為1，d2個系數為1，則剩余的系數均為0，可以得到以下多項式的集合：

1.2 密鑰的生成

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

我們隨機生成兩個次數不高于N-1 次的多項式f 和g 分別屬于Lf和Lg，Fp，Fq分別為多項式f 模算法參數p 和q 的逆。我們需要用擴展歐幾里得算法來對Fp和Fq是否存在進行驗證。

對于擴展歐幾里得算法：

設存在整數a，b，則一定存在整數x，y 滿足：

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

將整數a，b 擴展為多項式則可以得到

設存在多項式a（x），b（x），則一定存在u（x），v（x）滿足

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

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

那么也就存在多項式u（x）與多項式v（x），滿足：

其中多項式u（x）即為私鑰f 在多項式截斷環Z2[X]/（XN-1）求出的逆元。

隨后我們可以將私鑰f 在多項式截斷環Z2[X]/（XN-1）上的逆元一步步提升模的數值，使得最后提升至模q。且由于Fq是私鑰f在模2 情況下的逆元，即Fq*f=1 mod 2。

對于Fq*f=2k+1，進行賦值并帶入新的私鑰，進行如下運算：

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

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

1.3 明文加密

先隨機產生一個明文消息多項式m（x），該明文多項式屬于Lm，且該明文系數不超過N-1 次，隨后隨機產生一個多項式r（x），且該r（x）多項式次數不超過N-1 次。隨后進行計算e（x）=h（x）*r（x）+m（x）mod q，計算出的多項式e（x）則為明文加密之后產生的密文。

1.4 密文解密

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

多項式a 其系數需要限制再區間[-p/2，p/2]內，因此這個多項式在所有參數模q 的情形下都不會改變，即可得正確的密文解密。

3 NTRU 算法具體實現

量子計算機的發展，對目前廣泛應用的RSA、ECC 等公鑰密碼體制構成了嚴重的威脅，面臨量子計算機的挑戰，國際上掀起了抗量子計算公鑰密碼的研究熱潮。一種方案是采用量子密碼、DNA 密碼等基于非數 學難題的新型密碼。這些極具潛力的新型密碼的研究還處于初級階段，有待我們深入系統地研究完善。另一種方案是采用基于數學難題的、能夠抗量子計算攻擊的密碼?；诹孔佑嬎銠C不擅長計算的數學問題構造密碼，便可以抗量子計算的攻擊。

3.1 公私密鑰生成

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

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

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

3.2 明文加密過程

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

3.3 密文解密過程

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

3.4 實現界面

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

圖1 輸入關鍵參數

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

圖2 公鑰

圖3 私鑰

圖4 明文

圖5 密文

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

圖6 解密密文得到的消息

當我們選擇了不互素的多項式Lf，Lg 和Lr 時則會出現圖7 結果。

圖7 輸入多項式不符合要求

4 總結

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

對于截斷多項式環上的多項式運算，直接在外部進行運算是比較耗費時間的，因此將環R=Z[X]/（XN-1）上的兩個多項式運算（例如多項式模加，模乘以及模逆運算）直接分解為具體的功能函數，從而簡化了算法具體加解密實現的流程，體現了該算法實現的高效性。

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