NTRU算法的分析

第30卷增计算机工程2004年12月VoL30 Supplementary IssueComputer EngineeringDecember 2004●安全技术●文章编号: 1000 -34282004)增刊- -0308- -02文献标识码: A中圈分类号: TP393.08NTRU算法的分析陈克耀,谢康林(.上海交通大学计算机科学与工程系，上海200030)摘要: 介绍了一种新的公开密钥体制NTRU算法，NTRU算 法的安全性是基于数论中在-一个非常大的维数格中寻找一个很短向量的数学难题。NTRU算怯与RSA等算法相比具有更高的运算速度，更快的密钥生成速度和更少的存储空间，尽管在安全性方面与RSA相比有一些缺陷.但也有弥补的方法，因此NTRU算法将会有更广阔的应用前景。关健词: NTRU;公开密钥体制; 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)公开密钥体制是由同，但要将乘积后的X“变成1,X"“变成X, X**变成X, ...美国数学家(effrey HofsteinjJllPipher,Joseph H.Silverman)1.3 NTRU密钥的产生发明的，其安全性是基于数论中在一一个非常大的维数格中寻根据NTRU參数N，首先随机选择两个多项式f、g为使f找一个很短向量的数学难题。在实际应用中，由于在相同安对模p、模q的乘逆存在，f首先应满足gcd(f.pg)=|条件,分全级的前提下，NTRU比RSA算法运行的速度要快许多倍，别用fp、fq代表f对模p、模q的乘逆.即其密钥生成也更快，且需要的存储空间更少,这意味着降低f.fq≠lmodqandf.fp=1modp()了对处理器、存储器的性能要求，扩大了应用范围。尽管计算:h=p . fq. g (mod q)(2NTRU在解密系统方面有缺陷，攻击者可能利用这一一点发起.NTRU算法取私人密钥为一对多项式环(fp),公开密钥攻击，但是这个缺陷是可以补救的。总之，NTRU算法的发为多项式环h。明是计算机密码学的一一个重大成果，很有可能取代RSA等算1.4 NTRU算法的加密过程法成为公开密钥体制中最优秀的算法。设有明文多项式m,根据参数d随机选择多项式,使用公1 NTRU算法的描述开密钥h,按公式(3)对明文m加密，得到密文e.1.1 NTRU算法的数论基础"e=(r. h+ m) mod q设有整数环Z、整数N≥>2， 用R表示多项式截断环1.5 NTRU算法的解密过程(runcated polynomial rings)时，R可写成:用一对私人密钥(,fp) 解密密文e,计算:R= -Z[X]/ (X"-1)a=f. e( mod q)(4b=a (mod p)(5)对于任意正整数q,令R代表模q的多项式截断环时，R可c=fp●b(mod p)(6以写成:多项式c就是解密后的明文m。R = (ZZ)[X](X"-I)可证明当q是素数时，R具有可逆性。即对f, 有f* 满足:1.6 NTRU算法解密成功的推导”解密的执行过程可推导如下:f.f*=l modq1.2 NTRU算法参数=f.(r●h+m) ( mod q)NTRU算法需要3个整数参数(N,p.q) 和f、g T、m具(因为e=(r.h+m)modq)有的N-1阶多项式环。=f.(r. pfq . g+m) ( modq)设f、g r m是N-I阶多项式环，即(因为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*作者简介:陈克耀(195-)，男，硕士生，研究方向:计算机应多项式环之间的加、减运算与普通多项式的加、减运算用;谢康林，教授完全相同。多项式环之间相乘时与普通多项式相乘基本相收稿日期: 2004-08-15E-mail: wuxickyao@yahoo.com.cn08-选取的多项式, g, f和m的系数都很小，即r. g和f.mz=q/2,那么恢复的将是实际值的-1倍。所以还需要对f和-f都比q小又因为p小于q,所以(pr. g+f. m)多项式的系数在做-个校验选择。在以上寻找f的过程中有两点假设需要指出: (1)必须有z性,是]之间，模q运算不起作用。则的一个系数在范围之内; (2)z的其余的系数在[-q/2+2,q/2-1]b=a (mod p)的范围以内。如果这两个条件中有任何-一个不满足，当Mi==(pr. g+f. m)( mod p)0的时候，将会引起ε "(M'";)和E "(M";)的不可解密，这种(因为pr . g(mod p)=0)不可解密的结果是由于z超出范围引起的，这会引起5.=0的=f. m( mod p)错误。事实上,上面两点假设不成立的机会是非常小的。即c=fp.b(modp)=fp.f.m(modp)使真的出现了这种情况，攻击者只要对M和r稍做修改然后(因为f. fp=l mod p)再从步骤(2)开始或者直接回到步骤(1)从头开始。1.8 NTRU解密系统的缺陷的补教措施"= m(mod p)为了防止攻击者利用这- 点来进行攻击，NTRU在提高因为m的系数在[-是, 只]之间,所以c=m解密成功。系统安全性方面也做了相应的改进:引入了REACT改进算1.7 NTRU解密系统的缺陪"法(Rapid Enhanced-securityAsymmetric Cryptosystem但是NTRU公钥加密系统并没有提供完善的解密机制。Transform，高速增强型非对称加密系统改进算法)。这个算也就是说存在着用公钥加密产生合法密文不能被私钥解密的法引入了两个哈氏函数G和H,这两个哈氏函数分别各自产现象。攻击者可能利用这一点来进行攻击。攻击者会利用生k1比特和k2比特的字符串，从而使传统的NTRU的PKE nDC判断程序来判断合法的密文是否被正确解密,通过系统=(k,ε ,D)转化为PKE IT*=(k",ε ",D")。提供的相关信息来恢复用户的私钥。其中k"=k, ε "<(m;S,R):利用随机产生的S和R计算出ClNTRU加密系统没能提供完普的解密机制。对一对密钥e a(S,R), m是k1比特参与产生密文的信息，C2=G(S)田 m,环(pk,sk)而言，存在着用pk产生的密文m,却不能用sk正确C3=H(S,m,CI,C2)，最后由(CI,C2,C3)产生密文。解密。因为正确的解密依赖于私钥，所以当正确的密文不能D.(CI,C2,C3):S'= D.(CI), m'=G(S)田 C2, C3=H(m'$S,被正确的解密时，在解密的过程中就有可能泄露关于私钥的C1,C2)，如果产生的S是合法的且C3=C3',那么就输出m',即信息。m'就是所需的结果。下面来分析一下针对NTRU的这个弱点，攻击者是如何现在让我们来看- - 下如果攻击者采用以前的方法来进行进行攻击的。这种攻击-般是邮3个步骤组成的。攻击会怎样:步骤1:这一步骤的目标就是要找到函数(m,) [.x[,(1)选择参与II的运算的k位比特的信息m, m-.m和k从而可以产生-一个不可解密的密文。最简单的办法就是不断位比特的S,",S.ε M,以及参与I运算的..-,R.地选择m和r，并利用DC判断程序来校验其是否不可解密。(2)对1<=i<=k,计算ε "(m;SRlle)=(Cli,C2i,C3i)，其如果其不可解密的话,那就意味着步骤|的任务已经完成中e是k比特的{0,1}向量,这个向量除了第i个值之外,其余的了。可以看出，如果利用穷举法不断地寻找和尝试并不是一值是0。个很好的方法，工作量将是非常大的。可以看到，对于m和(3)对1<=i<=-k,送(Cli,C2i,C3i)到I的DC判断程序进行r反复用DC判断程序来校验e=ε "(m;)是否不可解密等同于密文的合法性校验。但是由于H和G在产生密文的过程中参判断m和r是否在的范围之内。比随机寻找m和r更为方便与运算, C2=G(S)田m,C3=H(S,m,Cl,C2),攻击者是无法获得和准确的方法是利用系统過近法来找到的最大交集。不可解密密文的详细信息的，也就无法恢复密钥了。步骤2:假设在步骤I中已经找到函数(m,)E[.x{[,如从以上的分析中可以看出, NTRU在引入REACT算法果要保证e=ε "(m; r)是不可解密的，那么mf+tpg的系数中后，对DC判断程序而言能够拿到的只是密文y和解密后的至少有一个在(-q/2, q/2]之外。现在攻击者在这-一步骤要做m,无论Da(y)是否等于m。而不再像以前那样在校验到不可的就是如何使e“"(0; r)不可解密，或者是找M2[m,从而使解密的密文是可以获得密钥的一些相关信息。所以引入ε N,(M; r)是不可解密的。注意此时Mf+rpg的所有系数都在REACT后的NTRU在安全性方面是进一一步得到了提高。[-/2,/2+1]的范围之内，只要将M的任何非0比特转化为0，2 NTRU算法的实现优势那么ε“(M;r也就变成可以解密的了。(1)速度E因为M和的所有系数都在{-1, 0, |}以内，当M的一个RSA的基本运算是.上千位的求幂操作，而NTRU算法运系数变为0时，则Z的系数会变为-1,0,或者1。当在重复过程算是小于255的操作。因为当密钥长度为I 000~2 00bits时中出现M不等于0且ε "(M;r)可以解密,则可以终止上述过RSA儒要运算完整的长密钥，而NTRU则可以把密钥拆成小程,即步骤2的工作结束。步骒3:现在假设在步骤2中已经找到了(M,r),从而使块，通常7~8bits -块。所以NTRU的运算速度要快得多。(2)系统需求ε "(M;)]不可解密。此时z=Mftrpg的 系数在[9/2,q/2+1]的范资源上的需求要小，围之内，其中只要M的任何非0位设为0，则e“(M;)将是可并且更中国煤化工以解密的。反过来也就是说如果ε "(M;r)是不可解密的，则fYHCNMHGz至少有一个系数在{-q/2,9/2+1}的范围之内。NTRU的随机选择多项式r或长密钥拆成小块都增加了现在可以假设，如果只有一个系数j在{-9/2,q/2+1}之加密处理的安全性和密钥生成速度。间，其余的系数都在[-q/2+2,q/2-1]之间。(下转第322页)当然对于上述步骤是在z = q/2+1的前提下作出的，如果4.2 MPLS网络密码设备设计原理纤的发送信号转换成电信号,再由协议处理器进行拆分并还密码设备要加密的对象是用户数据，而不能对信令和网原出帧中继帧，然后根据帧头DLCI进行识别，如是信令帧络管理维护帧或信元加密,否则逻辑连接将无法建立，网络则不作加密处理，如是用户信息帧则应进行加密处理。在进设备无法得到管理和维护。下面针对MPLS/ATM、.MPLS/行加密处理时，需提取帧头中的MPLS的标签来选择用户密FR、. MPLS/PPP3种网络进行加解密分析。钥，并将密钥和用户信息送入加密模块进行加密处理。加了(1)对于ATM(异步转移模式)，MPLS直接采用VPI/VCI密的信息安装上原帧中继头，再交由协议处理器进行封装并作为转发的标签，信元中的5字节信元头用于交换路由、流由物理层转换成光信号向网络发送;在解密过程中，首先由量控制等网络控制管理，用户数据信元中的加密对象应该是物理层将来自网络的信号转换成电信号，再由协议处理器进信元中48字节数据净荷部分。在ATM网络中规定了净荷类行拆分并还原出帧中继帧，然后根据据帧头DLCI进行识型标识域PTI1从000-01 I是用户数据信元，100- 11用于信别，如是信令帧则不作解密处理，如是用户信息帧则应进行令和管理信元; VCI从0-31用于信令信元，31以上用于用解密处理。户数据信元。引入MPLS后，LDP信令通道是VPI=0, VCl=(3)对于PPP是一个简单的OSI第2层网络协议。其标头32。密码设备可根据此规则判断是用户数据信元还是信令和只有两个字节，没有地址信息，只是按点到点顺序，面向无管理信元。主控制器根据MPLS的标签选取相应的用户密钥连接。对于该种方式加密处理很简单，对MPLS包头以后的的，调用加解密算法，对信元的数据净荷进行加解密。密码信息全部加密。设备对用户数据信元信息进行处理时，不改变原信元的结5结束语构。在加密过程中，首先由物理层将来自端设备光纤的发送本文在对MPLS交换的协议及其网络结构进行了分析讨信号转换成电信号，再由协议处理器进行拆分并还原出论后，提出了MPLS网络的加密方法，并设计了相应的网络ATM信元，然后根据信元头进行信元识别，如是信令信元密码设备，针对ATM、FR、PPP 3种链路层提出具体解决办则不作加密处理，如是用户信元则应进行加密处理。在进行法。密码设备采用硬件加解密，处理速度快，传输延时小。加密处理时，需提取信元头中的MPLS的标签以选择用户密同时密码设备的接入不影响原网络系统结构;不修改网络节钥，并将密钥和用户信元的净荷信息送入加密模块进行加密点的配置;不占用网络的地址资源;对上层完全透明，提高处理。加了密的信息安装上原ATM层信元头，再交由协议了MPLS网络安全性。处理器进行封装并由物理层转换成光信号向网络发送;在解伴随着信息共享所带来的便利，信息的安全性也呈现出密过程中，首先由物理层将来自网络的信号转换成电信号，日益重要的地位，MPLS网络加密技术的研究对通信网的信再由协议处理器进行拆分并还原出ATM信元，然后根据信息保密和网络安全有着重要的实用价值，而且对密码工程技元头进行信元识别，如是信令信元则不作解密处理，如是用术具有重要的学术意义。户信元则应进行解密处理。文献(2)对于FR(帧中继)，MPLS则直接采用DLCI作为转发. I肖萍萍，吴健学,周芳等编著. SDH原理与技术北京:邮电大学的标签，信令帧是标准的帧中继帧，它们用保留的DLCI以2沈鑫剡. IP交换网原理、技术及实现.北京:人民邮电出版社, 2002出版社.2002区别用户数据。LMI信令协议用DLCI =1023, ITU-T和ANSI3 Sallings W. Data and Computer Communication(3rd Edition) .北京:清信令协议用DLCI= 0，MPLS默认的信令通道是DLCI=IS。华大学出版社, 1997包括以上的3个DLCI值，DLCI 0-15、1008- 1023均被系统保肖丹. ATM互联网络技术及应用.北京:人民邮电出版社. 1998留，以备以后网络扩展服务使用。用户信息帧的DLCI范围5高飞高平编. 计算机网络和网络安全基础.北京:理工大学出是16-1007。在加密过程中，首先由物理层将来自端设备光版社，2002(_上接第309页)NTRU算法克服了RSA运算速度慢(尤其是密钥生成和3 NTRU Cryptosystems Technical Report #01S[R]. Articles at www.ntru.comi解密过程)和需要大数求幕运算，对系统要求高的缺点,使4 Goldreich O, Goldwasser s, Halvei s. Public key Cryptography from其在移动通信安全认证领域得到广泛应用。Lattice Reduction Problems[C]. In:proc CRYPTO97,Lect. Notes in3结束语Computer Science 1294.pringer-verlag, 1997本文简单介绍NTRU公开密钥体制，虽然NTRU在解密5 Cohen H. A Course in Compulational Algcbraic Number Theory,Graduate Texts in Math{M]. Springer Verlag Berlin,1993:138体系方面有一些缺陷，但是已经找到了补救方法，而且加密6 NTRU Cryptosytems Technical Repont #014. www.ntru.com系统和攻击永远是同时发展的，没有真正意义上永远安全的7 NTRU Cryptosystems Technical Report #009. www .ntru.com加密算法，不管怎么样，NTRU算法被认为是公开密钥体制8 Goldreich O, Goldwasser S.Halvei S.Public-key Cryprography from中最快的算法，也是比较容易实现的算法。因此，NTRU算Lattice Reduction Problems.roc. CRYPTO97,Lect.Notcs in Computer法很有可能取代RSA等算法而得到广泛的应用，尤其是在移9卢开湿计算机密码学(第)版)业 商:清华大学出版社, 1998Sciencel294,Springer-Verlag, 1997动通信安全认证领域。銬文献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-