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 256b-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.