工程科学与技术2018，Vol.50Issue(2)：163-169,7.DOI:10.15961/j.jsuese.201700629
基于e次根攻击RSA的量子算法
Quantum Algorithm for Attacking RSA Based on the ethRoot
摘要
Abstract
The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor's al-gorithm is the most important threatening algorithm for cryptanalysis currently.Shor's algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the crypt-analysis in the quantum computing environment.Solving the IFP is the core idea of Shor's algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintextMcan be got by calculating theethroot modulus .That is,without solving the IFP,RSA is broken.Different from the previousn practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintextMto start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor's algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus ,andn avoids the restriction that the order of ciphertext C modules n is even.关键词
信息安全/密码学/RSA密码/量子计算Key words
information security/cryptology/RSA cryptography/quantum computing分类
信息技术与安全科学引用本文复制引用
王亚辉,张焕国,王后珍..基于e次根攻击RSA的量子算法[J].工程科学与技术,2018,50(2):163-169,7.基金项目
国家自然科学基金重点资助项目(61332019) （61332019）
国家重点基础研究发展规划资助项目(2014CB340601) （2014CB340601）
国家自然科学基金资助项目(61402339 （）
61202386) （）
国家自然科学基金重大项目资助(91018008) （91018008）
国家密码发展基金资助项目(MMJJ201701304) （MMJJ201701304）
