Issue 
Wuhan Univ. J. Nat. Sci.
Volume 26, Number 6, December 2021



Page(s)  489  494  
DOI  https://doi.org/10.1051/wujns/2021266489  
Published online  17 December 2021 
Computer Science
CLC number: TP391
Quantum Algorithm for Attacking RSA Based on Fourier Transform and FixedPoint
^{1}
School of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, Hubei, China
^{2}
School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China
† To whom correspondence should be addressed. Email: liss@whu.edu.cn
Received:
28
September
2021
Shor in 1994 proposed a quantum polynomialtime algorithm for finding the order r of an element a in the multiplicative group Z_{n}^{*}, which can be used to factor the integer n by computing and hence break the famous RSA cryptosystem. However, the order r must be even. This restriction can be removed. So in this paper, we propose a quantum polynomialtime fixedpoint attack for directly recovering the RSA plaintext M from the ciphertext C, without explicitly factoring the modulus n. Compared to Shor’s algorithm, the order r of the fixedpoint C for RSA(e, n) satisfying does not need to be even. Moreover, the success probability of the new algorithm is at least and higher than that of Shor’s algorithm, though the time complexity for both algorithms is about the same.
Key words: information security / cryptology / RSA fixedpoint / quantum computing
Biography: WANG Yahui, female, Ph. D., research direction: quantum computing and cryptography. Email: wangyh_ecc@whu.edu.cn
Foundation item: Supported by Nanhu Scholars Program for Young Scholars of Xinyang Normal University
© Wuhan University 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
Since the discovery of quantum mechanics, people have paid much attention to quantum computers and quantum computing^{[1,2]}, which can perform some tasks, such as integer factorization problems, phase estimating problems, hidden subgroup problems, that are not feasible on a classical computer by using quantum parallelism and interference effect. In these quantum algorithms mentioned above, the Quantum Fourier Transform (QFT), which is a linear unitary transform, plays a significant role and lies in the core of the algorithms. Moreover, the QFT is one of the most important computational problems and many realworld applications require that the transform should be performed as quickly as possible.
It is well known that factoring an integer n can be reduced to finding the order of an integer a with respect to the module n. The order, r, of an element a in the multiplicative group Z_{n}^{*}, denoted by order(a, n), plays a significant role in the period of certain pseudorandom number generators, and particularly in Shor’s quantum integer factorization algorithm and other cryptographic applications. So far as is known, there is not a polynomial time algorithm running on classical computers which can compute order(a, n) in polynomial time. The main idea of Shor’s algorithm is simple: to factor n, one first computes the order r. If the computed r is even, then one further computes, with high probability, with 1<p, q<n.
The world was astonished when Shor announced in 1994^{[3]} that he found an efficient quantum integer factorization algorithm which can solve IFP (Integer Factrorization Problem) in time proportion to O((logn)^{2+ε}). Security analysis of public key cryptosystems is of great significance in theory and practical application, especially the security of widely used public key cryptosystems such as RSA, ElGamal and ECC, which is worthy of further research^{[1]}. Current research on quantum factoring is concentrated on various improved and compiled versions of Shor’s original algorithm. Smolin et al^{[4]} claimed that if one can find a such that order (a, n)=2, then Shor’s quantum factoring algorithm can be implemented easily using two quantum bits. Peng et al^{[5]} found an approach to implement the prime factorization of 21=3×7 based on the adiabatic theory. More recently, it extends to 143 on a DipolarCoupling Nuclear Magnetic Resonance System^{[6]}. Wang et al^{[7]} analyzed the RSA deciphering method based on DWave quantum annealing principle, which is a new attack algorithm for quantum computing.
There are three important research directions of quantum computing publickey cryptographic attacks:
1) Improve, modify and simply Shor’s algorithm or even invent new quantum factoring algorithms to be run on quantum computers with fewer quantum bits^{[5,812]}.
2) Quantum attack algorithms based on adiabatic quantum computing^{[6,7]}.
3) Quantum attack algorithms based on quantum annealing principle^{[13,14]}.
It has been known for a long time that there is no need to factor n if one just wish to break RSA.
In fact, to recover M from C, one could just compute the sequence of numbers (assume C is known):where the overline symbol indicates the periodic elements. Once the first occurrence of is found, the plaintext M is just the element immediately preceding .
In classical computing, this process of computation is equivalent to the factorization of n, which is believed to be a hard problem. However, it can be done efficiently on a quantum computer, and it is even more convenient than Shor’s original algorithm. In this paper, we shall propose a new quantum algorithm for directly recovering the RSA plaintext M from the ciphertext C by computing the order r of the fixedpoint C, without explicitly factoring the modulus n, with higher success probability. Before discussing the algorithm, we present some basic concepts and results that will be used throughout the paper.
Definition 1 ^{[15]} The RSA problem may be defined as follows. Given the RSA publickey (e,n) and the RSA ciphertext C, find the corresponding RSA plaintext M. That is,
Definition 2 Let 0≤x<n. If(1)then x is called a fixedpoint of RSA (e, n) and the smallest r satisfying (1) is the order of the fixedpoint.
Theorem 1 Let C to be the fixedpoint of RSA (e, n) with order r: (2)then(3)where M is the plaintext, C is ciphertext, and e is the encryption key.
Proof See Ref. [15].
1 The New Algorithm
In this section, we shall present a polynomialtime quantum algorithm for computing the order r of the fixedpoint C for RSA (e, n), such that
Algorithm 1 Quantum algorithm for attacking RSA based on Fourier transform and fixedpoint
Input: C,e,n
Output: M
Step 1 Find a number q, a power of 2, say 2^{t}, such that
Step 2 Initialize the two quantum registers, Reg1 and Reg2, , where Reg1 requires qubits, Reg2 requires qubits (whose number depends on the space requirement).
Step 3 Perform a Hadamard transform on Reg1, we get(4)
Step 4 Perform the unitary transform on Reg2, we getwhere , thus, .
Step 5 Measure Reg2. Suppose we observe , and at the same time, the state in Reg1 is collapsed into a superposition over all x such that . That leaves Reg1 in state(5)where n_{l} is the largest positive integer satisfying
Step 6 Perform QFT on Reg1.where
Step 7 Observe Reg1. This yields the state with probability
Then we can use continued fraction method to find the closest to c/q among all the convergent of the continued fractions with their denominators less than n, thus its denominator is the required order r, similar to Shor’s method^{[3]} for obtaining r from the observation value c.
Step 8 Compute hence, the required plaintext M is obtained, that is, RSA is broken.
An example illustrating each of computational steps is given as follows.
Example 1 Let n=35, e=5, C=10.
Step 1 Find a number q such that 35^{2}<q=2^{11}=2048<2×35^{2}.
Step 2 Initialize the two quantum registers .
Step 3 Perform a Hadamard transform on Reg1, we get(7)
Step 4 Perform the unitary transform on Reg2, we getwhere , thus, .
The computation of the detailed exponentiations 10^{5} mod 35 is as follows(8)
Step 5 Measure Reg2. Suppose we observe , this means that the state in Reg1 is collapsed into a superposition over all x such that . That leaves Reg1 in state(9)
Step 7 Measure Reg1. Suppose that c=1024 is observed with a higher probability 1/2, and in fact, all other states are observed with the probability 0. Then use the continued fraction expansion(10)r=2 can be deduced.
Step 8 Compute , hence, the required plaintext is obtained, that is, RSA is broken.
Table 1 summarizes the main processes and differences between Shor’s algorithm and Algorithm 1 for breaking RSA.
In what follows, we give a performance analysis of the algorithm. The number of gates needed are O(log n) for the initial Hadamard in Step 3. The computation for the multiple modular (which is a number between 1 and n1), in Step 4, which takes time proportion to . The QFT in Step 6 requires O((log n)^{2}) gates^{[16]}. The classical continued fraction algorithm in Step 7 needs (classical) gates. Thus the quantum circuit of Algorithm 1 requires only O((log n)^{2}) elementary quantum gates. That is, Algorithm 1 breaks RSA in quantum polynomialtime .
Now we estimate the size of the probability Prob(c). In Step 7, the probability Prob(c) that the machine reaches the state ( 0≤c≤q1) is(11)
Definition 3 If the state was observed and r can be found correctly by Algorithm 1, then c is a good value.
Theorem 2 If there exists a positive integer d which is less than r and is prime to r, such that(12) then c is a good value.
Proof We first introduce a lemma which will be used in the proof of the theorem.
Lemma 1 Suppose s/r is a rational number such that
Then s/r is a convergent of the continued fraction for φ.
Therefore, by Lemma 1, d/r must be a convergent of the continued fraction for c/q.
Suppose p_{s}/q_{s} is the closest to p/q among all the convergent of the continued fractions with their denominators less than n. Then we prove that .
Because d/r is a convergent of the continued fraction for c/q and r<n, thusand becausetherefore
Accordingly, p_{s}rq_{s}d=0, that is, p_{s}/q_{s}=d/r. Finally, because gcd(p_{s},q_{s})=1=gcd(d,r), thus q_{s}=r. This shows that r is found correctly by Algorithm 1, so c is a good value.
Lemma 2 If c is a good value, then
Proof If c is a good value, by Definition 3, there exists a positive integer d which is less than r and is prime to r, such thatthat is,(13)
We denote(14)thus, we can denote rc
Of course, (15)Using (13), (14) and (15), we can get(16)So(17)Since , so the probability Prob (c) is
Using the inequalities ≤x^{2} (where the lower bound holds for x≤π/2), we find(18)
Thus, the probability of observing a good value is at least 4/(π^{2}r).
Then we wish to extract the information of the value of r, given a value of c satisfying(19)
To do this we note that (19) is equivalent to(20)for some 0≤d≤r1.
Dividing by rq and rearranging the terms gives(21)
Because q≥n^{2}, there is exactly one fraction d/r with r<n that satisfies the above inequality. This fraction can be found efficiently using a continued fraction expansion of c/q. Hence, if gcd(d,r)=1, we get the value of r. In fact, there are φ(r) such coprime values of d, so we get(22)
So the success probability of Algorithm 1 is at least 4φ(r)/π^{2}r).
According to Theorem 5.3 in Ref. [16], we can conclude that(23)where m denotes the number of the factors of n.
So we can conclude that suppose n=pq, let x be an integer chosen uniformly at random from Z_{n}^{*} and r be the order of x modulo n. Then the probability of factoring integer n is greater than or equal to 3/4. And as the success probability of performing Shor’s order finding algorithm is 4φ(r)/π^{2}r). Therefore, the success probability of Shor’s algorithm for breaking RSA is(24)
However, the success probability of Algorithm 1 is at least 4φ(r)/π^{2}r). Hence the success probability of Algorithm 1 is higher than that of Shor’s algorithm for breaking RSA.
Comparison of Shor’s algorithm and Algorithm 1 for breaking RSA
2 Conclusion and Future Work
In this paper, a quantum algorithm for computing the order r of the fixedpoint C (the RSA ciphertext) of the given RSA publickey (e, n=pq) such that is presented. Since once r is obtained, the RSA plaintext M can be immediately computed by and hence, break the RSA completely. Compared to Shor’s original order finding algorithm, the order in the new algorithm does not need to be even and the algorithm is easy to be implemented on a quantum computer. Of course, for the algorithm to be practical, more research still needs to be done. One of our current research directions, along with this line, is to reduce the quantum bits used in the algorithm, so that it may be run on a smaller quantum computer that may be relatively easy to construct and build.
References
 Zhang H G, Han W B, Lai X J, et al. Survey on cyberspace security [J]. Science China Information Sciences, 2015, 58(11): 143. [NASA ADS] [Google Scholar]
 Wang Y L, Xu Q L. Principle and research progress of quantum computation and quantum cryptography [J]. Journal of Computer Research and Development, 2020, 57(10): 20152026. [Google Scholar]
 Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring [C] //Proceedings of 35th Annual Symposium on Foundations of Computer Science. Washington D C: IEEE Computer Society Press, 1994: 124134. [CrossRef] [Google Scholar]
 Smolin J A, Smith G, Vargo A. Oversimplifying quantum factoring [J]. Nature, 2013, 499(7457): 163165. [CrossRef] [PubMed] [Google Scholar]
 Peng X H, Liao Z Y, Xu N Y, et al. Quantum adiabatic algorithm for factorization and its experimental implementation [J]. Physical Review Letters, 2008, 101(22): 220405. [NASA ADS] [CrossRef] [PubMed] [Google Scholar]
 Xu N Y, Zhu J, Lu D W, et al.Quantum factorization of 143 on a dipolarcoupling nuclear magnetic resonance system [J]. Physical Review Letters, 2012, 108(13): 130501. [NASA ADS] [CrossRef] [PubMed] [Google Scholar]
 Wang C, Yao H N, et al. Progress in quantum computing cryptography attacks [J]. Chinese Journal of Computers, 2020, 43(9): 16911707(Ch). [Google Scholar]
 Geller M R, Zhou Z Y. Factoring 51 and 85 with 8 qubits [J]. Scientific Reports, 2013, 3(3023): 15. [NASA ADS] [Google Scholar]
 Wang Y H, Zhang H G, Wu W Q, et al. Quantum algorithms for breaking RSA based on phase estimation and equation solving [J]. Chinese Journal of Computers, 2017, 40(12): 26872699(Ch). [Google Scholar]
 Wang Y H, Zhang H G, Wang H Z. Quantum polynomialtime fixedpoint attack for RSA [J]. China Communications, 2018, 15(2): 2532. [NASA ADS] [CrossRef] [Google Scholar]
 Wang Y H, Yan S Y, Zhang H G. A new quantum algorithm for computing RSA ciphertext period [J]. Wuhan University Journal of Natural Sciences, 2017, 22(1): 6872. [CrossRef] [MathSciNet] [Google Scholar]
 Lawson T. Odd orders in Shor’s factoring algorithm [J]. Quantum Information Process, 2015, 14(3): 831838. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
 Dattani N S, Bryans N. Quantum factorization of 56153 with only 4 qubits. [EB/OL]. [20210510]. http://arxiv.org/pdf/1411.6758, 27, 2014. [Google Scholar]
 Peng W C, Wang B N, Hu F, et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters [J]. Science China: Physics, Mechanics & Astronomy, 2019, 62(6): 512(Ch). [Google Scholar]
 Yan S Y. Quantum Computational Number Theory [M]. Berlin: SpringerVerlag, 2015. [CrossRef] [MathSciNet] [Google Scholar]
 Nielson M A, Chuang I L. Quantum Computation and Quantum Information [M]. Cambridge: Cambridge University Press, 2000. [Google Scholar]
All Tables
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.