ntru的研究和实现

《ntru的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1绪论本章简要介绍了公钥密码的历史和发展，其后介绍NTRU的历史，以及目前美国标准化组织IEEE对针对网格难题的算法的标准化的进展。最后就是NTRU目前实际的市场应用和应用前景。1.1引言人类有了战争之后，密码随着战争也开始被智慧的应用于战争中，所以密码技术源远流长。作为一门学科真正蓬勃发展成长则是近几十年的事，随着今天在计算机被广泛应用的信息时代，信息给今天的社会带来的时间上的便利和经济上的财富。然而大量信息用数据形式存放在计算机系统里，信息的传输则是大众的公用渠道。这些计算机系统和公用渠道是不设防的，容易受到攻击和

2、破坏，一旦受到攻击和破坏，不被发现和制止的话，其后果可能是极其严重的。如何保护信息的安全涉及到很多部门，是军事和政府部门感兴趣的问题，也是各企业事业单位甚至个人开始关注的问题。今天的密码学的应用已经渗透到了社会的各个领域，如对计算机用户的认证、数据加密、网络安全、安全电子投票、安全电子商务和电子政务、电子支付等。在1949年，Shannon的一篇文章“保密通信的信息理论”开辟了密码学发展的道路。Shannon首用概率论的观点对信息源、密码源，接收和截获的密文进行定量分析和数学描述，并提出了通用的通信系统模型。其后，密码

3、学开始进入研究领域。在近代密码学上值得一提的大事有两件：一件是1977年美国国家标准式公布实施了美国的数据加密标准(DES)，并批准可用于非机密单商业上的保密通信。。二是DiffieHellman联合写的一篇文章“密码学的新方向”，提出了适应网的保密通信的公钥密码思想，提供了新的密码研究的方向。其后，各种公钥密码体制被提出，特别是RSA公钥密码的更是密码学史上是一个里程–1–碑。公钥密码的最初思想来于Diffie和Hellman两人合写的一篇文章“密码学的新方向”，目的在于解决对称密码体制中最难解决的两个问题：分配和数

4、字签名，以适应网络通信的发展。当时，他们并没有构造出一个完整的公钥体制，但是他们使用有限域上的离散对数困难问题构造了非对称的密钥交换协议。此后，各种公钥密码体制应运而生，例如基于大整数分解问题的RSA公钥体制，背包公钥体制。目前公钥密码体制已经有很大发展，在公钥密码体制的种类上有所增加，对运算速率和安全性的要求也与日俱增。目前在实际应用中最为广泛使用的公钥密码体制主要集中在两个方面，一类是基于大数分解困难性的公钥密码体制，其代表为RSA公钥密码体制，另一类是基于求解离散对数困难性的公钥密钥密码体制，其代表为EIGaju

5、al、DSA等。RSA公钥密码体制，是迄今为止理论上最为成功的非密钥加密体制。这种体制的安全性基于数论中的欧拉定理和计算复杂性理论中的下述论断:求两个大素数的乘积是容易的，但要分解两个大素数积，求出它们的素因子则是非常困难的。但是，随着整数因子分解方法的完善、计算机速度的提高以及计算机网络的发展，作为RSA加解密安全保大整数要求越来越大，目前一般认为RSA需要1024位以上的密钥长度才有保障。但是，密钥长度的增加导致了其加解密的速度大大降低，硬件实现得越来越困难，这对使用RSA的应用带来了很重的负担。从而使得其应用越来

6、越受到制约。还有一种比较安全的公钥密码是基于有限域上离散对数的难解性，比较典型的如美国政府数字签名算法DSA，DSA的安全性RSA相当。其后，基于椭圆曲线点群上的离散对数问题，又提出了椭圆曲线密码体制(ECC)。美国标准化组织IEEE已经制定关于椭圆曲线的标准。国内外一些知名密码学专家经过不泄的努力，相继提出了运算速度存储量、计算量和传输量小、安全性较高的新的公钥密码体制。如：Arj1en，EricR.Verheul等人在2000年美密会上提出的一种新的基于有的乘法群的子群中元素迹的紧致表示的XTR公钥密码体制，该体制

7、与RSA相比在保持安全性不变的情况下，计算量和信息的传输量减少为原来的13。又如JeffreyHoffstein等在1996年美密会上提出了于大维数格中寻找最短向量困难问题的NTRU(NumberTheoryResearehUnit)公钥密码体制，很好地解决了己知公钥密码体制的最大瓶颈速–2–度问题，也就是本文主要要介绍的密码算法。1.1NTRU的历史NTRU(NumberTheoryResearchUnit)公钥密码体制是由布朗大学3位数学家JeffreyHoffstein，J.Pipher和J.H.Silverma

8、n于1996年提出后，经过几年的迅速发展与完善，该算法在密码学领域中受到了高度的重视，并在实际应用中取得了良好的效果。NTRU公钥算法的安全性不是基于传统的困难问题，而是基于格基归约的困难性，从现有技术来看，在量子计算机中本算法仍是安全的。因此从理论上来说为公钥密码体制开辟了一个新的领域。在20世纪90年代中期，三个美国数学家Je