RSA-Verschlüsselung: Schritt 2

Die Lösung wurde von einem anderen Briten gefunden, Mathematiker und und Kryptograph, Clifford Cocks. Cocks musste eine besondere Art von Einwegfunktion konstruieren, eine sogenannte Einwegfunktion mit Falltür. Dies ist eine Funktion, die leicht in eine Richtung zu berechnen ist, dabei aber schwer umkehrbar. Es sei denn, du hast eine spezielle Information, die sogenannte Falltür. Hierfür wandte er die modulare Exponentiation an, die wir als Uhrenarithmetik, im Diffie-Hellman-Schlüsselaustausch vorgestellt hatten. Dies funktioniert wie folgt. Nimm eine Zahl und erhöhe sie um einen Exponenten, teile sie durch den Modulo und erhalte den Rest. Dies kann man nutzen, um eine Nachricht wie folgt zu verschlüsseln: Stell dir vor, Bob hat eine Nachricht, die in eine Zahl, m, umgewandelt wird. Dann multipliziert er seine Zahl mit sich selbst, e mal, wobei e ein öffentlicher Exponent ist, dann dividiert er das Ergebnis durch eine Zufallszahl, N, und gibt den Rest der Division aus. Das Ergebnis ist eine Zahl, c. Diese Berechnung ist einfach durchzuführen, auch wenn man nur c, e und N braucht, ist es viel schwieriger zu bestimmen, welches m verwendet wurde, denn wir müssten auf eine Art von Versuch und Irrtum zurückgreifen. Dies ist also unsere Einwegfunktion, die wir auf m anwenden können, leicht auszuführen, aber schwer umkehrbar. Das ist unser mathematisches Schloss. Nun, wie wäre es mit einem Schlüssel? Der Schlüssel ist die Falltür, ein Stück Information, die es einfacht macht, die Umkehrung der Verschlüsselung vorzunehmen. Wir müssen c mit einem anderen Exponenten potenzieren, sagen wir d. Das macht die ursprüngliche Operation an m rückgängig und gibt uns die eigentliche Nachricht m. Also sind beide Operationen zusammen, dasselbe wie m hoch e, potenziert mit d, was dasselbe ist wie: m hoch e mal d, e ist die Verschlüsselung, d ist die Entschlüsselung. Deshalb brauchen wir eine Möglichkeit für Alice, e und d zu konstruieren, was es schwierig macht für alle anderen, d zu finden Dies erfordert eine zweite Einwegfunktion, die zur Erzeugung von d verwendet wird. Und dafür griff er auf Euklid zurück.