Dies ist der vierte Artikel in einer siebenteiligen Reihe über Algorithmen und Berechnungen, in der untersucht wird, wie wir einfache Binärzahlen verwenden, um unsere Welt mit Strom zu versorgen. Der erste Artikel Wie Algorithmen die Welt steuern, in der wir leben , kann gefunden werden hier .
Einige Jahre bevor Sergei Brin und Larry Page ihre Google-Suchmaschine zum ersten Mal in das Geschäft integriert haben, das zum Aufbau des Internet beigetragen hat, wie wir es kennen. Peter Shor veröffentlicht ein Papier über den Algorithmus, der dazu bestimmt war, alle Schlösser der Verbindungen aufzubrechen, die das Ganze sicher halten sollten.
Peter Shor war kein bösartiger Anarcho-Hacktivist, sondern ein Mathematiker, für den gearbeitet wurde Bell Labs von AT & T versucht, ein schwieriges mathematisches Problem wie jeder andere Mathematiker auf diesem Gebiet zu lösen. Sein Algorithmus, bekannt als Shors Algorithmus erforderte eine Technologie, die theoretisch kaum existierte, geschweige denn die Realität, als er sie 1994 zum ersten Mal beschrieb.
VERBINDUNG: WAS ÄNDERT SICH QUANTUM COMPUTING GENAU?
In den späten 1990er und frühen 2000er Jahren gab es keinen Grund zu der Annahme, dass wir uns jemals Sorgen um die Unsicherheit von machen müssten. RSA-Verschlüsselung aber jetzt kennen wir die Wahrheit : RSA-Verschlüsselung ist zum Scheitern verurteilt. Nun wird die unwahrscheinliche Technologie Shor verwendet, Quantencomputer , rückt nicht nur vor eine ähnliche Rate zu Moores Gesetz bedeutet, dass Quantencomputer innerhalb von ein oder zwei Jahrzehnten leistungsfähig genug sind, um ausgeführt zu werden. Shors Algorithmus und Büste auf RSA-Verschlüsselung - Shors Algorithmus selbst half zu inspirieren die Entwicklung des Quantencomputers in erster Linie.
RSA-Verschlüsselung wurde einst als unzerbrechlich angesehen
RSA-Verschlüsselung das verwendet wird, um alles von Dateien auf unseren Festplatten bis hin zu vertraulichem Internetverkehr zu verschlüsseln, basiert auf den Prinzipien von Austausch öffentlicher Schlüssel und das rechnerisch schwierige Problem von Primfaktorisierung .
Für einen klassischen Computer ein effizienter Algorithmus zum Auffinden der Primfaktoren von a zusammengesetzte Nummer existiert nicht, was bedeutet, dass das Beste, was wir tun können, darin besteht, eine Antwort zu finden, die etwas weniger schrecklich ist als Exponentialzeit . RSA-Verschlüsselung wird normalerweise mit einer Bitlänge qualifiziert, wie z. 128-Bit , 256 Bit usw., die die Bitlänge des Schlüssels darstellt, der zum Ver- und Entschlüsseln von Daten verwendet wird. Also ein Brute-Force-Algorithmus mit exponentielle Zeitkomplexität Arbeiten an a 128-Bit-Verschlüsselungsschlüssel müsste versuchen 2 128 mindestens Werte
Dies ist gleich 340.282.366.920.938.463.463.374.607.431.768.211.456 mögliche Schlüssel und RSA-Verschlüsselungsschlüssel waren nicht so klein wie 128-Bit in mehr als einem Jahrzehnt. Die derzeit empfohlene Standardschlüssellänge für einen RSA-Verschlüsselungsschlüssel beträgt 2048-Bit was gleich ist 340,282,366,920,938,463,463,374,607,431,768,211,456 16 mögliche Tasten.
Diese Zahlen sind für uns unergründlich, aber es gibt eine Möglichkeit, Operationen mit diesen Zahlen zu verwalten und sogar auszuführen. modulare Arithmetik und diese Vorgänge bilden das Herzstück des RSA-Verschlüsselungsalgorithmus.
In vielen Ländern, in denen a 12-Stunden-Uhr anstatt a 24-Stunden-Uhr um Zeit zu behalten, sie Verwenden Sie buchstäblich immer modulare Arithmetik. Wenn ja 11 Uhr und ich bitte Sie, mich zu treffen vier Stunden , du weißt, dass ich mich treffen möchte 15 Uhr . Das liegt daran, dass wir die Nummer verwenden 12 genannt Modul um zu wissen, wann Sie wieder mit dem Zählen von Null beginnen müssen. Die modulare Arithmetik verwendet denselben Prozess, nur mit Zahlen von enormer Größe, um Berechnungen durchzuführen.
Wie jedes andere Schlüsselaustauschsystem RSA-Verschlüsselung verwendet a öffentlicher Schlüssel und a privater Schlüssel zum Ver- und Entschlüsseln von Daten, außer RSA-Verschlüsselung verwendet zwei Zahlen als öffentlichen Schlüssel, einen öffentlichen Exponenten zum Verschlüsseln einer Nachricht und a Modul für den Verschlüsselungsvorgang, der die Verschlüsselung erzeugt. Was macht das aus? Modul so wichtig ist die Tatsache, dass es das Produkt von ist zwei sehr große Primzahlen und diese kennen zwei Zahlen ermöglicht Ihnen das Reverse Engineering des privater Schlüssel das entsperrt die Verschlüsselung.
Die Schwierigkeit inhärent RSA-Verschlüsselung ist jedoch zweifach: Die Ungeheuerlichkeit der beteiligten Zahlen bedeutet, dass Sie Ihren Weg zum nicht brutal erzwingen können privater Schlüssel und die Tatsache, dass Primfaktorisierung von dieser unglaublich großen Zahl ist etwas nein klassischer Computer kann hoffen, in zu tun Billionen von Jahren .
Wie Quantencomputer und Shors Algorithmus die RSA-Verschlüsselung besiegen
Ohne sich in der zu verfangen endliche Details , Shors Algorithmus ist eine dreiteilige Antwort auf das Problem von Primfaktorisierung für beliebig Ganzzahl, funktioniert also unabhängig von der Größe der Ganzzahl. erster Teil wird ausgeführt an a klassischer Computer in Polynomzeit , aber es ist nur das Setup für die zweiter und wichtigster Teil . The zweiter Teil erfordert die Verwendung von speziell konstruierten Quantenschaltungen um die Quantenberechnung benötigt, um das zu finden Wert Sie benötigen für die dritter Teil mit dem Sie die finden können Primfaktoren der ganzen Zahl auf a klassischer Computer .
Der erste Teil des Algorithmus transformiert das Problem von Primfaktorisierung in eine gleichwertig Problem, das lösbar ist, nämlich das Finden des Punkt von a modularer Betrieb . Wenn Sie die finden können Punkt von dieser Funktion als Ganzzahl, die Sie als a faktorisieren möchten Modul Mit einigen zusätzlichen Berechnungen können Sie die Primfaktoren auf einem klassischen Computer ziemlich schnell finden.
Das Problem ist, dass Primfaktorisierung , das finden Punkt von diesem modularen Betrieb ist nichts a klassischer Computer kann in Polynomzeit , aber Shor gezeigt in zweiter Teil des Algorithmus, der a verwendet theoretischer Quantencomputer Sie könnten dies berechnen Punkt und vor allem konnte er mathematisch beweisen dass dieser Teil der Quantenalgorithmus lief ein Polynomzeit . Nach dem Finden der Punkt , a klassischer Computer könnte es verwenden, um die zu finden Primfaktoren einer beliebigen Ganzzahl
Wie Peter Shor und Shors Algorithmus das Quantencomputing starteten
Peter Shor zeigte, dass eine theoretische Quantencomputer könnte ein unlösbares mathematisches Problem auf folgende Weise lösen: a klassischer Computer könnte niemals die Notwendigkeit umgehen, einzelne Werte gleichzeitig zu berechnen. Quantencomputer kann Operationen an ausführen Qubits in Überlagerung und buchstäblich reduzieren zeitliche Komplexität eines Problems exponentiell.
Wann Shor entwickelte seinen Algorithmus Quantencomputer existierte in keiner sinnvollen Weise. Die Idee hatte war schon da für eine Weile, aber es war völlig theoretisch, unpraktisch, überhaupt zu versuchen, etwas zu bauen, und niemand konnte den Nutzen erkennen, wenn man versuchte, eines zu bauen, da es kein Beispiel für irgendetwas gab a Quantencomputer könnte das tun a klassischer Computer konnte nicht.
Indem gezeigt wird, wie a Quantencomputer könnte tatsächlich so nützlich sein, dass klassische Computer konnte nicht durch Lösen eines klassisch unlösbaren Problems in Polynomzeit , Peter Shor weckte die Interessen von Forschern auf der ganzen Welt, die ihre eigenen Forschungen begonnen haben Quantencomputer und jetzt sind es tatsächlich funktionierende Quantencomputer wird gebaut . Es wird mindestens ein Jahrzehnt dauern, bis ein Quantencomputer genug Qubits hat, um zu brechen RSA-Verschlüsselung aber sein Ende ist sicher und Kryptographen haben bereits neue Wege der Forschung eröffnet Post-Quanten-Kryptographie um sicherzustellen, dass alles, was sicher bleiben muss, funktioniert.
nach Peter Shors Algorithmus hat bewiesen, dass schwierige Probleme für klassische Computer könnte gelöst werden, andere haben begonnen, sich mit anderen schwierigen Problemen zu befassen, die möglicherweise auch von Quantencomputern gelöst werden könnten, und das aus gutem Grund; von den vielen noch zu lösenden Problemen ist der potenzielle Nutzen ihrer Lösung ebenso enorm wie die Probleme selbst.
Der fünfte Artikel in unserer Reihe über Algorithmen und Berechnungen Algorithmen, Optimierung und das Problem des Handlungsreisenden , kann gefunden werden hier .