导读:本文包含了格基约化论文开题报告文献综述及选题提纲参考文献,主要关键词:线性递归序列,整数剩余类环,截位序列,序列还原
格基约化论文文献综述
杨建斌,朱宣勇[1](2017)在《基于格基约化算法的环上截位序列还原》一文中研究指出研究由序列a-的最低l比特序列还原整体序列的问题。将该问题转化为使用格基约化算法求解线性同余方程组的问题。实验结果表明,对ZUC密码算法的驱动序列,即对于■/(2~(31)-1)上的16阶本原序列,当已知整体序列的最低8比特序列,长度为110拍,则可以还原整体序列。(本文来源于《信息工程大学学报》期刊2017年04期)
李建伟[2](2015)在《格理论中计算格基和格基约化问题研究》一文中研究指出这篇论文旨在研究格理论中两个非常基础又非常重要的计算问题:计算格基问题和格基约化问题.计算格基问题指的是给定一组格生成元,计算它们生成的格的一组基.格基约化问题则是给定一组格基,计算出具有某种较好性质的格基,或者是向量长度较短,或者是局部向量张成的体积较小等.这两个计算问题关系密切,互为交叉:计算格基是进行格基约化的前提;格基约化过程的局部处理常常涉及计算格基,而且格基约化方法经过适当的修正也能用来计算格基.两者作为基本问题有着重要和广泛的应用.例如,计算格基算法可以用来确定代数数域中的基本单位元,格基约化算法是密码分析的重要工具.因此,研究这两个问题的理论价值和实际意义不言而喻.本文的第一项工作是较为系统地研究了计算格基算法.先前的计算格基算法中,具有线性输出基的算法不具有拟线性时间复杂性,而具有拟线性时间复杂性的算法不具有线性输出基.我们通过引入Euclid交换、正则系统、松弛约化和按块交换等新的技术和想法,首次给出了一个同时具有线性输出基和时间复杂性关于log‖B0‖拟线性的计算格基算法,并且在标准算术下复杂性是O(mn4(log n+log‖B0‖)2),其中B0∈Zm×n表示输入的格生成元.我们进而给出了具有线性输出基和拟线性时间复杂性的本原向量组格基扩充算法.本文的第二项工作是探讨了滑动约化基的性质.作为当前理论上最好的近似求解最短向量问题的格基约化算法,Gama-Nguyen滑动约化算法被视为着名的Mordell不等式的算法实现.通过推广先前的证明方法,我们推导了Gama-Nguyen滑动约化基与逐次极小值之间的比例关系,从而对该类型基的约化程度给出了更全面的刻划.本文的第叁项工作是给出了一个近似求解最小体积问题的格基约化算法.我们证明了一个新的关于Rankin常数的不等式,该不等式用低维Rankin常数γk,r给出高维Rankin常数γn,r的上界.通过推广先前的约化概念,我们给出了输出因子对应上述新Rankin不等式的一个格基约化算法.该算法能确定性地在多项式时间内近似求解最小体积问题.这一项工作可以看成是经典的Mordell不等式和Gama-Nguyen滑动约化算法的延续.(本文来源于《清华大学》期刊2015-06-01)
刘向辉,韩文报,权建校[3](2013)在《基于遗传策略的格基约化算法》一文中研究指出格基约化算法是密码分析的重要工具。该文借鉴遗传算法的基本策略,通过对初始格基的调整变换,提出了一种新的格基约化算法,新算法总能得到给定格中长度更短的向量和质量更高的一组基。利用该算法,针对最短向量问题(SVP)挑战的部分数据进行了测试,新算法的输出结果达到或超过了挑战的公开记录,约化效果良好。(本文来源于《电子与信息学报》期刊2013年08期)
刘向辉[4](2013)在《格基约化算法并行化及应用研究》一文中研究指出格基约化作为数的几何理论的重要内容,具有悠久的研究历史。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体制格攻击的分析,利用隐藏数问题的求解给出了其一种不安全的使用情况:如果加密者使用相同的随机数,并且明文的部分信息泄漏,那么攻击者可以利用隐藏数问题,恢复出完全的明文信息。(本文来源于《解放军信息工程大学》期刊2013-04-15)
王丽萍,祝跃飞[5](2003)在《F[x]-格基约化算法和多条序列综合》一文中研究指出利用F[x]-格基约化算法给出了域F上长度为N的m条序列的最短线性移位寄存器(即极小多项式)的综合算法.此算法的计算复杂度为O(N2)次F中乘运算,同时给出了一个极小多项式惟一的充要判别条件,且在极小多项式不惟一时,给出所有的极小多项式的一般形式和当F为有限域时极小多项式的个数.(本文来源于《中国科学E辑:技术科学》期刊2003年02期)
白淑君,李俊全[6](2001)在《对RSA-型密码体制的格基约化攻击》一文中研究指出D.Boneh和G.Durfee在文献1中指出:当保密指数d<N0.292时RSA密码体制是不安全的。这是对Wiener的结果2的第一次改进。在研究中发现:这种攻击可以扩展到其模p的阶非常接近p的群上。例如,以椭圆曲线和LUC系统为基础的密码体制。(本文来源于《通信技术》期刊2001年05期)
何大可[7](1987)在《格基约化算法解低密度子集和问题的复杂度》一文中研究指出注意到子集和问题所关联的格L(α,M)的特殊性,本文证明了用文献[1~3]所提出的算法求格L(α,M)的约化基或半约化基,其计算量上界至多是用该算法求一般格的约化基或半约化基计算量上界的1/n。特别是,证明了束L(α,M)的半约化基的计算量,当采用快速整数乘法时,可限制在0(n~2(logB_α)~(2+σ))比特运算,只要1≤α_i≤B_α。,1≤i<n,B_α~2≥2~n,δ>0。本文还给出了用上述算法求解低密度和问题的条件与成功概率。(本文来源于《电子学报》期刊1987年06期)
格基约化论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
这篇论文旨在研究格理论中两个非常基础又非常重要的计算问题:计算格基问题和格基约化问题.计算格基问题指的是给定一组格生成元,计算它们生成的格的一组基.格基约化问题则是给定一组格基,计算出具有某种较好性质的格基,或者是向量长度较短,或者是局部向量张成的体积较小等.这两个计算问题关系密切,互为交叉:计算格基是进行格基约化的前提;格基约化过程的局部处理常常涉及计算格基,而且格基约化方法经过适当的修正也能用来计算格基.两者作为基本问题有着重要和广泛的应用.例如,计算格基算法可以用来确定代数数域中的基本单位元,格基约化算法是密码分析的重要工具.因此,研究这两个问题的理论价值和实际意义不言而喻.本文的第一项工作是较为系统地研究了计算格基算法.先前的计算格基算法中,具有线性输出基的算法不具有拟线性时间复杂性,而具有拟线性时间复杂性的算法不具有线性输出基.我们通过引入Euclid交换、正则系统、松弛约化和按块交换等新的技术和想法,首次给出了一个同时具有线性输出基和时间复杂性关于log‖B0‖拟线性的计算格基算法,并且在标准算术下复杂性是O(mn4(log n+log‖B0‖)2),其中B0∈Zm×n表示输入的格生成元.我们进而给出了具有线性输出基和拟线性时间复杂性的本原向量组格基扩充算法.本文的第二项工作是探讨了滑动约化基的性质.作为当前理论上最好的近似求解最短向量问题的格基约化算法,Gama-Nguyen滑动约化算法被视为着名的Mordell不等式的算法实现.通过推广先前的证明方法,我们推导了Gama-Nguyen滑动约化基与逐次极小值之间的比例关系,从而对该类型基的约化程度给出了更全面的刻划.本文的第叁项工作是给出了一个近似求解最小体积问题的格基约化算法.我们证明了一个新的关于Rankin常数的不等式,该不等式用低维Rankin常数γk,r给出高维Rankin常数γn,r的上界.通过推广先前的约化概念,我们给出了输出因子对应上述新Rankin不等式的一个格基约化算法.该算法能确定性地在多项式时间内近似求解最小体积问题.这一项工作可以看成是经典的Mordell不等式和Gama-Nguyen滑动约化算法的延续.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
格基约化论文参考文献
[1].杨建斌,朱宣勇.基于格基约化算法的环上截位序列还原[J].信息工程大学学报.2017
[2].李建伟.格理论中计算格基和格基约化问题研究[D].清华大学.2015
[3].刘向辉,韩文报,权建校.基于遗传策略的格基约化算法[J].电子与信息学报.2013
[4].刘向辉.格基约化算法并行化及应用研究[D].解放军信息工程大学.2013
[5].王丽萍,祝跃飞.F[x]-格基约化算法和多条序列综合[J].中国科学E辑:技术科学.2003
[6].白淑君,李俊全.对RSA-型密码体制的格基约化攻击[J].通信技术.2001
[7].何大可.格基约化算法解低密度子集和问题的复杂度[J].电子学报.1987