###
工程科学与技术:2018,50(2):163-169
←前一篇   |   后一篇→
本文二维码信息
码上扫一扫!
基于e次根攻击RSA的量子算法
(1.信阳师范学院 计算机与信息技术学院, 河南 信阳 464000;2.武汉大学 计算机学院, 湖北 武汉 430072)
Quantum Algorithm for Attacking RSA Based on the eth Root
(1.School of Computer and Info. Technol., Xinyang Normal Univ.,Xinyang 464000,China;2.Compute School,Wuhan Univ.,Wuhan 430072,China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 2152次   下载 1821
投稿时间:2017-08-05    修订日期:2018-02-02
中文摘要: 量子算法的出现给现有的公钥密码体制带来了严峻挑战,其中,最具威胁的是Shor算法。Shor算法能够在多项式时间内求解整数分解问题和离散对数问题,使得当前应用广泛的RSA、ElGamal和ECC等公钥密码体制在量子计算环境下不再安全,因此研究量子计算环境下的密码破译就有重大意义。解决整数分解问题是Shor算法攻击RSA的核心思想,但攻破RSA并非一定要从解决整数分解问题入手。作者试图从非整数分解角度出发,设计攻破RSA密码体制的量子算法。针对RSA公钥密码体制的特点,通过量子傅里叶变换求出RSA密文Cne次根进而得到RSA的明文M。即不通过整数分解问题攻破了RSA。与以往密码分析者通过分解模数n试图恢复私钥的做法不同,直接从恢复明文消息入手,给出一个对抗RSA密码体制的唯密文攻击算法。研究表明,本文算法的成功概率高于利用Shor算法攻击RSA的成功概率。同时本文算法具有如下性质,即不通过解决整数分解问题实现攻破RSA,且避开了密文Cn的阶为偶数这一限制。
中文关键词: 信息安全  密码学  RSA密码  量子计算
Abstract:The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor's algorithm 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 cryptanalysis 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 plaintext M can be got by calculating the eth root modulus n.That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext M to 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 n,and avoids the restriction that the order of ciphertext C modules n is even.
文章编号:201700629     中图分类号:TP301    文献标志码:
基金项目:国家自然科学基金重点资助项目(61332019);国家重点基础研究发展规划资助项目(2014CB340601);国家自然科学基金资助项目(61402339;61202386);国家自然科学基金重大项目资助(91018008);国家密码发展基金资助项目(MMJJ201701304)
作者简介:王亚辉(1988-),女,博士生.研究方向:密码学;量子计算.E-mail:wangyh_ecc@whu.edu.cn
引用文本:
王亚辉,张焕国,王后珍.基于e次根攻击RSA的量子算法[J].工程科学与技术,2018,50(2):163-169.
WANG Yahui,ZHANG Huanguo,WANG Houzhen.Quantum Algorithm for Attacking RSA Based on the eth Root[J].Advanced Engineering Sciences,2018,50(2):163-169.