Open Access
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

© Wuhan University 2021

Licence Creative CommonsThis 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 real-world 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 Zn*, denoted by order(a, n), plays a significant role in the period of certain pseudo-random 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 Dipolar-Coupling Nuclear Magnetic Resonance System[6]. Wang et al[7] analyzed the RSA deciphering method based on D-Wave quantum annealing principle, which is a new attack algorithm for quantum computing.

There are three important research directions of quantum computing public-key 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,8-12].

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 fixed-point 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 public-key (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 fixed-point of RSA (e, n) and the smallest r satisfying (1) is the order of the fixed-point.

Theorem 1   Let C to be the fixed-point 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 polynomial-time quantum algorithm for computing the order r of the fixed-point C for RSA (e, n), such that

Algorithm 1   Quantum algorithm for attacking RSA based on Fourier transform and fixed-point

Input: C,e,n

Output: M

Step 1   Find a number q, a power of 2, say 2t, 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 nl is the largest positive integer satisfying

Step 6   Perform QFT on Reg1.where

That is,(6)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 352<q=211=2048<2×352.

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 105 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 6   Perform QFT on Reg1.

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 n-1), 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 polynomial-time .

Now we estimate the size of the probability Prob(c). In Step 7, the probability Prob(c) that the machine reaches the state ( 0≤cq-1) 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 φ.

Because , thus

Therefore, by Lemma 1, d/r must be a convergent of the continued fraction for c/q.

Suppose ps/qs 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

On the other hand,

Accordingly, |psr-qsd|=0, that is, ps/qs=d/r. Finally, because gcd(ps,qs)=1=gcd(d,r), thus qs=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 x2 (where the lower bound holds for |x|≤π/2), we find(18)

Thus, the probability of observing a good value is at least 4/(π2r).

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≤dr-1.

Dividing by rq and rearranging the terms gives(21)

Because qn2, 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 co-prime values of d, so we get(22)

So the success probability of Algorithm 1 is at least 4φ(r)/π2r).

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 Zn* 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)/π2r). 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)/π2r). Hence the success probability of Algorithm 1 is higher than that of Shor’s algorithm for breaking RSA.

Table 1

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 fixed-point C (the RSA ciphertext) of the given RSA public-key (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

  1. Zhang H G, Han W B, Lai X J, et al. Survey on cyberspace security [J]. Science China Information Sciences, 2015, 58(11): 1-43. [NASA ADS] [Google Scholar]
  2. 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): 2015-2026. [Google Scholar]
  3. 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: 124-134. [CrossRef] [Google Scholar]
  4. Smolin J A, Smith G, Vargo A. Oversimplifying quantum factoring [J]. Nature, 2013, 499(7457): 163-165. [CrossRef] [PubMed] [Google Scholar]
  5. 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]
  6. Xu N Y, Zhu J, Lu D W, et al.Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system [J]. Physical Review Letters, 2012, 108(13): 130501. [NASA ADS] [CrossRef] [PubMed] [Google Scholar]
  7. Wang C, Yao H N, et al. Progress in quantum computing cryptography attacks [J]. Chinese Journal of Computers, 2020, 43(9): 1691-1707(Ch). [Google Scholar]
  8. Geller M R, Zhou Z Y. Factoring 51 and 85 with 8 qubits [J]. Scientific Reports, 2013, 3(3023): 1-5. [NASA ADS] [Google Scholar]
  9. 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): 2687-2699(Ch). [Google Scholar]
  10. Wang Y H, Zhang H G, Wang H Z. Quantum polynomial-time fixed-point attack for RSA [J]. China Communications, 2018, 15(2): 25-32. [NASA ADS] [CrossRef] [Google Scholar]
  11. 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): 68-72. [CrossRef] [MathSciNet] [Google Scholar]
  12. Lawson T. Odd orders in Shor’s factoring algorithm [J]. Quantum Information Process, 2015, 14(3): 831-838. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
  13. Dattani N S, Bryans N. Quantum factorization of 56153 with only 4 qubits. [EB/OL]. [2021-05-10]. http://arxiv.org/pdf/1411.6758, 27, 2014. [Google Scholar]
  14. 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): 5-12(Ch). [Google Scholar]
  15. Yan S Y. Quantum Computational Number Theory [M]. Berlin: Springer-Verlag, 2015. [CrossRef] [MathSciNet] [Google Scholar]
  16. Nielson M A, Chuang I L. Quantum Computation and Quantum Information [M]. Cambridge: Cambridge University Press, 2000. [Google Scholar]

All Tables

Table 1

Comparison of Shor’s algorithm and Algorithm 1 for breaking RSA

Current usage metrics show cumulative count of Article Views (full-text 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 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.