Anleitung
Erstelle eine Implementierung der affinen Chiffre, eines alten Verschlüsselungssystems, das im Nahen Osten entstanden ist.
Die affine Chiffre ist eine Art monoalphabetischer Substitutionschiffre.
Jedes Zeichen wird auf sein numerisches Äquivalent abgebildet, mit einer mathematischen Funktion verschlüsselt und dann in den Buchstaben umgewandelt, der zu seinem neuen numerischen Wert gehört.
Obwohl alle monoalphabetischen Chiffren schwach sind, ist die affine Chiffre deutlich stärker als die Atbash-Chiffre, weil sie viel mehr Schlüssel besitzt.
Verschlüsselung
Die Verschlüsselungsfunktion lautet:
E(x) = (ai + b) mod m
Wobei:
-
i ist der Index des Buchstabens von 0 bis zur Länge des Alphabets - 1.
-
m ist die Länge des Alphabets.
Beim römischen Alphabet ist m gleich 26.
-
a und b sind Ganzzahlen, die den Verschlüsselungsschlüssel bilden.
Die Werte a und m müssen teilerfremd (oder relativ prim) sein, damit die automatische Entschlüsselung gelingt. Das heißt, sie haben die Zahl 1 als einzigen gemeinsamen Teiler (mehr dazu findest du im Wikipedia-Artikel über teilerfremde ganze Zahlen).
Falls a nicht teilerfremd zu m ist, sollte dein Programm anzeigen, dass dies ein Fehler ist.
Andernfalls sollte es mit dem angegebenen Schlüssel ver- oder entschlüsseln.
Für diese Übung sind Ziffern gültige Eingaben, aber sie werden nicht verschlüsselt.
Leerzeichen und Satzzeichen sind ausgeschlossen.
Der Geheimtext wird in Gruppen fester Länge geschrieben, die durch ein Leerzeichen getrennt sind. Die traditionelle Gruppengröße beträgt 5 Buchstaben.
Dadurch ist es schwieriger, den verschlüsselten Text anhand von Wortgrenzen zu erraten.
Entschlüsselung
Die Entschlüsselungsfunktion lautet:
D(y) = (a^-1)(y - b) mod m
Wobei:
-
y ist der numerische Wert eines verschlüsselten Buchstabens, also y = E(x)
- wichtig ist, dass
a^-1 das modulare multiplikative Inverse (MMI) von a mod m ist
- das modulare multiplikative Inverse existiert nur, wenn
a und m teilerfremd sind.
Das MMI von a ist das x, für das der Rest bei Division von ax durch m gleich 1 ist:
ax mod m = 1
Mehr darüber, wie du ein modulares multiplikatives Inverses findest und was es bedeutet, findest du im zugehörigen Wikipedia-Artikel.
Allgemeine Beispiele
- Das Verschlüsseln von
"test" ergibt "ybty" mit dem Schlüssel a = 5, b = 7
- Das Entschlüsseln von
"ybty" ergibt "test" mit dem Schlüssel a = 5, b = 7
- Das Entschlüsseln von
"ybty" ergibt "lqul" mit dem falschen Schlüssel a = 11, b = 7
- Das Entschlüsseln von
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" ergibt "thequickbrownfoxjumpsoverthelazydog" mit dem Schlüssel a = 19, b = 13
- Das Verschlüsseln von
"test" mit dem Schlüssel a = 18, b = 13 ist ein Fehler, weil 18 und 26 nicht teilerfremd sind
Beispiel für das Finden eines modularen multiplikativen Inversen (MMI)
Das MMI für a = 15 finden:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, d. h. 105 mod 26 = 1
-
7 ist das MMI von 15 mod 26
