A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer
www.sciopen.comInteger factorization, the core of the Rivest−Shamir−Adleman (RSA) attack, is an exciting but formidable challenge. As of this year, a group of researchers’ latest quantum supremacy chip remains unavailable for cryptanalysis. Quantum annealing (QA) has a unique quantum tunneling advantage, which can escape local extremum in the exponential solution space, finding the global optimal solution with a higher probability. Consequently, we consider it an effective method for attacking cryptography. According to Origin Quantum Computing, QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers. We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer, and attack RSA-2048 which is composed of a class of special integers. The experiment factored this class of integers of size 22048, N=p×q. As an example, the article gives the results of 10 RSA-2048 attacks in the appendix. This marks the first successful factorization of RSA-2048 by D-Wave quantum computer, regardless of employing mathematical or quantum techniques, despite dealing with special integers, exceeding 21061−1 of California State University. This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.
That’s a lot of California State University. If I’m guessing correctly as to what they’re trying to say it’s an impressive result, but it is not a successful attack on RSA-2048 and it’s made somewhat less plausible by the misleading title.
Well, I got around to reading it although I didn’t look too closely at the actual mathematics of quantum annealing. The sensationalist tone of the headline dominates much of the text as well, unfortunately. But they did factor a 2048 bit number, taken as representative of a class of such numbers which have two factors that differ from each other in only two of their bits. So a space of roughly 2^1000 numbers I guess.
California State University previously factored a 1061 bit number. It’s reference 27, which says “https://eprint.iacr.org/2012/44” where it should be “https://eprint.iacr.org/2012/444.pdf”.