Station - RSA-Kryptosystem

Zielsetzung

Die Implementierung des RSA-Verfahrens im Abschnitt Station - Implementierung ist recht einfach gehalten. Zum einen benutzt sie ein eingeschränktes Textalphabet und ein einfaches Codierungsverfahren, um Zeichenketten in Zahlen und umgekehrt umzuwandeln. Zum anderen benutzt sie eine fest vorgegebene Blocklänge bei der Umwandlung von Zeichen in Zahlen. Realitätsnäher ist es, die Blocklänge aus dem benutzten Schlüssel zu generieren.

Ziel dieses Abschnitts ist es, eine Implementierungsmöglichkeit aufzuzeigen, die diese Einschränkungen nicht hat und somit realen Kryptosystemen näher kommt. Die hierzu entwickelten Funktionen sind in der Datei kryptosystem_rsa.txt zusammengefasst.

Das Implementierungsverfahren

Je nach Verwendungskontext können Texte, die verschlüsselt werden sollen, eine Reihe von Sonderzeichen enthalten. So enthält ein Text in deutscher Sprache in der Regel Umlaute und das "ß".

Es ist daher sinnvoll, einen Text gemäß einer vorgegebenen Codierung erst einmal in eine Bytefolge umzuwandeln.

In Python kann man hierzu die Funktion bytes benutzen:

>>> bytes('öffentlicher Schlüssel', 'utf8')
b'\xc3\xb6ffentlicher Schl\xc3\xbcssel'
>>> list(bytes('öffentlicher Schlüssel', 'utf8'))
[195, 182, 102, 102, 101, 110, 116, 108, 105, 99, 104, 101, 114, 32, 83, 99, 104, 108, 195, 188, 115, 115, 101, 108]

Aus einer Liste aus Bytes (dargestellt als Zahlen aus dem Bereich 0..255) kann man jetzt die Zahlen erzeugen, die letztlich vom RSA-Verfahren verarbeitet werden. Hierbei muss allerdings beachtet werden, dass die zu verarbeitenden Zahlen kleiner als die Zahl n eines Schlüsselpaares (e, n) oder (d, n) sind.

Eine Byteliste lässt sich recht einfach in eine natürliche Zahl umwandeln. Man benutzt die Bytezahlen als Ziffern im 256-er-System. Im Fall der Byteliste [195, 182, 102, 102, 101] erhält man:

>>> 195*256**4 + 182*256**3 + 102*256**2 + 102*256**1 + 101*256**0
840578786917

Damit die so erzeugte Zahl z die Bedingung z < n erfüllt, muss die Anzahl der Bytezahlen, die zur Erzeugung von z benutzt werden, eingeschränkt werden. Für die Anzahl b der Bytezahlen muss die Bedingung 256^b-1 < n gelten. Wenn z.B. n = 3001122295343 vorgegeben ist, so erhält man b = 5 als maximale Byteanzahl. Die Zahl b legt demnach die Byte-Blocklänge fest.

Mit Hilfe einer geeigneten Funktion byteListToNatList (siehe kryptosystem_rsa.txt) kann man aus einer Liste von Bytes eine zugehörige Liste aus Zahlen bestimmen, die alle kleiner als die Zahl n sind.

>>> byteListToNatList([195, 182, 102, 102, 101, 110, 116, 108, 105, 99, 104, 101, 114, 32, 83, 99, 104, 108, 195, 188, 115, 115, 101, 108], 5)
[840578786917, 474399664483, 448378576979, 426953720764, 1936942444]

Auf die Zahlen aus dieser Liste kann man jetzt das RSA-Verfahren anwenden. Die Funktion verschluesselnNatList (siehe kryptosystem_rsa.txt) übernimmt diese Aufgabe:

>>> verschluesselnNatList([840578786917, 474399664483, 448378576979, 426953720764, 1936942444], (65537, 3001122295343))
[72747982529, 2240263624583, 2259248567474, 1280377051294, 841896324548]

Die Zahlenliste [72747982529, 2240263624583, 2259248567474, 1280377051294, 841896324548] stellt die verschlüsselte Nachricht dar. Wenn man sie verschicken möchte, ist es zweckmäßig, diese Zahlenfolge in eine Bytefolge umzuwandeln. Mit der Funktion natToByteList (siehe kryptosystem_rsa.txt) kann man das erledigen:

>>> natToByteList(72747982529)
[16, 240, 30, 30, 193]

Aber Achtung: Die erzeugte Byteliste kann unterschiedliche Längen haben - von 1 bis b+1. Auch eine Länge b+1 ist möglich, wie das folgende Beispiel zeigt.

>>> natToByteList(2259248567474)
[2, 14, 5, 181, 84, 178]

Um eine reibungslose Rückumwandlung in Zahlen zu gewährleisten, werden die Zahlen hier in Bytelisten der Länge b+1 umgewandelt. Gegebenenfalls werden führende Nullen ergänzt. Hierzu wird die Funktion natListToByteListErweitert (siehe kryptosystem_rsa.txt) benutzt:

>>> natListToByteListErweitert([72747982529, 2240263624583, 2259248567474, 1280377051294, 841896324548], 6)
[0, 16, 240, 30, 30, 193, 2, 9, 154, 30, 23, 135, 2, 14, 5, 181, 84, 178, 1, 42, 28, 107, 88, 158, 0, 196, 4, 238, 109, 196]

Aus der erzeugten Byteliste kann jetzt die Bytefolge produziert werden, die als Geheimcode zum Ausgangstext dient:

>>> bytes([0, 16, 240, 30, 30, 193, 2, 9, 154, 30, 23, 135, 2, 14, 5, 181, 84, 178, 1, 42, 28, 107, 88, 158, 0, 196, 4, 238, 109, 196])
b'\x00\x10\xf0\x1e\x1e\xc1\x02\t\x9a\x1e\x17\x87\x02\x0e\x05\xb5T\xb2\x01*\x1ckX\x9e\x00\xc4\x04\xeem\xc4'

Zum Entschlüsseln dieses Codes muss man den umgekehrten Weg gehen:

Zuerst wird aus der Bytefolge eine Liste aus Bytes erzeugt:

>>> list(b'\x00\x10\xf0\x1e\x1e\xc1\x02\t\x9a\x1e\x17\x87\x02\x0e\x05\xb5T\xb2\x01*\x1ckX\x9e\x00\xc4\x04\xeem\xc4')
[0, 16, 240, 30, 30, 193, 2, 9, 154, 30, 23, 135, 2, 14, 5, 181, 84, 178, 1, 42, 28, 107, 88, 158, 0, 196, 4, 238, 109, 196]

Anschließend werden die Bytes in Zahlen umgewandelt. Hier muss natürlich die benutzte Blocklänge berücksichtigt werden.

>>> byteListToNatList([0, 16, 240, 30, 30, 193, 2, 9, 154, 30, 23, 135, 2, 14, 5, 181, 84, 178, 1, 42, 28, 107, 88, 158, 0, 196, 4, 238, 109, 196], 6)
[72747982529, 2240263624583, 2259248567474, 1280377051294, 841896324548]

Wenn man über den privaten Schlüssel verfügt, lassen sich die Zahlen mit dem RSA-Verfahren wie folgt "entschlüsseln". Beachte, dass hierzu dieselbe Funktion, die auch zum Verschlüsseln benutzt wird, zum Einsatz kommt:

>>> verschluesselnNatList([72747982529, 2240263624583, 2259248567474, 1280377051294, 841896324548], (2384015708753, 3001122295343))
[840578786917, 474399664483, 448378576979, 426953720764, 1936942444]

Die Zahlen werden jetzt wieder in Bytelisten übersetzt:

>>> natListToByteList([840578786917, 474399664483, 448378576979, 426953720764, 1936942444])
[195, 182, 102, 102, 101, 110, 116, 108, 105, 99, 104, 101, 114, 32, 83, 99, 104, 108, 195, 188, 115, 115, 101, 108]

Aus den Bytes gewinnt man wieder den Quelltext:

>>> str(bytes([195, 182, 102, 102, 101, 110, 116, 108, 105, 99, 104, 101, 114, 32, 83, 99, 104, 108, 195, 188, 115, 115, 101, 108]), 'utf8')
'öffentlicher Schlüssel'

Aufgabe 1

Teste die Funktionen der Datei kryptosystem_rsa.txt anhand eines selbst gewählten Beispiels.

Aufgabe 2

Mit dem Testprogramm rsa_test1.txt kannst du verschiedene Texte ver- und wieder entschlüsseln. Probiere das selbst aus.

Aufgabe 3

Das Testprogramm in rsa_test2.txt zeigt, wie man einen Text aus einer Textdatei verschlüsseln und den Code in einer neuen Datei abspeichern kann. Ebenso ist eine entschlüsselung des Codes möglich. Probiere das selbst aus.