Im fünften Teil dieser Codebrecher-Mysteries geht es um ein asymmetrisches Verfahren der Kryptographie. In diesem Fall verwendet RSA (Rivest, Shamir und Adleman) ein Schlüsselpaar, um die zu übermittelnde Nachricht zu verbergen. Das Schlüsselpaar besteht aus einem öffentlichen Schlüssel, mit dem der Klartext zum Geheimtext verschlüsselt wird und einem privaten Schlüssel, welcher zum Entschlüsseln verwendet wird. Die Stärke dieser Verschlüsselung besteht darin, dass der öffentliche Schlüssel nur mit sehr großem Aufwand aus dem geheim gehaltenen privaten Schlüssel berechnet werden kann.
An dieser Stelle sei bemerkt, dass im Folgenden ein wenig Rechnerei notwendig ist. Dazu sind jedoch keine Spezialtools oder leistungsfähige Computer notwendig. Alle Zahlen sind so gewählt, dass das RSA Verfahren gemäß der folgenden Schritte mit einer Tabellenkalkulation (oder einem Taschenrechner und ein wenig Papier) leicht verstanden und nachvollzogen werden kann.
Beim RSA Verfahren wird der Klartext gemäß folgender Gleichung in einen Geheimtext verschlüsselt:
C = Me (mod N)
mit
C = Geheimtext,
M = Klartext,
N = p * q (p, q = Primzahlen),
e = Zahl.
Die Zahlen N und e werden als öffentlicher Schlüssel allen Freunden und Bekannten bekanntgegeben.
Die Entschlüsselung vom Geheimtext zum Klartext geschieht gemäß folgender Gleichung:
M = Cd (mod N)
mit
C = Geheimtext,
M = Klartext,
N = p * q (p, q = Primzahlen),
d = Zahl, Dechiffrierschlüssel.
Die Zahlen p, q und d sind der private Schlüssel.
Gegeben ist folgender Geheimtext (C):
53 – 173 – 107 – 5 – 213 – 150 – 40 – 209 -215 – 159 – 158 – 159 – 150 – 207 – 63 – 9 – 217 – 149 – 223 – 45 – 54 – 116 – 102 – 78 – 106 – 120 – 149 – 211 – 251 – 161 – 209 – 106 – 223 – 15 – 207 – 251 – 22 – 65 – 163 – 162 – 189 – 98 – 100 – 22 – 162 – 145 – 248 – 96 – 211 – 10 – 140 – 143 – 10 – 130 – 231 – 211 – 10 – 140 – 217 – 149 – 223 – 216 – 211 – 116 – 9 – 180 – 3 – 175 – 243 – 208 – 63 – 9 – 47 – 85 – 225 – 189 – 171 – 168 – 41 – 143 – 158 – 201 – 24 – 218
|
Entstanden ist der Geheimtext durch folgende Schritte:
- Klartext definieren (96 Zeichen)
- Klartext durch 7-Bit ASCII-Zeichen darstellen (672 Bit)
- ASCII-Bitfolge in 8-er Blöcke aufteilen (84 Stück 8-er Blöcke)
- 8-Bit Binärzahlen in Dezimalzahlen umrechnen (84 Zahlen zwischen 0 und 255)
- Zahlenfolge aus den Dezimalzahlen gemäß dem RSA-Verfahren verschlüsseln
Um den Klartext zu erhalten, musst Du Dich als Codebrecher beweisen. Zur Verschlüsselung wurde dieser öffentliche Schlüssel verwendet:
N = 253
e = 17
Bestimme zunächst einmal die zwei Primzahlen p und q:
N = p * q mit p < 50 und q < 50
p = ____, q = ____
Nun fehlt Dir noch der Dechriffierschlüssel d. Für d gilt:
d * e = 1 (mod (p-1)*(q-1))
Das sieht schwieriger aus, als es letztendlich ist. In der vorangegangen Gleichung steht nur, dass „D*E“ beim Teilen durch den Nebenmodul (Nebenmodul = (p-1) * (q-1)) den Rest 1 haben muss. Du kennst die Zahlen p, q und e. Nun benutze den o. g. Zusammenhang mit unterschiedlichen Zahlen für d (1 < d < 50), bis die Gleichung erfüllt ist.
Nebenmodul = ____, d = ____
Nun hast Du alle notwenigen Informationen zusammen, um die oben genannten Schritte 1 bis 4 rückgängig zu machen und damit den Geheimtext wieder in Klartext umzuwandeln.
Anmerkung:
Die Berechnung M = Cd (mod N) kann Folgendermaßen vereinfacht werden:
M = Cd (mod N) = [ {CX (mod N)} * {CY (mod N)} * {CZ (mod N)} ] (mod N)
mit d = X + Y + Z
|