典型抗量子公鑰加密算法分析

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

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

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

1緒論

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

2NTRU加密算法原理

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

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

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

4總結(jié)

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

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