nru算法優(yōu)化設(shè)計(jì)與分析

nru算法優(yōu)化設(shè)計(jì)與分析

ntru（數(shù)量研究任務(wù)）是一種基于網(wǎng)絡(luò)中最短向量的公鑰密碼系統(tǒng)。主要優(yōu)點(diǎn)是，它有效地解決了公鑰密碼系統(tǒng)的最大瓶頸。它突破性地降低了以前以性能換安全的做法,可以在安全性不受影響的前提下,比同等安全級(jí)別的公鑰密碼體制(如RSA)要快幾個(gè)數(shù)量等級(jí),如表1和表2所示。表1和表2是NTRU與RSA、與橢圓曲線密碼算法ECC的速度比較。其次,它對(duì)系統(tǒng)要求極低,不需要較高的計(jì)算能力以及較復(fù)雜的硬件設(shè)備。另外,它的密鑰對(duì)產(chǎn)生速度也非?？?。高速度、低成本的特性使得它適合于安全性要求高,體積、成本、內(nèi)存及計(jì)算能力等受限的電子設(shè)備。NTRU是密碼理論和技術(shù)研究取得的一個(gè)重要成果,和ECC一起是目前公鑰密碼體制中最優(yōu)秀的算法。然而,NTRU仍然是一相對(duì)比較年輕的加密算法,還需要作更深入的研究。1多意義規(guī)則rNTRU是一種基于多項(xiàng)式環(huán)的加密系統(tǒng),其加、解密過程基于環(huán)上多項(xiàng)式代數(shù)運(yùn)算和對(duì)數(shù)p及q的模約化運(yùn)算,解密的有效性依賴于某些元素的概率。它是由正整數(shù)(N,p,q,df,dg,dr)以及4個(gè)(N-1)次整系數(shù)多項(xiàng)式集合Rf,Rg,Rr,Rm來建構(gòu)的。N一般為一大質(zhì)數(shù),R=Z[X]/(XN-1)為多項(xiàng)式截?cái)喹h(huán)(Truncatedrolynomialrings),其元素f可表示為向量的形式:f=∑i=0N?1fixi=[f0?f1???fN?1]。f=∑i=0Ν-1fixi=[f0?f1???fΝ-1]。定義R上多項(xiàng)式元素加運(yùn)算為普通多項(xiàng)式之間的加運(yùn)算,用符號(hào)+表示;R上多項(xiàng)式元素乘法運(yùn)算為普通多項(xiàng)式的乘法運(yùn)算,但乘完的結(jié)果要模上多項(xiàng)式(XN-1),即2個(gè)多項(xiàng)式的卷積運(yùn)算,常稱為星乘,用?表示。R上多項(xiàng)式元素模q運(yùn)算就是把多項(xiàng)式的系數(shù)作模q處理,用modq表示?？梢宰C明(R,+,?)是一個(gè)環(huán)。p和q在NTRU中一般作為模數(shù),不一定為質(zhì)數(shù),但是為了安全,要求p和q必須互質(zhì),且q遠(yuǎn)大于p。df,dg和dr為正整數(shù),分別決定了多項(xiàng)式集合Rf,Rg,Rr的系數(shù)分布。令R(d1,d2)={F∈R:F的d1個(gè)系數(shù)為1,d2個(gè)系數(shù)為-1,余下的系數(shù)為0},則多項(xiàng)式集合:Rf=R(df?df?1)?Rg=R(dg?dg)?Rr=R(dr?dr)。Rf=R(df?df-1)?Rg=R(dg?dg)?Rr=R(dr?dr)。Rm={m∈R:m的系數(shù)位于區(qū)間-1/2(p-1)到1/2(p-1)內(nèi)},Rm為明文空間。由于4個(gè)集合的元素系數(shù)一般都比較小,常稱為小多項(xiàng)式。1.1系統(tǒng)中fp、fp的定義要生成NTRU的公、私密鑰,進(jìn)行以下幾步:(1)隨機(jī)地從集合Rf中選擇一個(gè)多項(xiàng)式f,使f在環(huán)R中模p模q的逆多項(xiàng)式存在,記為Fp和Fq,即f?Fq=1(modq),f?Fp=1(modp)。f和Fp稱為私鑰。(2)隨機(jī)地從集合Rg中選擇一個(gè)多項(xiàng)式g,并計(jì)算h=pFq?g(modq),h稱為公鑰。為了安全,g和Fq也要保密。1.2ntra概率密碼(1)令m為集合Rm中的待加密的明文,隨機(jī)地從集合Rr中選擇一個(gè)小多項(xiàng)式r,通常被用來置亂密文,所以,NTRU是一種概率密碼方法。(2)加密密文為:e=r?h+m(modq)。1.3模q處理a(1)用私鑰f,計(jì)算:a=f?e(modq)。(2)將多項(xiàng)式a的系數(shù)作模q處理,并調(diào)整于(-q/2,q/2)區(qū)間之內(nèi)。(3)用私鑰Fp,計(jì)算d=Fp?a(modp),所得的結(jié)果d是解密的明文。1.4ntra算法求解由前a≡f?e≡f?r?(pFq?g)+f?m(modq)≡pr?g+f?m(modq)。不作模q處理計(jì)算t=pr?g+f?m,如果NTRU參數(shù)選擇得當(dāng),可以保證t的所有系數(shù)幾乎總是位于-q/2和q/2之間。于是,只要把a(bǔ)=f?e(modq)的所有系數(shù)調(diào)整到區(qū)間-q/2和q/2內(nèi),就可以準(zhǔn)確地在環(huán)R上恢復(fù)出t來,即a=pr?g+f?m,則d=Fp?a(modp)=Fp?(pr?g+f?m)(modp)=Fp?f?m(modp)=m。正確恢復(fù)消息的關(guān)鍵在于找出t的值。記|f|∞=maxai-minai,只有|f?m+pr?g|∞<q成立,解密才能成功。文獻(xiàn)中,令pr?g+f?m所有系數(shù)的平均值A(chǔ)av為調(diào)整區(qū)間的中心,則正確的區(qū)間即為(Aav-q/2,Aav+q/2)。只需調(diào)整a的系數(shù)于上述區(qū)間,便可恢復(fù)出t。NTRU公司提供下面的方法來計(jì)算Aav:I=Fq(1)(a(1)?pr(1)g(1))(modq)?Aav=(pr(1)g(1)+If(1))/N。Ι=Fq(1)(a(1)-pr(1)g(1))(modq)?Aav=(pr(1)g(1)+Ιf(1))/Ν。顯然,I=m(1)(modq)。由NTRU參數(shù)的特點(diǎn)知,r(1)=0,g(1)=0,f(1)=1,-N≤m(1)≤N,即Aav為0。這也就是解密時(shí)要把a(bǔ)的系數(shù)調(diào)整到區(qū)間(-q/2,q/2)中的原因。NTRU算法解密可能失敗的原因在于t=pr?g+f?m的系數(shù)不全位于區(qū)間(-q/2,q/2)中。如果maxti≥q/2或minti≤-q/2則稱限制失敗(Wrapingfailure)。如果|t|∞=(maxti-minti)≥q,則稱為間距失敗(Gapfailure)。雖然NTRU有解密失敗的可能,但如果選擇恰當(dāng)?shù)膮?shù),可以使兩種失敗的概率降低到10-6。表3給出了這方面的統(tǒng)計(jì)數(shù)據(jù)?？梢钥闯?在實(shí)際應(yīng)用中可以完全忽略掉失敗的情況。2轉(zhuǎn)化參數(shù)的選擇NTRU系統(tǒng)的構(gòu)建依賴于正整數(shù)集合{N,p,q,df,dg,dr}。如果這6個(gè)參數(shù)選擇得不恰當(dāng),會(huì)出現(xiàn)3種可能:①在環(huán)R上幾乎找不到模p或模q可逆的小多項(xiàng)式f,造成密鑰對(duì)生成困難;②造成系統(tǒng)解密限制失敗和間距失敗的概率很高以至于系統(tǒng)不可使用;③造成NTRU系統(tǒng)的安全性大幅度下降,攻擊者稍加運(yùn)算便可破解密文。因此,NTRU公司推薦使用表4里的幾組標(biāo)準(zhǔn)參數(shù),這幾組參數(shù)都是經(jīng)過反復(fù)論證、計(jì)算和長(zhǎng)期實(shí)踐檢驗(yàn)的。一般地,參數(shù)p取為3,而待加密的明文是二進(jìn)制比特流,這意味著需要進(jìn)行二進(jìn)制到三進(jìn)制的轉(zhuǎn)化。如果轉(zhuǎn)化算法設(shè)計(jì)不理想(例如多少二進(jìn)制位轉(zhuǎn)化為多少個(gè)三進(jìn)制位),那么加、解密的速度及效率都將受到極大的損失。文獻(xiàn)給出了q進(jìn)制到p進(jìn)制轉(zhuǎn)化效率的分析及度量公式E(q,m;p,n)=logqm/logpn,表示m位的q進(jìn)制數(shù)轉(zhuǎn)化為n位的p進(jìn)制數(shù)的效率,它越接近1,轉(zhuǎn)化效率越高。計(jì)算轉(zhuǎn)化參數(shù)可得:E(2,3;3,2)=94.64%,E(2,19;3,12)=99.897%,E(2,84;3,53)=99.9964%,E(2,1054;3,665)=99.999994%。在選擇轉(zhuǎn)化參數(shù)時(shí),不僅要注意編碼效率,也要注意實(shí)現(xiàn)算法的執(zhí)行開銷以及速度。綜合這兩方面的考慮,選擇第一組參數(shù)。卷積運(yùn)算是NTRU的核心算法,它的效率高低,將直接影響NTRU加解密以及密鑰對(duì)生成的速度。環(huán)R上多項(xiàng)式模逆運(yùn)算是整個(gè)系統(tǒng)中最難實(shí)現(xiàn),也是理論性最強(qiáng)的運(yùn)算。雖然,通過擴(kuò)展的歐基里德算法,可以求出環(huán)R上多項(xiàng)式模p或q的逆元,但實(shí)現(xiàn)起來比較困難。文獻(xiàn)給出了一種應(yīng)用可逆算法來求解環(huán)R上多項(xiàng)式模逆運(yùn)算的算法,效率高,實(shí)現(xiàn)起來也比較容易。本文是在這種方法的基礎(chǔ)上進(jìn)行實(shí)現(xiàn)的,給出的實(shí)現(xiàn)過程中,p取3,環(huán)R上的(N-1)次多項(xiàng)式統(tǒng)一用N個(gè)單元的數(shù)組來描述。以下均采用C偽碼來描述涉及的算法。2.1degfx強(qiáng)制檢測(cè)對(duì)于已知a∈R,求屬于環(huán)R的b使得a?b=1(modp)。應(yīng)用文獻(xiàn)中的可逆算法來實(shí)現(xiàn)。根據(jù)NTRU的實(shí)際,取p為3,q為2的指數(shù)冪。首先求模數(shù)為p=3的多項(xiàng)式逆元,算法如下:輸入為多項(xiàng)式a(x),輸出為多項(xiàng)式a(x)的模p逆元b(x)。步驟1:初始化k=0,b(x)=1,c(x)=0,f(x)=a(x),g(x)=xN-1,p=3;while(1){步驟2:while(f(0)==0){f(x)=f(x)/x,c(x)=c(x)?x,k=k+1}步驟3:if(f(x)=±1)return(b(x)=±xN-kb(x)modxN-1)步驟4:if(Deg(f(x))<Deg(g(x))){交換f(x)和g(x);交換b(x)和c(x);}步驟5:if(f(0)==g(0)){f(x)=f(x)-g(x)modp;b(x)=b(x)-c(x)modp;}else{f(x)=f(x)+g(x)modp;b(x)=b(x)+c(x)modp;}}f(0)為f的常數(shù)項(xiàng),步驟3中,可以簡(jiǎn)單地把b(x)的系數(shù)循環(huán)左移k位來計(jì)算xN-kb(x)modxN-1。求模數(shù)為q=2r的多項(xiàng)式的逆元,必須先求出模數(shù)q=2的多項(xiàng)式的逆元,再用牛頓迭代算法進(jìn)行計(jì)算。具體偽碼如下:輸入為多項(xiàng)式a(x),輸出為多項(xiàng)式a(x)的模q逆元b(x)。步驟1:初始化k=0,b(x)=1,c(x)=0,f(x)=a(x),g(x)=xN-1;while(1){步驟2:while(f(0)==0){f(x)=f(x)/x,c(x)=c(x)?x,k=k+1}步驟3:if(f(x)=1)return(b(x)=xN-kb(x)modxN-1)步驟4:if(Deg(f(x))<Deg(g(x))){交換f(x)和g(x);交換b(x)和c(x);}步驟5:f(x)=f(x)+g(x)mod2;b(x)=b(x)+c(x)mod2;}步驟6:v=2;while(v<q){v=2?v;b(x)=b(x)(2-a(x)b(x))modv;}其中,步驟1到步驟5完成求模2的逆元,步驟6完成求模2r的逆元。步驟6一般需要log2(r)次計(jì)算。前一個(gè)算法最多需要Deg(a(x))+Deg(xN-1)次迭代,后一個(gè)算法最多時(shí)需要Deg(a(x))+Deg(xN-1)+log2r次迭代。需要說明的,這兩個(gè)算法雖然運(yùn)行速度很快,但是它們并不會(huì)檢查多項(xiàng)式f在環(huán)R上模p或模q逆元的存在性,即它們計(jì)算出來的結(jié)果可能不對(duì),f可能根本不存在逆元,而判斷多項(xiàng)式f在環(huán)R上模p或模q是否存在逆元,目前并沒有較好的方法,只能通過查看所求結(jié)果與f的乘積是否等于1來判斷。2.2多次分解轉(zhuǎn)化卷積是NTRU的主要耗時(shí)運(yùn)算,將直接影響其速度。最一般的方法是2層循環(huán)逐位計(jì)算,大約需要N2次數(shù)乘運(yùn)算。NTRU算法中參加運(yùn)算的多項(xiàng)式一般都具有特殊的形式,這使得優(yōu)化成為可能。多項(xiàng)式h與e的系數(shù)都隨機(jī)地分布在(-q/2,q/2)區(qū)間內(nèi)(不在該區(qū)間內(nèi)時(shí),可通過模q運(yùn)算進(jìn)行調(diào)整),并且據(jù)實(shí)驗(yàn)觀察0的個(gè)數(shù)極少。r,f,g都是小多項(xiàng)式。這樣,如果在第2層循環(huán)中加入判斷,當(dāng)a[i],b[i]都不為0時(shí)才進(jìn)行乘加操作,便可以減少大約1/3的乘運(yùn)算。進(jìn)一步可知,參加卷積運(yùn)算的2個(gè)多項(xiàng)式中必有一個(gè)是小多項(xiàng)式,系數(shù)為-1,0,1,所以,卷積可以轉(zhuǎn)化為移位加、減運(yùn)算。實(shí)際使用中,參數(shù)df和dr都比較小,即:多項(xiàng)式f與r的系數(shù)中1與-1的個(gè)數(shù)比較少,因而加減的計(jì)算量也較少。這種算法的代碼簡(jiǎn)單,系統(tǒng)執(zhí)行開銷少。1999年,Silverman提出了一種可以有效提高NTRU卷積的算法。通過分解一個(gè)多項(xiàng)式為兩部分并分別進(jìn)行卷積,理論上可使乘操作減少到(3/4)wN2次。但是應(yīng)該注意,由于多次分解多項(xiàng)式及遞歸,不可避免地帶來了額外的運(yùn)行開銷,如果權(quán)衡不佳,那么系統(tǒng)的整體性能就會(huì)下降。以上4種卷積算法根據(jù)參加運(yùn)算的2個(gè)多項(xiàng)式的特點(diǎn)不同,在執(zhí)行時(shí)運(yùn)算的速度也不同,將在后面時(shí)間分析時(shí)給出詳盡的說明。2.3加密通信軟件文件基本算法編制完成后,就可以調(diào)用它們來實(shí)現(xiàn)密鑰的產(chǎn)生以及加、解密運(yùn)算,主要偽碼如下:(1)密鑰產(chǎn)生模塊NTRUCreateKey(N,q,p,f,g,h,Fp,Fq){計(jì)算f模q的逆元Fq;計(jì)算f模p的逆元Fp;計(jì)算h=g?Fq(modq);for(i=0;i<N;i++){if(h[i]<0)h[i]=h[i]+q;h[i]=(h[i]×p)%q;}}(2)加密模塊NTRUEncode(N,q,r,m,h,e){計(jì)算e=r?h(modq);for(i=0;i<N;i++)e[i]=(e[i]+m[i])%q;}(3)解密模塊NTRUDecode(N,q,p,f,Fp,e,d){計(jì)算a=f?e(modq);for(i=0;i<N;i++){if(a[i]<0)a[i]=a[i]+q;if(a[i]>q/2)a[i]=a[i]-q;//調(diào)整系數(shù)于區(qū)間(-q/2,q/2)}計(jì)算d=Fp?a(modp);}加解密文件時(shí),調(diào)用NTRUEncode過程便可對(duì)這個(gè)數(shù)據(jù)塊進(jìn)行加密。解密時(shí),調(diào)用NTRUDecode過程對(duì)數(shù)據(jù)塊進(jìn)行解密。反復(fù)重復(fù)上述過程,便可實(shí)現(xiàn)對(duì)文件的加解密。系統(tǒng)執(zhí)行框圖如圖1所示。3實(shí)驗(yàn)4:4種算法間的卷積執(zhí)行實(shí)驗(yàn)在測(cè)試前首先對(duì)NTRU3大模塊的主要運(yùn)算及其特點(diǎn)作簡(jiǎn)要分析。為了方便,把系數(shù)平均分布在(-q/2,q/2)之間(否則做模q處理),0的個(gè)數(shù)極少的多項(xiàng)式稱為大多項(xiàng)式。密鑰生成模塊NTRUCreateKey需要計(jì)算f模p、模q逆,一次卷積運(yùn)算Fq?g(modq),其中,g為小多項(xiàng)式,實(shí)驗(yàn)發(fā)現(xiàn)Fq一般為大多項(xiàng)式。解密模塊NTRUDecode需要計(jì)算2次卷積:a=f?e(modq)及d=Fp?a(modp),其中,f為小多項(xiàng)式,e,Fp和a一般為大多項(xiàng)式。加密模塊NTRUEncode需要計(jì)算一次卷積:e=r?h+m(modq),其中,r為小多項(xiàng)式,而h為大多項(xiàng)式。對(duì)NTRU系統(tǒng)進(jìn)行了兩方面的實(shí)驗(yàn),第1部分是對(duì)卷積運(yùn)算4種算法的執(zhí)行情況進(jìn)行了測(cè)試、分析。第2部分對(duì)NTRU的密鑰產(chǎn)生過程、加密過程以及解密過程進(jìn)行了測(cè)試、分析,并給出一種可小幅優(yōu)化NTRU性能的策略。采用NTRU的4組標(biāo)準(zhǔn)參數(shù)值進(jìn)行測(cè)試,平臺(tái)為550MHzPentinumIIPC機(jī),內(nèi)存為128M,操作系統(tǒng)為Windows98SE,編譯器為MSVisualC++6.0。(1)前面給出了卷積的4種算法,不妨依次稱為一般算法、條件算法、移位算法以及遞歸算法。對(duì)這4種算法,分別進(jìn)行卷積執(zhí)行實(shí)驗(yàn)。實(shí)驗(yàn)分為2項(xiàng),一項(xiàng)是對(duì)2個(gè)大多項(xiàng)式分別測(cè)試前3種算法的運(yùn)算速度,另一項(xiàng)是對(duì)一個(gè)小多項(xiàng)式和一個(gè)大多項(xiàng)式分別測(cè)試以上4種算法的運(yùn)算速度。測(cè)試中,遞歸算法反復(fù)遞歸調(diào)用自己直到被分解多項(xiàng)式的次數(shù)小于Cstop值(Cstop值為分解多項(xiàng)式的最小次數(shù))。N=503時(shí),Cstop值取128和64,其余情況取64和32。小多項(xiàng)式的系數(shù)從集合{-1,0,1}中隨機(jī)生成,大多項(xiàng)式的系數(shù)隨機(jī)地從區(qū)間(-q/2,q/2)按正態(tài)分布隨機(jī)產(chǎn)生。測(cè)試的樣本空間為5000組數(shù)據(jù)塊,每一個(gè)數(shù)據(jù)塊的長(zhǎng)度為當(dāng)前參數(shù)N的值,采用單位blks/s來度量運(yùn)行的平均時(shí)間。上述兩項(xiàng)實(shí)驗(yàn)結(jié)果如表5和表6所示。由此可見,在測(cè)試1中,一般算法的執(zhí)行速度明顯要比條件算法快很多。而在測(cè)試2中,它的執(zhí)行速度卻比不上條件算法。從算法的實(shí)現(xiàn)上來分析,對(duì)于條件算法,多項(xiàng)式系數(shù)中0的個(gè)數(shù)越多,乘加次數(shù)減少的就越多,算法效率就越好。相反地,如果多項(xiàng)式系數(shù)分布比較平均,0的個(gè)數(shù)極少,那么條件算法就退化為一般算法,且由于還需要執(zhí)行一些額外的判斷,反而速度不及一般算法。而對(duì)于一般算法,不管多項(xiàng)式系數(shù)如何,它都要完全執(zhí)行N2次乘加操作,因而多項(xiàng)式的系數(shù)分布對(duì)它沒有什么影響。這也是為什么會(huì)產(chǎn)生以上結(jié)果的主要原因。至于遞歸算法理論上只要(3/4)wN2次乘加操作便可完成運(yùn)算,應(yīng)比其它算法快,但從2個(gè)表中數(shù)據(jù)可以看出,除了個(gè)別N值非常大的情況外,它執(zhí)行的結(jié)果并不理想。究其原因是遞歸調(diào)用造成了大量運(yùn)算時(shí)間的浪費(fèi),使執(zhí)行效率降低。從表中可以清楚地看到,隨著Cstop值減少一倍,即遞歸調(diào)用多了一層,調(diào)用過程的系統(tǒng)耗費(fèi)導(dǎo)致算法運(yùn)行時(shí)間急劇下降。至于移位算法,由于它把卷積運(yùn)算轉(zhuǎn)化為移位加、減運(yùn)算并對(duì)代碼進(jìn)行了優(yōu)化,因而在測(cè)試2中,它的運(yùn)行時(shí)間自然是最少的,但是它要求2個(gè)多項(xiàng)式中必須有一個(gè)小多項(xiàng)式,且其1和-1系數(shù)盡可能的少。該算法是一個(gè)較理想的算法,且硬件實(shí)現(xiàn)也較容易。結(jié)論是:當(dāng)2個(gè)多項(xiàng)式的系數(shù)分布比較平均,且0的個(gè)數(shù)極少的情況,最好使用一般算法。而當(dāng)2個(gè)多項(xiàng)式中一個(gè)為小多項(xiàng)式,且0的個(gè)數(shù)極少的情況下,最好用移位算法。一般情況下,因通用性的原因,NTRU實(shí)現(xiàn)卷積時(shí)大多采用條件算法。另外,還發(fā)現(xiàn)2個(gè)整數(shù)的乘運(yùn)算以及一個(gè)整數(shù)的取余運(yùn)算是很耗時(shí)的2個(gè)運(yùn)算,而加減運(yùn)算耗時(shí)非常少。因此,在設(shè)計(jì)卷積算法時(shí),一定不要把多項(xiàng)式模q或模p運(yùn)算放在卷積運(yùn)算當(dāng)中一并實(shí)現(xiàn),這樣運(yùn)算效率會(huì)大幅下降,而應(yīng)該在求出卷積結(jié)果后再進(jìn)行模運(yùn)算。(2)在本實(shí)驗(yàn)中,采用條件算法、移位算法和一般算法,對(duì)NTRU的密鑰產(chǎn)生、加密過程以及解密過程的執(zhí)行時(shí)間分別進(jìn)行了測(cè)試。測(cè)試分2種情況:其一,3個(gè)模塊中的所有卷積都用條件算法實(shí)現(xiàn);其二,3個(gè)模塊中密鑰產(chǎn)生、加密過程以及解密過程中除解密過程第2個(gè)卷積用一般算法來實(shí)現(xiàn),其余卷積用移位算法來實(shí)現(xiàn)。實(shí)驗(yàn)的結(jié)果如表7和表8所示。從表7可見,NTRU在運(yùn)算速度上的優(yōu)勢(shì)是RSA等公鑰密碼體制不可比擬的,至少應(yīng)比它們高出一個(gè)數(shù)量等級(jí)。另外,表8顯示的整體性能比表7顯示的整體性能要好得多。由于密鑰生成模塊的主要時(shí)間用在求2個(gè)小多項(xiàng)式的逆多項(xiàng)式運(yùn)算上,因而卷積運(yùn)算效率的提高,對(duì)該模塊無太大意義。從表中數(shù)據(jù)看,NTRU密鑰對(duì)的生成速度沒有什么顯著的提高,在不同參數(shù)下相應(yīng)的值變化不大。而由于卷積運(yùn)算是NTRU加解密模塊的主要運(yùn)算,在采用了效率更高的移位算法后,NTRU加解密的速度都相應(yīng)的增加了3～5倍,性能得到了很大的提高。4ntr