毕业论文：格基规约算法研究.doc

1、I目录摘 要 .IAbstract .II第一章 引 言 .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第四章 格 基 规 约 算 法 .104.1 格基规约算法概述 .104.2 LLL 格基规约 .104.2.1 基本定义 .104.2.2 基本性质 .114.3 经 典 的

2、 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 算法 .

3、245.4.3 BKZ-FP 算法 .255.4.4 BKZ-QP 算法 .255.5 高复杂度算法实现的原理 .255.6 实例测试 .275.6.1 低复杂度实例 .27II5.6.2 高复杂度实例 .29第六章 结论 .32参 考 文 献 .33致 谢 .34附 录 .35III格基规约算法研究摘 要格是数学上非常典型的一种线性代数结构，而且格上一些问题的困难性已经得到了许多学者的证明。格的理论研究中的重点主要是集中在了格基规约上，这同时也是密码学中密码系统的设计和分析中利用到格的一个重要工具。目前，在格的理论研究中，许多格的问题均可以通过格基规约来进行求解（因为是 NP难问题，一般都只

4、能近似求解）。在实践中，例如是在密码体制的设计和密码系统的破解中，对一些密码系统和密码方案的分析其实在本质上均可以等价成格基规约问题。因此研究格基规约问题不仅具有很高的理论价值，而且具有重要的实用价值。本文首先对格问题的背景和基础知识进行了学习和分析，然后研究了格中的困难问题，最后重点研究了常见的格基规约方法。研究了经典的Gram- Schnorr 的 经典格基规约算法，用 C+语言将该经典算法实现，并用L实例进行试验，验证该算法的质量。其次还用了遗传算法来实现格基规约，并用相同实例，将得到的结果进行比较。论文的重点放在格的困难问题上，由于目前计算机内部数据表示的一些局限性，使得大数的运算和大

5、数格的运算称为困难问题，本文使用了 NTL 大数库进行辅助，在此基础上，分别实现了经典算法，LLL-FP 浮点算法， BKZ-FP 分块浮点算法，以及 BKZ-QP 分块四倍L精度浮点算法，并使用相关实例进行实验，比较各算法的优越性。关键词：格；格基规约；LLL；NTL 大数库IVAbstractThe lattice is mathematically a very typical of a linear algebraic structure, and the difficulty of some problems on the lattice has been proofed by ma

6、ny scholars. The studying of lattice of theoretical mainly focused in the the Lattice Basis 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

7、lattice can be solved by linear reduction (usually only can be approximate with the solution). 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 Researc

8、hing of Lattice Basis Reduction do not only has a high theoretical value, but also has important 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

9、some basic definitions of the lattice and basis with quasi-orthogonal, as well as Lattice 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. Sec

10、ondly, we also use a genetic algorithm to achieve Lattice Basis Reduction, and with the same 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 numb

11、ers computing and lattice computing of large numbers the difficult problem.In this article, 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

12、 BKZ-QP block quadruple precision floating-point arithmetic with some examples to experiment, we can see the comparison of the queality of all the algorithms.Keywords: Lattice, LLL Lattice Basis Reduction, NTL Library5第一章 引 言课题的背景和意义讨论格问题的最早出现要回溯到19世纪，当时的数论和密码被研究了很长的一段时间，那时候格在很多领域的应用主要是负面的，例如格被用来破解各

13、种密码系统。然而Ajtai发表了他得里程碑式的论文，其利用格的难题来构造新的密码系统的观点让许多的学者产生了兴趣。这个算法和格的相关的理论从此时才真正的被开始应用到密码学的领域。在1990年，基于背包问题的密码系统被LLL 的算法攻破。这一成果展开了格理论在密码分析学这一领域中的实际应用，并且同时更进一步的证明了 “单向函数假设”这一理论的不可靠性。1996年，在Coppersmith的论文中LLL 算法被提出来用于求解整系数同余方程(仅当方程一定有足够小的解的时候)的算法。之后，Coppersmith 的这一方法被学者们广泛的应用于对RSA 密码体制的部分密钥泄露攻击以及低指数攻击等领域的应

14、用中。在近年来格在许多领域都已经产生积极的作用。在对格问题的研究基础上，人们设计出了基于格困难问题(NP问题)的密码系统Shamir利用格基规约理论，用Lenstra的整数规划算法成功破解了 Merkle-Hellman得基于背包问题的公钥密码方案，其理论也被成功的用于加密指数为3的RSA密码方案的研究中，以及利用其对NTRU进行分析和攻击。密码学界已经认定格问题是在计算困难问题时的新的源泉。除此之外，格的困难问题也可以用来设计公钥密码，可以用来抗量子攻击，如NTRU密码。这也是密码学发展的一个新方向。6第二章 格问题的研究2.1 格问题的发展在 1982 年的时候，有三位伟大的数学家伦斯特拉

15、（A.K.Lenstra），伦斯特拉（H.W.Lestra），洛伐兹（ Jr.L.Lovasz）发明了 算法。之后， 算法被LL许多学者视为是对解决 NP 问题的一大突破，由于其简明性和广泛性的实际应用，很快被认为是 20 世纪后期中最重要的理论算法成果之一线性代数这一学科里面的一些基本理论表明：任何有限维欧氏空间都存在一个标准正交基，也就是说每一个基都是由两两正交的单位矢量组成。那么，是否每一个格都是有标准正交基的呢？然而，即使是对于 2 维格，也存在某种可能使得它不存在正交基。此时，格基规约的目标只能退而求其次。学者研究发现，对于任何一个格来说，总存在这样一个基，它离正交不远。（当然，要精

16、确定义什么是离正交不远也是需要某种技巧的，截止到目前为止，我们只能说存在这样一个基，它是由足够短的格矢量组成，这便意味着至少在几何的意义上来说这样的一些矢量相互之间是离正交不远的）。世界上的第一个SVP算法就是Lagrange的规约算法，他使得该算法能够在二次方的时间内解决精确的二维SVP 。而对于任意维格，都是有两类SVP算法：精确算法和近似算法。2.2 格问题的算法发展2.2.1 精确算法这些算法可证明找到一个最短矢量，但他们是开销很大，运行时间至少是维数的指数次本质上，这些算法执行一个穷举搜索精确算法可分成两类：（1）多项式空间精确算法这些算法基于列举法，但是由于不等式限制了搜索的范围，

17、当然也能找出所有长度小于M的非零的格的矢量。其中最好的具有确定行的算法是Kannan算法，该算法具有超过指数的最坏复杂度，其多项式运算的时间为 。Schnorr引用了Pruning的技巧，将列举法与分块进行规约两/(2)neo者相结合，事实上是在分块的KZ规约算法中加入一个子过程，这个子过程是用列举算法实现的，由于该小技巧的使用，整个算法的实现速度上有了很大的提升。（2）指数控件精确算法。在（1）的基础上，这些算法会有更短的渐近的运算时间，可是还是有 的空间复杂度。在这类算法中最有代表性的是AKS 算法()2n7(Ajtai,Kumar,Sivakumar)，这些算法即使在最坏的情况下起运算时

18、间也不会超过。后来 Micciancio等人又提出了一个更加具有确定行的算法，该算法可以在()2on的时间内解决CVP与SVP等问题。并且有多个AKS的变形，其时间复杂度达到 。()on2.2.2 近似算法这类算法比精确算法实现的时间要短，最后输出的结果保证是短的格矢量，但不一定保证是最短的。该算法常输出整个的规约基，所以我们称之为格基规约算法。该算法中最为著名的就是Lenstra,Lenstra, Lovasz提出的 算法，此L算法可以在多项式的时间复杂度内解决近似因子是 的SVP问题，这(2/3)nO个算法本质上就是Hermite 不等式的算法的变形。LLL算法出现后，研究的方向就集中在两

19、个方面：（1）更快的 算法。这个方向致力于获得在质量类可以接受类似于或者是更L加差一点的 规约基，当然，它只需要更少的运行时间，这里面的方法是利用的分治策略，或者是通过浮点算法也可以。因为当我们使用浮点数算术时，它可以加快格基规约的速度，然而同时也会带来更多大的浮点误差，这些误差很多时候就会让我们得到错误的结果，甚至使程序无法终止。因此，研究格基规约上的浮点运算的一些特性是非常有必要的。世界上首次得到正确的证明的浮点 是由Schnorr 提出来的，最近，一个比 更加有效的浮点 变形版L LL是由Nguyen和 Stehle这两位学者研究出来的。但就目前来说，最为流行的版本还是基于启发式的浮点

20、算法。尽管利用常规的方法就可以证明它的安全性，L但是有的时候基于启发式的算法会更加有效。1994年,一个非常重要的基于启发式的算法由Schnorr 和Euchner提出来，一直延续到今天，这个基于启发式的算法依旧是很多浮点 快速算法必不可少的基础。（2）更强的LLL算法。这种算法是以更长得运行时间为代价来获得比 算法L要更好更精确的近似因子。分块的规约方法其本质是在 算法和HKZ算法两L者取得中间方法，令分块的长度为 ,参数 =1时，分块规约与HKZ 规约是等价d的；令分块的长度 为2时，分块 KZ规约就是变成了 规约。目前最好的分d块规约算法可以达到 。不过这些算法在理论上没有学者证明其最(

21、log)/lOnn短矢量界，并且它的时间复杂度也有可能回升亚指数的，不过这个算法在实际应用中能运行得很好。之后Gama和Nguyen实现了三个算法： 算法，深插入的 算法，分LL块的KZ 规约算法，他们都是用NTL库实现的。而且实践证明，深插入的 算8法和分块KZ 规约算法比 算法的性能要好，且随着分块值k的增大，最终得L到的规约基的质量就越好，当然，运行时间也增加了。综上可以看出，更快和更高质量这两者之间是互补的，所有的精确算法首先都需要用一个近似的算法（比如 算法）来进行预处理，其中所有的分块算法都需要调用大量的低维格的精确算法来作为子过程进行处理。在实际中，大多采用基于启发式的算法，他们

22、的运行时间提升了许多，不过理论上很难被证明。事实上，当维数 ，能够实用的只有近似算法。150n最后，以前人们大都认为格基规约算法的实际执行的效率可以比学者们可证明的理论界会更好。在上世纪80年代末，格问题计算的复杂性程度引起了许多人们的关注，主要是因为Ajtai发现了某种格的近似问题在最坏情况复杂度和平均情况下的复杂度之间的相互联系，这引起了理论密码学家与计算机复杂度的领域专家的兴趣。2.3格问题的基础知识2.3.1 低复杂度的格问题格是离散的 加子群。每个格都是由一些线性无关的向量产生的集合，称nR之为基。任意格都有无数个基，格基规约是一种在格的无数基中选择这样一个基矢量：其长度尽可能小，并

23、且与基中其他矢量尽可能正交。格基规约理论有着悠久的历史，可以回溯到二次多项式的规约理论上。在Lenstra,Lenstra 和 a 个人的努力下，该工作达到了高峰，也就是著名Lovsz的 算法，它是第一个保证能够计算出包含近似短向量的格的基的多项式时L间算法。此后，格基规约的方法有了进一步的发展（例如，Schnorr-Euchner的格基规约算法）并且在基础数学和计算科学的许多领域该工作被认为其价值是无可估量的。特别是格理论的进展使得想组合优化和加密这些领域被彻底改革。例如，格基规约理论技术已被用于攻击截断线性同余发生器，基于哈希散列函数的背包问题以及像 Merkle-Hellman 公钥密码

24、体制的密码系统，RSA,GGH等。2.3.2 高复杂度格问题 然而，尽管在理论上取得了巨大的进步，但是面向大型问题的实例，还是缺少一般化的格基规约的方法。因此，在实践中去进一步的进行改善和提高理论技术是非常重要的。在下面，我们提出了一种新的基于动态近似的启发式算法，它是为了提高改善 Schnorr-Euchner 的格基规约算法，也是在实践中应用最为广泛的一种格基规约算法。特别是这种新的启发式算法在大型问题例子的9分解以及在例如用某些方法无法实现分解的问题上可以用我们提出的新算法解决，这拓展了 Schnoorr-Euchner 算法的适用性。格基规约10第三章 格基规约3.1格基的正交性设 是

25、 n 位欧式线性空间 中线性无关的向量，可以定义如下点集：1,.dbnR2.,1.,diLbZd我们称之为格，并称 为格的一个基，由于 是线性无关的，所1.d 1,.db以任一个格的矢量 X 可以用一组基的线性组合来表示，而且这种表示方式肯定是唯一，即有且仅有一种；但是如果 X 已经在格中，并且能够用以上的线性组合的形式来表出，那么系数 均为正数。1,.d任意格矢量均能被唯一表示为基矢量的线性组合。由于用基表出得格是有意义的，格基本身就能用一个全为实数的系数矩阵来表示，因此我们可以非常方便的使用电脑来表示任何一个格。如果从代数的角度来看，格则是由 d 个生成元组成的阿贝尔群，我们认为它是 的子

26、群。我们研究格问题的中心问题集中在 Shotrest Vector nRProblem（SVP 问题），就是最短向量问题，它的定义如下：对于给定的一个格基 B，要求找到这样的一个非零的格的矢量，使得满足一下条件： ，其0Bx长度要达到最小值 。（其中长度被定义为欧几里得长度）1Bx另一个集中点是 Closest Vector Problem(CVP 问题)，也就是最接近矢量问题。该问题对于给定的目标矢量和格基，要求找出最接近于该矢量的格点，即那组基。两个问题相比之下，CVP 比 SVP 要更加难以解决。因为精确的 SVP问题是属于 NP 问题，即多项式时间困难问题，但它在实际中需要的地方并不多，所以以下的近似 SVP 问题被提出。近似 SVP 问题的定义为：给定秩为 d 的格 L 基 B，近似因子为 ，要求1找出非零矢量 ，使得满足以下条件： 。它可以简单uLmin,0uv记为 apprSVP。截止到目前为止，已经能够证明 apprSVP 问题是 NP 难得当且仅当近似因子 。1/2log()en3.2 格基的规约下面给出一些格基规约的相关概念：对任何矢量集 ， 是由 生成的线性空间，或者称之为包含nSR()spaSS 的 的最小子空间。nR如果设 是格 的一个格基，于是它的 Gram 行列式可以表1,.ndbL