A Quantum of Lies: No, researchers did not break RSA 2048 encryption with Quantum Computers. Here is how they cheated.

Beim Thema Quanten-Computer ist es nicht so einfach Hype von Fakten zu trennen und es gibt noch eine dritte Kategorie, die man auf dem Radar haben muss:

Wissenschaftliche Publikationen, die große Durchbrüche bei Quanten-Computern behaupten, aber in Wirklichkeit keine sind, wie dieses Paper von 5 chinesischen Wissenschaftlern, das von keiner renommierten Konferenz peer-reviewed wurde.

Der Titel des Papers suggeriert, dass mit Quanten-Comptuern von D-Wave das erste Mal erfolgreich RSA-2048 Keys geknackt worden seien. Das wäre tatsächlich ein großer Durchbruch und ein Albtraum für die gesamte IT-Industrie. Mega-Schlagzeile. Quanten Computer brechen RSA-Verschlüsselung.

Es gibt nur einen kleinen Haken. Die Wissenschaftler haben gleich auf mehreren Ebenen geschummelt und eigentlich nichts erreicht.

Die RSA-Verschlüsselung basiert auf der Schwierigkeit das Produkt zweier großer Primzahlen zu faktorisieren.

N = p * q

Wobei p und q zwei unterschiedliche Primzahlen sein müssen und auch noch weitere Eigenschaften erfüllen müssen, damit RSA sicher ist.

Und genau hier schummelt das Paper heftig. Die Primzahlen wurden so gewählt, dass das Problem der Faktorisierung trivial wird.

Anstatt zwei unterschiedliche Primzahlen zu verwenden, verwenden sie für p und q dieselbe Primzahl, haben aber lediglich Bit 1 und Bit 2 geflippt.

Dadurch wird die Faktorisierung nahezu trivial. Es ergeben sich im Prinzip nur 4 mögliche Bitfolgen für die letzten 4 Bits von p und q: 0111 * 0001, 1111 * 1001, 0011 * 0101 und 1011 * 1101.

Der zweite Punkt, wo die Wissenschaftler schummeln, ist, dass sie für die Faktorisierung einen hybriden Ansatz verwenden, d.h. sowohl einen klassischen als auch einen Quanten-Computer. Und jetzt haltet euch fest, für die Faktorisierung verwenden sie hauptsächlich den klassischen Computer. Den relevanten Teil des Problems muss ein klassischer Computer lösen.

Der Quanten-Computer berechnet lediglich die zwei geflippten Bits, was eine triviale Aufgabe ist, die eigentliche Faktorisierung muss ein klassischer Algorithmus erledigen (siehe Equation 16 und 18 im Paper), worauf im Paper aber nicht klar hingewiesen wird.

Und der dritte Punkt, wo das Paper ein bisschen schummelt, ist in der Konvertierung der objective Function der Multiplikation in ein QUBO-Problem (Quadratic Unconstrained Binary Optimization). Hier werden einige Vereinfachungen durchgeführt, um das Problem überhaupt mit Quantum-Annealing berechnen zu können.

Im Prinzip ist mit dem Quanten-Computer nichts gewonnen, sondern es wurde ein trivialer Fall konstruiert, um einen Quanten-Computer zu verwenden, ohne einen wirklichen Nutzen zu generieren, um behaupten zu können, sie haben einen Spezial-Fall mit schwachen Primzahlen mit einem Quanten-Computer geknackt, wobei die relevante Berechnung klassisch stattfinden muss.

Insgesamt ist das eine ziemlich unseriöse Vorgehensweise.

Interessant an dem Paper ist hingegen, dass man mit Quantum-Annealing auch Faktorisierungen berechnen könnte, aber die Frage ist, ob das mit den Vereinfachungen und mit den bekannten Problemen von Quanten-Computern (Noise, Skalierung, Annealing liefert keine exakten Ergebnisse sondern ist ein Optimierungsalgorithmus) in der Praxis überhaupt bei größeren Zahlen, die mehr als ein paar Bits lang sind, funktionieren würde. Hier könnte es in der Praxis schnell zu Limitierungen kommen.

Was sagt ihr dazu? Denkt ihr, dass man mit Quantum-Annealing tatsächlich größere Zahlen faktorisieren kann oder ist das mehr Hype als Realität?

Wang C, Yu J, Pei Z, et al. A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer.

https://www.sciopen.com/article/10.26599/TST.2024.9010028

Kaspersky: Quantum of Lies

https://www.kaspersky.com/blog/quantum-cryptography-2024-hype/52884/

Sabine Hossenfelder: Chinese claim "First Successful Factorization of RSA-2028 Integer".

Video credit: Sabine Hossenfelder

English

When it comes to quantum computing, it's not so easy to separate hype from fact and there's a third category to keep on the radar:

Scientific publications that claim major breakthroughs in quantum computing but in reality are not, like this paper by 5 Chinese scientists that has not been peer-reviewed by any reputable conference.

The title of the paper suggests that by using quantum computers from D-Wave they have successfully cracked RSA-2048 keys for the first time. This would indeed be a major breakthrough and a nightmare for the entire IT industry. Mega headline. Quantum computers break RSA encryption.

There's just one small catch. The scientists cheated on several levels and didn't actually achieve anything.

RSA encryption is based on the difficulty of factorizing the product of two large prime numbers.

N = p * q

Whereby p and q must be two different prime numbers and must also fulfill other properties for RSA to be secure.

And this is exactly where the paper cheats badly. The primes were chosen in such a way that the problem of factorization becomes trivial.

Instead of using two different primes, they used the same prime for p and q, but only flipped bit 1 and bit 2.

This makes factorization almost trivial. In principle, there are only 4 possible bit sequences for the last 4 bits of p and q: 0111 * 0001, 1111 * 1001, 0011 * 0101 and 1011 * 1101.

The second point where the scientists cheat is that they use a hybrid approach for the factorization, i.e. both a classical and a quantum computer. And now brace yourself, for the factorization they mainly use a classical computer. The relevant part of the problem has to be solved by a classical computer.

The quantum computer only calculates the two flipped bits, which is a trivial task, the actual factorization has to be done by a classical algorithm (see Equation 16 and 18 in the paper), but this is not clearly pointed out in the paper.

And the third point where the paper cheats a bit is in the conversion of the objective function of the multiplication into a QUBO problem (Quadratic Unconstrained Binary Optimization). Some simplifications are made here in order to be able to calculate the problem with quantum annealing at all.

In principle, nothing is gained with the quantum computer, but a trivial case has been constructed to use a quantum computer without generating any real benefit in order to be able to claim that they have cracked a special case with weak primes with a quantum computer, whereas the relevant calculation must take place classically.

All in all, this is a rather dubious approach.

What is interesting about the paper, however, is that quantum annealing could also be used to calculate factorizations, but the question is whether this would even work in practice with the simplifications made and with the known problems of quantum computers (noise, scaling, annealing does not provide exact results but is an optimization algorithm) for larger numbers that are more than a few bits long. This could quickly lead to limitations in practice.

What do you think? Do you think that quantum annealing can actually be used to factorize larger numbers or is this more hype than reality?