基于e次根攻击RSA的量子算法

量子算法的出现给现有的公钥密码体制带来了严峻挑战，其中，最具威胁的是Shor算法。Shor算法能够在多项式时间内求解整数分解问题和离散对数问题，使得当前应用广泛的RSA、ElGamal和ECC等公钥密码体制在量子计算环境下不再安全，因此研究量子计算环境下的密码破译就有重大意义。解决整数分解问题是Shor算法攻击RSA的核心思想，但攻破RSA并非一定要从解决整数分解问题入手。作者试图从非整数分解角度出发，设计攻破RSA密码体制的量子算法。针对RSA公钥密码体制的特点，通过量子傅里叶变换求出RSA密文C模n的e次根进而得到RSA的明文M。即不通过整数分解问题攻破了RSA。与以往密码分析者通过分解模数n试图恢复私钥的做法不同，直接从恢复明文消息入手，给出一个对抗RSA密码体制的唯密文攻击算法。研究表明，本文算法的成功概率高于利用Shor算法攻击RSA的成功概率。同时本文算法具有如下性质,即不通过解决整数分解问题实现攻破RSA，且避开了密文C模n的阶为偶数这一限制。

Quantum Algorithm for Attacking RSA Based on the eth Root

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 e^th 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.