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

A Univariate Coppersmith Algorithm Based on Dimensional Reduction

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

RSA is one of the most classic public-key cryptosystems.In practical applications,plaintext may be intercepted in RSA systems.The Coppersmith algorithm is widely used in RSA analysis for the leakage of partial RSA plaintext information,and its main idea is to use LLL algorithm to solve a univariate modular equation.If the equation is solved successfully,then the whole plaintext can be recovered.In this paper,the univariate Coppersmith algorithm based on the small roots problem is improved from three aspects.Firstly,based on the work of Nguyen et al.,a more accurate estimate of the length of the first vector for the LLL algorithm is obtained.The estimation is mainly used to obtain a lower dimension required for solving the equation,and from this dimension,e-dimension is successively increased for reduction until the equation is successfully solved.Secondly,considering that the Coppersmith lattice is not strictly a lattice,if the work of Nguyen et al.is directly applied to the Coppersmith lattice,it is estimated that there may be some errors.Therefore,this paper obtains a new estimation of the reduction effect of the LLL algorithm on the Coppersmith lattice by introducing probability and statistics,and optimizes the starting dimension.Finally,this paper adopts the technique of substituting variables for the original unknown quantity by using the number of unknown plaintext bits,which reduces the solution complexity of the algorithm.Experiments show that the I-Coppersmith algorithm proposed in this paper can improve the efficiency of solving small root problems,and the running time of the algorithm is reduced by about 50%.