Breaking RSA Using Shor's Algorithm

Cryptographic implications of our construction

Implications for RSA

Today, the arguably most commonly used modulus size for RSA is $n = 2048$ bits. Larger moduli are however in widespread use and smaller moduli have been used historically.

The best published academic record is the factorization of an 829 bit RSA modulus in 2020. For the earlier record. In Table 3 and Figure 1, we provide estimates for the resource and time requirements for attacking RSA for various cryptographically relevant modulus lengths $n$ . The estimates are for factoring RSA integers with Ekerå -Håstad's algorithm that computes a short discrete logarithm. As single correct run of this quantum algorithm suffices for the RSA integer to be factored with at least 99% success probability in the classical post-processing.

		Parameters							Volume (megaqubitdays)		Qubits (megaqubits)	Runtime (hours)
n	n_e	d₁	d₂	δ_off	c_mul	c_exp	c_sep	Retry Risk	per run	expected	per run	per run
1024	3(n/2 - 1) - 40	15	27	5	5	5	1024	6%	0.5	0.5	9.7	1.3
2048		15	27	4	5	5	1024	31%	4.1	5.9	20	5.1
3072		17	29	6	4	5	1024	9%	19	21	38	12
4096		17	31	9	4	5	1024	5%	48	51	55	22
8192		19	33	4	4	5	1024	5%	480	510	140	86
12288		19	33	3	4	5	1024	12%	1700	1900	200	200
16384		19	33	4	4	5	1024	24%	3900	5100	270	350

Table 3: Factoring an $n$ bit RSA integer by computing a short discrete logarithm. This table was produced by the script in the ancillary file "estimate costs.py”.