RSA-Verschlüsselung: Schritt 4

Wir haben jetzt eine Falltür zum Lösen von Phi. Wenn du die Faktorisierung für N kennst, dann ist das Finden von Phi N einfach. Zum Beispiel ist die Primfaktorzerlegung von 77 sieben mal 11. Also ist Phi von 77 sechs mal zehn, 60. Schritt drei. Wie verbindet man die Phi-Funktion mit modularer Exponentiation. Dafür wandte er sich an den Satz von Euler, welcher eine Beziehung zwischen der Phi-Funktion und modularer Exponentiation ist. Und zwar wie folgt: m hoch Phi n, ist kongruent zu 1 mod n. Das bedeutet, dass du zwei beliebige Zahlen auswählen kannst, so dass sie keinen gemeinsamen Faktor haben, nennen wir sie "m" und "n". Sagen wir m ist gleich fünf und n ist gleich acht. Wenn du nun m mit phi n, also 4, potenzierst und durch n teilst, bleibt immer 1 übrig. Jetzt müssen wir diese Gleichung nur noch abändern, indem wir zwei einfache Regeln anwenden. Erstens: Wenn du die Zahl 1 zu irgendeinem Exponenten k potenzierst, erhältst du immer 1. Auf dieselbe Weise können wir den Exponenten Phi n mit einer beliebigen Zahl k multiplizieren, und die Lösung ist immer noch 1. Zweitens: Multiplizierst du 1 mit einer beliebigen Zahl, zum Beispiel m, ergibt das immer m. Auf dieselbe Weise können wir die linke Seite mit m multiplizieren, um m auf der rechten Seite zu erhalten. Und das kann vereinfacht werden als m hoch k, mal phi n, plus 1. Das ist der Durchbruch. Wir haben jetzt eine Gleichung zum Auffinden von e mal d, die von Phi n abhängt. Daher ist es einfach, d zu berechnen, nur wenn die Faktorisierung von n bekannt ist. Das bedeutet, dass d der private Schlüssel von Alice sein sollte. Es ist die Falltür, die es ihr ermöglicht, die Wirkung von e rückgängig zu machen. Lass uns ein einfaches Beispiel machen, um all dies in Aktion zu sehen. Sagen wir, Bob hat eine Nachricht, die er in eine Zahl mit einem Padding-Schema umwandelt. Nennen wir das "m". Dann erzeugt Alice ihren öffentlichen und privaten Schlüssel wie folgt: Zuerst generiert sie zwei zufällige Primzahlen von ähnlicher Größe und multipliziert sie, um n, 3127, zu erhalten. Dann kann sie phi von n leicht berechnen, da sie die Faktorisierung von n kennt, die sich als 3016 herausstellt. Als nächstes wählt sie einen kleinen öffentlichen Exponenten, e, mit der Bedingung, dass es eine ungerade Zahl sein muss, die sich keinen Faktor mit phi n teilt. In diesem Fall wählt sie e gleich drei. Schließlich findet sie den Wert ihres privaten Exponenten, d, der in diesem Fall zwei mal Phi von n plus eins, geteilt durch drei, also 2011. Jetzt versteckt sie alles außer dem Wert von n und e, weil n und e ihren öffentlichen Schlüssel bilden. Stell dir das wie ein offenes Schloss vor. Sie schickt dies an Bob, um seine Nachricht damit zu verschlüsseln. Bob verschlüsselt seine Nachricht, indem er m potenziert mit e, mod n. Nennen wir das "c", seine verschlüsselte Nachricht, die er an Alice zurückschickt. Schließlich entschlüsselt Alice seine Nachricht mit ihrem privaten Schlüssel, d, den sie durch ihre Falltür erreicht. c hoch d mod n ergibt Bobs ursprüngliche Nachricht, m. Beachte, dass Eva oder jemand anderes, mit c, n und e, den Exponenten d nur finden kann, wenn sie Phi n berechnen können, was voraussetzt, dass sie die Primfaktorzerlegung von n kennen. Wenn n groß genug ist, kann Alice sicher sein, dass dies Hunderte von Jahren dauern wird, selbst mit dem leistungsfähigsten Netzwerk von Computern. Dieser Trick wurde sofort nach seiner Veröffentlichung als geheim eingestuft. Aber es wurde unabhängig davon 1977 von Ron Rivest, Adi Shamir und Len Adleman wiederentdeckt. Deshalb ist es heute als RSA-Verschlüsselung bekannt. RSA ist der am häufigsten verwendete öffentliche Schlüssel-Algorithmus der Welt und die am häufigsten kopierte Software in der Geschichte. Jeder Internetnutzer auf der Welt verwendet RSA, oder eine Variante davon, ob sie es merken oder nicht. Seine Stärke beruht auf der Schwierigkeit der Primfaktorzerlegung, die ein Ergebnis tiefgründiger Fragen über die Verteilung von Primzahlen ist. Eine Frage, die seit Tausenden von Jahren ungelöst geblieben ist. ...