Affine Chiffre

Die affine Chiffre ist ein Verschlüsselungsverfahren, das jeden einzelnen Buchstaben des Klartextes nach einer linearen mathematischen Formel substituiert. Die affine Chiffre lässt sich zwar ohne größeren Aufwand berechnen, dafür ist sie allerdings nicht besonders sicher. Einerseits gibt es nur eine begrenzte Anzahl geheimer Schlüssel, sodass diese alle durchprobiert werden können. Andererseits kann der Geheimtext auch ohne Probieren entschlüsselt werden, sobald die Verschlüsselung von nur zwei Zeichen bekannt ist.

Verfahren

Lateinisches Alphabet

Dieser Abschnitt zeigt die Verwendung der affinen Chiffre für das lateinische Alphabet mit seinen 26 Buchstaben.

Geheimer Schlüssel

Sender und Empfänger müssen sich vor Verwendung der affinen Chiffre auf einen geheimen Schlüssel verständigen. Dieser Schlüssel ist ein Zahlenpaar $(a,b)$, wobei

• $a$ eine zu $k$, der Anzahl der Buchstaben des Alphabets (hier 26), teilerfremde Zahl zwischen 0 und $k$ ist (hier also eine der Zahlen 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 oder 25); und
• $b$ eine beliebige Zahl von 0 bis $k-1$ ist.

Wenn $a$ nicht teilerfremd zu $k$ ist, also $\operatorname {ggT} (a,k)>1$, dann ist die Abbildung nicht invertierbar, und der Geheimtext kann nicht eindeutig entschlüsselt werden. Das wäre hier bei geraden $a$ und bei $a=13$ der Fall.

Als Beispiel wird im Folgenden die Ver- und Entschlüsselung mit dem Schlüssel $(7,15)$ beschrieben.

Verschlüsselung

Zur Verschlüsselung werden die Buchstaben des Alphabets fortlaufend durchnummeriert: A=0, B=1, …. Man verschlüsselt jeden Buchstaben einzeln, indem man seinen Zahlenwert $x$ mit $a$ multipliziert und anschließend $b$ addiert. Das Ergebnis teilt man dann durch $k$.

$(a\cdot x+b):k$

Der bei dieser Division auftretende Rest ist die Nummer des verschlüsselten Buchstabens.

Will man beispielsweise den Buchstaben S, dem die Zahl 18 zugeordnet ist, mit dem Schlüssel $(7,15)$ verschlüsseln, so berechnet man

$(7\cdot 18+15):26=141:26=5\,\operatorname {Rest} \,11$

Das S wird also durch das L (den Buchstaben mit der Nummer 11) ersetzt.

Entschlüsselung

Zu jeder Zahl $a$ des Schlüssels gibt es eine zweite Zahl $a^{-1}$, die der folgenden Tabelle entnommen werden kann.

$a$:	1	3	5	7	9	11	15	17	19	21	23	25
$a^{-1}$:	1	9	21	15	3	19	7	23	11	5	17	25

Mit den Zahlen $a^{-1}$ und $b$ des Schlüssels lässt sich der Geheimtext wieder entschlüsseln. Man nimmt dazu den Zahlenwert $y$ des Geheimtextbuchstabens, berechnet $a^{-1}\cdot (y-b)$ und teilt das Ergebnis wieder durch $k$.

$a^{-1}\cdot (y-b):k$

Auch bei dieser Division tritt ein Rest auf, der die Nummer des Buchstabens vor der Verschlüsselung angibt.

Um beispielsweise den Buchstaben L wieder zu entschlüsseln, schlägt man in der Tabelle $a^{-1}=15$ nach und berechnet

$15\cdot (11-15):26=-60:26=-3\,\operatorname {Rest} \,18$

Der Rest 18 zeigt, dass der ursprüngliche Buchstabe ein S war. (Anstatt durch 26 zu teilen kann man bei negativen Zahlen auch so oft 26 addieren, bis man eine positive Zahl erhält. Diese Zahl ist mit dem Rest der Division identisch.)

Anzahl gültiger Schlüssel

Für ein Alphabet mit $n$ Zeichen gibt es $\varphi (n)\cdot n$ mögliche Schlüssel für die affine Chiffre, wobei $\varphi (\cdot )$ die Eulersche Phi-Funktion bezeichnet. So gibt es insgesamt $12\cdot 26=312$ verschiedene Schlüssel bei Verwendung des lateinischen Alphabets mit 26 Buchstaben.

Beliebiges Alphabet

Anstatt des lateinischen lässt sich jedes andere Alphabet verwenden. Auch hier werden die einzelnen Buchstaben beginnend mit der Null durchnummeriert. Im Weiteren bezeichnet $m$ die Anzahl der Zeichen des Alphabets.

Der geheime Schlüssel ist ein Zahlenpaar $(a,b)$, wobei sowohl $a$ als auch $b$ Zahlen von 0 bis $m-1$ sind. Die Zahl $a$ muss zusätzlich noch teilerfremd zu $m$ sein.

Zur Verschlüsselung verwendet man den Modulo-Operator, der dem Rest bei der Division entspricht. Ist $x$ das zu verschlüsselnde Zeichen, dann berechnet sich das zugehörige Zeichen $y$ des Geheimtexts nach der Formel

$y=(a\cdot x+b)\mod m$

Zur Entschlüsselung berechnet man das multiplikativ inverse Element $a^{-1}$ mit Hilfe des erweiterten euklidischen Algorithmus. Anschließend erhält man das ursprüngliche Zeichen aus dem Zeichen des Geheimtexts nach der Formel

$x=\left[a^{-1}\cdot (y-b)\right]\mod m$

Verschiebechiffre

Wenn $a=1$ ist, wird die Affine Chiffre als Verschiebechiffre bezeichnet. Bei einer Verschiebung um $b=3$ handelt es sich um die Caesar-Chiffre.

Sicherheit

Die affine Chiffre ist für längere Texte ein sehr schwaches Verschlüsselungsverfahren. Es gibt zwei Methoden, um sie zu brechen. Am einfachsten ist es, alle möglichen geheimen Schlüssel auszuprobieren. Eine schnellere Methode kann angewandt werden, wenn zu zwei Buchstaben des Geheimtextes die jeweiligen Klartextbuchstaben bekannt sind (Klartextangriff). Dann lässt sich der geheime Schlüssel in wenigen Schritten berechnen. Zu den beiden notwendigen Buchstabenpaaren gelangt man beispielsweise durch eine Häufigkeitsanalyse.

Literatur

• Johannes Buchmann: Einführung in die Kryptographie. 2. erweiterte Auflage. Springer, Berlin u. a. 2001, ISBN 3-540-41283-2, S. 73–74.