计算机科学 ›› 2016, Vol. 43 ›› Issue (4): 24-27.doi: 10.11896/j.issn.1002-137X.2016.04.004

• 2015年全国理论计算机科学学术年会 • 上一篇    下一篇

一种新的攻击RSA的量子算法

王亚辉,颜松远   

  1. 武汉大学计算机学院 武汉430072,武汉大学计算机学院 武汉430072
  • 出版日期:2018-12-01 发布日期:2018-12-01

New Quantum Algorithm for Breaking RSA

WANG Ya-hui and YAN Song-yuan   

  • Online:2018-12-01 Published:2018-12-01

摘要: 整数分解是数论中一个非常古老的难解性问题,而对于当今世界上最有名且广泛使用的RSA公钥密码体制,其安全性是基于整数分解的难解性的。迄今为止,最有希望破解RSA的方法就是Shor的量子算法。利用RSA不动点性质,基于量子Fourier变换和变量代换,提出了一种新的攻击RSA的量子算法。该算法不需要分解n,而是从RSA密文C中直接恢复其明文M。该算法与Shor算法相比,需要的量子位更少,且成功概率大于1/2。最后将新算法的资源消耗情况与Shor算法的进行了对比。

关键词: 量子Fourier变换,RSA密码,量子算法,信息安全

Abstract: It is well known that the security of the most famous and widely used public-key cryptosystem RSA relies on the computational intractability of the integer factorization problem.In this paper,by a combined use of the fixed-point property of RSA,multiple Fourier transforms and variable substitution,a new quantum algorithm for directly recovering the RSA plaintext M from the ciphertext C was presented,without explicitly factoring the modulus n.Compared to Shor’s quantum algorithm,the new algorithm requires fewer quantum bits.The probability of success of the new algorithm is bigger than 1/2.Moreover,a comparison of the required resources between our algorithm and Shor’s was pre-sented.

Key words: Quantum Fourier transform,RSA cryptography,Quantum algorithm,Information 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,1(6):120-126
[2] Lenstra A K,Lenstra Jr H W,et al.The Development of the Number Field Sieve [M].Springer-Verlag,1993
[3] Kleinjung T,Aoki K,Lenstra A K,et al.Factorization of a 768-Bit RSA modulus [C]∥Lecture Notes in Computer Science 6223.Springer,2010:333-350
[4] Shor P W.Algorithms for Quantum Computation:Discrete Loga-rithms and Factoring [C]∥ Proc of 35th Annual Symposium on Foundations of Computer Science.IEEE Computer Society Press,1994:124-134
[5] Lu X,Feng D G.Quantum Analysis of Modern Cryptosystems [J].Computer Science,2005,32(2)(in Chinese) 吕欣,冯登国.密码体制的量子算法分析[J].计算机科学,2005,32(2)
[6] Vandersypen L M K,Steffen M,Breyta G,et al.Experimental Realization of Shor’s Quantum Factoring Algorithm Using Nuclear Magnetic Resonance [J].Nature,2001,414(6866):883-887
[7] Peng X H,Liao Z Y,Xu N Y,et al.A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation[J].Physical Review Letters,2008,101(22):4473-4475
[8] Xu N Y,Zhu J,Lu D W,et al.Quantum Factorization of 143 on a Dipolar-coupling Nuclear Magnetic Resonance System [J].Physical Review Letters,2012,108(13):4089-4091
[9] Geller M R,Zhou Z Y.Factoring 51 and 85 with 8 Qubits [J].Scientific Report,2013,3(10):3023
[10] Cohen H.A Course in Computational Algebraic Number Theory [M]∥Graduate Texts in Mathematics 138.New York:Sprin-ger,1993
[11] Nielson M A,Chuang I L.Quantum Computation and Quantum Information [M].Cambridge:Cambridge University Press,2000
[12] Yan S Y.Cryptanalytic Attacks on RSA [M].New York:Springer,2010
[13] Yan S Y.Computational Number Theory and Modern Public-Key Cryptography[M].Wiley and Higher Education Press,2013
[14] Shor P W.Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [J].SIAM Journal on Computing,1997,41(2):1484-1509
[15] Zallka C.Fast Versions of Shor’s Quantum Factoring Algo-rithm .arXiv:Quant-ph/9806084v1,1998
[16] Dattani N S,Bryans N.Quantum Factorization of 56153 with only 4 Qubits .arXiv:1411.6758v3[quant-ph],Nov 2014
[17] Smolin J A,Vargo A.Oversimplifying Quantum Factoring [J].Nature,2013,499(7457):163-165

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!