Szenario zur RSA-Demo (Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo)

Im folgenden wird ein Szenario für die RSA-Demonstration vorgestellt. Das Szenario beinhaltet die Erzeugung von Primzahlen, die RSA-Demo und die Faktorisierung (Zerlegung in Primfaktoren) von natürlichen Zahlen.

Die Veranschaulichung durch viele Bildschirmfotos erleichtert das Nachvollziehen der mit CrypTool durchgeführten Schritte. Weitere Informationen finden Sie unter RSA-Verschlüsselung und unter Dialog RSA-Demo.

Beim RSA-Verfahren werden nicht nur die Funktionsweise, sondern auch die Einzelschritte zur Durchführung des RSA-Verfahrens anhand kleiner Zahlen beschrieben.

Dieses Szenario besteht aus drei Teilen

  1. Der Erzeugung eines RSA-Schlüssels,

  2. Dem Ver- und Entschlüsseln von Nachrichten und
  3. Dem Angriff auf das RSA-Verfahren.

1. Erzeugen von RSA-Schlüsseln

Wir wollen zunächst einen RSA-Schlüssel erzeugen. Öffnen Sie hierzu den Dialog unter Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo.

dialogrsa-kryptosystem1.gif

Für den RSA-Schlüssel benötigen wir als erstes zwei unterschiedliche Primzahlen p und q. Sie können zwei Primzahlen in die Felder Primzahl p und Primzahl q eingeben, oder Sie können zwei zufällige Primzahlen p und q generieren lassen.

Als Beispiel wollen wir einen zufälligen 256-Bit RSA-Schlüssel erzeugen. Klicken Sie dafür den Button Primzahlen generieren....
Wie unter dem Menü Einzelverfahren \ RSA-Kryptosystem \ Primzahlen generieren... öffnet sich der Dialog zum Generieren von Primzahlen p und q. Wählen Sie für die Primzahl p als Untergrenze 2^127+2^126 und als Obergrenze 2^128 sowie für deren Wertebereich den Radiobutton Beide gleich. Wenn Sie den Button Primzahlen generieren klicken, werden zwei Primzahlen p und q mit einer Bitlänge zwischen 127,5 und 128 erzeugt. Die Multiplikation von p und q ergibt als Ergebnis das RSA-Modul N (Bitlänge größer als 2*127,5 = 255 - also ein 256-Bit RSA-Schlüssel).

rsaszenariopzgenerieren.gif

Sie können beliebig oft Primzahlen generieren. Durch den Button Primzahlen übernehmen werden die Primzahlen p und q in den RSA-Dialog übertragen. Gleichzeitig werden der RSA-Modul N sowie die Eulersche Phi-Funktion Phi(N) berechnet.

Als nächstes müssen Sie als öffentlichen RSA-Schlüssel e eine zu Phi(N) teilerfremde Zahl bestimmen. Es scheint manchmal nicht einfach solch eine Zahl zu finden. Deshalb ein kleiner Tipp: Die Primzahl e = 2^16+1 = 65537 (= 10000000000000001 binär) ist fast immer teilerfremd zu Phi(N).

dialogrsa-kryptosystem2.gif

Aus der Zahl e berechnet sich dann nach dem Klick auf dem Button Parameter aktualisieren der geheime RSA-Schlüssel d.

Sie können jetzt Nachrichten ver- und entschlüsseln.

2. Das Ver- oder Entschlüsseln von Nachrichten mit dem RSA-Schlüsselpaar

Haben Sie den RSA-Schlüssel erzeugt, dann können Sie Nachrichten ver- oder entschlüsseln. Wir wollen die verschiedenen Optionen des RSA-Verfahrens an den Beispielen aus dem Skript demonstrieren:

Beispiel aus dem Skript Kapitel 4.13.2: Verschlüsseln der Nachricht ATTACK AT DAWN:

Erzeugen Sie sich zunächst den RSA-Schlüssel: Geben Sie dazu die Parameter p=47, q=79 e=37 in den Dialog nach den Menüeinträgen Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo ein. Nach dem Klick auf Parameter aktualisieren werden die Parameter N = p*q = 3713, Phi(N) = 3588 und d = 97 berechnet.

Wählen Sie dann unter Optionen für Alphabet und Zahlensystem... den Radiobutton Alphabet vorgeben. Das voreingestellte Alphabet

" ABCDEFGHIJKLMNOPQRSTUVWXYZ"

codiert <BLANK> nach 0, A nach 1, ... und Z nach 26. Wählen Sie im Themenbereich "Verfahren bei der Codierung in Zahlen" die Option Basissystem und im Themenbereich "Blocklänge" die Blocklänge 2.

dialogrsaoptions1.gif

Übernehmen Sie die Optionen mit OK. Sie können jetzt den Eingabetext ATTACK AT DAWN in die Eingabezeile eingeben und den Button Verschlüsseln klicken.

dialogrsa-kryptosystem3.gif

Als Verschlüsselung erhalten Sie die Zahlenfolge

1404 # 2932 # 3536 # 0001 # 3284 # 2280 # 2235 

Das Zeichen '#' dient hierbei nur zur optischen Trennung der einzelnen Zahlen. Wenn Sie diese Zahlen in die Eingabezeile einfügen und dann Entschlüsseln wählen, erhalten Sie wieder den ursprünglichen Klartext.

dialogrsa-kryptosystem3b.gif

Beispiele aus dem Skript, Kapitel 4.13.3: Verschlüsselung der Nachricht RSA works!

Erzeugen Sie sich zunächst den RSA-Schlüssel: Geben Sie dazu die Parameter p=251, q=269 e=65537 in den Dialog nach den Menüeinträgen Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo ein. Nach dem Klick auf Parameter aktualisieren werden die Parameter N = p*q = 67519, Phi(N) = 67000 und d = 2473 berechnet.

  1. Verschlüsseln der Nachricht mit Blocklänge 1
  2. Wählen Sie dann unter Optionen für Alphabet und Zahlensystem... den Radiobutton Alle 256 Zeichen. Wählen Sie in der Gruppierung "Methode" die Option b-adisch und in der Gruppierung "Blocklänge" die Blocklänge 1.

    Übernehmen Sie die Optionen mit OK. Sie können jetzt den Eingabetext RSA works! in die Eingabezeile eingeben und den Button Verschlüsseln wählen.

    dialogrsa-kryptosystem4.gif

    Als Verschlüsselung erhalten Sie die Zahlenfolge

    58455 # 39103 # 16634 # 28092 # 58597 #
    65768 # 33441 # 20214 # 40199 # 03240

    Das Zeichen '#' dient hierbei nur zur optischen Trennung der einzelnen Zahlen. Wenn Sie diese Zahlen in die Eingabezeile einfügen und dann Entschlüsseln wählen, erhalten Sie wieder den ursprünglichen Klartext.

  3. Verschlüsseln der Nachricht mit Blocklänge 2
  4. Wählen Sie jetzt unter Optionen für Alphabet und Zahlensystem... den Radiobutton Alle 256 Zeichen. Wählen Sie in der Gruppierung "Methode" die Option b-adisch und in der Gruppierung "Blocklänge" die maximale Blocklänge 2.

    Wenn Sie jetzt die Nachricht "RSA works!" verschlüsseln, erhalten sie den nur halb so langen Chiffretext:

    03046 # 29337 # 62503 # 09978 # 40883

3. Der Angriff auf das RSA-Verfahren

Wir verdeutlichen den potentiell möglichen Angriff auf das RSA-Kryptosystem anhand von schon veröffentlichten Challenges, also Herausforderungen (meist öffentlichen Wettbewerben) zum Knacken von Chiffretexten. Neben dem Chiffretext ist dem Angreifer auch der öffentliche Schlüssel e und der RSA Modul N zugänglich.

Die folgenden Beispiele beschreiben Angriffe zur Faktorisierung des öffentlichen RSA-Moduls N. Ist die Faktorisierung erfolgreich, können alle geheimen Parameter des RSA-Kryptosystems berechnet werden, womit auch die Chiffretext-Challenge geknackt werden kann. Die bekanntesten Krypto-Challenges werden auf der Homepage von RSA Security Laboratories veröffentlicht (www.rsa.com) veröffentlicht.


Challenge 1 (Stinson) [vergleiche Skript, Kapitel 4.13.4]

Die von Professor Stinson in seinem Buch [Stinson1995, Exercise 4.6] vorgestellte Challenge können Sie auch mit CrypTool lösen:

Challenge:

Die 2 Komponenten des öffentlichen Schlüssels:

RSA-Modul N = 31313
Öffentlicher Exponent e = 4913

Chiffretext:

6340   8309 14010  8936 27358 25023 16481 25809
23614  7135 24996 30590 27570 26486 30388  9395
27584 14999  4517 12146 29421 26439  1606 17881
25774  7647 23901  7372 25774 18436 12056 13547
 7908  8635  2149  1908 22076  7372  8686  1304
 4082 11803  5314   107  7359 22470  7372 22827
15698 30317  4685 14696 30388  8671 29956 15705
 1417 26905 25809 28347 26277  7897 20240 21519
12437  1108 27106 18743 24144 10685 25234 30155
23005  8267  9917  7994  9694  2149 10042 27705
15930 29748  8635 23645 11738 24591 20240 27212
27486  9741  2149 29329  2149  5501 14015 30155
18154 22319 27705 20321 23254 13624  3249  5443
 2149 16975 16087 14600 27705 19386  7325 26277
19554 23614  7553  4734  8091 23973 14015   107
 3183 17347 25234  4595 21498  6360 19837  8463
 6000 31280 29413  2066   369 23204  8425  7792
25973  4477 30989

Die Aufgabenstellung dieser Challenge finden Sie auch im Skript zu CrypTool [4.13.4 Eine kleine RSA-Cipher-Challenge (1)].

Kryptoanalyse mittels CrypTool:

Die Analyse erfolgt in zwei Schritten: Zunächst werden mit der Faktorisierung die Primfaktoren des RSA-Moduls berechnet und daraus im zweiten Schritt der geheime Schlüssel zur Entschlüsselung der Nachricht bestimmt. Danach kann der Chiffretext mit dem geknackten geheimen Schlüssel entschlüsselt werden.

  1. Primfaktorzerlegung des RSA-Moduls:
    Per Einzelverfahren \ RSA-Kryptosystem \ Faktorisieren einer Zahl zerlegen Sie die natürliche Zahl N = 31313 in ihre Primfaktoren p und q.

    dialogfactorisation1.gif

    Interessant ist hier, welches Verfahren am schnellsten den RSA-Modul zerlegt hatte (hier die Brute-Force Methode). Kopieren Sie das Ergebnis der Faktorisierung (Markieren der Ausgabe und mit Strg-C in die Zwischenablage kopieren) in ein Textfeld.

  2. Berechnung des geheimen Schlüssels d aus der Primfaktorzerlegung von N und dem öffentlichen Schlüssel e:

    Mit Kenntnis der Primfaktoren p = 173 und q = 181 und des öffentlichen Schlüssels e = 4913 sind Sie nun in der Lage, den Chiffretext zu entschlüsseln:

    1. Öffnen Sie den Dialog per Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo:

    2. Fügen Sie die gefundenen Primfaktoren p = 173 und q = 181 und den öffentlichen Schlüssel e = 4913 ein.

    3. Klicken Sie den Button Parameter aktualisieren. Aus den Zahlen p und q wird die Eulersche Phi-Funktion Phi(N) = (p-1)*(q-1) berechnet und daraus bestimmt sich mit dem öffentlichen Schlüssel e der geheime RSA-Schlüssel d.

    4. Stellen Sie die folgenden Optionen ein, indem Sie auf den Button Optionen für Alphabet und Zahlensystem... klicken:

    5. dialogrsaoptions2.gif

    6. Geben Sie nun den Chiffretext im obersten Eingabefeld der unteren Gruppierung ein: Am schnellsten geht das, indem Sie den oben angegebenen Chiffretext markieren und mit Strg-C in die Zwischenablage kopieren. Mit Strg-V fügen Sie den Text in das Eingabefeld ein.

    7. Durch das Klicken des Buttons Entschlüsseln erhalten Sie den Klartext.


    8. dialogrsa-kryptosystem5.gif

Vollständig dargestellt lautet der Klartext:

LAKEWOBEGONISMOSTLYPOORSANDYSOILANDEVERYSPRINGTHEEARTHHEAVES
UPANEWCROPOFROCKSPILESOFROCKSTENFEETHIGHINTHECORNERSOFFIELDS
PICKEDBYGENERATIONSOFUSMONUMENTSTOOURINDUSTRYOURANCESTORSCHO
SETHEPLACETIREDFROMTHEIRLONGJOURNEYSADFORHAVINGLEFTTHEMOTHER
LANDBEHINDANDTHISPLACEREMINDEDTHEMOFTHERESOTHEYSETTLEDHEREFO
RGETTINGTHATTHEYHADLEFTTHEREBECAUSETHELANDWASNTSOGOODSOTHENE
WLIFETURNEDOUTTOBEALOTLIKETHEOLDEXCEPTTHEWINTERSAREWORSEZ

Die pure Lösung hat Prof. Stinson unter http://www.cacr.math.uwaterloo.ca/~dstinson/solns.html veröffentlicht.


Challenge 2 (Yan) [vergleiche Skript, Kapitel 4.13.5]

Mit CrypTool sind Sie in der Lage, die von Professor Yan in seinem Buch [Yan2000, Example 3.3.7, S. 318] vorgestellte Challenge zu lösen:

Challenge:

Die 2 Komponenten des öffentlichen Schlüssels:

RSA-Modul N = 63978486879527143858831415041
Öffentlicher Exponent e = 17579

Chiffretext:

45411667895024938209259253423,
16597091621432020076311552201,
46468979279750354732637631044,
32870167545903741339819671379

Die Aufgabenstellung dieser Challenge finden Sie auch im Skript zu CrypTool [4.13.5 Eine kleine RSA-Cipher-Challenge (2)].

Kryptoanalyse mittels CrypTool:

Die Analyse erfolgt in zwei Schritten: Zunächst werden mit der Faktorisierung die Primfaktoren des RSA-Moduls berechnet und daraus im zweiten Schritt der geheime Schlüssel zur Entschlüsselung der Nachricht bestimmt. Danach kann der Chiffretext mit dem geknackten geheimen Schlüssel entschlüsselt werden.

  1. Primfaktorzerlegung des RSA-Moduls:
    Per Einzelverfahren \ RSA-Kryptosystem \ Faktorisieren einer Zahl zerlegen Sie die natürliche Zahl N = 63978486879527143858831415041 in ihre Primfaktoren p und q.

    dialogfactorisation2.gif

    Interessant ist hier, welches Verfahren am schnellsten den RSA-Modul zerlegt hatte (hier das Quadratische Sieb). Kopieren Sie das Ergebnis der Faktorisierung (Markieren der Ausgabe und mit Strg-C in die Zwischenablage kopieren) in ein Textfeld.


  2. Berechnung des geheimen Schlüssels d aus der Primfaktorzerlegung von N und dem öffentlichen Schlüssel e:

    Mit Kenntnis der Primfaktoren p = 145295143558111 und q = 440334654777631 und des öffentlichen Schlüssels e = 17579 sind Sie nun in der Lage, den Chiffretext zu entschlüsseln:

    1. Öffnen Sie den Dialog per Einzelverfahren \ RSA-Kryptosystem \ RSA-Demo:

    2. Fügen Sie die gefundenen Primfaktoren p = 145295143558111 und q = 440334654777631 und den öffentlichen Schlüssel e = 17579 ein.

    3. Klicken Sie den Button Parameter aktualisieren. Aus den Zahlen p und q wird die Eulersche Phi-Funktion Phi(N) = (p-1)*(q-1)von dem RSA-Modul berechnet und daraus bestimmt sich mit dem öffentlichen Schlüssel e der geheime RSA-Schlüssel d.

    4. Stellen Sie die folgenden Optionen ein, indem Sie auf den Button Optionen für Alphabet und Zahlensystem... klicken:

    5. Geben Sie nun den Chiffretext im obersten Eingabefeld der unteren Gruppierung ein: Am schnellsten geht das, indem Sie den oben angegebenen Chiffretext markieren und mit Strg-C in die Zwischenablage kopieren. Mit Strg-V fügen Sie den Text in das Eingabefeld ein.

    6. Durch das Klicken des Buttons Entschlüsseln erhalten Sie den Klartext.

Kontrollieren Sie Ihr Ergebnis:

NATURAL NUMBERS ARE MADE BY GOD

Bemerkung:

Die zwei obigen Beispiele zum Angriff auf das RSA-Verfahren lassen sich auch ganz aus der Dialogbox RSA-Demo heraus durchführen. Sie sparen dadurch die manuelle Übernahme von Zahlenwerten zwischen den Masken.

Dazu starten Sie den Dialog per Einzelverfahren \ Das RSA-Kryptosystem \ RSA-Demo und klicken oben auf den zweiten Radiobutton, da Ihnen ja nur die öffentlichen Parameter bekannt sind. Danach klicken Sie auf RSA-Modul faktorisieren... .

rsaszenariomodulfactorisation.gif