RSA-Verschlüsselung: Schritt 3

- Vor über 2000 Jahren zeigte Euklid, dass es für jede Zahl genau eine Primfaktorzerlegung gibt, die wir uns wie einen geheimen Schlüssel vorstellen können. Es stellt sich heraus, dass die Primfaktorzerlegung eine grundlegend "schwierige Aufgabe" ist. Lass uns klären, was wir mit "leicht" und "schwierig" meinen, indem wir das einführen, was man als "Zeitkomplexität" bezeichnet. Wir alle haben schon einmal Zahlen multipliziert. Und es gibt unterschiedliche Wege, um Dinge einfacher auszurechnen. Wenn wir einen Computer programmieren, um Zahlen zu multiplizieren, kann er das viel schneller tun, als jeder Mensch es kann. Hier ist eine Grafik. Sie zeigt die benötigte Zeit, die ein Computer für die Multiplikation zweier Zahlen benötigt. Und natürlich auch die Zeit, die es benötigt, um die Antwort zu finden, je größer die Zahlen werden. Beachte, dass die Berechnungszeit deutlich unter einer Sekunde bleibt, auch bei ziemlich großen Zahlen. Daher ist es "einfach" durchzuführen. Vergleiche dies nun mit der Primfaktorzerlegung. Wenn dir jemand sagt, dass du die Primfaktorzerlegung von 589 zu finden, wirst du merken, dass die Aufgabe schwieriger ist. Egal, wie deine Strategie aussieht, du wirst einige Versuche und Fehler machen müssen, bis du eine Zahl findest, die 589 gleichmäßig teilt. Nach einigem Ringen wirst du feststellen, dass 19 mal 31 die Primfaktorzerlegung ist. Wenn du die Aufgabe hättest, die Primfaktorzerlegung von 437'231 zu finden, würdest du wahrscheinlich aufgeben und einen Computer um Hilfe bitten. Bei kleinen Zahlen funktioniert das gut. Aber wenn wir einen Computer hinzunehmen, um immer größere Zahlen zu faktorisieren, gibt es einen Runaway-Effekt. Die Zeit, die es für die Berechnungen benötigt, steigt rapide an, da es mehrere Schritte gibt. Wenn die Zahlen wachsen, braucht der Computer Minuten, dann Stunden, und schließlich benötigt er Hunderte oder Tausende von Jahre, um große Zahlen zu berechnen. Deshalb sagen wir, es ist ein "schwieriges" Problem, und zwar aufgrund der zunehmenden Zeit, die für die Lösung des Problems benötigt wird. Die Faktorisierung ist also das, was Cocks verwendet hat, um die Lösung der Falltür zu finden. Schritt eins: Stell dir vor, Alice erzeugt zufällig eine Primzahl mit mehr als 150 Ziffern; nenne dies "P1". Dann, eine zweite Randon-Primzahl, die ungefähr die gleiche Größe hat. Nenne sie "P2". Dann multipliziert sie diese beiden Primzahlen miteinander, um eine zusammengesetzte Zahl, N, zu erhalten, die über 300 Ziffern lang ist. Dieser Multiplikationsschritt würde weniger als eine Sekunde dauern. Wir könnten ihn sogar in einem Webbrowser durchführen. Dann nimmt sie die Faktorisierung von N, P1 mal P2 und versteckt sie. Wenn sie nun N an jemand anderen weitergeben würde, müsste derjenige den Computer für Jahre laufen lassen, um die Lösung zu finden. Schritt zwei: Cocks musste eine Funktion finden, die von der Kenntnis der Faktorisierung von N abhängt. Hierfür griff er auf Arbeiten des Schweizer Mathematikers Leonard Euler aus dem Jahre 1760 zurück.