Der RSA-Algorithmus - am Beispiel erklärt
Stellen Sie sich einmal vor, Sie sind männlich und haben seit Anfang des Schuljahres einen Schwarm. Sie sieht so gut aus, dass jeder gern etwas mit ihr hätte. Sie kommen aber nicht an Ihren Schwarm heran, weil sie immer in Begleitung von drei unangenehmen Freundinnen ist.
Sie entscheiden sich daher, auf den Valentinstag zu warten und ihr dann eine Karte zu schicken.
Am schönsten wäre es ja, Ihr Schwarm liest die Karte und lädt Sie zu einem Essen bei Kerzenschein ein.
Seien Sie aber mal ehrlich, das ist sehr unwahrscheinlich. Ihr Schwarm wird mehrere Karten erhalten und sich auf einen anderen Verehrer einlassen, oder die drei unangenehmen Freundinnen Ihres Schwarms fischen Ihre Karte aus dem Haufen heraus.
Und nun stehen Sie völlig nackt da, Ihre Gefühle stehen auf einer Valentinskarte und die ganze Welt wird davon erfahren.
Noch ist aber Zeit bis zum Valentinstag. Sie können sich ja eine elegante Lösung ausdenken. Nur wie stellt man es an, seinem Schwarm die Liebe zu gestehen, ohne das die Herumstehenden etwas davon merken.
Ihr Schwarm leidet natürlich auch an dem Kommunikationsproblem. Sie hätte die Lage ja gern einmal abgecheckt, nur keiner traut sich, seine Gefühle zu offenbahren.
Da hat Ihr Schwarm eine Idee. Sie schreibt auf kleine Papierschnipsel immer zwei Zahlen und verteilt sie kurz vor Valentinstag an alle die sie trifft. Auch Sie sind in den Besitz eines Zettels gelangt.
| Das steht auf der Vorderseite | Das steht auf der Rückseite | ||
|
3 15 |
Du hast zwei Zahlen von mir. Mit diesen zwei Zahlen kannst Du Deine Botschaft verschlüsseln. |
||
| Anleitung | Beispiel mit dem Buchstaben "L" | ||
|
L = 12 | ||
|
123 = 1728 | ||
|
1728 : 15 = 115 Rest 3 | ||
|
Schreibe die Reste nacheinander auf. Nun ist Deine Nachricht verschlüsselt |
aus L wird also 3 | ||
Aufgabe
Suchen Sie sich einen Schwarm aus Ihrer Klasse und schreiben Sie ihm eine Botschaft mit den Codezahlen 3 und 15.
Versuchen Sie die Nachricht eines vermeintlichen Nebenbuhlers zu entschlüsseln.
Sicherlich werden Sie sich fragen, wie Ihr Schwarm auf die Zahlen 3 und 15 gekommen ist und wie man die Nachricht entschlüsseln kann. Lesen Sie dafür die folgende Anleitung und Sie wissen es.
|
|
Beispiel |
Bemerkung |
|
Wir benötigen zwei Primzahlen P und Q |
P=3 Q=5 |
|
|
|
|
|
|
Nun brauchen wir noch eine Zahl E, die folgende Bedingungen erfüllen muss: |
|
|
|
PQ=15 |
Teil von Public Key und Secret Key |
|
(P-1)(Q-1)=8 |
|
|
E=3 |
Public Key |
|
Nun müssen wir noch eine Zahl D bestimmen. Diese muss folgende Bedingungen erfüllen: |
|
|
D= (X(P-1)(Q-1)+1)/E |
In unserem einfachen Fall kann X=4 gewählt werden.
D=(4*2*4+1)/3=33/3 D=11.
Damit gilt für DE=33. Die Probe ist 33/8=4 Rest 1. |
Secret Key |
Verschlüsselung
Die Rechenvorschrift für die Verschlüsselung lautet:
C=KE mod PQ
Die Zeile sagt lediglich: Potenziere den Klartext mit E, teile das durch PQ und gib den Rest als Ciphertext aus. Nehmen wir mal an, wir wollen folgende Zahlenreihe verschlüsseln:
12 13 05 08
Die Ciphertexte wären demnach:
|
123= 1728 |
1728/15 = 115 Rest 03 |
|
133= 2197 |
2197/15 = 146 Rest 07 |
|
053= 125 |
125/15 = 8 Rest 05 |
|
083= 512 |
512/15 = 34 Rest 02 |
Das Ergebnis ist dann:
03 07 05 02
Entschlüsselung
Die Rechenvorschrift für die Entschlüsselung lautet:
K=CD mod PQ
Die Mathematik ist exakt die gleiche wie bei der Verschlüsselung. Rechnen wir mal den Ciphertext zurück:
03 07 05 02
0311= 177147 |
177147/15= 11809 Rest 12 |
0711= 1977326743 |
1977326743/15= 131821782 Rest 13 |
0511= 48828125 |
48828125/15= 3255208 Rest 05 |
|
0211=2048 |
2048/15=136 Rest 08 |
Das Ergebnis ist dann:
12 13 05 08