一种新型的RSA密码体制模数分解算法  

A Novel Modulus Factorization Algorithm for RSA Cryptosystem

作　　者：张亚泽[1] 

机构地区：[1]西安电子科技大学通信工程学院,西安710071

出　　处：《信息安全研究》2016年第3期225-229,共5页Journal of Information Security Research

基　　金：国家自然科学基金项目(61370188)

摘　　要：为了提高RSA密码分析效率,提出了一种新的针对RSA密码体制的大整数分解算法.根据Coppersmith定理,利用LLL算法可以在多项式时间内求解非线性低维度多项式方程的小整数解问题.该算法基于格基规约LLL算法,对参数满足e_ix-y_iφ(n_i)=z_i这一多项式方程的情况进行了研究,其中e为加密指数,n为模数,x,y_i为小整数系数.与传统的数域筛法、Monte Carlo方法和椭圆曲线法相比,该大整数分解方法计算复杂度更低.还利用该密码分析方法进行了大整数模数分解.A new large integer factorization algorithm is presented in this paper to improve the cryptanalysis efficiency of RSA. According to the Coppersmith’s theorem,the small integer roots for polynomial equations problem can be solved with LLL algorithm in polynomial time. The lattice reduction algorithm-LLL algorithm is applied in the research of the situation in which the polynomial equation meets eix - yiφ（ni）=zi , where e is the encryption index, n is the modulus and xi, y , are the small integer parameters. Compared with those traditional algorithms,the computational complexity of this paper’s new factorization algorithm is lower. In additions,the factorization of the modulus is provided with the cryptanalysis algorithm.

关 键 词：RSA密码分析 大整数分解 格基规约 LLL算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]