Quantencomputer: Das Ende der Kryptographie?

Werbung

Quantum Computing ist eine dieser Technologien, die so geheimnisvoll ist, dass TV-Charaktere sie fallen lassen, wenn sie intelligent klingen möchten.

Quantencomputer als Idee gibt es schon seit einiger Zeit - die theoretische Möglichkeit wurde ursprünglich 1982 von Yuri Manin und Richard Feynman eingeführt. In den letzten Jahren ist das Feld jedoch der Praktikabilität besorgniserregend näher gekommen.

Unternehmen wie Google und Microsoft sowie Regierungsbehörden wie die NSA verfolgen seit Jahren fieberhaft Quantencomputer. Eine Firma namens D-Wave hat Geräte hergestellt und verkauft diese (obwohl sie keine richtigen Computer sind und können) nur wenige Algorithmen ausführen) Quanteneigenschaften ausnutzen und sind ein weiterer inkrementeller Schritt auf dem Weg zu a völlig Turing-komplett Was ist der Turing-Test und wird er jemals geschlagen werden?Der Turing-Test soll feststellen, ob Maschinen denken. Hat das Eugene Goostman-Programm den Turing-Test wirklich bestanden oder haben die Macher einfach geschummelt? Weiterlesen Quantenmaschine.

Es erscheint nicht unangemessen zu sagen, dass es zu Durchbrüchen kommen könnte, die es ermöglichen, den ersten großen Quantencomputer innerhalb eines Jahrzehnts zu bauen.

Warum also all das Interesse? Warum sollte es dich interessieren? Computer werden immer schneller Was ist Moores Gesetz und was hat es mit dir zu tun? [MakeUseOf erklärt]Pech hat nichts mit Moores Gesetz zu tun. Wenn das die Assoziation ist, die Sie hatten, verwechseln Sie sie mit Murphys Gesetz. Sie waren jedoch nicht weit weg, weil Moores Gesetz und Murphys Gesetz ... Weiterlesen - Was ist das Besondere an Quantencomputern?

Um zu erklären, warum diese Maschinen so wichtig sind, müssen wir einen Schritt zurücktreten und genau untersuchen, was Quantencomputer sind und warum sie funktionieren. Lassen Sie uns zunächst über ein Konzept sprechen, das als "Laufzeitkomplexität" bezeichnet wird.

Was ist Laufzeitkomplexität?

Eine der großen Überraschungen in den frühen Tagen der Informatik war die Entdeckung, dass, wenn Sie einen Computer haben, der ein Problem löst Bei einer bestimmten Größe in einer bestimmten Zeit und einer Verdoppelung der Geschwindigkeit des Computers kann er Probleme nicht unbedingt doppelt so schnell lösen groß.

Einige Algorithmen erhöhen die Gesamtausführungszeit sehr, sehr schnell, wenn das Problem größer wird - einige Algorithmen können schnell abgeschlossen werden Bei 100 Datenpunkten würde die Vervollständigung des Algorithmus bei 1000 Datenpunkten einen Computer von der Größe der Erde erfordern, der eine Milliarde läuft Jahre. Die Laufzeitkomplexität ist eine Formalisierung dieser Idee: Sie untersucht die Kurve, wie schnell die Komplexität eines Problems wächst, und verwendet die Form dieser Kurve, um den Algorithmus zu klassifizieren.

Im Allgemeinen werden diese Schwierigkeitsgrade als Funktionen ausgedrückt. Ein Algorithmus, der proportional schwieriger wird, wenn der Datensatz, an dem er arbeitet, zunimmt (wie eine einfache Zählfunktion), wird als eine Funktion mit einer Laufzeitkomplexität von „n ” (wie in, es dauert n Zeiteinheiten zu verarbeiten n Datenpunkte).

Alternativ kann es auch als "linear" bezeichnet werden, da Sie beim Zeichnen eine gerade Linie erhalten. Andere Funktionen könnten sein n ^ 2 oder 2 ^ n oder n! (n Fakultät). Diese sind polynomisch und exponentiell. In den beiden letztgenannten Fällen wachsen die exponentiellen so schnell, dass sie in fast allen Fällen nur für sehr triviale Beispiele gelöst werden können.

Laufzeitkomplexität und Kryptographie

Wenn Sie dieses Zeug zum ersten Mal hören und es bedeutungslos und geheimnisvoll klingt, versuchen wir, diese Diskussion zu begründen. Die Komplexität der Laufzeit ist für die Kryptografie von entscheidender Bedeutung. Daher ist die Entschlüsselung für Personen, die einen geheimen Schlüssel kennen, wesentlich einfacher als für Personen, die dies nicht tun. In einem idealen kryptografischen Schema sollte die Entschlüsselung linear sein, wenn Sie den Schlüssel haben, und 2 ^ k (wobei k die Anzahl der Bits im Schlüssel ist), wenn Sie dies nicht tun.

Mit anderen Worten, der beste Algorithmus zum Entschlüsseln der Nachricht ohne den Schlüssel sollte darin bestehen, einfach mögliche Schlüssel zu erraten, was für Schlüssel, die nur einige hundert Bit lang sind, nicht möglich ist.

Für die Kryptografie mit symmetrischen Schlüsseln (bei der die beiden Parteien die Möglichkeit haben, ein Geheimnis sicher auszutauschen, bevor sie mit der Kommunikation beginnen) ist dies ziemlich einfach. Bei asymmetrischer Kryptographie ist es schwieriger.

Die asymmetrische Kryptographie, bei der die Verschlüsselungs- und Entschlüsselungsschlüssel unterschiedlich sind und nicht einfach voneinander berechnet werden können, ist mathematisch viel schwieriger Struktur zu implementieren als symmetrische Kryptografie, aber sie ist auch viel leistungsfähiger: Mit asymmetrischer Kryptografie können Sie private Gespräche führen, auch wenn Sie zu viel tippen Linien! Außerdem können Sie "digitale Signaturen" erstellen, um zu überprüfen, von wem eine Nachricht stammt und ob sie nicht manipuliert wurde.

Dies sind leistungsstarke Tools, die die Grundlage für die moderne Privatsphäre bilden: Ohne asymmetrische Kryptografie hätten Benutzer elektronischer Geräte keinen zuverlässigen Schutz vor neugierigen Blicken.

Da asymmetrische Kryptografie schwieriger zu erstellen ist als symmetrische, sind die heute verwendeten Standardverschlüsselungsschemata nicht so stark wie sie sein könnten: Der gängigste Verschlüsselungsstandard, RSA, kann geknackt werden, wenn Sie die Primfaktoren eines sehr großen effizient finden können Nummer. Die gute Nachricht ist, dass dies ein sehr schwieriges Problem ist.

Der bekannteste Algorithmus zum Einbeziehen großer Zahlen in ihre Komponentenprimzahlen wird als allgemeines Zahlenfeldsieb bezeichnet und weist eine Laufzeitkomplexität auf, die etwas langsamer wächst als 2 ^ n. Infolgedessen müssen Schlüssel etwa zehnmal länger sein, um eine ähnliche Sicherheit zu gewährleisten. Dies wird normalerweise von den Geschäftskosten toleriert. Die schlechte Nachricht ist, dass sich das gesamte Spielfeld ändert, wenn Quantencomputer in den Mix geworfen werden.

Quantencomputer: Ändern des Kryptospiels

Quantencomputer funktionieren, weil sie durch ein Quantenphänomen namens „Überlagerung“ mehrere interne Zustände gleichzeitig haben können. Das bedeutet, dass sie verschiedene Teile eines Problems gleichzeitig angreifen können, aufgeteilt auf mögliche Versionen des Universums. Sie können auch so konfiguriert werden, dass die Zweige, die das Problem lösen, mit der größten Amplitude aufgewickelt werden, sodass beim Öffnen der Box auf Schrödingers Katze, die Version des internen Zustands, mit der Sie am wahrscheinlichsten konfrontiert werden, ist eine selbstgefällig aussehende Katze mit einer entschlüsselten Katze Botschaft.

Weitere Informationen zu Quantencomputern finden Sie unter unser aktueller Artikel zu diesem Thema Wie funktionieren optische und Quantencomputer?Das Exascale-Zeitalter kommt. Wissen Sie, wie optische Computer und Quantencomputer funktionieren, und werden diese neuen Technologien unsere Zukunft sein? Weiterlesen !

Das Ergebnis ist, dass Quantencomputer nicht nur linear schneller sind als normale Computer: zwei, zehn oder hundert Zeiten schneller helfen nicht viel, wenn es um konventionelle Kryptografie geht, für deren Verarbeitung Sie hunderte Milliarden Mal zu langsam sind. Quantencomputer unterstützen Algorithmen, deren Laufzeitkomplexität geringer ist als sonst möglich. Dies ist es, was Quantencomputer grundlegend von anderen zukünftigen Computertechnologien unterscheidet, wie z Graphen- und Memrister-Berechnung Die neueste Computertechnologie, die Sie sehen müssen, um zu glaubenSchauen Sie sich einige der neuesten Computertechnologien an, die die Welt der Elektronik und PCs in den nächsten Jahren verändern werden. Weiterlesen .

Für ein konkretes Beispiel kann Shors Algorithmus, der nur auf einem Quantencomputer ausgeführt werden kann, große Zahlen berücksichtigen log (n) ^ 3 Zeit, die drastisch besser ist als der beste klassische Angriff. Die Verwendung des allgemeinen Zahlenfeldsiebs zum Faktorisieren einer Zahl mit 2048 Bit dauert etwa 10 ^ 41 Zeiteinheiten, was mehr als einer Billion Billionen Billionen entspricht. Bei Verwendung des Shor-Algorithmus dauert dasselbe Problem nur etwa 1000 Zeiteinheiten.

Der Effekt wird umso deutlicher, je länger die Tasten sind. Das ist die Stärke von Quantencomputern.

Versteh mich nicht falsch - Quantencomputer haben viele potenzielle nicht böse Verwendungszwecke. Quantencomputer können das Problem der reisenden Verkäufer effizient lösen und es Forschern ermöglichen, effizientere Schifffahrtsnetzwerke aufzubauen und bessere Schaltkreise zu entwerfen. Quantencomputer haben bereits leistungsstarke Anwendungen in der künstlichen Intelligenz.

Ihre Rolle in der Kryptographie wird jedoch katastrophal sein. Die Verschlüsselungstechnologien, die es unserer Welt ermöglichen, weiter zu funktionieren, hängen davon ab, dass das Problem der ganzzahligen Faktorisierung schwer zu lösen ist. Mit RSA und verwandten Verschlüsselungsschemata können Sie darauf vertrauen, dass Sie sich auf der richtigen Website befinden, auf der Sie sich befinden Der Download ist nicht mit Malware durchsetzt und die Leute spionieren Ihr Surfen im Internet nicht aus (wenn Sie es verwenden) Tor).

Kryptografie schützt Ihr Bankkonto und die nukleare Infrastruktur der Welt. Wenn Quantencomputer praktisch werden, funktioniert all diese Technologie nicht mehr. Die erste Organisation, die einen Quantencomputer entwickelt, wenn die Welt noch an den Technologien arbeitet, die wir heute verwenden, wird in einer erschreckend mächtigen Position sein.

Ist die Quantenapokalypse also unvermeidlich? Können wir etwas dagegen tun? Wie sich herausstellt... ja.

Post-Quanten-Kryptographie

Es gibt verschiedene Klassen von Verschlüsselungsalgorithmen, die nach unserem Kenntnisstand auf einem Quantencomputer nicht wesentlich schneller zu lösen sind. Diese werden zusammen als Post-Quanten-Kryptographie bezeichnet und geben Hoffnung, dass die Welt zu Kryptosystemen übergehen kann, die in einer Welt der Quantenverschlüsselung sicher bleiben.

Zu den vielversprechenden Kandidaten gehört die gitterbasierte Verschlüsselung wie Ring-Learning With Error, die ihre Sicherheit aus einem nachweislich komplexen System ableitet Problem des maschinellen Lernens und multivariate Kryptographie, die ihre Sicherheit aus der Schwierigkeit ableitet, sehr große einfache Systeme zu lösen Gleichungen. Weitere Informationen zu diesem Thema finden Sie auf der Wikipedia-Artikel. Achtung: Viele dieser Dinge sind komplex, und Sie müssen möglicherweise Ihren mathematischen Hintergrund erheblich verbessern, bevor Sie sich wirklich mit den Details befassen können.

Viele davon sind, dass Post-Quanten-Kryptoschemata sehr cool, aber auch sehr jung sind. Sie brauchen mehr Arbeit, um effizient und praktisch zu sein und um zu zeigen, dass sie sicher sind. Der Grund, warum wir Kryptosystemen vertrauen können, ist, dass wir lange genug genug klinisch paranoide Genies auf sie geworfen haben dass alle offensichtlichen Mängel inzwischen entdeckt worden wären, und Forscher haben verschiedene Eigenschaften nachgewiesen, die sie ausmachen stark.

Die moderne Kryptographie hängt vom Licht als Desinfektionsmittel ab, und die meisten kryptografischen Post-Quanten-Schemata sind einfach zu neu, um der Sicherheit der Welt zu vertrauen. Sie sind jedoch auf dem Weg dorthin und mit etwas Glück und etwas Vorbereitung können Sicherheitsexperten den Wechsel abschließen, bevor der erste Quantencomputer überhaupt online geht.

Wenn sie jedoch fehlschlagen, können die Folgen schwerwiegend sein. Der Gedanke an jemanden, der diese Art von Macht besitzt, ist beunruhigend, auch wenn Sie hinsichtlich seiner Absichten optimistisch sind. Die Frage, wer zuerst einen funktionierenden Quantencomputer entwickelt, sollte jeder genau beobachten, wenn wir in das nächste Jahrzehnt eintreten.

Sind Sie besorgt über die Unsicherheit der Kryptographie gegenüber Quantencomputern? Was halten Sie davon? Teilen Sie Ihre Gedanken in den Kommentaren unten!

Bildnachweis: Binäre Kugel Über Shutterstock