Monat: Januar 2018

2018

2018_KratzerHintergrund 2018 ist eine unscheinbare Zahl. Da lohnt sich ein Ausflug in die Zahlentheorie kaum. Wir versuchen es trotzdem:  2018 hat nur zwei Primfaktoren (2018 = 2·1009), ist also eine Fast-Primzahl. Was macht man, wenn man mehr wissen will? Man schaut in der OEIS nach, der Online Encyclopedia of Integer Sequences1. Dort findet man die übrigen Fast-Primzahlen mit nur zwei Primfaktoren (Semiprimes) unter der Nummer A001358.  Die Folge beginnt mit 4, 6, 10, 14, 15, … In den Bemerkungen zu A001358  liest man, dass große Semiprimes mit verschiedenen Primfaktoren in der RSA-Verschlüsselung benutzt werden. Es geht um Zahlen mit beispielsweise 129 Ziffern (RSA-129) – oder noch mehr Ziffern (RSA-140, …). In dieser Liga spielt 2018 natürlich nicht, zur Familie gehört sie aber.

Deshalb ein kleiner Spaß: Wir RSA-verschlüsseln einen Text mit n = 2018, also p = 2 und q = 1009 (n = p·q). Als zweite Zahl des öffentlichen Schlüsselpaares (n, e) wählen wir e = 521 (Eine willkürliche Wahl, e muss aber teilerfremd zum Wert φ (2018) = (p – 1)·(q – 1) = 1·1008 der Eulerfunktion sein). Wir verschlüsseln also gemäß  y = xe mod n = x521 mod 2018. Dabei ist x das Klartextzeichen, y das entsprechende Zeichen der verschlüsselten Nachricht. Unser Klartext sei ASCII-codiert, er besteht damit aus Blöcken x mit je zwei Ziffern. Der Einfachheit halber beschränken wir uns auf den Bereich der ASCII-Codes 32..90. Der Großbuchstabe „A“ (ASCII-Code x = 65) beispielsweise wird zu y = 65521 mod 2018 = 483 verschlüsselt. Um den Zeichen des verschlüsselten Textes eine einheitliche Länge von 4 Stellen zu geben, fügen wir bei dreistelligen Zahlen y links eine Null hinzu. Unsere gesamte verschlüsselte Nachricht lautet (jeder 4-er Block stellt ein verschlüsseltes zweistelliges ASCII-Zeichen dar)2:

0483 0718 0718 0823 0395 1270 0557 0587 1986 0823 1270 1462 0587 0823 1036 1270 0398 0174 0225 1970

Zum Entschlüsseln benötigen wir den geheimen Schlüssel. Der setzt sich zusammen aus n = 2018 und einer Zahl d,  die der Bedingung genügt d·e  =  1 mod φ (2018) = 1 mod 1008. Das führt zu d = 89. Die ASCII-Zeichen des Klartextes werden also mit Hilfe von x = y89 mod 2018 zurückgewonnen. Beispiel: Das Zeichen y = 0483 des verschlüsselten Textes wird zu x = 48389 mod 2018 = 65 im Klartext, also zum vorhin verschlüsselten „A“. Und jetzt die Hausaufgabe: wie lautet die obige Nachricht im Klartext? Ein guter Taschenrechner und eine ASCII-Tabelle wären bei der Lösung hilfreich3. Knobeln führt vielleicht auch zum Ziel – Spaß muss sein.

https://oeis.org
Nochmals: Dies ist ein kleiner Scherz, keine ernsthafte Verschlüsselung.
Beim Taschenrechner TI-nspire z. B. gibt man ein mod(43889, 2018) und erhält sofort 65 als Ergebnis.