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

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

一种基于行公因子提取的改进Coppersmith算法

1996年欧密会上,Coppersmith提出一种对单变元模方程求小根的多项式时间算法,该算法对公钥密码系统的安全性分析具有重要意义。结合Coppersmith算法中格基矩阵的结构特点和元素性质提出一种改进算法,通过逐次提取格基矩阵不同块中行向量的公因子,有效降低了Coppersmith算法的求解时间。同时通过实验证明了此改进算法可有效兼容一种预处理算法,通过将这两种算法结合,进一步提高了Coppersmith算法的求解效率,实验表明较原Coppersmith算法最高可提升22.64%。

RSA及其变体算法的格分析方法研究进展

格分析是一种利用格困难问题的求解算法分析公钥密码安全性的分析方法,是研究RSA类密码算法安全性的有力数学工具之一.格分析的关键在于构造格基,虽然目前已有通用简洁的格基构造策略,然而,这种通用方法无法充分、灵活地利用RSA及其变体的代数结构.近年来, RSA类算法的格分析工作大多在通用策略的基础上引入特殊格基构造技巧.首先介绍了格分析方法以及通用格基构造策略,并总结提炼了几种常用格基构造技巧;其次,回顾了标准RSA算法格分析的主要成果,即模数分解攻击、小解密指数攻击以及部分私钥泄漏攻击;然后,总结了几种主流RSA变体算法的特殊代数结构,及其适用的特殊格基构造技巧;最后,对现有RSA及其变体算法的格分析工作进行了分类总结,并展望了格分析方法的研究与发展方向.

基于格的RSA密码分析

格在公钥密码分析领域中有着十分重要的地位.1996年,Coppersmith以多项式方程求小值解的问题为桥梁,把攻击RSA密码体制的问题转换为求格中短向量的问题,开辟了基于格的RSA密码分析的研究,他的工作也在后人的简化完善下逐渐形成了Coppersmith方法.一方面,关于基于格的Coppersmith方法,依次介绍了模多项式方程求小值解的方法、整系数多项式方程求小值解的方法、求解近似公共因子问题的方法,还简单描述了除Coppersmith方法外的一种在低维格中寻找最短非零向量的格方法.另一方面,关于RSA密码分析,回顾了小加密指数攻击、小解密指数攻击、部分私钥泄露攻击、求解私钥d与分解模数N的等价性证明、隐式分解问题的分析、素因子部分比特泄露攻击、共模攻击等,并且以Prime Power RSA,Takagi's RSA,CRT-RSA,Common Prime RSA为例,介绍了格方法在RSA密码变体分析中的应用.

SIMON算法的不可能差分分析

SIMON算法是2013年由NSA提出的一族轻量级分组密码算法,至今已有很多密码学者进行了安全性分析,如线性分析,差分分析,不可能差分和零相关线性hull分析等.SIMON算法根据不同的分组和密钥长度一共提供了10个不同的版本,可以满足不同的安全性需求.在这篇论文中,我们首先利用自动化搜索技术,获得了SIMON32算法最长的不可能差分路径,在此基础上对SIMON算法进行了不可能差分分析.我们给出了19轮SIMON 32/64的不可能差分分析的详细过程.在数据收集过程中,我们利用明文差分和第一轮输出差分与密钥无关的特点,使用建立并解方程的方法构造出满足明文和第一轮输出差分条件的明密文对,极大地降低了数据收集过程的计算复杂度.在密钥恢复过程中,采用Wang等提出的动态密钥猜测技术,降低了密钥过滤过程中的计算复杂度,改进了之前SIMON算法的不可能差分结果.

私钥低比特特定泄露下的RSA密码分析

基于Coppersmith方法,RSA密码分析取得了许多新结果,其中包括部分私钥泄露攻击与低解密指数攻击.现实中侧信道攻击能够泄露私钥的部分比特位,而部分私钥泄露攻击正是通过泄露的这些比特位来实现对RSA密码的破解.低解密指数攻击则是在解密指数取值较小的条件下来破解RSA,Boneh和Durfee给出了至今最好的结果.针对私钥最低几位比特泄露的攻击,是一类重要的部分私钥泄露攻击,并且和低解密指数攻击紧密相关.基于Coppersmith方法在模多项式方程求小值解的应用,以及线性化模方程的技巧,本文给出了新的针对私钥最低几位比特泄露的攻击结果.其中线性化模方程的技巧,来源于Herrmann和May对于Boneh和Durfee的低解密指数攻击结果的简化证明.注意到目前针对私钥最低几位比特泄露的攻击只关注所泄露比特的位数,而本文还关注所泄露比特的取值.当所泄露比特的取值满足一定的条件时,本文的结果改进了Ernst等人的攻击结果.另外Ernst等人只考虑了加密指数与RSA模基本相等的特殊情况,本文进一步研究了加密指数小于RSA模的一般情况.

部分私钥泄露下的CRT-RSA分析

2003年,Bl?mer和May在研究针对RSA密码的部分私钥泄露攻击的同时,也研究了针对CRT-RSA的部分私钥泄露攻击.此后,大量关于CRT-RSA部分私钥泄露攻击的研究是针对泄露的比特为MSBs (最高数位比特)或者LSBs (最低数位比特).2014年,Sarkar与Venkateswarlu首次考虑了关于CRT-RSA部分私钥泄露攻击中未泄露比特块数超过1个的情况,其格构造的方法借鉴了2008年Herrmann和May在解决线性模方程求小值解问题中的想法.文章在Sarkar等研究基础上通过使用有益多项式及连续有益多项式的定义对构造的多项式集合进行筛选,这种方法来源于Takayasu等对Herrmann和May求解模多项式小值解的改进工作.因此所构造的格维数比Sarkar等构造的更低且缩短了LLL算法的运行时间,改进了Sarkar等的结果.