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

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

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

1緒論

量子計(jì)算機(jī)的概念是最早是由英國(guó)牛津大學(xué)物理學(xué)家DavidDeutsch和美國(guó)科學(xué)家RichardFeynman于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é)問(wèn)題的困難性），ECC公鑰加密算法（基于橢圓曲線的離散對(duì)數(shù)問(wèn)題）完全可以采用量子計(jì)算機(jī)來(lái)進(jìn)行暴力破解，現(xiàn)代密碼體系的安全性即將遭受重大威脅。簡(jiǎn)單來(lái)說(shuō)，這是因?yàn)榱孔佑?jì)算機(jī)能夠幫助黑客更快闖過(guò)算法陷門(mén)這道難關(guān)。與各個(gè)比特只能處于1或0狀態(tài)的經(jīng)典計(jì)算機(jī)不同，量子計(jì)算機(jī)可以使用能夠同時(shí)代表1與0的多種可能狀態(tài)的量子比特——這就是所謂疊加現(xiàn)象。另外，通過(guò)所謂糾纏現(xiàn)象，各個(gè)量子比特之間也能夠在遠(yuǎn)距離條件下相互影響。在這些現(xiàn)象的作用之下，只需要添加少數(shù)額外的量子比特，我們就能夠讓計(jì)算機(jī)的處理能力呈指數(shù)級(jí)上升。擁有300個(gè)量子比特的量子計(jì)算機(jī)就可以表達(dá)比可觀察宇宙中全部原子總數(shù)更多的值。假設(shè)量子計(jì)算機(jī)能夠克服其自身特性帶來(lái)的某些固有限制，那么其最終完全有可能在相對(duì)較短的時(shí)間之內(nèi)測(cè)試加密密鑰的所有潛在排列?？沽孔蛹用苁且环N新的加密方法探索方向，其能夠利用現(xiàn)有經(jīng)典計(jì)算機(jī)實(shí)現(xiàn)，但卻具有足以抵御未來(lái)量子攻擊的能力。其中一種防御方式在于進(jìn)一步增加數(shù)字密鑰的大小，以便持續(xù)提升黑客利用算力進(jìn)行暴力破解時(shí)所需要搜索的總體排列數(shù)量。舉例來(lái)說(shuō)，如果將密鑰的大小從128位加倍至256位，將能夠快速增加使用Grover算法時(shí)量子計(jì)算機(jī)所需要搜索的全部可能排列數(shù)量。另一種方法則涉及更為雜的陷門(mén)函數(shù)，這意味著即使是像Shor這樣的算法也很難幫助量子計(jì)算機(jī)成功破解密鑰內(nèi)容。研究人員正在探索各種各樣的方法，包括基于格子的密碼學(xué)以及超奇異同構(gòu)密鑰交換等相當(dāng)新奇的實(shí)現(xiàn)途徑無(wú)論具體方法如何，新方法的目標(biāo)都在嘗試將一種或者幾種能夠廣泛采用的方法歸為一類(lèi)。美國(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)沒(méi)那么多時(shí)間用來(lái)應(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的QSystemOne）實(shí)現(xiàn)“量子優(yōu)越性”（國(guó)外稱“量子霸權(quán)”）的國(guó)家。

2NTRU加密算法原理

在量子計(jì)算機(jī)現(xiàn)世之后仍能夠保持機(jī)密性而不被其暴力破解，即能夠抵御出破譯依舊存活的密碼稱為后量子密碼（Post-QuantumCryptography）。NTRU（NumberTheoryResearchUnit）加密算法便是后量子公鑰加密算法中最為典型的算法。20世紀(jì)90年代，美國(guó)的三名數(shù)學(xué)家及密碼學(xué)家J.Hoffstein，J.Pipher和J.H.Silverman共同首先提出了NTRU公鑰加密算法。NTRU公鑰加密算法不僅能夠抵御可能出現(xiàn)的量子計(jì)算機(jī)的暴力破譯，而且在密碼算法所基于的數(shù)學(xué)問(wèn)題上比現(xiàn)在市面上大多數(shù)采用的RSA及ECC橢圓曲線算法更難以破解。從現(xiàn)階段的研究來(lái)看，NTRU公鑰加密算法所基于的數(shù)學(xué)困難問(wèn)題是難以被量子計(jì)算機(jī)所暴力破解的。不僅如此，在加解密的速度方面，NTRU因?yàn)榱鞒滔鄬?duì)簡(jiǎn)單，步驟簡(jiǎn)潔，其運(yùn)算速度比現(xiàn)有的大多數(shù)加密算法更勝一籌，公鑰系統(tǒng)也相對(duì)容易實(shí)現(xiàn)?？偟膩?lái)說(shuō)，我們有理由相信后量子公鑰加密算法（NTRU）完全有可能在未來(lái)的公鑰密碼體系中占有主導(dǎo)地位。1.1NTRU算法參數(shù)NTRU公鑰加密算法中的關(guān)鍵參數(shù)為三個(gè)整數(shù)參數(shù)（N，p，q），以及四個(gè)N-1次整數(shù)系多項(xiàng)式的集合。該算法的加密以及解密過(guò)程均是在多項(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)式的集合：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公鑰加解密的過(guò)程中，絕大部分的運(yùn)算都是發(fā)生在多項(xiàng)式截?cái)喹h(huán)R=Z[X]/（XN-1）上。通過(guò)了解該加密算法的加解密流程，我們可以得知加密時(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。通過(guò)設(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ò)展歐幾里得算法來(lái)對(duì)Fp和Fq是否存在進(jìn)行驗(yàn)證。對(duì)于擴(kuò)展歐幾里得算法：設(shè)存在整數(shù)a，b，則一定存在整數(shù)x，y滿足：ax+by=gcd（a，b）（5）當(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）滿足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ǔ)上我們可以合理推測(cè)，若存在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)式截?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=1mod2。對(duì)于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）即可計(jì)算出私鑰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)生一個(gè)明文消息多項(xiàng)式m（x），該明文多項(xiàng)式屬于Lm，且該明文系數(shù)不超過(guò)N-1次，隨后隨機(jī)產(chǎn)生一個(gè)多項(xiàng)式r（x），且該r（x）多項(xiàng)式次數(shù)不超過(guò)N-1次。隨后進(jìn)行計(jì)算e（x）=h（x）*r（x）+m（x）modq，計(jì)算出的多項(xiàng)式e（x）則為明文加密之后產(chǎn)生的密文。1.4密文解密在得到密文多項(xiàng)式e（x）后，我們用私鑰f進(jìn)行計(jì)算得出多項(xiàng)式a=f*emodq，隨后計(jì)算Fq*amodp計(jì)算值得到明文m。多項(xiàng)式a其系數(shù)需要限制再區(qū)間[-p/2，p/2]內(nèi)，因此這個(gè)多項(xiàng)式在所有參數(shù)模q的情形下都不會(huì)改變，即可得正確的密文解密。

3NTRU算法具體實(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é)問(wèn)題構(gòu)造密碼，便可以抗量子計(jì)算的攻擊。3.1公私密鑰生成在生成NTRU的公私密鑰時(shí)，我們需要先進(jìn)行參數(shù)選擇，方便起見(jiàn)已將df，dg，dr都定義為d。voidKeyGeneration（intLf[]，intU[]，intg[]，inth[]）函數(shù)為密鑰生成函數(shù)。通過(guò)輸入的Lf，U，以及多項(xiàng)式g，來(lái)生成私鑰f，公鑰h。要保證私鑰f多項(xiàng)式中系數(shù)-1和1的個(gè)數(shù)相同，則f*Fq=1mod2。在NTUR算法原理中可以得知若fmod2的逆元存在，那么fmodq的逆元必定也的得出。因此在密鑰生成函數(shù)中需不斷提高f模的值大小來(lái)完成密鑰生成。3.2明文加密過(guò)程voidEncryption（inth[]，intLr[]，intm[]，inte[]）通過(guò)該函數(shù)我們可以實(shí)現(xiàn)對(duì)輸入明文消息多項(xiàng)式m的加密。通過(guò)具體的e=r*h+mmodq算法得到密文e。3.3密文解密過(guò)程voidDecryption（inte[]，intLf[]，inta[]，intFp[]）通過(guò)該函數(shù)可以實(shí)現(xiàn)對(duì)加密后的密文e的解密。在運(yùn)行該函數(shù)時(shí)我們首先需要先進(jìn)行a=f*emodq運(yùn)算，并且使得該多項(xiàng)式系數(shù)位于[-p/2，p/2]之間，隨后計(jì)算amod結(jié)果得明文m。3.4實(shí)現(xiàn)界面選取參數(shù)N，p，q分別為11，3，32，加解密結(jié)果如圖1所示。

4總結(jié)

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

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