《山东理工大学信息与计算科学专业毕业设计说明书》由会员分享，可在线阅读，更多相关《山东理工大学信息与计算科学专业毕业设计说明书（56页珍藏版）》请在金锄头文库上搜索。
1、摘 要SHANDONG毕业设计说明书格基规约算法研究学 院： 理学院 专 业： 信息与计算科学 学生姓名： 学 号： 指导教师： 2012 年 6 月52摘 要格是数学上非常典型的一种线性代数结构，而且格上一些问题的困难性已经得到了许多学者的证明。格的理论研究中的重点主要是集中在了格基规约上，这同时也是密码学中密码系统的设计和分析中利用到格的一个重要工具。目前，在格的理论研究中，许多格的问题均可以通过格基规约来进行求解（因为是NP难问题，一般都只能近似求解）。在实践中，例如是在密码体制的设计和密码系统的破解中，对一些密码系统和密码方案的分析其实在本质上均可以等价成格基规约问题。因此研究格基规约
2、问题不仅具有很高的理论价值，而且具有重要的实用价值。本文首先对格问题的背景和基础知识进行了学习和分析，然后研究了格中的困难问题，最后重点研究了常见的格基规约方法。研究了经典的Gram- Schnorr的经典格基规约算法，用C+语言将该经典算法实现，并用实例进行试验，验证该算法的质量。其次还用了遗传算法来实现格基规约，并用相同实例，将得到的结果进行比较。论文的重点放在格的困难问题上，由于目前计算机内部数据表示的一些局限性，使得大数的运算和大数格的运算称为困难问题，本文使用了NTL大数库进行辅助，在此基础上，分别实现了经典算法，LLL-FP浮点算法，BKZ-FP分块浮点算法，以及BKZ-QP分块四
3、倍精度浮点算法，并使用相关实例进行实验，比较各算法的优越性。关键词：格；格基规约；LLL；NTL大数库AbstractThe lattice is mathematically a very typical of a linear algebraic structure, and the difficulty of some problems on the lattice has been proofed by many scholars. The studying of lattice of theoretical mainly focused in the the Lattice Basi
4、s Reduction, which is also an important tool at password system designing and analysising in cryptography that can take advantage of of the lattice. In the theoretical study of the lattice problem, many of the lattice can be solved by linear reduction (usually only can be approximate with the soluti
5、on). In practice, for example, in cryptosystem designing and password cracking, the analysising of some of the password and password programs, in fact, are equivalented into Lattice Basis Reduction. The Researching of Lattice Basis Reduction do not only has a high theoretical value, but also has imp
6、ortant practical value. In this peper, firstly, we present the background of lattice and the basic knowledge, the studying and analysising are focused on the difficult preblem of the lattice. And then we study some basic definitions of the lattice and basis with quasi-orthogonal, as well as Lattice
7、Basis Reduction and the basic knowledge and basic theorems.we Study the classic Gram-Schnorr LLL classic algorithm and and validate the quality of the algorithm by using C + + with an examples to be tested. Secondly, we also use a genetic algorithm to achieve Lattice Basis Reduction, and with the sa
8、me instance we can compare the quaelity of the results. This paper focus on the difficult problem of the lattice.For some limitations of the data representation inside the computer so that making the large numbers computing and lattice computing of large numbers the difficult problem.In this article
9、, with the using of the NTL library auxiliary, we validate the quality of the algorithm by using the classical LLL algorithm LLL-FP floating-point arithmetic, the BKZ-FP block floating-point arithmetic, and the BKZ-QP block quadruple precision floating-point arithmetic with some examples to experime
10、nt, we can see the comparison of the queality of all the algorithms.Keywords: Lattice, LLL Lattice Basis Reduction, NTL Library目录摘 要IAbstractII第一章 引 言3课题的背景和意义3第二章 格问题的研究42.1 格问题的发展42.2格问题的算法发展42.2.1 精确算法42.2.2 近似算法52.3格问题的基础知识62.3.1低复杂度的格问题62.3.2高复杂度格问题6第三章格基规约73.1格基的正交性73.2格基的规约73.3格基规约的基本定义和定理8第四
11、章格基规约算法104.1格基规约算法概述104.2 LLL格基规约104.2.1 基本定义104.2.2 基本性质114.3 经典的LLL格基规约算法134.3.1 低复杂度的LLL格基规约算法134.3.2使用实例进行实验174.3.3结果分析与结论184.4 遗传算法实现格基规约的算法194.4.1算法实现的概念194.4.2 遗传算法的实质194.4.3算法的步骤204.4.4 实例的实验20第五章 困难格问题的规约225.1高复杂度的格问题介绍225.2 NTL大数库的介绍225.3大数库的使用235.4几种变种规约算法的介绍245.4.1经典LLL算法：245.4.2 LLL-FP算
12、法245.4.3 BKZ-FP算法255.4.4 BKZ-QP算法255.5高复杂度算法实现的原理255.6实例测试275.6.1低复杂度实例275.6.2高复杂度实例29第六章 结论32参考文献33致 谢34附录35第一章 引 言课题的背景和意义讨论格问题的最早出现要回溯到19世纪，当时的数论和密码被研究了很长的一段时间，那时候格在很多领域的应用主要是负面的，例如格被用来破解各种密码系统。然而Ajtai发表了他得里程碑式的论文，其利用格的难题来构造新的密码系统的观点让许多的学者产生了兴趣。这个算法和格的相关的理论从此时才真正的被开始应用到密码学的领域。在1990年，基于背包问题的密码系统被L
13、LL的算法攻破。这一成果展开了格理论在密码分析学这一领域中的实际应用，并且同时更进一步的证明了 “单向函数假设”这一理论的不可靠性。1996年，在Coppersmith的论文中LLL算法被提出来用于求解整系数同余方程(仅当方程一定有足够小的解的时候)的算法。之后，Coppersmith的这一方法被学者们广泛的应用于对RSA密码体制的部分密钥泄露攻击以及低指数攻击等领域的应用中。在近年来格在许多领域都已经产生积极的作用。在对格问题的研究基础上，人们设计出了基于格困难问题(NP问题)的密码系统Shamir利用格基规约理论，用Lenstra的整数规划算法成功破解了Merkle-Hellman得基于背
14、包问题的公钥密码方案，其理论也被成功的用于加密指数为3的RSA密码方案的研究中，以及利用其对NTRU进行分析和攻击。密码学界已经认定格问题是在计算困难问题时的新的源泉。除此之外，格的困难问题也可以用来设计公钥密码，可以用来抗量子攻击，如NTRU密码。这也是密码学发展的一个新方向。第二章 格问题的研究2.1 格问题的发展在1982年的时候，有三位伟大的数学家伦斯特拉（A.K.Lenstra），伦斯特拉（H.W.Lestra），洛伐兹（Jr.L.Lovasz）发明了算法。之后，算法被许多学者视为是对解决NP问题的一大突破，由于其简明性和广泛性的实际应用，很快被认为是20世纪后期中最重要的理论算法成果之一线性代数这一学科里面的一些基本理论表明：任何有限维欧氏空间都存在一个标准正交基，也就是说每一个基都是由两两正交的单位矢量组成。那么，是否每一个格都是有标准正交基的呢？然而，即使是对于2维格，也存在某种可能使得它不存在正交基。此时，格基规约的目标只能退而求其次。学者研究发现，对于任何一个格来说，总存在这样一个基，它离正交不远。（当然，要精确定义什么是离正交不远也是需要某种技巧的，截止到目前为止，我们只能说存在这样一个基，它是由足够短的格矢量组成，这便意味着至少在几何的意义上来说这样的一些矢量相互之间是离正交不远的）。世界上的第一个SVP算法就是Lagrange的规约算法，他使得该算
