Did Schnorr destroy RSA? Show me the factors.

Claus buries the lede.

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.

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.

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.

Epilogue

Schnorr ultimately withdrew this paper in June 2021.

Not so destroyed.

Epilogue Epilogue

Schnorr’s paper is back online in July 2021 with a new eprint link: https://eprint.iacr.org/2021/933

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Steve Weis

Steve Weis

Working in security and cryptography. Opinions are entirely my own.