Quantum Polynomial-Time Fixed-Point Attack for RSA

Yahui Wang, Huanguo Zhang*, Houzhen Wang

School of computer, Wuhan University, Wuhan 430072, Hubei Province, China

Key Laboratory of Aerospace Information security and trusted computing Ministry of Education, Wuhan University, Wuhan 430072, China

I. INTRODUCTION

Advances in quantum computation present a serious challenge to existing public-key cryptosystems: the RSA public-key cryptosystem can be attacked by Shor’s algorithm.Researching cryptanalysis in the quantum computing environment is thus of great significance [1]. It is well known that the security of RSA essentially depends on only the computational intractability of the Integer Factorization Problem (IFP), and in particular, it is only secured if the IFP does not have an efficient algorithm. That is, anyone who can solve the IFP in polynomial-time can break the RSA cryptographic system in polynomial-time.The IFP has been studied since ancient times,and exponential-time algorithms for it have been developed, including Lehman’s method,Shanks’SQU are FOrm Factorization method,Shanks’ class group method, the continued fraction method, Pollard’sρmethod [2]. With the invention of RSA public-key cryptography in 1978 [3], the problem became important and attracted a great deal of attention.

There are many methods for attacking RSA,such as the integer factorization attacks, the discrete logarithm attacks, the public exponent attacks, the private exponent attacks and side channel attacks [4][5]. The computers we are using at present are called classical computers.The most powerful method for breaking RSA is to use the Number Field Sieve (NFS) [6] to factorn, which runs in subexponential-timewherec≈1.92. In fact, all the existing factoring algorithms up to this point, such as the NFS and theρmethods, are inefficient and cannot run in polynomial-time. The ineffectiveness of factoring makes it useful for constructing unbreakable cryptography. However, a polynomial-time quantum factoring algorithm,proposed by Shor in 1994 [7,8], can solve the IFP in a time proportional to Ο（（logn）2+ε）.The idea of Shor’s quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factorn, it suffices to findr, which is the smallest integer, satisfyingar≡1（modn）, whereThe factors are then given byIt is best to implement the full version of Shor’s algorithm to factorn. The most straightforward method for attacking RSA is to factorn.Shor showed that both integer factorization based cryptography and discrete logarithm based cryptography can be totally broken in polynomial-time on practical quantum computers. If a quantum computer with several thousand quantum bits can be built, many existing public-key cryptosystems such as RSA,ElGamal and ECC, will no longer be secure,threatening cyberspace security [1,9].

The emergence of Shor’s algorithm has injected new vitality into research on quantum computation, and has led to an upsurge of quantum computation and quantum computer research over the last twenty years [9-14]. Tremendous efforts have been made to develop practical quantum computers and to improve Shor’s algorithm using different techniques. In[15] a compiled version for factoring 15 using quantum entanglement was proposed, while[16] provided an experimental demonstration of a factoring method with a temporal Talbot effect for factoring the number 19403. For a more compiled version of Shor’s algorithm,please refer to the references [17-22]. Recent research has sought to reduce the number of quantum bits and to make it easy to run on a quantum computer with fewer quantum bits.For example, [23] constructed simplified quantum circuits and gave an example for factoring the numbers 51 and 85 with 8 qubits, and [24]proposed a quantum computing idea to find the numberasuch thatFor more information, please refer to the references [25,26].

It has nevertheless been known for a long time that there is no need to factornif the only aim is to attack RSA. In fact, to recoverMfromC, it is enough to compute the order,r, of the fixed pointC. Once the orderrhas been found, the plaintextMis simply the elementmodn. In classical computing,this computation is equivalent to factoringn,which is believed to be hard. In this paper, we present a new polynomial-time quantum algorithm that can be used to attack RSA without factoring the modulusn.

II. PRELIMINARIES

We first present some basic concepts of the RSA problem, the RSA fixed-point and Quantum Fourier Transform(QFT); for more related information, please refer to the references[2,27].

Definition 1 (The RSA Problem)Given the RSA public-key （e,n） and the RSA ciphertextC, find the corresponding RSA plaintextM. That is,

Definition 2Let 0≤x＜n. If

thenxis called a fixed-point ofRSA（e,n）and the smallestrsatisfying (1) is the order of the fixed-point.

Theorem 1LetCbe the fixed-point ofRSA（e,n） with orderr, such that

Then

whereMis the plaintext,Cis ciphertext, andeis the encryption key.

Proof Please refer to the reference [2].

Definition 3(Quantum Fourier Transform(QFT))The quantum Fourier Transform on an orthonormal basisdefined to be a linear operator with the following action on the basis states,

Equivalently, the action on an arbitrary state may be written as

In addition, for reference, we state the action of the quantum inverse Fourier transform (denoted QFT-1) on the basis states

Accordingly, the phase can be easily estimated using the quantum inverse Fourier transform. This is, of course, based on the basic assumptions of quantum mechanics [27].

III. THE NEW ALGORITHM

Shor discovered a polynomial-time quantum integer factorization algorithm in 1994. For a given numbern, he provided an algorithm for finding the order of the elementato get the factors ofn, and further, to attack RSA.If the integer factorization problem is solved,RSA can be broken; however, attacking RSA does not require factoringn. Therefore, in this section, using the fixed point property of RSA and based on the quantum inverse Fourier transform and phase estimation, we present a new polynomial-time quantum algorithm for directly recovering the RSA plaintextMfrom the ciphertextC, without explicitly factoring the modulusn. The specific steps of the algorithm steps are as follows.

3.1 Algorithm design

We present a quantum algorithm for computing the order of the fixed pointC, enabling breaking RSA in polynomial-time without factoring.

Algorithm 1 Given the RSA public-key（e,n） and RSA ciphertextC, this algorithm tries to find the orderrof the fixed-pointCsuch thatbased on the quantum inverse Fourier transform and phase estimation. Once such anris found,

Input:C,e,n

Output:M

Step 1. Find a numberq=2k, where

Step 2. Give twokdimensional quantum registers whose initial state are

Step 3. Perform a Hadamard transform on the first register, yielding

Step 4. Perform the unitary transformon the second register, giving

whereris the order of the fixed pointC.

Step 5. Perform QFT-1on the first register,giving

Step 6. Measure the first register; suppose we observe the stateusing the continued fractions algorithm to getr1satisfying

Step 7. Repeat Steps 1-5; suppose we observe the stateusing the continued fractions algorithm to getr2satisfying

As we can see, Algorithm 1 breaks RSA without factoringnand without using any knowledge of the trap-door informationwhich only recovers the plaintextMfrom the ciphertextC. Moreover,obtaining the ciphertextCis also the most easily satisfied condition in the real break, so the attack for Algorithm 1 belongs to the category of ciphertext-only attacks. It changes the practices by which cryptanalysts try to recover the private-key, directly from recovering the plaintextMto start, Algorithm 1 gives a ciphertext-only attacks of RSA.

Algorithm 1 breaks RSA from the angle of non-factorization. That is, attacking RSA in Algorithm 1 does not pass through factorization from the traditional mathematical method of RSA itself, whereas traditional methods for breaking RSA all pass through factorization.

3.2 Algorithm analysis

First, we give a complexity analysis of Algorithm 1 as follows.

The dominant computation of the algorithm is that of the inverse quantum Fourier transform, which takes time proportional towhereas the gcd computation takes timeTherefore, in total, the computation time of the algorithm is proportional to

That is, Algorithm 1 recoversMfromCin quantum polynomial-time Ο（（logn）2+ε）.

We next analyze the correctness of Algorithm 1.

From the literature [27], we know that the Hadamard transform we use in Step 3 of Algorithm 1 is a unitary transform. The transformused in Step 4 is constructed as follows:

For a given positive integerC, which is prime ton, there exists a unitary transformand the unitary transform UCcan be performed efficiently. Thus,

Consider the following state:

wheresis a positive integer satisfying 0 ≤s≤r-1.

Consider

Notice that becauseris the order of the fixed pointmodn. The amplitude of the statein the above state is then the sum over the terms for whicht=0. That is,

Thus the amplitude of the stateis 1,and consequently the amplitude of all other basis states must be 0. Therefore, we have

Performing the unitary transform UCon the quantum state

Performing the unitary transformon the quantum statewe get

Then substituting (16) and (18) intoof (8), we get

That is (10).

From [27], we known that the quantum inverse Fourier transform is a unitary transform.The transforms we use in Algorithm 1 satisfy the reversible conditions required by the quantum computing algorithm. Thus in terms of the transforms used in Algorithm 1, the algorithm is correct. Figure 1 presents a circuit for implementing the Algorithm 1.

Finally, we analyze the success probability of Algorithm 1 as follows.

By (12) in Step 5, ifr|q,

Accordingly, the amplitude of the quantum stateis zero, and does not satisfyφs=c/q; that is, after Step 5, the quantum statesleaving in the first register satisfyφs=c/q. By Step 5, the probability Prob（c）that the machine reaches the state

whereφs=c/q, so at this time each state of the quantum superposition that we require is observed with the probability

Ifrq,we can see from Figure 2 thatcsatisfying

When satisfying (22), it is easy to learn that the phase is concentrated in the upper or lower part of the complex plane, while at the same time, the summation ofxcan lead to the superposition of phases. If it does not satisfy(22) at this point, the summation ofxcan lead to the offset of phases by each other, with its size being almost negligible. Therefore, the probability of observing the statecis

Fig. 1. Circuit for implementing the quantum part of Algorithm 1.

Fig. 2.The search for r in the case q.Thus, the probability of the observed stateis approximated toin case ofrq.Similarly, the statesatisfying gcd（c,r）=1 only has?（r） possible values. Thus the probability of outputting the correct statein Step 6 is

that is, whenrq, the probability of success of Algorithm 1 is

Accordingly, the probability of success of Algorithm 1 depends on the order of the fixed pointC. In particular, whenris a prime number, the probability of Algorithm 1 is similar to （r-1）/r; that is, asrincreases,the probability of success approaches 1. Further, we show that the probability of success of Algorithm 1 is higher than that of Shor’s algorithm. In fact, the probability of success of Shor’s algorithm for breaking RSA isFrom the above analysis, we know that for Algorithm 1,whenr|q, the probability of success of Algorithm 1 isand whenrq, the probability of success of Algorithm 1 isBecausethe probability of success of Algorithm 1 is higher than that of Shor’s algorithm.

We now more clearly distinguish the features of Algorithm 1 from those of its predecessor in attacking RSA. Table 1 compares time complexity, the probability of success,required quantum qubits, theoretical basis, and type of attack for both algorithms .

In Table 1, we can see that Algorithm 1 has the following properties: 1) it recovers the RSA plaintextMfrom the ciphertextCwithout factoringn; 2) it does not require the order of the element to be even; 3) it has higher probability of success; 4) it is the first quantization algorithm for an RSA fixed-point attack based on the current literature.

IV. CONCLUSION

Because the RSA cryptosystem is widely used in industry and government, quickly cracking RSA has become an important research direction for modern cryptanalysis. The essential trick to attacking the RSA public-key cryptosystem is a method for factoring modulusnefficiently. If the only goal, however, is to break RSA, we can compute the orderrof the fixed-pointCdirectly without factoring. This paper thus presents a new quantum algorithm for finding the orderrof the fixed-pointCof the given RSA public-keybased on the QFT-1and phase estimation. Because onceris found, the RSA plaintextMcan be immediately obtained by computingRSA can be attacked without factoring the modulusn. The probability of success of Algorithm 1 is higher than that of Shor’s algorithm, and the algorithm runs in polynomial time. Moreover, our algorithm for breaking RSA does not require randomly choosing an integerxsuch that the order ofxmodulonis even; it only needs to find the order of the fixed-pointC, regardless of its parity.

Until now, only Shor’s algorithm has been suitable for quickly solving some periodic problems, such as the integer factorization problem, discrete logarithm problem, elliptic curve discrete logarithm problem, and Pell equation. However, the question of whether Shor’s algorithm can also solve non-periodic problems is a meaningful research direction,which remains a problem for further study.

ACKNOWLEDGEMENT

This work is partially supported by he State Key Program of National Natural Science of China No. 61332019, Major State Basic Research Development Program of China (973 Program) No. 2014CB340601, the National Science Foundation of China No. 61202386,61402339, the National Cryptography Development Fund No. MMJJ201701304.

[1] H.G Zhang, W.B Han, X.J Lai, et al., “Survey on cyberspace security”,SCIENCE CHINA:Information Science, vol. 58, no. 11, 2015, pp. 1-43.

[2] S.Y Yan, “Quantum computational number theory”,Berlin: Springer, 2015.

[3] R.L Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public key cryptosystems”,Communications of the ACM,vol. 21, no. 2, 1978, pp. 120-126.

[4] F. Jia, D. Xi, “A unified method based on SPA and timing attacks on the improved RSA”,China Communications, vol. 13, no. 4, 2016, pp. 89-96.

[5] P. Zhou, T. Wang, G. Li, F. Zhang, X.J Zhao,“Analysis on the parameter selection method for FLUSH+RELOAD based cache timing attack on RSA”,China Communications, vol. 12, no. 6,2015, pp. 33-45.

[6] A.K Lenstra, H.W Lenstra, M.S Manasse, J.M Pollard, “The number field sieve”,Lecture Notes in Mathematics, Berlin: Springer, vol. 1554, 1993,pp. 11-42.

[7] P.W Shor, “Algorithms for quantum computation: discrete logarithms and factoring”,Proc.35th Annual Symposium on Foundations ofComputer Science, 1994, pp. 124-134.

[8] P.W Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”,SIAM Journal on Computing, vol. 26, no. 5, 1997, pp. 1484-1509.

[9] W.Q Wu, H.G Zhang, H.Z Wang, et al., “A public key cryptosystem based on data complexity under quantum environment”,SCIENCE CHINA:Information Science, vol. 58, no. 11, 2015, pp.1-11.

[10] H.F Wang, “Quantum algorithm for obtaining the eigenstates of a physical system”,Physical Review A, vol. 93, 2016, pp. 052334.

[11] S.W Mao, H.G Zhang, W.Q Wu, et al. "Key exchange protocol based on tensor decomposition problem",China Communications, vol. 13,no. 3, 2016, pp. 174-183.

[12] W.Q Wu, H.G Zhang, H.Z Wang, S.W Mao,“Polynomial-time quantum algorithms for finding the linear structures of boolean function”,Quantum Information Process, vol. 14, no. 4,2015, pp. 1215-1226.

[13] H.G Zhang, S.W Mao, W.Q Wu, et al., “Overview of quantum computation complexity theory”,Chinese Journal of Computers, vol. 39, no. 12,2016, pp. 2403-2428.

[14] S. Wang, X.H Song, X.M Niu, “Quantum cosine transform based watermarking scheme for quantum images”,Chinese Journal of Electronics, vol. 24, no. 2, 2015, pp. 321-325.

[15] B.P Lanyon, T.J Weinhold, N.K Langford, “Experimental demonstration of a compiled version of Shor’s algorithm with quantum entanglement”,Physical Review Letters, vol. 99, no. 25, 2007, pp.250505.

[16] M.R Geller, Z.Y Zhou, “Factoring 51 and 85 with 8 qubits”,Scientific Reports, vol. 3, no. 3023,2013, pp. 1-5.

[17] Z.J Cao, Z.F Cao, “On Shor’s factoring algorithm with more registers and the problem to certify quantum computers”,arXiv:1409.7352v1 [cs.DS]10 Sep 2014.

[18] C. Lu, D. Browne, T. Yang, et al., “Demonstration of a compiled version of Shor’s quantum algorithm using photonic qubits”,Physical Review Letters, vol. 99, no. 25, 2007, pp. 250504.

[19] E. Lucero, R. Barends, Y. Chen, et al., “Computing prime factors with a Josephson phase qubit quantum processor”,Nature Physics, vol. 8, no.10, 2012, pp. 719-723.

[20] X.H Peng, Z.Y Liao, N.Y Xu, et al., “Quantum adiabatic algorithm for factorization and its experimental implementation”,Physical Review Letters, vol. 101, no. 22, 2008, pp. 220405.

[21] N.Y Xu, J. Zhu, D.W Lu, et al., “Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system”,Physical Review Letters,vol.108, no.13, 2012, pp. 130501.

[22] T. Lawson, “Odd orders in Shor’s factoring algorithm”,Quantum Information Process,vol. 14,no. 3, 2015, pp. 831-838.

[23] D. Bigourd, B. Chatel, W.P Schleich, et al., “Factorization of numbers with the Temporal Talbot effect: optical implementation by a sequence of shaped Ultrashort pulse”,Physical Review Letters, vol. 100, no. 3, 2008, pp. 030202.

[24] J.A Smolin, G. Smith, A. Vargo, “Oversimplifying quantum factoring”,Nature, vol. 499, 2013, pp.163-165.

[25] N.S Dattani, N. Bryans, “Quantum factorization of 56153 with only 4 qubits”,http://arxiv.org/pdf/1411.6758, 27 Nov 2014,6 pages, 2014.

[26] E. Martin-Lopez, A. Laing, T. Lawson, et al., “Experimental realization of Shor’s quantum factoring algorithm using qubit recycling”,Nature Photonics,vol. 6, no. 11, 2012, pp. 773-776.

[27] M.A Nielsen and I.L Chuang, “Quantum computation and quantum information”,10th anniversary edition, Cambridge: Cambridge University Press, 2010.

[28] L.H Liu and Z.J Cao, “On computing ordn(2) and its application”,Information and Computation,vol. 204, no. 7, 2006, pp. 1173-1178.