Mir wurde gesagt, dass Physiker und Informatiker an Computern arbeiten, die mithilfe der Quantenphysik die Rechenfähigkeiten erheblich verbessern und jede Verschlüsselung aufheben könnten, damit die Kryptographie bedeutungslos wird.
Stimmt das?
Mir wurde gesagt, dass Physiker und Informatiker an Computern arbeiten, die mithilfe der Quantenphysik die Rechenfähigkeiten erheblich verbessern und jede Verschlüsselung aufheben könnten, damit die Kryptographie bedeutungslos wird.
Stimmt das?
Nein, das ist es nicht.
Quantencomputer können große Zahlen effizient faktorisieren, wodurch viele der häufig verwendeten Kryptosysteme mit öffentlichem Schlüssel wie RSA, die auf der Härte des Factorings basieren, zerstört werden können.
Es gibt jedoch auch andere Kryptosysteme wie die gitterbasierte Kryptographie, die nicht auf der Härte des Factorings basieren und (nach unserem derzeitigen Kenntnisstand) nicht anfällig für Angriffe sind von einem Quantencomputer.
Quantencomputer sind vielversprechend, aber nicht unendlich leistungsfähig.
Die (übertriebenen) Behauptungen, die Sie gehört haben, basieren wahrscheinlich auf dem bekanntesten Quantencomputer-Algorithmus, Shors Algorithmus. Dies ist eine Methode zur Verwendung eines Quantencomputers, um ganze Zahlen in Primzahlen zu zerlegen. Wie sich herausstellt, beruhen viele Verschlüsselungsschemata auf der Tatsache, dass das Faktorisieren großer Zahlen sehr schwierig ist. Nachrichten können ziemlich einfach so verschlüsselt werden, dass nur jemand, der die Primfaktorisierung einer bestimmten Zahl kennt, sie mit angemessenem Aufwand entschlüsseln kann. Wenn Sie große Zahlen schnell faktorisieren könnten, würden Sie viele heutige Verschlüsselungsschemata brechen.
Es gibt jedoch andere Techniken, die von Quantencomputern nicht sofort bedroht sind. Wenn nichts anderes, können Sie immer ein einmaliges Pad verwenden, solange die Nachricht selbst angezeigt wird. Dies ist mathematisch unzerbrechlich, da jede Nachricht mit der entsprechenden Schätzung des Schlüssels von der verschlüsselten "entschlüsselt" werden kann, sodass ein Lauscher die Möglichkeit nicht hat, die zu kennen echte Nachricht.
Die Quantenberechnung kann auch die Türen für Möglichkeiten der nächsten Generation öffnen, Informationen sicher zu übertragen. Zum Beispiel ist die meiste Verschlüsselung heutzutage genau das - das Verwürfeln der Nachricht, so dass nur der beabsichtigte Empfänger einen Sinn daraus ziehen kann. Es kann jedoch gute Quantenmöglichkeiten 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: "Nein, sie kann keinen Code brechen." Die Klasse ist als BQP oder "begrenzte Fehlerquantenpolynomzeit" bekannt. Es ist die Klasse von Entscheidungsproblemen, die von einem Quantencomputer in Polynomzeit mit nicht mehr als 1/3 Fehlergrenze gelöst werden können (dieser Fehlerterm wird in einem klassischen Berechnungsschritt berücksichtigt, der nach den meisten Quantenalgorithmen auftritt, um dies zu überprüfen Ergebnisse sind korrekt).
Es wird angenommen, dass BQP die folgenden Beziehungen zu anderen Komplexitäten aufweist:
(Das wichtigste Unbekannte in dieser Liste ist, dass es noch nicht bekannt ist, ob P = NP. Die Liste geht von P! = NP aus, aber wenn P = NP Natürlich wären NP und NP-vollständig auch Teil von BQP. Wir wissen auch nicht, ob NP = BQP ist oder nicht. Es bleibt noch so viel zu entdecken! )
RSA ist Mit Quantencomputern knackbar, weil die Aufgabe darin besteht, große zusammengesetzte Zahlen zu berücksichtigen ers ist in BQP, wie der Shor-Algorithmus zeigt. 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 enthält Links zur gitterbasierten Kryptographie, die eine solche Klasse von Algorithmen darstellt).
Die bisherigen Antworten konzentrierten sich auf die Verschlüsselung mit öffentlichen Schlüsseln, bei der jemand einen öffentlichen Schlüssel veröffentlicht, mit dem Nachrichten an ihn verschlüsselt werden können und der nicht geheim ist. Es ist bekannt, dass Quantencomputer einige der Probleme, die am häufigsten als Grundlage für die Kryptographie mit öffentlichen Schlüsseln verwendet werden, effizient lösen. Es betrifft nicht die Kryptografie mit allen öffentlichen Schlüsseln, sondern nur die beliebtesten Schemata. Dies betrifft jedoch die gängigsten Schemata.
Die Verschlüsselung umfasst jedoch mehr als den öffentlichen Schlüssel. Es wird angenommen, dass symmetrische Verschlüsselungsschemata, bei denen die beiden Parteien einen geheimen Schlüssel gemeinsam nutzen, mit Quantencomputern nur einer quadratischen Beschleunigung unterliegen (Quantencomputer können bei allgemeinen Suchproblemen eine quadratische Beschleunigung erzielen, jedoch nicht mehr). Dies entspricht einer effektiven Halbierung der Schlüssellänge. Im Gegensatz zu den gängigen Public-Key-Systemen ist es äußerst einfach, die Schlüssellänge effektiv zu halbieren: Sie können Ihre Schlüssellängen einfach verdoppeln und weitermachen. Symmetrische Verschlüsselung ist äußerst verbreitet. Selbst wenn die Verschlüsselung mit öffentlichem Schlüssel verwendet wird, wird sie meistens nur zum Austausch eines Schlüssels gegen symmetrische Verschlüsselung verwendet.
Das am häufigsten verwendete symmetrische System, AES, verfügt über eine 256-Bit-Schlüsselvariante, die 128 Bit Sicherheit bietet gegen Quantencomputer. Andere in der Entwicklung befindliche Schemata unterstützen 512-Bit-Schlüssel, die 256 Bit effektive Sicherheit bieten würden. Es wird angenommen, dass sowohl 128 als auch 256 Bit auf absehbare Zeit sicher sind.
Ebenso wird angenommen, dass kryptografische Hash-Funktionen sehr gut gegen Quantencomputer bestehen. Es gibt den gleichen algorithmischen Angriff von Grover, aber wie bei Verschlüsselungsfunktionen ist es einfach zu kontern.
Alle Behauptungen, dass Kryptographie bedeutungslos wird, sind völlig falsch, weil das einzige, was ist stark betroffen sind Public-Key-Systeme. Public-Key-Systeme sind wichtig, aber Kryptographie ist ein viel breiteres Feld.
Nein. Es kann keinen X-Computer geben, der eine Verschlüsselung brechen kann, da das eine Zeitfeld eine Verschlüsselung ist und ein Zeitfeld nicht durch einen Algorithmus gebrochen werden kann (trivialer Beweis in der Informationstheorie)
Ich möchte hinzufügen, dass Quantencomputer keinen vorhandenen Code beschädigen können, da ihre logischen Gatter dieselben Operationen ausführen können wie klassische logische Gatter. Sie fügen neue Möglichkeiten hinzu und behalten gleichzeitig die Möglichkeiten bei, die früher in klassischen Computern möglich waren.
Da Programme im Kern an logischen Gattern arbeiten, ist es vernünftig anzunehmen, dass vorhandener Code für klassische Computer vorhanden ist Computer können auf einem Quantencomputer arbeiten.
Siehe auch Quantentor auf Wikipedia.
Sie können eine normale Berechnung starten und sie parallel für alle möglichen berechnen Eingabetasten. Das bedeutet, dass das Entschlüsseln eines verschlüsselten Textes mit dem richtigen Schlüssel genauso lange dauert wie das Entschlüsseln mit jedem möglichen Schlüssel (mit einer festen Länge). Dies würde bedeuten, dass alle herkömmlichen Verschlüsselungsmethoden wie AES usw. so schnell geknackt werden könnten, wie sie vom Inhaber des legalen Schlüssels entschlüsselt werden könnten.
Der schwierige Teil (wo sich das One Time Pad auszeichnet) ist, wie zu wissen, ob die resultierende Nachricht, die Sie beim Entschlüsseln erhalten haben, tatsächlich der richtige Text ist. Zum Beispiel sende ich die Nachricht OK
verschlüsselt mit AES 256bit an Sie. Jetzt gibt es 2 ^ 256 mögliche Schlüssel, mit denen diese Nachricht entschlüsselt werden kann, und alle führen zu einem Ergebnis. Viele möglicherweise in # §
oder anderen kryptischen Bytesymbolen, aber einige Schlüssel können zu zwei Buchstaben "WB" führen, und eine Kombination kann sogar zu "NO" führen.
Also Der schwierige Teil ist dann herauszufinden, welche die richtige Nachricht ist! Da der (theoretische) Quantencomputer am Ende nur wenige Ergebnisse mit hoher Wahrscheinlichkeit ausgibt, müssen Sie eine Prüfung codieren, die 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. Wenn es jedoch mehrere mögliche Ergebnisse gibt, die gültig aussehen, muss ein Mensch sie sortieren, sodass im Fall eines einmaligen Pads das Knacken des Codes genauso gut ist wie das einfache Erraten aus heiterem Himmel. 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 zu sein ...
-
Dies würde nur funktionieren, wenn ein tatsächlicher Quantencomputer so funktionieren könnte. Soweit ich weiß, gibt es keine eindeutigen Beweise dafür, dass ein QC tatsächlich so funktioniert. Vielleicht geht es einfach nicht und wir haben nicht einmal ein Problem ;-)