格基约化作为数的几何理论的重要内容,具有悠久的研究历史。LLL算法的提出使得格基约化开始成为一种强有力的密码分析工具,尤其是在RSA等公钥密码体制的安全性分析中发挥着重要作用。随着维数或者输入数据规模的增大,格基约化算法的运行时间会急剧增加,对算法进行并行化是提高其实现效率的重要途径。RSA等公钥密码体制在实际使用中经常会出现诸如私钥信息泄漏之类的特殊情况,在这些特殊条件下,对其攻击往往都可以等价成格基约化问题来进行求解。于是,格基约化算法的实现及其在公钥密码分析中的应用成为密码学界关注的热点。一方面,对格基约化算法的实施有助于提高其实现效率,从而帮助其在实际中对公钥密码体制进行有效攻击；另一方面,研究格基约化算法在公钥密码分析中应用能够增强对这些密码体制的理解和认识,进而指导其在实际中进行恰当的使用。本文主要研究格基约化算法及其在公钥密码分析中应用的一些理论和工程实现问题,包括LLL和BKZ等算法的并行实现技术、基于遗传策略的格基约化算法设计与分析、RSA算法私钥指数d离散比特泄漏的格攻击、离散对数公钥密码体制的格攻击等四个方面,取得的主要成果如下：1.给出了基于分块思想的LLL算法并行实现方案并在Sunway集群上进行了有效实现,实验结果表明其效率低下,并指出了瓶颈所在：边界处需要不断交换更新造成算法执行时各个计算节点的负载不均衡；给出了BKZ算法的变形版本及其并行实现方案,大量的实验表明原始BKZ算法并不适合并行实现,于是提出了一种新的并行BKZ算法,新算法能够得到一组BKZ约化基,同时算法具有良好的加速比；通过对Goldstein格和Ajtai格的实验验证,新算法在处理高维格或者分块规模较大时具有较强的实用性,处理100维格时并行加速比能够达到40倍,同时,新算法得到的首向量长度更短。2.考察了输入格基的序对LLL算法运行效率的影响,如果输入格基采用合适的顺序,那么可以有效降低LLL算法的运行时间；借鉴遗传算法的基本思想,提出了基于遗传策略的格基约化算法框架,分别对初始种群、适应度函数、遗传算子、终止条件进行了详细设计和分析；利用基于遗传策略的格基约化算法框架,对SVP挑战进行了详细测试,结果表明新算法都能达到或超过公开的挑战结果。3.对Coppersmith的格构造方法进行了系统的总结和分析,讨论了求解单变元同余方程和多变元同余方程时格的构造策略,给出了统一的构造过程；分别利用不同的格构造方法,给出了两种私钥指数d的离散比特泄漏情形的攻击算法并进行实验验证,结果表明,RSA算法模数N长度为m,公钥参数为e=Nβ,如果私钥d的长度为(1／2-β)m的比特块未知,那么可以将私钥d恢复出来；对两种攻击算法进行了比较和分析,算法1要求所构造格的密度较低,但其所构造的格维数较低,算法2构造的格维数较高,但克服了要求低密度格的局限。4.讨论了大数分解的格攻击方法,并给出了不同规模大数进行分解时理论上所需格的维数以及复杂度分析；借鉴大数分解的格攻击的基本思路,提出了Z*p上离散对数求解的具体实现方案；给出了ElGamal体制格攻击的分析,利用隐藏数问题的求解给出了其一种不安全的使用情况：如果加密者使用相同的随机数,并且明文的部分信息泄漏,那么攻击者可以利用隐藏数问题,恢复出完全的明文信息。