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. 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.
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).
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).
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.
Ü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.
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.
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.
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.
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.
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.
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.
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... .