Breaking RSA Using Shor's Algorithm

Given a generator g of an order r subgroup to $Z∗ N$, where the modulus $N$ is prime, and an element $x = g^d$, the finite field discrete logarithm problem is to compute $d = log_g \; x$. In what follows, we assume r to be prime. If r is composite, the discrete logarithm problem may be decomposed into problems in subgroups of orders dividing $r$, as shown by Pohlig and Hellman. For this reason, prime order subgroups are used in cryptographic applications. 

As $Z∗ N$ has order $N −1$, it must be that $r$ divides $N−1$, so $N = 2rk + 1$ for some integer $k ≥ 1$. The asymptotically best currently known classical algorithms for computing discrete logarithms in subgroups of this form are generic cycle-finding algorithms, such as Pollard's ρ- and λ-algorithms, that run in time $O(√r)$ and $O(√d)$, respectively, and the general number field sieve (GNFS), that runs in subexponential time in the bit length $N$ of $N$ . 

The idea of factoring via algebraic number fields was originally introduced by Pollard for integers on special forms. It was over time generalized, by amongst others Buhler et al., Lenstra et al. and Pollard, to factor general integers, and modified by amongst others Gordon and Schirokauer to compute discrete logarithms in finite fields. Much research effort has since been devoted to optimizing the GNFS in various respects. For an in-depth historical account of the development of the GNFS. For the best academic record. 

Let z be the number of bits of security provided by the modulus with respect to classical attacks using the GNFS. Let $n_d$ and $n_r$ be the lengths in bits of $d$ and $r$, respectively. It then suffices to pick $n_d, n_r ≥ 2z$ to achieve $z$ bits of classical security, as the generic cycle-finding algorithms are then not more efficient than the GNFS.

When instantiating schemes based on the intractability of the finite field discrete logarithm problem, one may hence choose between using a Schnorr group, for which $n_d = nr = 2z$, or a safe-prime group, for which $n_r = N − 1$. In the latter case, one may in turn choose between using a short exponent, such that $n_d = 2z$, or a full length exponent, such that $n_d = n_r = N − 1$. All three parameterization options provide $z$ bits of classical security.

What finite field groups are used in practice?

In practice, Schnorr groups or safe-prime groups with short exponents are often preferred over safe- prime groups with full length exponents, as the comparatively short exponents yield considerable performance improvements. 

The discrete logarithm problem in Schnorr groups is of standard form, unlike the short discrete logarithm problem in safe-prime groups, and Schnorr groups are faster to generate than safe-prime groups. A downside to using Schnorr groups is that group elements received from untrusted parties must be tested for membership of the order $r$ subgroup. This typically involves exponentiating the element to the power of $r$, which is computationally expensive. Safe-prime groups are more flexible than Schnorr groups, in that the exponent length may be adaptively selected depending on the performance requirements. In more recent years, the use of safe-prime groups would appear to have become increasingly prevalent. Some cryptographic schemes, such as the Diffie-Hellman key agreement protocol, are agnostic to the choice of group, whereas other schemes, such as DSA, use Schnorr groups for efficiency reasons. 

The National Institute of Standards and Technology (NIST) in the United States standardizes the use of cryptography in unclassified applications within the federal government. Up until April of 2018, NIST recommended the use of randomly selected Schnorr groups with moduli of length 2048 bits for Diffie-Hellman key agreement. NIST changed this recommendation in the 3rd revision of SP800-56A, and are now advocating using a fixed set of safe-prime groups with moduli of length up to 8192 bits, with short or full length exponents. These groups were originally developed for TLS and IKE where, again, they are used either with short of full length exponents.

Complexity estimates

To estimates the resource and time requirements for computing discrete logarithms in finite fields for various modulus lengths $N$, and for the aforementioned parameterization options, we need to decide on what model to use for estimating $z$ as a function of $N$. Various models have been proposed over the years. For simplicity, we use the same model that NIST uses in SP 800-56A. Note that NIST rounds z to the closest multiple of eight bits. 

To compute short logarithms in safe-prime groups, the best option is to use Ekerå -Håstad's algorithm that is specialized for this purpose. To compute general discrete logarithms in safe-prime or Schnorr groups, one option is to use Ekerå 's algorithm. A single correct run of these quantum algorithms suffices for the logarithm to be recovered with ≥ 99% success probability in the classical post-processing. These algorithms do not require the order of the group to be known. See Table 4 and Figure 1 for complexity estimates. 

If the group order is known, a better option for computing general discrete logarithms in safe- prime groups and Schnorr groups when not making tradeoffs is to use Shor's original algorithm, modified to work in the order $r$ subgroup rather than in the whole multiplicative group $Z^∗_N$, and to start with a uniform superposition of all exponent values, as opposed to superpositions of $r$ values. Note that the latter modification is necessary to enable the use of the semi-classical Fourier transform, qubit recycling and the windowing technique.

When using this modified version of Shor's algorithm to compute discrete logarithms, the heuristic analysis shows that a single correct run suffices to compute the logarithm with ≥ 99% success probability, assuming that each of the two exponent registers is padded with 5 bits, and that a small search is performed in the classical post-processing. This implies that Shor's algo- rithm outperforms Ekerå 's algorithm, as Shor's algorithm performs only approximately $2n_r$ group operations per run, compared to $3n_r$ operations in Ekerå 's algorithm, see Table 5 for complexity estimates. This is because Ekerå 's algorithm does not require r to be known. In fact, it computes both $d$ and $r$.

Table 4: Computing discrete logarithms using Ekerå -Håstad's  and Ekerå 's algorithms. This table was produced by the script in the ancillary file "estimate costs.py".

Table 5: Computing discrete logarithms using Shor's algorithm modified. This table was produced by the script in the ancillary file "estimate costs.py".

Note that for safe-prime groups, $r = (N − 1)/2$, so when $N$ is known to the adversary then so is $r$. For Schnorr groups, it may be that $r$ is unknown to the adversary, especially if the group is randomly selected. It may be hard to compute $r$ classically, as it amounts to finding a $n_r = 2z$ bit prime factor of $(N − 1)/2$.