Quantencomputer: Neue Ansätze brechen Verschlüsselung mit weniger Qubits
Quantencomputer sind eine Gefahr für klassische Kryptografiesysteme, die auf elliptischen Kurven (EC) oder dem Diskreter-Logarithmus-Problem (DLP) basieren. Die Erkenntnis ist nicht neu.
Bislang besagten Abschätzungen, dass dafür Millionen physischer Qubits erforderlich seien. Bis reale Quantencomputer so weit seien, werde es noch viele Jahre dauern, so die Annahme. Zwei neue Veröffentlichungen stellen dies infrage.
So haben Forscher von Google nach eigenen Angaben eine Optimierung des Shor-Algorithmus gefunden, die deutlich weniger Ressourcen benötigt. Sie schreiben von zwei Varianten(öffnet im neuen Fenster) mit 1.200 oder 1.450 logischen Qubits sowie 90 oder 70 Millionen Toffoli-Gattern. Letztere Variante könne auf Quantencomputern mit schnellen Fehlerkorrekturzyklen, etwa mit supraleitenden Qubits, einen privaten 256-Bit-ECDLP-Schlüssel in neun Minuten berechnen.
Die Rechenzeit wird hervorgehoben, da die Forscher Kryptowährungen als Angriffsziel wählten. Hier spielt Geschwindigkeit eine Rolle, wenn Transaktionen manipuliert werden sollen. Interessanterweise veröffentlichten die Forscher ihren Algorithmus nicht, sondern gaben nur einen sogenannten Null-Wissen-Beweis(öffnet im neuen Fenster) an, der seine Existenz belegt.
Geheimhaltung von Forschungsergebnissen erforderlich?
Dies wird als neue Form des Responsible Disclosure bezeichnet, um die Gefahr durch Optimierungen von Algorithmen zum Brechen von Verschlüsselungen zu verringern. Selbst der Forscher Scott Aaronson, der dies anfangs befürwortete, spricht sich aber mittlerweile für die Veröffentlichung solcher Ergebnisse(öffnet im neuen Fenster) aus.
Aaronson geht davon aus, dass entsprechend leistungsfähige Quantencomputer noch einige Jahre auf sich warten lassen werden und Optimierungen diesen Zeitraum lediglich leicht verkürzen. Dennoch sei Angst vor realen Angriffen auf nicht quantensichere Verschlüsselungsverfahren möglicherweise erforderlich, um den Umstieg auf Post-Quanten-Kryptografie zu beschleunigen.
Dem pflichtete auch Kryptograf Filippo Valsorda bei(öffnet im neuen Fenster) : Die relevante Frage sei nicht, wann Quantencomputer ausreichend leistungsfähig seien, sondern ob sich mit Sicherheit ausschließen lasse, dass dies in einigen Jahren der Fall sei.
Andere Architekturen benötigen viel weniger Qubits
Dass die Gefahr nicht mehr rein theoretisch ist, zeigt eine zweite, noch nicht peer-reviewte Veröffentlichung(öffnet im neuen Fenster) . Sie stammt von Forschern des California Institute of Technology (Caltech) sowie dessen Ausgründung Oratomic. Während die Google-Forscher für ihren Algorithmus noch immer über 500.000 physische Qubits benötigen, halten die Caltech-Forscher rund 10.000 für ausreichend.
Sie setzen dafür auf Quantencomputer mit neutralen Atomen, die mittels optischer Pinzetten(öffnet im neuen Fenster) manipuliert werden. Während supraleitende Qubits in der Praxis üblicherweise nur mit ihren direkten Nachbarn interagieren können, sind bei Realisierung der Qubits über neutrale Atome beliebige Interaktionen möglich. Das wiederum erlaubt die Nutzung wesentlich effizienterer Algorithmen zur Quantenfehlerkorrektur, weshalb für ein logisches Qubit deutlich weniger physische benötigt werden.
Auch wenn die Forscher darauf hinweisen, dass ein System mit rund 6.100 Qubits bereits demonstriert(öffnet im neuen Fenster) worden sei, steht aber auch hier die Krypto-Apokalypse nicht direkt vor der Tür. Denn einerseits wurden mit diesem System bislang noch keine Quantengatter implementiert, andererseits rechnen solche Systeme aufgrund langer Fehlerkorrekturzyklen langsamer als etwa supraleitende Quantencomputer.
Dennoch sei ein 256-Bit-EC-Schlüssel wohl in wenigen Tagen zu knacken, ein RSA-2048-Schlüssel in Wochen bis Monaten, schätzen die Forscher. Sie schreiben allerdings auch, dass Quantencomputer auf Basis neutraler Atome noch vor großen Herausforderungen stünden.
Dennoch gilt der Ansatz als vielversprechend. Die beiden Veröffentlichungen sind damit wieder einmal eine Warnung: Wer sensible Informationen speichert und austauscht, sollte schleunigst den Umstieg auf Post-Quanten-Kryptografie angehen, sofern das noch nicht geschehen ist.
- Anzeige Hier geht es zu Hacking & Security: Das umfassende Handbuch bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.