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

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

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