NTRU算法的分析

第30卷增計算機工程2004年12月VoL30 Supplementary IssueComputer EngineeringDecember 2004●安全技術(shù)●文章編號: 1000 -34282004)增刊- -0308- -02文獻標識碼: A中圈分類(lèi)號: TP393.08NTRU算法的分析陳克耀,謝康林(.上海交通大學(xué)計算機科學(xué)與工程系，上海200030)摘要: 介紹了一種新的公開(kāi)密鑰體制NTRU算法，NTRU算 法的安全性是基于數論中在-一個(gè)非常大的維數格中尋找一個(gè)很短向量的數學(xué)難題。NTRU算怯與RSA等算法相比具有更高的運算速度，更快的密鑰生成速度和更少的存儲空間，盡管在安全性方面與RSA相比有一些缺陷.但也有彌補的方法，因此NTRU算法將會(huì )有更廣闊的應用前景。關(guān)健詞: NTRU;公開(kāi)密鑰體制; RSAAnalysis of NTRU AlgorithmCHEN Keyao, XIE Kanglin[Abstract ] This paper introduces a new public key cryplosystem which is called NTRU algorihm. The security of the NTRU is based on the hardmathematical problem of finding very short vectors in laties of very high dimension . NTRU has very high speed of computation and very fast speed ofkey creation and very less space of storage than RSA and so on. Although NTRU has some defects in its security compared with RSA, the remedialactions have been found and applied into NTRU.[Key words I NTRU ; Public key cryptosystem; RSANTRU(Number Theory Research Unit)公開(kāi)密鑰體制是由同，但要將乘積后的X“變成1,X"“變成X, X**變成X, ...美國數學(xué)家(effrey HofsteinjJllPipher,Joseph H.Silverman)1.3 NTRU密鑰的產(chǎn)生發(fā)明的，其安全性是基于數論中在一一個(gè)非常大的維數格中尋根據NTRU參數N，首先隨機選擇兩個(gè)多項式f、g為使f找一個(gè)很短向量的數學(xué)難題。在實(shí)際應用中，由于在相同安對模p、模q的乘逆存在，f首先應滿(mǎn)足gcd(f.pg)=|條件,分全級的前提下，NTRU比RSA算法運行的速度要快許多倍，別用fp、fq代表f對模p、模q的乘逆.即其密鑰生成也更快，且需要的存儲空間更少,這意味著(zhù)降低f.fq≠lmodqandf.fp=1modp()了對處理器、存儲器的性能要求，擴大了應用范圍。盡管計算:h=p . fq. g (mod q)(2NTRU在解密系統方面有缺陷，攻擊者可能利用這一一點(diǎn)發(fā)起.NTRU算法取私人密鑰為一對多項式環(huán)(fp),公開(kāi)密鑰攻擊，但是這個(gè)缺陷是可以補救的?？傊?，NTRU算法的發(fā)為多項式環(huán)h。明是計算機密碼學(xué)的一一個(gè)重大成果，很有可能取代RSA等算1.4 NTRU算法的加密過(guò)程法成為公開(kāi)密鑰體制中最優(yōu)秀的算法。設有明文多項式m,根據參數d隨機選擇多項式,使用公1 NTRU算法的描述開(kāi)密鑰h,按公式(3)對明文m加密，得到密文e.1.1 NTRU算法的數論基礎"e=(r. h+ m) mod q設有整數環(huán)Z、整數N≥>2， 用R表示多項式截斷環(huán)1.5 NTRU算法的解密過(guò)程(runcated polynomial rings)時(shí)，R可寫(xiě)成:用一對私人密鑰(,fp) 解密密文e,計算:R= -Z[X]/ (X"-1)a=f. e( mod q)(4b=a (mod p)(5)對于任意正整數q,令R代表模q的多項式截斷環(huán)時(shí)，R可c=fp●b(mod p)(6以寫(xiě)成:多項式c就是解密后的明文m。R = (ZZ)[X](X"-I)可證明當q是素數時(shí)，R具有可逆性。即對f, 有f* 滿(mǎn)足:1.6 NTRU算法解密成功的推導”解密的執行過(guò)程可推導如下:f.f*=l modq1.2 NTRU算法參數=f.(r●h+m) ( mod q)NTRU算法需要3個(gè)整數參數(N,p.q) 和f、g T、m具(因為e=(r.h+m)modq)有的N-1階多項式環(huán)。=f.(r. pfq . g+m) ( modq)設f、g r m是N-I階多項式環(huán)，即(因為h=p. fq . g(mod q))deg()-deg(g) = deg(r)=deg(m)=N-1,fgr.m∈Rf(f++8+.+.x*..中國煤化工g-g+gxX+*+..uX.MHCNMHGm-m+m,X+m.X+..+muxX*作者簡(jiǎn)介:陳克耀(195-)，男，碩士生，研究方向:計算機應多項式環(huán)之間的加、減運算與普通多項式的加、減運算用;謝康林，教授完全相同。多項式環(huán)之間相乘時(shí)與普通多項式相乘基本相收稿日期: 2004-08-15E-mail: wuxickyao@yahoo.com.cn08-選取的多項式, g, f和m的系數都很小，即r. g和f.mz=q/2,那么恢復的將是實(shí)際值的-1倍。所以還需要對f和-f都比q小又因為p小于q,所以(pr. g+f. m)多項式的系數在做-個(gè)校驗選擇。在以上尋找f的過(guò)程中有兩點(diǎn)假設需要指出: (1)必須有z性,是]之間，模q運算不起作用。則的一個(gè)系數在范圍之內; (2)z的其余的系數在[-q/2+2,q/2-1]b=a (mod p)的范圍以?xún)?。如果這兩個(gè)條件中有任何-一個(gè)不滿(mǎn)足，當Mi==(pr. g+f. m)( mod p)0的時(shí)候，將會(huì )引起ε "(M'";)和E "(M";)的不可解密，這種(因為pr . g(mod p)=0)不可解密的結果是由于z超出范圍引起的，這會(huì )引起5.=0的=f. m( mod p)錯誤。事實(shí)上,上面兩點(diǎn)假設不成立的機會(huì )是非常小的。即c=fp.b(modp)=fp.f.m(modp)使真的出現了這種情況，攻擊者只要對M和r稍做修改然后(因為f. fp=l mod p)再從步驟(2)開(kāi)始或者直接回到步驟(1)從頭開(kāi)始。1.8 NTRU解密系統的缺陷的補教措施"= m(mod p)為了防止攻擊者利用這- 點(diǎn)來(lái)進(jìn)行攻擊，NTRU在提高因為m的系數在[-是, 只]之間,所以c=m解密成功。系統安全性方面也做了相應的改進(jìn):引入了REACT改進(jìn)算1.7 NTRU解密系統的缺陪"法(Rapid Enhanced-securityAsymmetric Cryptosystem但是NTRU公鑰加密系統并沒(méi)有提供完善的解密機制。Transform，高速增強型非對稱(chēng)加密系統改進(jìn)算法)。這個(gè)算也就是說(shuō)存在著(zhù)用公鑰加密產(chǎn)生合法密文不能被私鑰解密的法引入了兩個(gè)哈氏函數G和H,這兩個(gè)哈氏函數分別各自產(chǎn)現象。攻擊者可能利用這一點(diǎn)來(lái)進(jìn)行攻擊。攻擊者會(huì )利用生k1比特和k2比特的字符串，從而使傳統的NTRU的PKE nDC判斷程序來(lái)判斷合法的密文是否被正確解密,通過(guò)系統=(k,ε ,D)轉化為PKE IT*=(k",ε ",D")。提供的相關(guān)信息來(lái)恢復用戶(hù)的私鑰。其中k"=k, ε "<(m;S,R):利用隨機產(chǎn)生的S和R計算出ClNTRU加密系統沒(méi)能提供完普的解密機制。對一對密鑰e a(S,R), m是k1比特參與產(chǎn)生密文的信息，C2=G(S)田 m,環(huán)(pk,sk)而言，存在著(zhù)用pk產(chǎn)生的密文m,卻不能用sk正確C3=H(S,m,CI,C2)，最后由(CI,C2,C3)產(chǎn)生密文。解密。因為正確的解密依賴(lài)于私鑰，所以當正確的密文不能D.(CI,C2,C3):S'= D.(CI), m'=G(S)田 C2, C3=H(m'$S,被正確的解密時(shí)，在解密的過(guò)程中就有可能泄露關(guān)于私鑰的C1,C2)，如果產(chǎn)生的S是合法的且C3=C3',那么就輸出m',即信息。m'就是所需的結果。下面來(lái)分析一下針對NTRU的這個(gè)弱點(diǎn)，攻擊者是如何現在讓我們來(lái)看- - 下如果攻擊者采用以前的方法來(lái)進(jìn)行進(jìn)行攻擊的。這種攻擊-般是郵3個(gè)步驟組成的。攻擊會(huì )怎樣:步驟1:這一步驟的目標就是要找到函數(m,) [.x[,(1)選擇參與II的運算的k位比特的信息m, m-.m和k從而可以產(chǎn)生-一個(gè)不可解密的密文。最簡(jiǎn)單的辦法就是不斷位比特的S,",S.ε M,以及參與I運算的..-,R.地選擇m和r，并利用DC判斷程序來(lái)校驗其是否不可解密。(2)對1<=i<=k,計算ε "(m;SRlle)=(Cli,C2i,C3i)，其如果其不可解密的話(huà),那就意味著(zhù)步驟|的任務(wù)已經(jīng)完成中e是k比特的{0,1}向量,這個(gè)向量除了第i個(gè)值之外,其余的了?？梢钥闯?，如果利用窮舉法不斷地尋找和嘗試并不是一值是0。個(gè)很好的方法，工作量將是非常大的?？梢钥吹?，對于m和(3)對1<=i<=-k,送(Cli,C2i,C3i)到I的DC判斷程序進(jìn)行r反復用DC判斷程序來(lái)校驗e=ε "(m;)是否不可解密等同于密文的合法性校驗。但是由于H和G在產(chǎn)生密文的過(guò)程中參判斷m和r是否在的范圍之內。比隨機尋找m和r更為方便與運算, C2=G(S)田m,C3=H(S,m,Cl,C2),攻擊者是無(wú)法獲得和準確的方法是利用系統過(guò)近法來(lái)找到的最大交集。不可解密密文的詳細信息的，也就無(wú)法恢復密鑰了。步驟2:假設在步驟I中已經(jīng)找到函數(m,)E[.x{[,如從以上的分析中可以看出, NTRU在引入REACT算法果要保證e=ε "(m; r)是不可解密的，那么mf+tpg的系數中后，對DC判斷程序而言能夠拿到的只是密文y和解密后的至少有一個(gè)在(-q/2, q/2]之外?，F在攻擊者在這-一步驟要做m,無(wú)論Da(y)是否等于m。而不再像以前那樣在校驗到不可的就是如何使e“"(0; r)不可解密，或者是找M2[m,從而使解密的密文是可以獲得密鑰的一些相關(guān)信息。所以引入ε N,(M; r)是不可解密的。注意此時(shí)Mf+rpg的所有系數都在REACT后的NTRU在安全性方面是進(jìn)一一步得到了提高。[-/2,/2+1]的范圍之內，只要將M的任何非0比特轉化為0，2 NTRU算法的實(shí)現優(yōu)勢那么ε“(M;r也就變成可以解密的了。(1)速度E因為M和的所有系數都在{-1, 0, |}以?xún)?，當M的一個(gè)RSA的基本運算是.上千位的求冪操作，而NTRU算法運系數變?yōu)?時(shí)，則Z的系數會(huì )變?yōu)?1,0,或者1。當在重復過(guò)程算是小于255的操作。因為當密鑰長(cháng)度為I 000~2 00bits時(shí)中出現M不等于0且ε "(M;r)可以解密,則可以終止上述過(guò)RSA儒要運算完整的長(cháng)密鑰，而NTRU則可以把密鑰拆成小程,即步驟2的工作結束。步騍3:現在假設在步驟2中已經(jīng)找到了(M,r),從而使塊，通常7~8bits -塊。所以NTRU的運算速度要快得多。(2)系統需求ε "(M;)]不可解密。此時(shí)z=Mftrpg的 系數在[9/2,q/2+1]的范資源上的需求要小，圍之內，其中只要M的任何非0位設為0，則e“(M;)將是可并且更中國煤化工以解密的。反過(guò)來(lái)也就是說(shuō)如果ε "(M;r)是不可解密的，則fYHCNMHGz至少有一個(gè)系數在{-q/2,9/2+1}的范圍之內。NTRU的隨機選擇多項式r或長(cháng)密鑰拆成小塊都增加了現在可以假設，如果只有一個(gè)系數j在{-9/2,q/2+1}之加密處理的安全性和密鑰生成速度。間，其余的系數都在[-q/2+2,q/2-1]之間。(下轉第322頁(yè))當然對于上述步驟是在z = q/2+1的前提下作出的，如果4.2 MPLS網(wǎng)絡(luò )密碼設備設計原理纖的發(fā)送信號轉換成電信號,再由協(xié)議處理器進(jìn)行拆分并還密碼設備要加密的對象是用戶(hù)數據，而不能對信令和網(wǎng)原出幀中繼幀，然后根據幀頭DLCI進(jìn)行識別，如是信令幀絡(luò )管理維護幀或信元加密,否則邏輯連接將無(wú)法建立，網(wǎng)絡(luò )則不作加密處理，如是用戶(hù)信息幀則應進(jìn)行加密處理。在進(jìn)設備無(wú)法得到管理和維護。下面針對MPLS/ATM、.MPLS/行加密處理時(shí)，需提取幀頭中的MPLS的標簽來(lái)選擇用戶(hù)密FR、. MPLS/PPP3種網(wǎng)絡(luò )進(jìn)行加解密分析。鑰，并將密鑰和用戶(hù)信息送入加密模塊進(jìn)行加密處理。加了(1)對于A(yíng)TM(異步轉移模式)，MPLS直接采用VPI/VCI密的信息安裝上原幀中繼頭，再交由協(xié)議處理器進(jìn)行封裝并作為轉發(fā)的標簽，信元中的5字節信元頭用于交換路由、流由物理層轉換成光信號向網(wǎng)絡(luò )發(fā)送;在解密過(guò)程中，首先由量控制等網(wǎng)絡(luò )控制管理，用戶(hù)數據信元中的加密對象應該是物理層將來(lái)自網(wǎng)絡(luò )的信號轉換成電信號，再由協(xié)議處理器進(jìn)信元中48字節數據凈荷部分。在A(yíng)TM網(wǎng)絡(luò )中規定了凈荷類(lèi)行拆分并還原出幀中繼幀，然后根據據幀頭DLCI進(jìn)行識型標識域PTI1從000-01 I是用戶(hù)數據信元，100- 11用于信別，如是信令幀則不作解密處理，如是用戶(hù)信息幀則應進(jìn)行令和管理信元; VCI從0-31用于信令信元，31以上用于用解密處理。戶(hù)數據信元。引入MPLS后，LDP信令通道是VPI=0, VCl=(3)對于PPP是一個(gè)簡(jiǎn)單的OSI第2層網(wǎng)絡(luò )協(xié)議。其標頭32。密碼設備可根據此規則判斷是用戶(hù)數據信元還是信令和只有兩個(gè)字節，沒(méi)有地址信息，只是按點(diǎn)到點(diǎn)順序，面向無(wú)管理信元。主控制器根據MPLS的標簽選取相應的用戶(hù)密鑰連接。對于該種方式加密處理很簡(jiǎn)單，對MPLS包頭以后的的，調用加解密算法，對信元的數據凈荷進(jìn)行加解密。密碼信息全部加密。設備對用戶(hù)數據信元信息進(jìn)行處理時(shí)，不改變原信元的結5結束語(yǔ)構。在加密過(guò)程中，首先由物理層將來(lái)自端設備光纖的發(fā)送本文在對MPLS交換的協(xié)議及其網(wǎng)絡(luò )結構進(jìn)行了分析討信號轉換成電信號，再由協(xié)議處理器進(jìn)行拆分并還原出論后，提出了MPLS網(wǎng)絡(luò )的加密方法，并設計了相應的網(wǎng)絡(luò )ATM信元，然后根據信元頭進(jìn)行信元識別，如是信令信元密碼設備，針對ATM、FR、PPP 3種鏈路層提出具體解決辦則不作加密處理，如是用戶(hù)信元則應進(jìn)行加密處理。在進(jìn)行法。密碼設備采用硬件加解密，處理速度快，傳輸延時(shí)小。加密處理時(shí)，需提取信元頭中的MPLS的標簽以選擇用戶(hù)密同時(shí)密碼設備的接入不影響原網(wǎng)絡(luò )系統結構;不修改網(wǎng)絡(luò )節鑰，并將密鑰和用戶(hù)信元的凈荷信息送入加密模塊進(jìn)行加密點(diǎn)的配置;不占用網(wǎng)絡(luò )的地址資源;對上層完全透明，提高處理。加了密的信息安裝上原ATM層信元頭，再交由協(xié)議了MPLS網(wǎng)絡(luò )安全性。處理器進(jìn)行封裝并由物理層轉換成光信號向網(wǎng)絡(luò )發(fā)送;在解伴隨著(zhù)信息共享所帶來(lái)的便利，信息的安全性也呈現出密過(guò)程中，首先由物理層將來(lái)自網(wǎng)絡(luò )的信號轉換成電信號，日益重要的地位，MPLS網(wǎng)絡(luò )加密技術(shù)的研究對通信網(wǎng)的信再由協(xié)議處理器進(jìn)行拆分并還原出ATM信元，然后根據信息保密和網(wǎng)絡(luò )安全有著(zhù)重要的實(shí)用價(jià)值，而且對密碼工程技元頭進(jìn)行信元識別，如是信令信元則不作解密處理，如是用術(shù)具有重要的學(xué)術(shù)意義。戶(hù)信元則應進(jìn)行解密處理。文獻(2)對于FR(幀中繼)，MPLS則直接采用DLCI作為轉發(fā). I肖萍萍，吳健學(xué),周芳等編著(zhù). SDH原理與技術(shù)北京:郵電大學(xué)的標簽，信令幀是標準的幀中繼幀，它們用保留的DLCI以2沈鑫剡. IP交換網(wǎng)原理、技術(shù)及實(shí)現.北京:人民郵電出版社, 2002出版社.2002區別用戶(hù)數據。LMI信令協(xié)議用DLCI =1023, ITU-T和ANSI3 Sallings W. Data and Computer Communication(3rd Edition) .北京:清信令協(xié)議用DLCI= 0，MPLS默認的信令通道是DLCI=IS。華大學(xué)出版社, 1997包括以上的3個(gè)DLCI值，DLCI 0-15、1008- 1023均被系統保肖丹. ATM互聯(lián)網(wǎng)絡(luò )技術(shù)及應用.北京:人民郵電出版社. 1998留，以備以后網(wǎng)絡(luò )擴展服務(wù)使用。用戶(hù)信息幀的DLCI范圍5高飛高平編. 計算機網(wǎng)絡(luò )和網(wǎng)絡(luò )安全基礎.北京:理工大學(xué)出是16-1007。在加密過(guò)程中，首先由物理層將來(lái)自端設備光版社，2002(_上接第309頁(yè))NTRU算法克服了RSA運算速度慢(尤其是密鑰生成和3 NTRU Cryptosystems Technical Report #01S[R]. Articles at www.ntru.comi解密過(guò)程)和需要大數求幕運算，對系統要求高的缺點(diǎn),使4 Goldreich O, Goldwasser s, Halvei s. Public key Cryptography from其在移動(dòng)通信安全認證領(lǐng)域得到廣泛應用。Lattice Reduction Problems[C]. In:proc CRYPTO97,Lect. Notes in3結束語(yǔ)Computer Science 1294.pringer-verlag, 1997本文簡(jiǎn)單介紹NTRU公開(kāi)密鑰體制，雖然NTRU在解密5 Cohen H. A Course in Compulational Algcbraic Number Theory,Graduate Texts in Math{M]. Springer Verlag Berlin,1993:138體系方面有一些缺陷，但是已經(jīng)找到了補救方法，而且加密6 NTRU Cryptosytems Technical Repont #014. www.ntru.com系統和攻擊永遠是同時(shí)發(fā)展的，沒(méi)有真正意義上永遠安全的7 NTRU Cryptosystems Technical Report #009. www .ntru.com加密算法，不管怎么樣，NTRU算法被認為是公開(kāi)密鑰體制8 Goldreich O, Goldwasser S.Halvei S.Public-key Cryprography from中最快的算法，也是比較容易實(shí)現的算法。因此，NTRU算Lattice Reduction Problems.roc. CRYPTO97,Lect.Notcs in Computer法很有可能取代RSA等算法而得到廣泛的應用，尤其是在移9盧開(kāi)濕計算機密碼學(xué)(第)版)業(yè) 商:清華大學(xué)出版社, 1998Sciencel294,Springer-Verlag, 1997動(dòng)通信安全認證領(lǐng)域。銬文獻10T1中國煤化工-A Tutorial. www .tru.com110Rapid Enancd-security| Hofstcin J, Pilpher J, Silverman J H. A Ring based Public KeyTYHCN M H Gn Poc. r35R100),Cryptosystem. Articles at www.ntru.comof LNCS, Spring-verlag 2001,202:19-1752 NTRU Cryptosystem Technical Report #013[R]. Articles at www.ntru.com-322-