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"
  • Wandle jeden Buchstaben Deiner Nachricht in eine Zahl um, also a=1, b=2, ..., z=26

L = 12
  • Potenziere nun jede Zahl mit der ersten Codezahl.

123 = 1728
  • Dividiere jedes Ergebnis durch die zweite Codezahl und ermittle den Rest.

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:

 

 

  • E muss kleiner als der Wert sein, der sich ergibt, wenn man P und Q miteinander multipliziert (Produkt aus P und Q)

PQ=15

Teil von Public Key und Secret Key

  • E darf keine gemeinsamen Faktoren mit dem Produkt (P-1)(Q-1) haben

 (P-1)(Q-1)=8

 

  • E muss ungerade sein

E=3

Public Key

Nun müssen wir noch eine Zahl D bestimmen. Diese muss folgende Bedingungen erfüllen:

 

 

  • D darf nicht gleich E sein

  • DE muss durch ((P-1)(Q-1)) so teilbar sein, dass der Rest 1 bleibt.

  • Wie macht man das? Nun, eigentlich ganz einfach: man muss nur eine ganzzahlige Zahl X finden, die dafür sorgt, dass die folgende Gleichung ein ganzzahliges Ergebnis liefert:

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

 

 

Aufgabe

Legen Sie einen Public Key und den Secret Key fest, wenn Sie die folgenden Primzahlen verwenden:

 

P = 7
Q = 13