一种基于维数缩减的单变元Coppersmith算法

RSA是最为经典的公钥密码体制之一,在实际使用中,RSA系统有明文被截获的可能.针对部分RSA明文信息泄露的情况,Coppersmith算法被广泛应用于RSA分析中,其主要思想是利用LLL算法求解一个单变元模方程,如果成功求解方程,那么全部明文将会被恢复.本文主要从三个方面对基于小根问题的单变元Coppersmith算法进行了改进.首先根据Nguyen等人的工作,我们可以获得随机格的LLL约减基首向量模长的较为精确的估计.本文利用上述估计获得了一个平均意义上的可能成功求解方程所需的较低维数,并以此维数为起点,逐次增加e维进行约化,直至成功求解方程.其次,考虑到Coppersmith格严格意义上不是随机格,如果将Nguyen等人工作直接应用到Coppersmith格上,结果可能会有误差.因此,本文通过引入概率统计的方法获得了LLL算法在Coppersmith格上约化效果的新估计,优化了起始维数.最后,本文采取了利用已知的未知明文比特位数对原来的未知量进行变量代换的技巧,降低了算法的求解复杂度.实验表明,本文提出的I-Coppersmith算法能较大幅度地提高小根问题的求解效率,算法的运行时间减少约50%.

一种基于分块采样方法的格基约减算法

基于格理论构造的密码方案普遍被认为可以抵抗量子计算攻击,最近几年发展更是迅猛.格密码的安全性依赖于格中困难问题,如最短向量问题等,而要解这些问题需要高效的格基约减算法.国内外学者针对格中困难问题已提出了多种基于枚举法的格基约化算法,如LLL算法、BKZ算法和随机采样算法(RS)等.本文针对最短向量问题的求解,主要对RS算法进行了分析,并指出了其不足之处在于过大的随机性导致格性质倒退及需要生成大量向量导致复杂度过高.本文基于以上分析,进一步结合了分块的思想和插入指数等方法,提出了改进型随机采样约减算法,简称I-RS算法.该算法通过在局部格中的随机化采样和调整基向量的排列顺序改进格基的内部性质,进而提升约减效果.初步的理论分析表明, I-RS算法在O(n^3(k/6)^(k/4))的时间内明显改进了输出格基的长度性质,其中2k是分块的大小.实验表明,新算法比RS算法和BKZ算法在约减效果和稳定性等方面有所提升,输出向量长度较BKZ算法缩短20%,近似因子在BKZ算法的0.95倍以下.

求解子集和问题的采样格归约算法

子集和问题是计算机科学中的重要问题,也是构建多种公钥密码体制的基础.提出了采样归约算法,使用随机采样方法降低问题维度,将原问题分解并归约为多个更小规模的格上最短向量,降低了构造格的半径,从而提高求解的效率,得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地,在目标解重量较低的情况下,可以进行分段采样,对问题增加限定条件,提高解题效率.实验结果表明,对于高维度的子集和问题,与CJLOSS等已有的格归约子集和问题方法相比,该算法可以更高效地求解出问题的精确解,而且可以提高近似解的逼近程度,输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍.

一种适用于高维格基约化的综合算法

格基约化算法是求解格上最短向量问题(SVP)的一类算法,在格理论中有重要地位,尤其在格理论构造的公钥密码中发挥重要作用.目前公认效率最高的主流算法是Blockwise-Korkine-Zolotarev(BKZ)及其改进形式BKZ 2.0,主要思想是分块约化,调用多项式次的局部格上SVP算法.但是BKZ类算法仍然存在约化程度不够充分、在高维度格中约化效率不高的问题,也存在多种改进的算法.本文在已有算法的基础上,对BKZ结构进行优化,并应用筛法的最新研究成果,设计了一种新的综合算法——Blockwise-Sieving-Reduction(BSR).在预处理阶段,将格矩阵划分后分别进行BKZ预处理,该过程可直接进行并行化.在格基约化阶段,该算法结合BKZ算法与筛法的优点,使用分块逐次增大的多轮BKZ算法进行预处理,并在BKZ结构中使用改进的筛法替代原有的枚举子过程,通过插入向量改进局部格的性质,提高了BKZ算法的效率,使之能在更大的分块下求解SVP.针对更高维度的格矩阵,设计了递归调用的算法变种,称为i-BSR算法,该算法使用了渐进约化等实现技术,可以进行更大维度格的约化.从理论角度进行分析,论证了该算法可以进行格基约化并求格上短向量.实验结果表明,该算法在较大分块下,能够以可接受的时间代价完成SVP求解,且得到的向量优于已有算法的实验结果,新算法得到的首向量长度可以缩短至BKZ 2.0的90%.

对两个特定安全模型下密钥交换协议的分析

认证密钥交换协议的设计中,安全性分析是一个重要的环节。目前已有多种安全模型被提出以证明协议的安全性。然而在繁琐的规约过程中易出现人为失误,一些已被证明安全的协议实际上存在着明显的安全缺陷。对两个特定安全模型下可证明安全的密钥交换协议进行了安全性分析。结果表明,两个协议都存在安全隐患,其中CL-AKA协议不具备抗未知密钥共享安全性;GAAKE协议不具备前向安全性。