© Wuhan University 2021

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 Z_n^*, 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, $\text{gcd(}{a}^{r/2}\pm 1,n)=\{p,q\},$ 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):$\begin{array}{l}\overline{C,C{}^e,C{}^{e^2},C{}^{e^3},\cdot \cdot \cdot ,C{}^{e^{r-1}}},\\ \overline{C^{e^r},C{}^{e^{r+1}},C{}^{e^{r+2}},\cdot \cdot \cdot ,C{}^{e^{2r-1}}},\\ C^{e^{2r}},C{}^{e^{2r+1}},\cdot \cdot \cdot \end{array}$where the overline symbol indicates the periodic elements. Once the first occurrence of $C{}^{e^{r-1}}{\mathrm{mod}}_{}n=C$ is found, the plaintext M is just the element $C{}^{e^{r-1}}{\mathrm{mod}}_{}n$ immediately preceding $C{}^{e^r}{\mathrm{mod}}_{}n$.

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,$\left\{e,n,C\equiv M^e\left(\text{mod\hspace{0.17em}}n\right)\right\}\stackrel{\text{find}}{\to }\left\{M\equiv C^d\left(\text{mod\hspace{0.17em}}n\right)\right\}$

Definition 2   Let 0≤x<n. If$x^{e^x}\equiv x\left(\text{mod\hspace{0.17em}}n\right),r\in Z^{+},$(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: $C^{e^r}\equiv C\left(\text{mod\hspace{0.17em}}n\right),r\in Z^{+}$(2)then$C^{e^{r-1}}\equiv M\left(\text{mod\hspace{0.17em}}n\right),r\in Z^{+}$(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 $C^{e^r}\equiv C(\text{mod\hspace{0.17em}}n).$

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 2^t, such that $n^2\le q=2^t<2n^2.$

Step 2   Initialize the two quantum registers, Reg1 and Reg2, $|{\Psi }_0\rangle =|0\rangle |C\rangle$, where Reg1 requires $2\lceil \log n\rceil$ qubits, Reg2 requires $\lceil \log n\rceil$ qubits (whose number depends on the space requirement).

Step 3   Perform a Hadamard transform on Reg1, we get$H:|{\Psi }_0\rangle \to |{\Psi }_1\rangle =\frac{1}{\sqrt{q}}{\displaystyle \sum _{x=0}^{q-1}|x\rangle }|C\rangle$(4)

Step 4   Perform the unitary transform $U_C^x$ on Reg2, we get$\begin{array}{l}{U}_C^x:|{\Psi }_1\rangle \to |{\Psi }_2\rangle \\ =\frac{1}{\sqrt{q}}{\displaystyle \sum _{x=0}^{q-1}|x\rangle }{U}_C^x|C\rangle \\ =\frac{1}{\sqrt{q}}{\displaystyle \sum _{x=0}^{q-1}|x\rangle }|C^{e^x}({\mathrm{mod}}_{}n)\rangle \end{array}$where $U_C|y\rangle =|y^e{\text{mod}}_{}n\rangle$, thus, $U_C^x|y\rangle \text{\hspace{0.17em}}=|y^{e^x}\text{mod\hspace{0.17em}}n\rangle$.

Step 5   Measure Reg2. Suppose we observe $m\equiv C^{e^l}\text{\hspace{0.17em}mod\hspace{0.17em}}n$, and at the same time, the state in Reg1 is collapsed into a superposition over all x such that $C^{e^x}\equiv m\text{\hspace{0.17em}mod\hspace{0.17em}}n$. That leaves Reg1 in state$|{\Psi }_3\rangle =\frac{1}{\sqrt{n_t+1}}(|l\rangle +|l+r\rangle +\cdot \cdot \cdot +|l+n_{l}r\rangle )$(5)where n_l is the largest positive integer satisfying $l+n_{l}r\le 2^t-1.$

Step 6   Perform QFT on Reg1.$\begin{array}{l}\text{QFT(\hspace{0.17em}}|{\Psi }_3\rangle )\\ =\text{QFT}\left(\frac{1}{\sqrt{n_l+1}}(|l\rangle +|l+r\rangle +\cdot \cdot \cdot +|l+n_{l}r\rangle )\right)\\ =\text{QFT}\left(\frac{1}{\sqrt{n_l+1}}{\displaystyle \sum _{j=0}^{n{}_l}|l+jr\rangle }\right)\\ =\frac{1}{\sqrt{n_l+1}}\text{QFT}\left({\displaystyle \sum _{j=0}^{n{}_l}|l+jr\rangle }\right)\\ =\frac{1}{\sqrt{n_l+1}}\frac{1}{\sqrt{q}}{\displaystyle \sum _{c=0}^{q-1}\left({\displaystyle \sum _{j=0}^{n_l}{e}^{\frac{2\text{π}i\left(l+jr\right)c}{q}}}\right)|c\rangle }\\ =\frac{1}{\sqrt{q(n_l+1)}}{\displaystyle \sum _{c=0}^{q-1}{w}_q^{lc}\left({\displaystyle \sum _{j=0}^{n_l}{w}_q^{jrc}}\right)|c\rangle },\end{array}$where $w_q=e^{\frac{2\text{π}i}{q}}.$

That is,$\text{QFT(\hspace{0.17em}}|{\Psi }_3\rangle )={\displaystyle \sum _{c}f(c)}|c\rangle$(6)where $f(c)=\frac{1}{\sqrt{q(n_l+1)}}{w}_q^{lc}{\displaystyle \sum _{j=0}^{n_l}{w}_q^{jrc}}.$

Step 7   Observe Reg1. This yields the state $|c\rangle$ with probability$\begin{array}{l}\text{Prob}(c)=|f(c){|}^2\\ ={\left|\frac{1}{\sqrt{q(n_l+1)}}{w}_q^{lc}{\displaystyle \sum _{j=0}^{n_l}{w}_q^{jrc}}\right|}^2\\ ={\left|\frac{1}{\sqrt{q(n_l+1)}}{\displaystyle \sum _{j=0}^{n_l}{w}_q^{jrc}}\right|}^2\\ ={\left|\frac{1}{\sqrt{q(n_l+1)}}{\displaystyle \sum _{j=0}^{n_l}{w}_q^{j(rc\mathrm{mod}q)}}\right|}^2\end{array}$

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 $M\equiv C^{e^{r-1}}(\text{mod\hspace{0.17em}}n),$ 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²<q=2¹¹=2048<2×35².

Step 2   Initialize the two quantum registers $|{\Psi }_0\rangle =|0\rangle |C\rangle$.

Step 3   Perform a Hadamard transform on Reg1, we get$H:|{\Psi }_0\rangle \to |{\Psi }_1\rangle =\frac{1}{\sqrt{2048}}{\displaystyle \sum _{x=0}^{2047}|x\rangle }|10\rangle$(7)

Step 4   Perform the unitary transform $U_{10}^x$ on Reg2, we get$\begin{array}{c}{U}_{10}^x:|{\Psi }_1\rangle \to |{\Psi }_2\rangle \\ =\frac{1}{\sqrt{q}}{\displaystyle \sum _{x=0}^{q-1}|x\rangle }{U}_{10}^x|C\rangle \\ =\frac{1}{\sqrt{2048}}{\displaystyle \sum _{x=0}^{2047}|x\rangle }|{10}^{5^x}(\mathrm{mod}35)\rangle \end{array}$where $U_{10}|C\rangle =|{10}^5\text{\hspace{0.17em}mod\hspace{0.17em}}35\rangle$, thus, $U_{10}^x|10\rangle =$$|{10}^{5^x}\text{\hspace{0.17em}mod\hspace{0.17em}}35\rangle$.

The computation of the detailed exponentiations 10⁵ mod 35 is as follows$\mathrm{Re}\text{g}2=[10,5,10,5,10,5,10,5,\cdots ,10,5]$(8)

Step 5   Measure Reg2. Suppose we observe ${10}^{5^l}\equiv 5\text{\hspace{0.17em}mod\hspace{0.17em}}35$, this means that the state in Reg1 is collapsed into a superposition over all x such that ${10}^{5^x}\equiv 5\text{\hspace{0.17em}mod\hspace{0.17em}}35$. That leaves Reg1 in state$|{\Psi }_3\rangle =\frac{1}{\sqrt{1024}}(|1\rangle +|3\rangle +|5\rangle +\cdots +|2045\rangle +|2047\rangle )$(9)

Step 6   Perform QFT on Reg1.$\begin{array}{l}\text{QFT}(|{\Psi }_3\rangle )\\ =\text{QFT}\left(\frac{1}{\sqrt{1024}}(|1\rangle +|3\rangle +\cdots +|2045\rangle +|2047\rangle )\right)\\ =\frac{1}{\sqrt{1024}}\text{QFT}(|1\rangle +|3\rangle +\cdots +|2045\rangle +|2047\rangle )\\ =\frac{1}{\sqrt{1024}}\frac{1}{\sqrt{2048}}({\displaystyle \sum _{c=0}^{2047}{e}^{\frac{2\text{π}ic}{2048}}}|c\rangle +{\displaystyle \sum _{c=0}^{2047}{e}^{\frac{2\text{π }i3c}{2048}}}|c\rangle +\cdots \\ +({\displaystyle \sum _{c=0}^{2047}{e}^{\frac{2\text{π}i2045c}{2048}}}|c\rangle +{\displaystyle \sum _{c=0}^{2047}{e}^{\frac{2\text{π }i2047c}{2048}}}|c\rangle )\\ =\frac{1}{2}|c\rangle -\frac{1}{2}|1024\rangle .\end{array}$

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$\frac{c}{q}=\frac{1024}{2048}=\frac{1}{2}$(10)r=2 can be deduced.

Step 8   Compute $M\equiv {10}^{5^{2-1}}(\mathrm{mod}35)\equiv 5$, 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 $C^{e^x}\text{\hspace{0.17em}mod\hspace{0.17em}}n$ (which is a number between 1 and n-1), in Step 4, which takes time proportion to ${\rm O}({(\text{log\hspace{0.17em}}n)}^{2+\epsilon })$. The QFT in Step 6 requires O((log n)²) gates^[16]. The classical continued fraction algorithm in Step 7 needs ${\rm O}({(\text{log\hspace{0.17em}}n)}^{2+\epsilon })$ (classical) gates. Thus the quantum circuit of Algorithm 1 requires only O((log n)²) elementary quantum gates. That is, Algorithm 1 breaks RSA in quantum polynomial-time ${\rm O}({(\text{log\hspace{0.17em}}n)}^{2+\epsilon })$.

Now we estimate the size of the probability Prob(c). In Step 7, the probability Prob(c) that the machine reaches the state $|c\rangle$( 0≤c≤q-1) is$\text{Prob}(c)=\frac{1}{q(n_l+1)}{\left|{\displaystyle \sum _{j=0}^{n_l}{w}_q^{j(rc\mathrm{mod}q)}}\right|}^2$(11)

Definition 3   If the state $|c\rangle$ 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$\left|\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}$(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$\left|\frac{s}{r}-\phi \right|\le \frac{1}{2r^2}$

Then s/r is a convergent of the continued fraction for φ.

Because $q\ge n^2$, $n\ge \phi (n)\ge r,$ thus$\left|\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}\le \frac{1}{2n^2}\le \frac{1}{2r^2}$

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 $\frac{p_s}{q_s}=\frac{d}{r}$.

Because d/r is a convergent of the continued fraction for c/q and r<n, thus$\left|\frac{c}{q}-\frac{p_s}{q_s}\right|\le \left|\frac{c}{q}-\frac{d}{r}\right|$and because$\left|\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}$therefore$\left|\frac{p_s}{q_s}-\frac{d}{r}\right|\le \left|\frac{p_s}{q_s}-\frac{c}{q}+\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}+\frac{1}{2q}=\frac{1}{q}$

On the other hand,$\left|\frac{p_s}{q_s}-\frac{d}{r}\right|=\left|\frac{p_{s}r-q_{s}d}{q_{s}r}\right|>\frac{\left|p_{s}r-q_{s}d\right|}{n^2}\ge \frac{\left|p_{s}r-q_{s}d\right|}{q}$

Accordingly, |p_sr-q_sd|=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 $\left|rc\text{\hspace{0.17em}mod\hspace{0.17em}}q\right|\le \frac{r}{2}.$

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 that$\left|\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}$that is,$\left|rc-dq\right|\le \frac{r}{2}<\frac{q}{2}$(13)

We denote$\frac{rc}{q}+\frac{1}{2}=\lceil \frac{rc}{q}+\frac{1}{2}\rceil +t,0\le t<1$(14)thus, we can denote rc${\mathrm{mod}}_{}q=\left(t-\frac{1}{2}\right)q.$

Of course, $-\frac{q}{2}\le r{c}_{}{\mathrm{mod}}_{}q<\frac{q}{2}$(15)Using (13), (14) and (15), we can get$r{c}_{}{\mathrm{mod}}_{}q=rc-dq$(16)So$\left|r{c}_{}{\mathrm{mod}}_{}q\right|\le \frac{r}{2}$(17)Since ${\left|e^{ix}-1\right|}^2={\left|\cos x+i\sin x-1\right|}^2{=4\text{sin}}^2\frac{x}{2}$, so the probability Prob (c) is$\begin{array}{c}\text{Prob}(c)=\frac{1}{q(n_l+1)}{\left|{\displaystyle \sum _{j=0}^{n_l}{w}_q^{j(rc\mathrm{mod}q)}}\right|}^2\\ =\frac{1}{q(n_l+1)}\frac{{\sin }^2\frac{\text{π}(rc-dq)(n_l+1)}{q}}{{\sin }^2\frac{\text{π}(rc-dq)}{q}}\end{array}$

Using the inequalities $4x^2/{\pi }^2\le {\text{sin}}^{2}x$≤x² (where the lower bound holds for |x|≤π/2), we find$\text{Prob(}c)\ge \frac{4}{{\pi }^{2}r}$(18)

Thus, the probability of observing a good value $|c\rangle$ is at least 4/(π²r).

Then we wish to extract the information of the value of r, given a value of c satisfying$\left|r{c}_{}{\mathrm{mod}}_{}q\right|\le \frac{r}{2}$(19)

To do this we note that (19) is equivalent to$\left|rc-dq\right|\le \frac{r}{2}$(20)for some 0≤d≤r-1.

Dividing by rq and rearranging the terms gives$\left|\frac{c}{q}-\frac{d}{r}\right|\le \frac{1}{2q}$(21)

Because q≥n², 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$\text{Prob}{\left(d\text{ is prime to }r\right)}_c\ge \frac{4\phi \left(r\right)}{{\pi }^{2}r}$(22)

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

According to Theorem 5.3 in Ref. [16], we can conclude that$\text{Prob}\left(r\text{ is even and }{x}^{r/2}\ne -1(\mathrm{mod}n)\right)\ge 1-\frac{1}{2^m}$(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)/π²r). Therefore, the success probability of Shor’s algorithm for breaking RSA is$3\phi (r)/({\pi }^{2}r)\le \text{Prob(Shor}’\text{s)}<4\phi (r)/({\pi }^{2}r)$(24)

However, the success probability of Algorithm 1 is at least 4φ(r)/π²r). Hence the success probability of Algorithm 1 is higher than that of Shor’s algorithm 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 $C^{e^r}\equiv C\left(\text{mod\hspace{0.17em}}n\right)$ is presented. Since once r is obtained, the RSA plaintext M can be immediately computed by $M\equiv C^{e^{r-1}}\left(\text{mod\hspace{0.17em}}n\right),$ 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

All Tables