《计算机应用研究》|Application Research of Computers

大数因子分解算法综述

Survey of large integer factorization algorithms

免费全文下载 (已被下载 次)  
获取PDF全文
作者 刘新星,邹潇湘,谭建龙
机构 1.中国科学院信息工程研究所,北京 100093;2.国家计算机网络应急技术处理协调中心,北京 100029
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2014)11-3201-07
DOI 10.3969/j.issn.1001-3695.2014.11.001
摘要 大数因子分解不仅是非对称加密算法RSA最直接的攻击手段,也是RSA安全性分析最关键的切入点,对其研究具有极其重要的应用和理论价值。主要概括了大数因子分解的研究现状,回顾了当前主流的大数因子分解算法,介绍了它们的基本原理和实现步骤;此外,对比分析了现有大数因子分解技术在实现和应用上的优缺点;最后分析并展望了大整数分解未来的研究趋势。
关键词 大数因子分解;非对称加密;RSA;安全性
基金项目 国家“863”计划资助项目(2012AA012502)
中国科学院战略性先导科技专项基金资助项目(XDA06030602)
本文URL http://www.arocmag.com/article/01-2014-11-001.html
英文标题 Survey of large integer factorization algorithms
作者英文名 LIU Xin-xing, ZOU Xiao-xiang, TAN Jian-long
机构英文名 1. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; 2. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China
英文摘要 The large integer factorization is not only the most direct attacking method against RSA asymmetric encryption algorithm, but also the most important point to analyze the security of RSA. Study on the large integer factorization problem is of great value for theory and practice. This paper summarized the study on of the large integer factorization problem and reviewed modern popular integer factorization algorithms, and introduced their basic prinple and implementation steps. In addition, this paper made an analysis on existing large integer factorization techniques’ advantage and disadvantage of implementation and application. At last, this paper stated the future prospect of large integer factorization.
英文关键词 large integer factorization; asymmetric encryption; RSA; security
参考文献 查看稿件参考文献
  [1] RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J] . Communications of the ACM, 1978, 21(2):120-126.
[2] AGRAWAL M, KAYAL N, SAXENA N. PRIMES is in P[J] . Annals of Mathematics, 2004, 160(2):781-793.
[3] RSA Laboratories. The RSA factoing Challenge[EB/OL] . (2013). http://www. emc. com/emc-plus/rsa-labs/historical/the-rsa-factoring-challengehtm.
[4] BONENBERGER D, KRONE M. Factorization of RSA-170[R] . Wolfenbiittel:Ostfalla Clniversity of Applied Sciences, 2010.
[5] DANILOV S, POPOVYAN I. Factorization of RSA-180[EB/OL] . IACR (2010-05-09). http://eprint. iacr. org/2010/270. pdf.
[6] POPOVYAN I, TIMOFEEV A. RSA-190 factored[EB/OL] . (2010-11-10). http://maths-people. anu. edu. au/~bai/factor/rsa190. html.
[7] KLEINJUN T. We have factored RSA200 by GNFS[EB/OL] . (2005-05-09). http://www. loria. fr/~zimmerma/records/rsa200.
[8] PROPPER R. RSA-210 factored[EB/OL] . (2013-10-17). http://www. mersenneforum.
[9] BAI Shi, THOM E, ZIMMERMANN P. Factorisation of RSA-704 with CADO-NFS[EB/OL] . (2010-05-09)[2012-07-05] . http://eprint. iacr. org/2012/369. pdf.
[10] KLEINJUNG T, AOKI K, FRANKE J, et al. Factorization of a 768-bit RSA modulus[C] //Advances in Cryptology. Berlin:Springer, 2010:333-350.
[11] 付向群, 鲍皖苏, 周淳, 等. 具有高概率的整数分解量子算法[J] . 电子学报, 2011, 39(1):35-39.
[12] DENG Ying-pu, PAN Yan-bin. An algorithm for factoring integers[BE/OL] . (2012-02-29). http://eprint. iacr. org/2012/097. pdf.
[13] BAI Shi, ZIMMERMANN P. Size optimization of sextic polynomials in the number field sieve[EB/OL] . (2012-12-03). http://hal. inria. fr/docs/00176103/31/PDF/sopt. pdf.
[14] 李骏. 分布式计算环境下大整数分解的研究[D] . 上海:上海交通大学, 2007.
[15] GHEBREGIORGISH S T. Quadratic sieve integer factorization using Hadoop[D] . Stavanger:University of Stavanger, 2012.
[16] TORDABLE J. MapReduce for integer factorization[EB/OL] . (2010-01-04). http://www. javiertordable. com/files/MapreduceForIntegerFactorization. pdf.
[17] ZIMMERMANN R, GUNEYSU T, PAAR C. High-performance integer factoring with reconfigurable devices[C] //Proc of International Conference on Field Programmable Logic and Applications. Washington DC:IEEE Computer Society, 2010:83-88.
[18] ATANASSOV E, GEORGIEV D, MANEV N L. ECM integer factorization on GPU cluster[C] //Proc of the 35th International Convention. 2012:328-332.
[19] LI Lei, HAN Wen-bao. Hardware implemention of the pipeline architecture of integer factorization based on elliptic curve method[J] . Journal of Information Engineering University, 2012, 13(1):13-17.
[20] ARCHER C. GPU Integer factorisation with the quadratic sieve[D] . Bath:University of Bath, 2010.
[21] IZU T, KOGURE J, SHIMOYAMA T. CAIRN:dedicated integer factoring devices[C] //Proc of the 13th International Conference on Network-based Information Systems. Washington DC:IEEE Computer Society, 2010:558-563.
[22] POLLARD J M. A Monte Carlo method for factorization[J] . BIT Numerical Mathematics, 1975, 15(3):331-334.
[23] BRENT R P. An improved Monte Carlo factorization algorithm[J] . BIT Numerical Mathematics, 1980, 20(2):176-184.
[24] BRENT R P, POLLARD J M. Factorization of the eighth Fermat number[J] . Mathematics of Computation, 1981, 36(154):627-630.
[25] POLLARD J M. Theorems on factorization and primality testing[J] . Mathematical Proceedings of the Cambridge Philosophical Society, 1974, 76(3):521-528.
[26] Jr LENSTRA H W. Factoring integers with elliptic curves[J] . Annals of Mathematics, 1987, 126(3):64-73.
[27] BRENT R D. Factorization of the tenth Fermat number[J] . Mathematics of Computation of the American Mathematical Society, 1999, 68(225):429-451.
[28] BRENT R. Factorization of the tenth and eleventh Fermat numbers[R] . Canberra:Australian National University, 1996.
[29] ZIMMERMANN P. 50 largest factors found by ECM[EB/OL] . [2013] . http://www. loria. fr/~zimmerma/records/top50. html.
[30] COPPERSMITH D. Solving homogeneous linear equations over GF(2) via block wiedemann algorithm[J] . Mathematics of Computation, 1994, 62(205):333-350.
[31] MONTGOMERY P L. A block Lanczos algorithm for finding dependencies over GF (2)[C] //Advances in Cryptology . Berlin:Springer, 1995:106-120.
[32] POMERANCE C. The quadratic sieve factoring algorithm[C] // Advances in Cryptology. Berlin:Springer, 1985:169-182.
[33] LANDQUIST E. The quadratic sieve factoring algorithm[C] //Advances in Cryptology. Berlin:Springer, 1985:169-182.
[34] SILVERMAN R D. The multiple polynomial quadratic sieve[J] . Mathematics of Computation, 1987, 48(177):329-339.
[35] GUAN D J. Experience in factoring large integers using quadratic sieve[R] . Kaohsiung:National Sun Yat-Sen University, 2005.
[36] POMERANCE C. A tale of two sieves[J] . Notices of the American Mathematical Society, 1996, 43(1):1473-1482.
[37] ATKINS D, GRAFF M, LENSTRA A K, et al. The magic words are squeamish ossifrage[C] //Advances in Cryptology. Berlin:Springer, 1995:261-277.
[38] LENSTRA A K, Jr LENSTRA H W. The development of the number field sieve[M] . Berlin:Springer, 1993.
[39] LANDQUIST E. The number field sieve factoring algorithm[D] . Kutztown:Kutztown University, 2002.
[40] BUHLER J P, Jr LENSTRAH W, POMERANCE C. Factoring integers with the number field sieve[M] //The Development of the Number Field Sieve. Berlin:Springer, 1993:50-94.
[41] MURPHY B A. Polynomial selection for the number field sieve integer factorisation algorithm[D] . Canberra:Australian National University, 1999.
[42] KLEINJUNG T. On polynomial selection for the general number field sieve[J] . Mathematics of Computation, 2006, 75(256):2037-2047.
[43] KLEINJUNG T. Polynomial selection[C] //Proc of CADO Workshop on Integer Factorization. 2008.
[44] PREST T, ZIMMEMANN P. Non-linear polynomial selection for the number field sieve[J] . Journal of Symbolic Computation, 2012, 47(4):401-409.
[45] CAVALLAR S, DODSON B, LENSTRA A K, et al. Factorization of a 512-bit RSA modulus[C] //Advances in Cryptology- EUROCRYPT. Berlin:Springer, 2000:1-18.
[46] POLLARD J M. The lattice sieve[M] //The Development of the Number Field Sieve. Berlin:Springer, 1993:43-49.
[47] BAI Shi, GAUDRY P, KRUPPA A, et al. CADO-NFS, an implementation of the number field sieve[EB/OL] . (2011-10-27). http://cado-nfs. gforge. inria. fr.
[48] GOLLIVER R A, LENSTRA A K, McURLEY K S. Lattice sieving and trial division[C] //Proc of the 1st International Symposium on Algorithmic Number Theory. Berlin:Springer, 1994:18-27.
[49] FRANKE J, KLEINJUNG T. Continued fractions and lattice sieving[C] //Proc of the 1st Workshop on Special-Purpose Hardware for Attacking Cryptographic Systems. 2005.
[50] COUVEIGNES J M. Computing a square root for the number field sieve[M] //The Development of the Number Field sieve. Berlin:Springer, 1993:95-102.
[51] COWIE J, DODSON B, ELKENBRACHT-HUIZING R, et al. A world wide number field sieve factoring record:on to 512 bits[C] //Advances in Cryptology. Berlin:Springer, 1996:382-394.
[52] CHILDERS G. Factorization of a 1061-bit number by the Special Number Field Sieve[EB/OL] . (2012-08-06). http://eprint. iacr. org/2012/444. pdf. 2012:444.
[53] AOKI K, FRANKE J, KLEINJUNG T, et al. A kilobit special number field sieve factorization[C] //Advances in Cryptology. Berlin:Springer, 2007:1-12.
收稿日期 2014/2/18
修回日期 2014/4/24
页码 3201-3207
中图分类号 TP309.2
文献标志码 A