導(dǎo)語：典型抗量子公鑰加密算法分析一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：量子計算機(jī)便是一種理論上計算量可以無限大的一臺并行計算機(jī)。如果我們采用這種量子計算機(jī)來窮舉法暴力破解密碼，由于其可以在同一時間進(jìn)行多種狀態(tài)的運(yùn)算，現(xiàn)有的大多數(shù)密碼技術(shù)所產(chǎn)生的密文都將被完全破譯。在量子計算機(jī)這把高掛于空中的達(dá)摩克利斯之劍威脅下，抗量子密碼算法應(yīng)運(yùn)而生。本文研究內(nèi)容主要是典型的抗量子公鑰加密算法（NTRU公鑰加密算法）的具體實(shí)現(xiàn)，其中簡單介紹該加密算法實(shí)現(xiàn)過程中所需要了解的數(shù)學(xué)基礎(chǔ)，包括環(huán)上的多項(xiàng)式乘法及多項(xiàng)式求逆等；闡述了NTRU公鑰加密算法中公私鑰的產(chǎn)生以及加密和解密的具體流程。

關(guān)鍵詞：抗量子攻擊；NTRU公鑰加密算法；環(huán)上多項(xiàng)式運(yùn)算；密鑰生成；加密；解密

1緒論

量子計算機(jī)的概念是最早是由英國牛津大學(xué)物理學(xué)家DavidDeutsch和美國科學(xué)家RichardFeynman于20世紀(jì)80年代共同提出。量子理論中定義了一個粒子同時可具有數(shù)個不同狀態(tài)。若我們采用這種具備不同狀態(tài)的粒子進(jìn)行數(shù)學(xué)運(yùn)算，那么在同一時間就可以完成對多種狀態(tài)的結(jié)果的運(yùn)算。假設(shè)采用1個粒子就可以表示0和1兩種不同狀態(tài)，那么采用128個這樣的粒子就可以完成在同一時間計算出2128種狀態(tài)的結(jié)果。量子計算機(jī)一旦現(xiàn)世，其計算量與現(xiàn)在市面上存在的超級計算機(jī)的計算量完全不在一個數(shù)量級，因此現(xiàn)代密碼體系中的各種加密算法如RSA公鑰加密算法（基于大整數(shù)分解數(shù)學(xué)問題的困難性），ECC公鑰加密算法（基于橢圓曲線的離散對數(shù)問題）完全可以采用量子計算機(jī)來進(jìn)行暴力破解，現(xiàn)代密碼體系的安全性即將遭受重大威脅。簡單來說，這是因?yàn)榱孔佑嬎銠C(jī)能夠幫助黑客更快闖過算法陷門這道難關(guān)。與各個比特只能處于1或0狀態(tài)的經(jīng)典計算機(jī)不同，量子計算機(jī)可以使用能夠同時代表1與0的多種可能狀態(tài)的量子比特——這就是所謂疊加現(xiàn)象。另外，通過所謂糾纏現(xiàn)象，各個量子比特之間也能夠在遠(yuǎn)距離條件下相互影響。在這些現(xiàn)象的作用之下，只需要添加少數(shù)額外的量子比特，我們就能夠讓計算機(jī)的處理能力呈指數(shù)級上升。擁有300個量子比特的量子計算機(jī)就可以表達(dá)比可觀察宇宙中全部原子總數(shù)更多的值。假設(shè)量子計算機(jī)能夠克服其自身特性帶來的某些固有限制，那么其最終完全有可能在相對較短的時間之內(nèi)測試加密密鑰的所有潛在排列。抗量子加密是一種新的加密方法探索方向，其能夠利用現(xiàn)有經(jīng)典計算機(jī)實(shí)現(xiàn)，但卻具有足以抵御未來量子攻擊的能力。其中一種防御方式在于進(jìn)一步增加數(shù)字密鑰的大小，以便持續(xù)提升黑客利用算力進(jìn)行暴力破解時所需要搜索的總體排列數(shù)量。舉例來說，如果將密鑰的大小從128位加倍至256位，將能夠快速增加使用Grover算法時量子計算機(jī)所需要搜索的全部可能排列數(shù)量。另一種方法則涉及更為雜的陷門函數(shù)，這意味著即使是像Shor這樣的算法也很難幫助量子計算機(jī)成功破解密鑰內(nèi)容。研究人員正在探索各種各樣的方法，包括基于格子的密碼學(xué)以及超奇異同構(gòu)密鑰交換等相當(dāng)新奇的實(shí)現(xiàn)途徑無論具體方法如何，新方法的目標(biāo)都在嘗試將一種或者幾種能夠廣泛采用的方法歸為一類。美國國家標(biāo)準(zhǔn)與技術(shù)研究院于2016年啟動了一項(xiàng)流程，旨在制定政府使用的后量子加密標(biāo)準(zhǔn)。其目前已經(jīng)將最初的69個提案縮小至26個，并表示初步標(biāo)準(zhǔn)草案可能會在2022年前后正式公布。由于加密技術(shù)需要被深深嵌入眾多不同的系統(tǒng)當(dāng)中，所以標(biāo)準(zhǔn)制定面臨著巨大的壓力，找到可行途徑并實(shí)現(xiàn)新的技術(shù)也可能需要投入大量時間。去年，美國國家科學(xué)院研究報告指出，以往業(yè)界花了十多年時間才全面推出一種能夠廣泛部署的加密方法——但其中仍然存在缺陷?？紤]到量子計算的發(fā)展速度，我們的世界也許已經(jīng)沒那么多時間用來應(yīng)對這一波新的安全威脅。2017年5月3日，世界上第一臺光量子計算機(jī)誕生。這臺計算機(jī)是真正“中國制造”，它是由中國科技大學(xué)、中國科學(xué)院-阿里巴巴量子計算實(shí)驗(yàn)室、浙江大學(xué)、中國科學(xué)院物理所等單位協(xié)同完成研發(fā)。2020年12月4日，中國科學(xué)技術(shù)大學(xué)宣布該校潘建偉等人成功構(gòu)建76個光子的量子計算原型機(jī)“九章”?！熬耪隆笔侵袊茖W(xué)技術(shù)大學(xué)潘建偉團(tuán)隊與中科院上海微系統(tǒng)所、國家并行計算機(jī)工程技術(shù)研究中心合作，成功構(gòu)建76個光子的量子計算原型機(jī)，求解數(shù)學(xué)算法高斯玻色取樣只需200秒。這一突破使我國成為全球第二個（第一個為IBM的QSystemOne）實(shí)現(xiàn)“量子優(yōu)越性”（國外稱“量子霸權(quán)”）的國家。

2NTRU加密算法原理

在量子計算機(jī)現(xiàn)世之后仍能夠保持機(jī)密性而不被其暴力破解，即能夠抵御出破譯依舊存活的密碼稱為后量子密碼（Post-QuantumCryptography）。NTRU（NumberTheoryResearchUnit）加密算法便是后量子公鑰加密算法中最為典型的算法。20世紀(jì)90年代，美國的三名數(shù)學(xué)家及密碼學(xué)家J.Hoffstein，J.Pipher和J.H.Silverman共同首先提出了NTRU公鑰加密算法。NTRU公鑰加密算法不僅能夠抵御可能出現(xiàn)的量子計算機(jī)的暴力破譯，而且在密碼算法所基于的數(shù)學(xué)問題上比現(xiàn)在市面上大多數(shù)采用的RSA及ECC橢圓曲線算法更難以破解。從現(xiàn)階段的研究來看，NTRU公鑰加密算法所基于的數(shù)學(xué)困難問題是難以被量子計算機(jī)所暴力破解的。不僅如此，在加解密的速度方面，NTRU因?yàn)榱鞒滔鄬唵?，步驟簡潔，其運(yùn)算速度比現(xiàn)有的大多數(shù)加密算法更勝一籌，公鑰系統(tǒng)也相對容易實(shí)現(xiàn)?？偟膩碚f，我們有理由相信后量子公鑰加密算法（NTRU）完全有可能在未來的公鑰密碼體系中占有主導(dǎo)地位。1.1NTRU算法參數(shù)NTRU公鑰加密算法中的關(guān)鍵參數(shù)為三個整數(shù)參數(shù)（N，p，q），以及四個N-1次整數(shù)系多項(xiàng)式的集合。該算法的加密以及解密過程均是在多項(xiàng)式截斷環(huán)R=Z[X]/（XN-1）上運(yùn)算。對于整數(shù)p和q，他們不需要是素數(shù)，但必須滿足gcd（p，q）=1，且q必須遠(yuǎn)遠(yuǎn)大于p。我們設(shè)：L（d1，d2）意味著對于多項(xiàng)式F屬于R，多項(xiàng)式中共有d1個系數(shù)為1，d2個系數(shù)為1，則剩余的系數(shù)均為0，可以得到以下多項(xiàng)式的集合：Lf=（df，df-1）（1）Lg=（dg，dg-1）（2）Lr=（dr，dr-1）（3）Lm定義為：m屬于多項(xiàng)式R且m的系數(shù)位于區(qū)間-（p-1）/2到（p-1）/2之間（4）1.2密鑰的生成在NTRU公鑰加解密的過程中，絕大部分的運(yùn)算都是發(fā)生在多項(xiàng)式截斷環(huán)R=Z[X]/（XN-1）上。通過了解該加密算法的加解密流程，我們可以得知加密時需要用多項(xiàng)式h和多項(xiàng)式r想乘，而在解密時需要用私鑰f與密文多項(xiàng)式e相乘得多項(xiàng)式a，且還原明文時會用到私鑰f模p的逆Fp與多項(xiàng)式a相乘得到解密后得明文m我們不妨設(shè)私鑰f多項(xiàng)中系數(shù)-1和系數(shù)+1的個數(shù)相等均為d，這樣在使用擴(kuò)展歐幾里得算法時就可以很簡單的得出私鑰f模p的逆Fp=1。通過設(shè)置私鑰f的多項(xiàng)式中正負(fù)一系數(shù)的個數(shù)就可以提高NTRU加密算法的運(yùn)算速率。我們隨機(jī)生成兩個次數(shù)不高于N-1次的多項(xiàng)式f和g分別屬于Lf和Lg，F(xiàn)p，F(xiàn)q分別為多項(xiàng)式f模算法參數(shù)p和q的逆。我們需要用擴(kuò)展歐幾里得算法來對Fp和Fq是否存在進(jìn)行驗(yàn)證。對于擴(kuò)展歐幾里得算法：設(shè)存在整數(shù)a，b，則一定存在整數(shù)x，y滿足：ax+by=gcd（a，b）（5）當(dāng)b=0時存在x與y為最后一組解，而每一組的解均可以根據(jù)最后一組求得。所以第一組的解x與y必定存在，這時可用遞歸算法，求得b=0時返回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）滿足u（x）a（x）+v（x）b（x）=gcd（a（x），b（x））（6）在這種前提下，我們不妨設(shè)私鑰多項(xiàng)式f為a（x）且b（x）=（xN-1）=（x-1）（xN-1+xN-2+……+x+1）代入即可算出第一層的多項(xiàng)式為私鑰f模p和q的逆元。在此的基礎(chǔ)上我們可以合理推測，若存在gcd（f，xN-1）=1mod2；那么也就存在多項(xiàng)式u（x）與多項(xiàng)式v（x），滿足：u（x）f+v（x）（xN-1）=1mod2（7）其中多項(xiàng)式u（x）即為私鑰f在多項(xiàng)式截斷環(huán)Z2[X]/（XN-1）求出的逆元。隨后我們可以將私鑰f在多項(xiàng)式截斷環(huán)Z2[X]/（XN-1）上的逆元一步步提升模的數(shù)值，使得最后提升至模q。且由于Fq是私鑰f在模2情況下的逆元，即Fq*f=1mod2。對于Fq*f=2k+1，進(jìn)行賦值并帶入新的私鑰，進(jìn)行如下運(yùn)算：Fq*f=Fq*（2-f*Fq）*f=Fq*f*（2-f*Fq）=（1+2k）*（2-1-2k）=（1+2k）*（1-2k）=1-4k*kmodq（8）即可計算出私鑰f模4，16，256等數(shù)值的逆元，由由于q一般選為2n，則可以推出若私鑰q模2存在逆元，那么模q一定也存在相應(yīng)的逆元。綜上可得公鑰為多項(xiàng)式h（x）=Fq*gmodp，私鑰為多項(xiàng)式f（x）。1.3明文加密先隨機(jī)產(chǎn)生一個明文消息多項(xiàng)式m（x），該明文多項(xiàng)式屬于Lm，且該明文系數(shù)不超過N-1次，隨后隨機(jī)產(chǎn)生一個多項(xiàng)式r（x），且該r（x）多項(xiàng)式次數(shù)不超過N-1次。隨后進(jìn)行計算e（x）=h（x）*r（x）+m（x）modq，計算出的多項(xiàng)式e（x）則為明文加密之后產(chǎn)生的密文。1.4密文解密在得到密文多項(xiàng)式e（x）后，我們用私鑰f進(jìn)行計算得出多項(xiàng)式a=f*emodq，隨后計算Fq*amodp計算值得到明文m。多項(xiàng)式a其系數(shù)需要限制再區(qū)間[-p/2，p/2]內(nèi)，因此這個多項(xiàng)式在所有參數(shù)模q的情形下都不會改變，即可得正確的密文解密。

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

量子計算機(jī)的發(fā)展，對目前廣泛應(yīng)用的RSA、ECC等公鑰密碼體制構(gòu)成了嚴(yán)重的威脅，面臨量子計算機(jī)的挑戰(zhàn)，國際上掀起了抗量子計算公鑰密碼的研究熱潮。一種方案是采用量子密碼、DNA密碼等基于非數(shù)學(xué)難題的新型密碼。這些極具潛力的新型密碼的研究還處于初級階段，有待我們深入系統(tǒng)地研究完善。另一種方案是采用基于數(shù)學(xué)難題的、能夠抗量子計算攻擊的密碼?；诹孔佑嬎銠C(jī)不擅長計算的數(shù)學(xué)問題構(gòu)造密碼，便可以抗量子計算的攻擊。3.1公私密鑰生成在生成NTRU的公私密鑰時，我們需要先進(jìn)行參數(shù)選擇，方便起見已將df，dg，dr都定義為d。voidKeyGeneration（intLf[]，intU[]，intg[]，inth[]）函數(shù)為密鑰生成函數(shù)。通過輸入的Lf，U，以及多項(xiàng)式g，來生成私鑰f，公鑰h。要保證私鑰f多項(xiàng)式中系數(shù)-1和1的個數(shù)相同，則f*Fq=1mod2。在NTUR算法原理中可以得知若fmod2的逆元存在，那么fmodq的逆元必定也的得出。因此在密鑰生成函數(shù)中需不斷提高f模的值大小來完成密鑰生成。3.2明文加密過程voidEncryption（inth[]，intLr[]，intm[]，inte[]）通過該函數(shù)我們可以實(shí)現(xiàn)對輸入明文消息多項(xiàng)式m的加密。通過具體的e=r*h+mmodq算法得到密文e。3.3密文解密過程voidDecryption（inte[]，intLf[]，inta[]，intFp[]）通過該函數(shù)可以實(shí)現(xiàn)對加密后的密文e的解密。在運(yùn)行該函數(shù)時我們首先需要先進(jìn)行a=f*emodq運(yùn)算，并且使得該多項(xiàng)式系數(shù)位于[-p/2，p/2]之間，隨后計算amod結(jié)果得明文m。3.4實(shí)現(xiàn)界面選取參數(shù)N，p，q分別為11，3，32，加解密結(jié)果如圖1所示。

4總結(jié)

對于多項(xiàng)式模運(yùn)算中的求逆元運(yùn)算，直接選擇模q運(yùn)算較為困難，代碼實(shí)現(xiàn)起來也很復(fù)雜，會使得密鑰生成的速度不夠快捷，因此可以選擇從模2求逆一步步提升到模q求逆元（q取值一般為，n為正整數(shù)），這樣使得密鑰生成能夠更為快捷的完成，提升了整個算法實(shí)現(xiàn)的高效性。對于截斷多項(xiàng)式環(huán)上的多項(xiàng)式運(yùn)算，直接在外部進(jìn)行運(yùn)算是比較耗費(fèi)時間的，因此將環(huán)R=Z[X]/（XN-1）上的兩個多項(xiàng)式運(yùn)算（例如多項(xiàng)式模加，模乘以及模逆運(yùn)算）直接分解為具體的功能函數(shù)，從而簡化了算法具體加解密實(shí)現(xiàn)的流程，體現(xiàn)了該算法實(shí)現(xiàn)的高效性。NTRU加密算法并不是十全十美的，它依舊存在著解密錯誤的問題。通過不斷選擇合適參數(shù)測試出錯概率，可以看出參數(shù)N，q均對于解密的成功性具有一定影響。在具體代碼實(shí)現(xiàn)NTRU加解密的過程中，由于我個人能力的不足，編程水平有限，并不能夠特別明顯優(yōu)化該算法的實(shí)現(xiàn)過程，但我相信，隨著人們對于該領(lǐng)域不斷探索學(xué)習(xí)，未來一定會出現(xiàn)更為高效的加解密實(shí)現(xiàn)方式。對于典型后量子公鑰加密算法中的NTRU加密算法具備著重大的潛力，并且能夠抵抗量子計算機(jī)的量子分析，未來一定會成為公鑰加密算法體系的一大熱點(diǎn)。

作者：喻文韜 單位：東南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院