NTRU的原理及安全性现状分析

《NTRU的原理及安全性现状分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NTRU的原理及安全性现状分析【摘要】NTRU一种比较新的公开密钥体制，由于NTRU产生的密钥方法比较容易，加密、解密的速度比RSA等著名算法快得多，NTRU成为当前公钥体制研究的一个热点。本文介绍了NTRU的原理，总结了对该算法密码分析的结果，给相关的理论研究及工程应用提供一些参考。【关键词】NTRU；加密；解密1引言1.1NTRU的研究背景和意义NTRU(NumberTheoryResearchUnit)算法是1996年由美国布朗大学三位数学教授发明的公开秘密体制。这是一个基于多项式环（其中N是一个安全参数）的密码体制。它的安全性依赖于格中最短向量问题（SVP

2、）。相对于离散对数或大数分解等公开秘密体制来说，它有许多优势。在安全性方面，NTRU算法具有抵抗量子计算攻击的能力，而RSA和ECC算法是无法抵抗量子计算的。当前，对于用什么公钥密码来替代正在大量使用的RSA和ECC，主要有以下互相竞争的技术解决方案：NTRU公钥密码体制、McEliece公钥密码体制、MQ公钥密码体制。McEliece公钥密码体制的安全性基于纠错码问题，安全性强，但计算效率低。MQ公钥密码体制，即多变元二次多项式公钥密码体制（MultivariateQuadraticPolynomialsinPublicKeyCryptosystem），基于有限

3、域上的多变元二次多项式方程组的难解性，在安全性方面的缺点比较明显。相比之下，NTRU公钥加密体制算法简洁、计算速度快、占用存贮空间小。1.2国内外研究现状随着信息技术的迅猛发展和一些高技术武器设备、通信指挥系统等的需要，未来军事部门将大量地使用公钥密码技术。由于RSA和ECC不能抗量子计算攻击，而NTRU能抗量子计算攻击，且速度快和安全性高，特别别适合用于诸如智能卡，保密蜂窝电话系统，保密传真、无线保密数据网，以及认证系统等业务，这也扩大了公钥密钥体制的应用范围。有理由相信NTRU算法完全有可能在公钥密钥体制中占有主导地位。自从该密码体制被提出来后，就引起国外一流

4、的密码学家的关注，这包括DonCoppersmithJohanHastad,AndresOdlyzko,andAdiShamir等。到目前为止，有很多讨论NTRU算法安全性。但还没有哪一种分析方法能破译该密码体制。从现阶段研究来看，NTRU所基于的困难问题是安全的。接下来的研究主要集中在体制的参数设置和适当的使用填充方案。在2000年，Jaulmes和Joux论证了仔细的选择填充方案可以防止选择密文攻击，Howgrave-Graham等的研究结果显示了仔细的选择参数集可以使得解密失败概率降为几乎为0，一旦正确的参数的选择和适当填充方案的使用，任何对NTRU的攻击都

5、可以转发为对困难格问题的求解。为了充分利用在学术界和商界的专家的经验和知识，提供一个完善的、有效的、能共同操作的，正确使用NTRU公钥密码系统的方法，在2002年10月出版了一个标准EESS1v1：NTRU加密和签名的实施，2003年5月对第一版进行完善和修改出台二版:EESS1v2。1.3本文安排本文将在第2节中介绍NTRU的数学背景—23格的知识，然后就是LLL算法、BKZ算法和NTRU算法的数学基础；在第3节中，介绍NTRU公钥加密体制，第4节介绍一些对NTRU算法的攻击方法，进而对算法的安全性进行分析；最后在第5节进行了小结。2数学背景2.1格问题（lat

6、ticeproblem）2.1.1格的定义这里的格是指点格。它是的一个离散子群。特别地，对于的任意加法子群都构成一个格，这样的格称为整格（integerlattice）。格的具体定义如下：定义1设为中一组线性无关向量，取集合为的整线性组合，即这样的集合称为格，其中称为格的一组基或简称格基。的每一组基所含向量的个数相同，基中所含向量个数称之为格的维数或秩，记为，它与所张成的线性子空间的维数相同。当时，格中有无数组基。任意两组基之间都可以通过一个幺模矩阵（行列式为的整数矩阵）进行相互转化。因此格中所有的基都有相同的Gram行列式，其中表示两个向量的内积。格的体积定义为

7、格基的Gram行列式的平方根。当，也就是为满维格时，它的体积等于以任何一组基为行向量的矩阵的行列式的绝对值。中向量的欧氏范数和中心化欧氏范数定义为：若，则的欧氏范数为，而的中心化欧氏范数定义为，其中本节以下部分如无特别说明均指中心化欧氏范数。23由于格是离散的，所以格中必有最短非零向量，这个向量的欧式范数称为格的第一最小，记为或。更一般的，对于所有的，Minkowski的次最小定义为其中最小值取自中个线性无关向量构成的向量组的集合。，，…，称为的逐次最小。总存在一组线性无关向量达到所有的逐次最小，即对所有的，。但是当时，这样的一组向量不一定是一组格基；当时，甚至可

8、能不存在这