NTRU算法加密及签名的实现

毕业设计（论文）中文题目：NTRU算法加密及签名的实现英文题目：NTRUencryptionandsignaturealgorithmstoachieve北京交通大学毕业设计（论文）任务书0题目：NTRU加密及签名的实现适合专业：通信工程、电子通信指导教师（签名）：提交日期：年月日毕业设计（论文）基本内容和要求：NTRU是一种公钥密码体制，相对于基于离散对数的Elgamal或基于大数分解的RSA等公钥密码体制而言，它具有以下优点：（1）NTRU基于格上的困难问题，可以抵抗量子算机攻击；而Elgamal和RSA在量子算机中的破解是多项式复杂度的；（2）对长为n的密钥，NTRU加解密算的复杂度都是O（n^2），而Elgamal和RSA是O（n^3）。因此，NTRU在1996年被提出，就备受关注。在标准化方面，NTRU已正式成为IEEEP1363标准，并被CEES、IEEE802.15.3等机构所接受。NTRU算法只需要进行多项式环上的和积运算，很好的解决了公钥密码体制的最大瓶颈--速度问题，这使它有着非常广泛的应用前景，从而很有可能取代RSA等算法成为公钥密钥体制中的一种优秀运算，就目前来说NTRU的安全性至少和RSA算法ECC算法等是一样安全的。NTRU是一种比较新的公开密钥体制，NTRU产生的密钥算法比较容易，加密和解密的速度比RSA等著名算法快得多，NTRU将成为当前公钥体制研究的一大热点。北京交通大学毕业设计（论文）任务书1毕业设计（论文）重点研究的问题：1.掌握NTRU算法的基本原理，对NTRU算法的运行现状进行分析；2.掌握数字签名的基本内容；3.用c/c++实现NTRU加密算法NTRUEncrypt和签名算法NTRUSign。毕业设计（论文）应完成的工作：用c/c++实现NTRU加密算法NTRUEncrypt和签名算法NTRUSign。北京交通大学毕业设计（论文）任务书2参考资料推荐：[1]张利华，章丽萍，张有光.NTRUsign无线认证和密钥协商协议[D].北京：算机工程与应用，2009:45-52.[2]步山岳，徐辛娅，姚清海.NTRU公开密钥体制安全性分析[D].[3]胡玉璞，一个新型的NTRU类数字签名方案.[N]算机学报其他要说明的问题：北京交通大学毕业设计（论文）开题报告0题目：NTRU加密及签名的实现文献综述：NTRU算法介绍：NTRU公钥加密体制是由J．Hoffstein，J．Pipher，和J．H．Silverman三位美国数学家提出的，算法是基于多项式环[]/(1)NRZXX的密钥体制，其中N是一个安全参数。算法的原理是基于数论寻找一个很短向量的数学难题。在目前的技术水平来说，NTRU和目前有影响的RSA算法、椭圆曲线加密体制Ecc等算法具有一样安全性。在安全性的相同条件下，NTRU算法比其它公开密钥体制算法的运算速度快，这是因为NTRU算法时非常巧妙设计，整个算法过程只有一个小整数的加，乘、模运算，这就提高算法执行的速度。NTRU算法的优势在于可以减少对带宽、处理器、存储器的性能要求，同时也扩大NTRU公开密钥体制的在实际中的应用范围。由此可见，对NTRU的研究尤其是对应用范围的研究将有十分重要的意义的。基本研究方法：NTRU密码体制依赖于三个参数(,,)Npq和1N次整系数多项式的4格多项式集合,,,fgrmLLLL，其中：,pq不必是素数，但是有,1pq，一般的假设qp；本文记：1212(,){:110}LddFRFdd的个系数为，个系数为，余下系数为北京交通大学毕业设计（论文）开题报告11(,)fffLLdd(,1)gggLLdd(,1)rrrLLdd{:1/2(1)1/2(1)}mLmRmpp的系数位于区间1.密钥的生成由NTRU已知参数N，需要先随机的选择两个多项式(),()fxgx，满足(),()fxgxR，,pqFF是f模p，模q的乘逆，满足*1modpfFp(1)*1modqfFq(2)由此可以得到密钥：*modphFgp（）(3)NTRU算法取私人密钥是多项式环(,)qfF，公开密钥是多项式环h。2.加密给定明文多项式m，由参数rd先随机的选择多项式r，使用公开密钥h对明文m进行加密，得到密文e(**)modeqrhmp(4)3.解密用私人密钥(,)qfF进行解密e(*)modafep(5)北京交通大学毕业设计（论文）开题报告2modbaq(6)这里a的系数需要满足在{/2,/2}pp之间(*)modqcFbq(7)记多项式c为明文m。NTRU算法的运行现状：在国外对NTRU算法的研究、开发和应用发展速度是异常快的，NTRU算法被认为是公开密钥体制中运行最快的算法，同时也是比较容易实现的算法。在国外有很多研究机构针对NTRU算法安全性展开了研究，但到目前为止还没有任何数据显示NTRU算法是不安全的，所以本文是有理由相信NTRU算法能够在公开密钥体制中占有主导地位。随着信息技术的迅猛发展和一些高技术武器设备、通信指挥系统等的需要，未来军事部门将大量地使用公钥密码技术。由于RSA和ECC都不能够抵抗量子算攻击，但是NTRU能够抵抗量子算攻击，而且速度快，安全性也高，非常适合用于例如智能卡，保密蜂窝电话系统，保密传真、无线保密数据网，以及其他认证系统的业务，从而扩大了公钥密钥体制的应用范围。再次证明了NTRU算法完全能够在公钥密钥体制中占有主导地位。自从该密码体制被提出来后，就引起国外一流的密码学家的关注，这包括DonCoppersmithJohanHastad,AndresOdlyzko,andAdiShamir等。到目前为止，有很多讨论NTRU算法安全性。但还没有哪一种分析方法能破译该密码体制。从目前研究结果来看，NTRU算法基于的困难问题是安全的。后面的研究主要是集中于对体制的参数设置和选择适当的填充方案。Jaulmes和Joux在2000年论证了仔细的选择填充方案可北京交通大学毕业设计（论文）开题报告3以有效防止对密文攻击，Howgrave-Graham等的研究成果显示选择正确的参数设置可以使解密失败概率几乎降为0，如果正确的参数选择和使用适当的填充方案，可以把任何对NTRU的攻击都可以转发为对格中困难问题的求解。研究内容：1、掌握NTRU算法的基本原理，对NTRU算法的运行现状进行分析；2、掌握数字签名的基本内容；3、用c/c++实现NTRU加密算法NTRUEncrypt和签名算法NTRUSign。必要性和价值：NTRU算法只需要进行多项式环上的和积运算，很好的解决了公钥密码体制的最大瓶颈--速度问题，这使它有着非常广泛的应用前景，从而很有可能取代RSA等算法成为公钥密钥体制中的一种优秀运算，就目前来说NTRU的安全性至少和RSA算法ECC算法等是一样安全的。NTRU是一种比较新的公开密钥体制，NTRU产生的密钥算法比较容易，加密和解密的速度比RSA等著名算法快得多，NTRU将成为当前公钥体制研究的一大热点。北京交通大学毕业设计（论文）开题报告4主要参考文献：[1]张利华，章丽萍，张有光.NTRUSign无线认证和密钥协商协议[D].北京：算机工程与应用,2009：45-52.[2]步山岳，徐新亚，姚清海.NTRU公开密钥体制安全性分析[D].江苏：淮阴工学院算机研究所,2002：180-196.[3]李道丰，王智文.基于矩阵变换的NTRUSign密钥生成算法[D].广西：广西工学院算机工程系,2007：5389-5402.[4]胡玉璞.一个新型的NTRU类数字签名方案.[N]算机学报,2008,31(9):1661-1666[5]髂祥华，何大可和余位驰等．NTRU中多项式的逆问题。[D]北京：算机技术与自动化，2005：72-103[6]卓泽朋.一种基于NTRUSign的代理签名方案[D].安徽：淮北师范学院算机科学与技术,2007：43-64.[7]步山岳.NTRU~开密钥体制算法分析与实现[D].江苏：淮阴工学院算机研究所,2001：111-133.[8]李筱熠.一种基于NTRU格的数字签名[D].上海：东华大学信息科学与技术学院,2009：57-74.[9]杨真真.基于NTRU签名的理论研究[D].四川：四川省西华大学信息科学与技术学院,2007：1-65.[10]刘广聪，韦东丽，邬欢欢.基于MYK．NTRUSign签名的无线网认证协议研究[D].广东：广东工业大学算机学院,2011：102-111.北京交通大学毕业设计（论文）开题报告5研究方案：理论基础：C语言算法，C++算法，多项式环的应用，向量的应用，数论的基础，NTRU算法，数字签名的应用，研究方法和步骤：1、通过调查法对NTRU算法进行深入了解。2、通过实验法对NTRU算法的数论基础进一步分析，应用C语言C++来进行编写程序。3、通过定量分析法选择合适的参数和改进算法。4、最后进行经验总结，书写毕业论文。预期成果：用c/c++实现NTRU加密算法NTRUEncrypt和签名算法NTRUSign。通过定量分析法选择合适的参数和改进算法。毕业设计（论文）进度安排：序号毕业设计（论文）各阶段内容时间安排备注1了解题目并搜索NTRU算法的相关资料2013.1-2013.32学习c语言和c++的相关知识2013.1-2013.33学习并了解NTRU算法2013.1-2013.34应用C语言编写NTRU算和数字签名2013.3-2013.4北京交通大学毕业设计（论文）开题报告65选择合适的参数和改进算法2013.4-2013.56向导师汇报工作并改进，编写毕业设计论文2013.5-2013.6指导教师意见：指导教师签名：审核日期：年月日北京交通大学毕业设计（论文）摘要NTRU（NumberTheoryResearchUnit)公钥密码体制是由三位美国数学家J.Hoffstein，J.Pipher和J.H.Silverman于1996年提出来的，安全性是基于最近向量问题（ClosestVectorProblem--CVP）。NTRU算法只需要进行多项式环上的和积运算，很好的解决了公钥密码体制的最大瓶颈--速度问题，这使它有着非常广泛的应用前景，从而很有可能取代RSA等算法成为公钥密钥体制中的一种优秀运算，就目前来说NTRU的安全性至少和RSA算法ECC算法等是一样安全的。本文主要研究了NTRU公钥密码体制，然后结合NTRU算法的特性，详细介绍了NTRU算法的实现过程；对NTRU的主要算法---多项式环乘法进行了优化，由于多项式环乘法是NTRU的主要耗时运算，其设计的好坏将直接影响其速度，为此，采用“平方递归法”使乘法运算大大减少，从而使整个系统运行速度更快，性能更优。分析一种基于NTRU的数字签名，详细介绍了其密钥生成，签名和验证的过程，讨论了NTRUsign签名算法的密钥生成过程，当NTRU参数选择较大时，大矩阵运算的运算量会大大增加，所花费的时间也会成倍增长，因此，NTRUsign算法在密钥生成上效率很低。关键词：NTRU公钥密码体制；多项式环乘法；数字签名北京交通大学毕业设计（论文）AbstractTheNTRUEncryptPublicKeycryptosystemwasdevelopoveraperiodofseveralyearsin1996byateamofmathematicians(J.Hoffstein，J.Pipher和J.H.Silverman).ThesecurityofNTRUisbasedonClosetVectorProblem(CVP).NTRUalgorithmhasthefastestspeedinpublickeycryptography.NTRUhassolvedthebottleneckofPKCSspeed，whichgreatlypromptsitswideapplicationandwillbecomeoneofthemostexcellentPKCS，andithasatleastthesa