Einfache Mathematik hinter der Public-Key-Kryptographie

Originalfassung von diese Geschichte erschien in Quanta-Magazin.

Wenn man über Jahrtausende hinweg eine geheime Nachricht senden wollte, gab es grundsätzlich eine Möglichkeit, dies zu tun. Verschlüsseln Sie Ihre Botschaft mithilfe spezieller Regeln, die nur Sie und Ihre Zielgruppe kennen. Diese Regel diente als Schlüssel. Wenn Sie den Schlüssel haben, können Sie die Nachricht entschlüsseln. Andernfalls müssen Sie es entsperren. einige Schlösser Es ist so effektiv, dass Sie es selbst dann nicht wählen könnten, wenn Sie unendlich viel Zeit und Ressourcen hätten. Aber selbst diese Systeme leiden unter der gleichen Achillesferse, die allen kryptografischen Systemen dieser Art zu schaffen macht. Es geht darum, den Schlüssel in die richtigen Hände zu bekommen, ohne ihn der falschen Person zu geben.

Dies wird als kontraintuitive Lösung bezeichnet. Public-Key-Kryptographiesetzt darauf, den Schlüssel allgemein verfügbar zu machen, anstatt ihn geheim zu halten. Der Trick besteht darin, einen zweiten Schlüssel zu verwenden, den Sie niemals weitergeben, selbst nicht mit den Personen, mit denen Sie kommunizieren. Nur durch die Kombination dieser beiden Schlüssel (einem öffentlichen und einem privaten) können Nachrichten sowohl verschlüsselt als auch entschlüsselt werden.

Um zu verstehen, wie das funktioniert, kann man sich den „Schlüssel“ leicht nicht als einen Gegenstand vorstellen, der in das Schloss passt, sondern als zwei komplementäre Elemente in unsichtbarer Tinte. Das erste Element löscht die Nachricht und das zweite Element zeigt die Nachricht erneut an. Wenn ein Spion namens Boris seiner Amtskollegin Natasha eine geheime Nachricht senden möchte, schreibt er die Nachricht und versteckt sie mit dem ersten Element auf der Seite. (Das ist für ihn einfach; Natasha hat eine einfache und berühmte Formel zum Löschen von Tinte veröffentlicht.) Als Natasha das Papier per Post erhält, trägt sie die zweite Zutat auf, die Boris‘ Botschaft wiedergibt.

Bei diesem Schema kann jeder Nachrichten ausblenden, aber nur Natasha kann sie wieder anzeigen. Und da sie die Formel für die zweite Zutat noch nie jemandem mitgeteilt hat (nicht einmal Boris), können wir sicher sein, dass die Botschaft nicht unterwegs entschlüsselt wurde. Als Boris eine geheime Nachricht erhalten möchte, geht er einfach genauso vor. Er veröffentlicht ein einfaches Rezept, um die Nachricht verschwinden zu lassen (das von Natasha oder jedem anderen verwendet werden kann), während er ein anderes Rezept für sich behält, um die Nachricht wieder erscheinen zu lassen.

In der Public-Key-Kryptographie fungieren der „öffentliche“ und der „private“ Schlüssel wie das erste und zweite Element dieser speziellen unsichtbaren Tinte. Einer verschlüsselt die Nachricht und der andere entschlüsselt sie. Doch statt Chemikalien verwendet die Public-Key-Kryptographie ein mathematisches Rätsel namens . Falltürfunktion. Diese Funktionen sind in einer Richtung leicht zu berechnen, in der entgegengesetzten Richtung jedoch sehr schwierig. Sie enthalten aber auch „Falltüren“, Informationen, die, sofern bekannt, die Berechnung von Funktionen in beide Richtungen erleichtern.

Eine übliche Falltürfunktion besteht darin, zwei große Primzahlen zu multiplizieren, und das ist einfach. Aber die Umkehrung, beginnend mit dem Produkt und der Suche nach jedem Primfaktor, ist rechnerisch unpraktisch. Um einen öffentlichen Schlüssel zu erstellen, beginnen Sie mit zwei großen Primzahlen. Das sind deine Falltüren. Multiplizieren Sie zwei Zahlen und führen Sie zusätzliche Operationen durch. mathematische Operationen. Mit diesem öffentlichen Schlüssel können Sie nun Nachrichten verschlüsseln. Um sie zu entschlüsseln, benötigen wir den entsprechenden privaten Schlüssel, der das Hauptelement enthält: die notwendige Falltür. Mit diesen Zahlen können Sie die Nachricht leicht entschlüsseln. Wenn Sie diese beiden Hauptfaktoren geheim halten, bleibt Ihre Botschaft geheim.