Mir wurde gesagt, dass Physiker und Informatiker an Computern arbeiten, die die Quantenphysik nutzen könnten, um die Rechenleistung erheblich zu steigern und jede Chiffre zu brechen, sodass die Kryptografie bedeutungslos wird.
Ist es wahr?
Nein ist es nicht.
Quantencomputer können große Zahlen effizient faktorisieren, was es ermöglichen würde, viele der häufig verwendeten Public-Key-Kryptosysteme wie RSA zu knacken, die auf der Härte der Faktorisierung basieren.
Es gibt jedoch andere Kryptosysteme wie die gitterbasierte Kryptographie , die nicht auf der Härte des Faktorisierens basieren und die (nach unserem derzeitigen Wissen) nicht anfällig für Angriffe durch einen Quantencomputer wären.
Quantencomputing ist vielversprechend, aber nicht unendlich leistungsfähig.
Die (übertriebenen) Behauptungen, die Sie gehört haben, basieren wahrscheinlich auf dem berühmtesten Quantencomputing-Algorithmus, dem Shor-Algorithmus . Dies ist eine Methode, um mit einem Quantencomputer ganze Zahlen in Primzahlen zu zerlegen. Wie sich herausstellt, verlassen sich viele Verschlüsselungsschemata auf die Tatsache, dass das Faktorisieren großer Zahlen sehr schwierig ist. Nachrichten lassen sich relativ einfach so verschlüsseln, dass nur jemand, der die Primfaktorzerlegung einer bestimmten Zahl kennt, sie mit vertretbarem Aufwand entschlüsseln kann. Wenn Sie große Zahlen schnell faktorisieren könnten, würden Sie viele heutige Verschlüsselungsschemata knacken.
Es gibt jedoch auch andere Techniken, die nicht unmittelbar von Quantencomputern bedroht sind. Wenn nichts anderes, können Sie immer ein One-Time-Pad verwenden , solange die Nachricht selbst verwendet wird. Dies ist mathematisch unzerbrechlich, da jede Nachricht aus der verschlüsselten mit der entsprechenden Schätzung des Schlüssels "entschlüsselt" werden kann, sodass es für einen Lauscher keine Möglichkeit gibt, die echte Nachricht zu kennen.
Die Quantenberechnung kann auch die Türen zu Möglichkeiten der nächsten Generation zur sicheren Übertragung von Informationen öffnen. Beispielsweise besteht die meiste Verschlüsselung heute genau darin, die Nachricht so zu verschlüsseln, dass nur der beabsichtigte Empfänger sie verstehen kann. Aber es kann gute Quantenwege geben, um physisch sicherzustellen, dass Lauscher überhaupt nicht auf die Übertragung zugreifen können.
Es gibt tatsächlich eine ganze Komplexitätsklasse, die der Antwort gewidmet ist, die lautet: "Nein, es kann keinen Code knacken." Die Klasse ist als BQP oder „Bounded Error Quantum Polynomial Time“ bekannt. Es ist die Klasse von Entscheidungsproblemen, die von einem Quantencomputer in polynomieller Zeit gelöst werden können, mit nicht mehr als 1/3 Fehlermarge (dieser Fehlerterm wird in einem klassischen Rechenschritt berücksichtigt, der nach den meisten Quantenalgorithmen auftritt, um dies zu verifizieren Ergebnisse sind korrekt).
Es wird angenommen, dass BQP die folgenden Beziehungen zu anderen Komplexitäten hat:
(Die größte Unbekannte in dieser Liste ist, dass noch nicht bekannt ist, ob P = NP. Die Liste geht von P! = NP aus, aber wenn P = NP, wären NP und NP-vollständig auch Teil von BQP. Wir wissen es auch nicht Ich weiß nicht, ob NP = BQP oder nicht. Es bleibt also noch viel zu entdecken! )
RSA ist mit Quantencomputern knackbar, da die Aufgabe, große zusammengesetzte Zahlen zu faktorisieren, in BQP liegt, wie der Algorithmus von Shor demonstriert. Shors Algorithmus ist NP (aber nicht NP-vollständig). Es gibt andere NP-Algorithmen, von denen angenommen wird, dass sie außerhalb von BQP liegen und zur Verschlüsselung verwendet werden können (die akzeptierte Antwort ist mit gitterbasierter Kryptographie verknüpft, einer solchen Klasse von Algorithmen).
Die bisherigen Antworten konzentrierten sich auf die Verschlüsselung mit öffentlichem Schlüssel, bei der jemand einen öffentlichen Schlüssel veröffentlicht, der zum Verschlüsseln von Nachrichten an ihn verwendet werden kann und der nicht geheim ist. Quantencomputer sind dafür bekannt, einige der Probleme, die am häufigsten als Grundlage der Public-Key-Kryptographie verwendet werden, effizient zu lösen. Es betrifft nicht alle Public-Key-Kryptografien, sondern nur die beliebtesten Schemata; es wirkt sich auf die beliebtesten Schemata aus.
Verschlüsselung ist jedoch mehr als nur ein öffentlicher Schlüssel. Es wird angenommen, dass symmetrische Verschlüsselungsschemata, bei denen die beiden Parteien einen geheimen Schlüssel teilen, nur einer quadratischen Beschleunigung mit Quantencomputern unterliegen (Quantencomputer können eine quadratische Beschleunigung für allgemeine Suchprobleme erreichen, aber nicht mehr). Dies entspricht effektiv einer Halbierung der Schlüssellänge. Im Gegensatz zu den gängigen Public-Key-Systemen ist die effektive Halbierung der Schlüssellänge extrem einfach zu reagieren: Sie können einfach Ihre Schlüssellängen verdoppeln und weitermachen. Symmetrische Verschlüsselung ist weit verbreitet; Selbst wenn die Verschlüsselung mit öffentlichen Schlüsseln verwendet wird, wird sie meistens nur zum Austausch eines Schlüssels für die symmetrische Verschlüsselung verwendet.
Das am weitesten verbreitete symmetrische System, AES, hat eine 256-Bit-Schlüsselvariante, die 128 Bit Sicherheit gegenüber Quantencomputern bietet. Andere in der Entwicklung befindliche Schemata unterstützen 512-Bit-Schlüssel, die 256 Bit effektive Sicherheit bieten würden. Sowohl 128 als auch 256 Bit gelten als auf absehbare Zeit sicher.
Ebenso wird angenommen, dass kryptografische Hash-Funktionen sehr gut gegen Quantencomputer bestehen. Es gibt denselben Algorithmus-basierten Angriff von Grover, aber wie bei Verschlüsselungsfunktionen ist er einfach abzuwehren.
Daher sind alle Behauptungen, dass Kryptografie bedeutungslos wird, völlig falsch, da das Einzige, was ernsthaft betroffen ist, Public-Key-Systeme sind. Public-Key-Systeme sind wichtig, aber Kryptografie ist ein viel breiteres Feld.
Nein. Es kann keinen X-Computer geben, der irgendeine Chiffre knacken kann, weil das One-Time-Pad eine Chiffre ist und One-Time-Pad nicht durch einen Algorithmus gebrochen werden kann (trivialer Beweis in der Informationstheorie).
Ich möchte hinzufügen, dass Quantencomputer keinen bestehenden Code knacken können, da ihre logischen Gatter genau die gleichen Operationen ausführen können wie klassische logische Gatter. Sie fügen neue Möglichkeiten hinzu, während sie die früher in klassischen Computern möglichen beibehalten.
Da Programme im Kern auf logischen Gattern arbeiten, ist es vernünftig anzunehmen, dass jeder existierende Code für klassische Computer auf einem Quantencomputer funktionieren kann.
Siehe auch Quantengatter auf Wikipedia.
Sie können eine normale Berechnung starten und für alle möglichen Eingabetasten parallel berechnen. Das heißt, die Entschlüsselung eines verschlüsselten Textes mit dem richtigen Schlüssel dauert genauso lange wie die Entschlüsselung mit jedem möglichen Schlüssel (mit fester Länge). Das würde bedeuten, dass alle traditionellen Verschlüsselungsverfahren wie AES etc. so schnell geknackt werden könnten, wie sie vom Inhaber des legalen Schlüssels entschlüsselt werden könnten.
Der knifflige Teil (wobei sich das One-Time-Pad auszeichnet) besteht darin, festzustellen, ob die resultierende Nachricht, die Sie beim Entschlüsseln erhalten haben, tatsächlich der richtige Text ist. Zum Beispiel sende ich die Nachricht OKan Sie verschlüsselt mit AES 256bit. Jetzt gibt es 2^256 mögliche Schlüssel, um diese Nachricht zu entschlüsseln, und alle von ihnen werden zu einem Ergebnis führen. Viele vielleicht in so etwas wie #§dem einen oder anderen kryptischen Byte-Symbolen, aber einige Schlüssel könnten zu zwei Buchstaben "WB" führen und einige Kombinationen könnten sogar zu "NO" führen.
Der schwierige Teil besteht also darin, herauszufinden, welches die richtige Nachricht ist! Denn der (theoretische) Quantencomputer wird am Ende nur wenige Ergebnisse mit hoher Wahrscheinlichkeit ausgeben - also muss man einen Check codieren, der erkennt, ob die Ausgabe tatsächlich ein gültiger Text ist. Wenn der Text viel größer als der Schlüssel ist und so etwas wie einfaches Englisch, oder besser ein Standardformat, das auf Integrität überprüft werden kann, könnte dies möglich sein. Aber wenn es mehrere mögliche Ergebnisse gibt, die gültig aussehen, muss ein Mensch sie sortieren, so dass im Falle eines Onetime-Pads, das den Code knackt, genauso gut ist, wie einfach aus heiterem Himmel zu raten. Andere Verschlüsselungsschemata müssen möglicherweise angepasst werden, um gültig aussehende Nachrichten für falsche Schlüssel zu erzeugen, aber dies scheint möglich ...
--
Das würde nur funktionieren, wenn ein echter Quantencomputer so funktionieren könnte. Soweit ich weiß, haben wir keine eindeutigen Beweise dafür, dass ein qc tatsächlich so funktioniert. Vielleicht geht es einfach nicht und wir haben nicht einmal ein Problem ;-)
Benutzer
Kyle Kanos
David z
Nathan Cooper
Daniel Sank
Gedächtnis
Daniel Sank
Steven Sagona