Les Bell
Blog entry by Les Bell
A really interesting, and somewhat tongue-in-cheek, paper gives us a bit of welcome relief from the threat of the imminent collapse of (online) civilisation thanks to the complete breakdown of public-key cryptography.
The threat arises from the much-vaunted ability of quantum computers to break public-key crypto based on the widely-used RSA algorithm. RSA is used in many popular protocols and applications, such as Transport Layer Security, S/MIME and PGP email, and end-to-end encrypted messaging applications. It plays two important roles: a) the signing of messages in these protocols - including the signing of SSL/TLS certificates - and b) the solution of the key echange problem, by encapsulating a session key for exchange over untrusted networks (although in the latter case, especially for TLS, it has been supplanted by ECDHE, or Elliptic Curve Diffie-Hellman Key Agreement.
You see, the RSA algorithm is based upon the difficulty of factoring very large composite numbers - numbers which are the product of two large numbers which are probably prime (I say probably prime because proving the two randomly-selected large numbers actually are prime is itself a computationally challenging process, so we try a number of times to prove each number is not, and if it passes these tests, we accept it probably is). To give you an idea of the sizes involved, the RSA key for this web site uses a 4096-bit bit modulus - that's 1,234 decimal digits in length.
Hence the algorithm can be broken by an adversary who can factor very large numbers - something that is impractical using classical computers. However, in 1994 physicist Peter Shor developed an algorithm which can perform factorization of large composites in polynomial time using a combination of classical and quantum computation (Shor, 1997).
This has led to increasing concern that the cryptographic underpinnings of our 'secure enough' Internet could be completely broken, provided two problems are solved:
- Building a quantum computer with enough qubits (and not subject to noise, etc.), and
- Generalizing Shor's algorithm - the original algorithm requires the construction of a quantum circuit for each number to be factored.
Obviously, physicists, mathematicians and cryptanalysts all around the world have been beavering away on this problem over the years, some of them announcing their results in a series of 'record-breaking' factorizations of increasingly large composites. (I say 'some of them', because anyone who makes a really serious breakthrough, especially solving both those problems, is going to keep it very quiet indeed so that they can make best use of it).
I cover some of these results in our CISSP Fast Track Review course.
But now, a paper with the lovely title, Replication of Quantum Factorisation Records with an
8-bit Home Computer, an Abacus, and a Dog (Gutmann and Neuhaus, 2025) shows that a lot of the vaunted progress in quantum factorization is, in fact, smoke and mirrors. In many cases, the answers to the factorization are known in advance. In others, the two factors are carefully chosen to make factorization easy in what the authors more correctly describe as a physics experiment.
In one example, the factors of a 2048-bit RSA modulus are carefully selected to differ by only a few bits from the square root of that modulus - so that a simple integer square root calculation essentially performs the factorization. In practice, such a value would never be encountered in the real world - the RSA key generation algorithm generally requires that the two factors are much more different from each other.
Other cases rely on using prior knowledge of the factors to reduce the problem to a form that can be solved using the so-called 'compiled' form of Shor's algorithm which simply confirms that those are, in fact, the factors - something that can also be done by a simple multiplication. In other cases, preprocessing can be used to simplify the factorization or even transform it into a completely different problem which can then be solved using far fewer qubits. For example, a carefully-chosen 20,000 bit (6,021 decimal digit) number can be 'factorized' using only 2 qubits in the compiled form!
There are lots of sleight-of-hand tricks for creating these more-apparent-than-real quantum factorization records: Gutmann and Neuhaus describe the 'Smolin-Smith-Vargo algorithm' and the 'Callas Normal Form for Sleight-of-Hand Quantum Factorization', to give names to just two.
But in section 4 of their paper, they go on to perform quantum factorizations on a Commodore VIC-20 computer, one of the earliest hobby/home computers of the late 1970's, based on a 6502 processor with 1 MHz clock speed and less than only 4 KB of usable RAM. As they point out, since the 6502 is a transistor-based integrated circuit, and transistors work using quantum effects, it is just as much a "quantum computer" as the D-Wave machine (which operates by quantum annealing) used to factorize an RSA-2048 number in a widely-cited paper. In fact, the D-Wave paper feature ten different RSA-2048 moduli, and an emulated 6502 factorized them all - using an algorithm developed in 1945 for the EDVAC computer!
In section 5 of the paper, the authors performed several of the record-breaking factorizations using an abacus. In section 6, they replicated an earlier demonstration in which Gutmann trained a dog to 'perform factorizations' - the dog, Scribble, was trained to bark three times, and then re-trained to bark 5 times. One can only imagine what they might have achieved - perhaps even factorization of the RSA-2048 numbers - had Mr. Ed been available!
It's not all fun and games, however - section 7 turns serious by suggesting a numer of evaluation criteria for future claims of record-breaking quantum factorizations.
So, can we relax and abandon all efforts to move to post-quantum crypto or quantum-resistant cryptographic techniques? The prudent approach would suggest not. After alll, we know what we know - but we don't know what possible adversaries might know. As Bletchley Park demonstrated with the Ultra intelligence produced by their breaking of the Enigma cipher, you never want to leak your capabilities to an adversary, causing them to change their techniques (the Enigma cracking was not publicly disclosed until the 1970's). And a well-resourced adversary could also store and save intercepted communications traffic in preparation for an attack becoming feasible, then use it to retrospectively break that traffic.
So, don't panic - the sky is not falling. But plan for the eventual switch to quantum-resistant crypto, such as the standards (e.g. CRYSTALS-Dilithium) adopted by NIST. You never know . . .
References and Further Reading
Gutmann, Peter, and Stephan Neuhaus, Replication of Quantum Factorisation Records with an8-bit Home Computer, an Abacus, and a Dog, IACR pre-print, March - September 2025. Available online at https://eprint.iacr.org/2025/1237.
Shor, Peter W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, 26 (5), 1 October 1997. Available online at http://epubs.siam.org/doi/abs/10.1137/S0097539795293172.
Upcoming Courses
There is still just time to register for one of the two remaining CISSP courses this year:
Sydney
Online Virtual
About this Blog
I produce this blog while updating the course notes for various courses. Links within a story mostly lead to further details in those course notes, and will only be accessible if you are enrolled in the corresponding course. This is a shallow ploy to encourage ongoing study by our students. However, each item ends with a link to the original source.
These blog posts are collected at https://www.lesbell.com.au/blog/index.php?user=3. If you would prefer an RSS feed for your reader, the feed can be found at https://www.lesbell.com.au/rss/file.php/1/dd977d83ae51998b0b79799c822ac0a1/blog/user/3/rss.xml.
Copyright to linked articles is held by their individual authors or publishers. Our commentary is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License and is labeled TLP:CLEAR.