Did Schnorr destroy RSA? Show me the factors.
A recent paper, “Fast Factoring Integers by SVP Algorithms” by Claus P. Schnorr, claims significant improvements in factoring that “destroys the RSA cryptosystem”. If true, it would be practical to demonstrate on well known RSA factoring challenges.
Update: Schnorr withdrew this paper on June 5th, 2021.
Update v2: Schorr’s paper is back online as of July 8th, 2021 with a new eprint submission.
No such demonstration has been made. Without this, assessing the correctness of the paper will have to wait for reviewers to wade through the details and give their feedback.
Big, If True
This paper drew the attention of many cryptographers because Schnorr, notable for Schnorr signatures, is an accomplished cryptographer who has worked on factoring problems for at least a decade. There have been significant improvements in factoring over the last 20 years, so a big new result from a known researcher is at least plausible.
Initial misspellings and version inconsistencies led to speculation that the submission was a prank. However, the provenance of the paper has been confirmed: it is indeed Schnorr.
Claimed Factoring Runtime
Schnorr’s paper claims to factor 400-bit moduli in 4.2·10⁹ operations and 800-bit moduli in 8.4·10¹⁰ operations. The 800-bit claims would be 36 bits of work.
That would be demonstrable on commodity hardware.
For comparison, the two most recent factoring records using CADO-NFS are:
- 795-bit RSA using 900 physical CPU core years set in 2019
- 829-bit RSA using 2700 physical CPU core years set in 2020
The Crypto 2020 paper “Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment” covers some of these results.
Show Me the Factors
According to the claims in Schnorr’s paper, it should be practical to set significant new factoring records. There is a convenient 862-bit RSA challenge that has not been factored yet. Posting its factors, as done for the CADO-NFS team’s records, would lend credence to Schnorr’s paper and encourage more review of the methodology.
Followup
Several critiques of this post pointed out that asking for someone to break a record or even implement their code is a high bar for essentially a theory paper. I agree with that in general and wouldn’t, for instance, expect Shamir to build a TWIRL device to prove it works. This Schnorr paper is different because it makes a concrete runtime claim which is orders of magnitude faster than a record set just last year, which took 2700 years of CPU time.
This paper has been circulating for at least 2 years and so far, the nearest implementation is this “Factoring Integers via Lattice Algorithms” code.
Several people smarter than me are trying to reproduce Schnorr’s results and check his work, and have already raised issues which I’ll append here.
Epilogue
Schnorr ultimately withdrew this paper in June 2021.
Epilogue Epilogue
Schnorr’s paper is back online in July 2021 with a new eprint link: https://eprint.iacr.org/2021/933
