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

信息安全研究 ›› 2016, Vol. 2 ›› Issue (3): 225-229.

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

张亚泽

西安电子科技大学通信工程学院

收稿日期:2016-03-15 出版日期:2016-03-15 发布日期:2016-03-16
通讯作者: 张亚泽
作者简介:硕士研究生，主要研究方向为密码学、可证明安全、格理论、信息安全.

A Novel Modulus Factorization Algorithm for RSA Cryptosystem

Received:2016-03-15 Online:2016-03-15 Published:2016-03-16

摘要/Abstract

摘要： 为了提高RSA密码分析效率，提出了一种新的针对RSA密码体制的大整数分解算法.根据Coppersmith定理，利用LLL算法可以在多项式时间内求解非线性低维度多项式方程的小整数解问题.该算法基于格基规约LLL算法，对参数满足eix－yiφ(ni)=zi这一多项式方程的情况进行了研究，其中e为加密指数，n为模数，x，yi为小整数系数.与传统的数域筛法、Monte Carlo方法和椭圆曲线法相比，该大整数分解方法计算复杂度更低.还利用该密码分析方法进行了大整数模数分解.

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

Abstract: 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, yi 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.

Key words: cryptanalysis of RSA, large integer factorization, lattice reduction, LLL algorithm

张亚泽. 一种新型的RSA密码体制模数分解算法[J]. 信息安全研究, 2016, 2(3): 225-229.

参考文献

［1］Rivest R, Shamir A, Adleman L. A method for obtaining digital signatures and publickey cryptosystems［J］. Communications of the ACM, 1978, 21(2): 120126［2］Aardal K, Eisenbrand F. The LLL algorithm and integer programming［C］ Proc of the Advances in Information Security and Cryptography. Berlin: Springer, 2010: 293307［3］Hanrot G, Xavier P, Damien S. Algorithms for the shortest and closest lattice vector problems［C］ Proc of the Advances in IWCC 2011. Berlin: Springer, 2011: 159190［4］Shamir A. A polynornial time algorithm for breaking the basic merklehellman cryptosystem ［M］ Advances in Cryptology. Berlin: Springer, 1983: 279288［5］Adleman L M. On breaking the iterated merklehellman publickey cryptosystem［M］ Advances in Cryptology. Berlin: Springer, 1983: 308308［6］Coppersmith D, Franklin M, Patarin J, et al. Lowexponent RSA with related messages［M］ Advances in Cryptology. Berlin: Springer, 1996: 19［7］Coron J S, May A. Dcterministic polynomialtime equivalence of computing the RSA secrct key and factoring［J］. Journal of Cryptolog, 2007, 20: 3950［8］Nitaj A, Ariffin M R K, Massr D I, et al. New attacks on the RSA cryptosystem［J］. Lecture Notes in Computer Science, 2014, 8469: 178198［9］Faugere J C, Gligoroski D. A polytime keyrecovery attack on MQQ cryptosystems［C］ Proc of Advances in PKC 2015. Berlin: Springer, 2015: 150174［10］Nitaj A. Another generalization of wieners attack on RSA［G］ LNCS 5023: AFRICACRYPT 2008. Berlin: Springer, 2008: 174190［11］Lenstra A K, Lenstra H W, Lovász L. Factoring polynomials with rational coefficients［J］. Mathematische Annalen, 1982, 261(4): 515534［12］Nitaj A, Muhammad R l A. New Attacks on the RSA cryptosystem［G］ Proc of Advances in AFRICACRYPT 2014. Berlin: Springer, 2014: 3151［13］Aoki K, Franke J, Kleinjung. A kilobit special number field sieve factorization［G］ Proc of Advances in Cryptology. Berlin: Springer, 2007: 112［14］Atanassov E, Georgiev D, Manev N L. ECM integer factorization on GPU cluster［C］ Proc of the 35th Int Convention. 2012: 328332