Autokey

Variante von Vigenère, die auch Klartext als Schlüssel nutzt

Optionen:
Alphabete:
0
0

Es handelt sich um eine modifizierte Version von Vigenère. Die Autokey-Chiffre umgeht, dass das Schlüsselwort periodisch wiederholt wird. Wenn das Schlüsselwort kürzer ist als der Klartext, so wird einfach der Klartext an das Schlüsselwort angehängt.

Klartext: DIES IST EIN GEHEIMER TEXT
Schlüsselwort: KEY
Schlüssel: KEYDIESISTEINGEHEIMERT
Geheimtext: NMCVQ WLMAG KMUKM TIZFI OM

Die Autokey-Chiffre stammt ebenfalls von Blaise de Vigenère. Sie basiert im Wesentlichen auf demselben Verfahren wie die eigentliche Vigenère-Chiffre, enthält aber eine Modifikation, welche die Sicherheit der Chiffre verbessert. Diese Modifikation basiert auf Ideen von Gerolamo Cardano.

Die Sicherheit der Autokey-Chiffre ist höher einzustufen als die der Vigenère-Chiffre, denn eine Mustersuche mit dem Kasiski- oder dem Friedman-Test führt bei der Autokey-Chiffre zu keinem Ergebnis.
Auf der anderen Seite ist die Chiffre sehr unsicher, wenn dem Angreifer Teile des Klartextes bekannt sind, denn der Klartext kommt ebenfalls im Schlüssel vor. Außerdem lassen sich Buchstaben durch analytische Methoden auffinden.
Da der Klartext Teil des Schlüssels ist, kann man davon ausgehen, dass natürliche Sprache im Schlüssel verwendet wird. Wird jetzt des Weiteren von einem deutschen Text ausgegangen, so wäre sowohl im Schlüssel als auch im Klartext das E der am häufigsten vorkommende Buchstabe. Dadurch ergibt sich die Kombination von Klartext E und Schlüssel E mit dem daraus resultierenden Geheimtextbuchstaben I, am häufigsten. Nach diesem Verfahren lässt sich auch auf andere Buchstaben im Klartext schlussfolgern. ¹

(1) Lang, H.W.: „Klassische Kryptografie“, http://www.iti.fh-flensburg.de/lang/krypto/klassisch.htm, Abrufdatum: 2009-02-20

Was ist ein Alphabet?

Ein Alphabet[1] ist eine geordnete Menge aller Zeichen, die bspw. der Klartext, der Geheimtext oder der Schlüssel annehmen kann. "Geordnet" bedeutet, dass eine Sortierung möglich ist.

Für klassische Verfahren besteht das Alphabet oft nur aus den Großbuchstaben (A-Z). Zeichen, die nicht zum Alphabet gehören, werden nicht verschlüsselt oder nicht als Schlüssel zugelassen.

Wie man Nicht-Alphabetzeichen behandelt (konvertieren, überspringen, ...), kann in Optionen eingestellt werden -- das ist aber keine Funktion des eigentlichen Verschlüsselungsverfahrens selbst. Dazu sind zusätzliche Meta-Informationen der Buchstaben notwendig, die vor der Verschlüsselung erfasst werden müssen. Auch gibt es keine allgemeine Übereinstimmung, wie mit Ziffern oder Sonderzeichen umgegangen werden soll. Statt eine Konvertierung (Transformation) vor der Verschlüsselung vorzunehmen, erlaubt diese Implementierung, mehrere Alphabete anzugeben (siehe unten) und dadurch Ähnliches innerhalb des Verschlüsselungsverfahrens zu erreichen.

Unsere Implementierung von Vigenère, Beaufort, etc. rechnet intern nicht mit Buchstaben, sondern mit Zahlen. Daher muss eine Übersetzung stattfinden, die zum einen Buchstaben in Zahlen abbilden kann und umgekehrt aus Zahlen wieder Buchstaben generiert. Eine Funktion, die dies durchführt, wird im folgenden Alphabet-Funktion genannt.

Sei s eine solche umkehrbare Funktion. Dann kann die Vigenère-Verschlüsselung für ein Eingabezeichen in und ein Schlüsselzeichen key beschreiben werden als:

out = s–1(s(in) + s(key))

Die Buchstaben von in und key werden in Zahlen gewandelt, diese Zahlen werden addiert, und die Summe wird wieder in einen Buchstaben gewandelt.
Die Rückwandlung in Buchstaben findet dabei modulo zur Alphabet-Länge statt: Wenn zu dem letzten Zeichen eine 1 addiert wird, ist das Ergebnis der Summe das erste Zeichen des Alphabets.


Wie kann man ein Alphabet beschreiben?

Alphabete (ja, es kann mehrere geben: dazu weiter unten mehr) können durch eine Liste L von Buchstaben beschrieben werden. Die Alphabet-Funktion sL liefert zu einem Buchstaben, der in L vorhanden ist, den kleinsten Index, an dem er auftritt. Der Index des ersten Zeichens kann konfiguriert werden. Für Buchstaben, die nicht in L vorkommen, ist die Alphabet-Funktion sL nicht definiert.

Obwohl sich die Funktion wohldefiniert verhält, wenn ein Buchstabe mehrfach vorkommt, so macht dies bei Verschlüsselungs-Algorithmen wenig Sinn, da die Umkehrbarkeit darunter leidet. Eine entsprechende Warnung wird angezeigt.

Die Umkehrfunktion liefert für eine Zahl n das n-te Zeichen in L. Zu n wird gegebenenfalls so oft die Länge der Liste L hinzugezählt oder abgezogen, bis der Index in der Liste liegt.


Beispiel für ein Alphabet

Nehmen wir als Beispiel die Liste L = "ABCD", deren Länge 4 ist. Es soll die Nachricht "ACDC" mit dem Schlüssel "ABBA" nach dem Vigenère-Verfahren verschlüsselt werden. Es finden folgende Schritte statt:

in sL(in) key sL(key) sL(in) + sL(key) sL–1(sL(in) + sL(key))
A 0 A 0 0 A
C 2 B 1 3 D
D 3 B 1 4 A
C 2 A 0 2 C

Im Beispiel ist beim dritten Buchstaben ein Überlauf aufgetreten, so dass modulo |L| = 4 gerechnet wird.


Kurzschreibweise für Alphabete

Um die Darstellung der Alphabete zu vereinfachen, wurde folgende Kurzschreibweise eingeführt: Das Minuszeichen in der Folge Buchstabe1-Buchstabe2 wird zu allen Buchstaben erweitert, die zwischen den beiden flankierenden Buchstaben stehen.

So steht etwa:

  • "A-Z" für alle Großbuchstaben,
  • "a-z" für alle Kleinbuchstaben,
  • "z-a" für alle Kleinbuchstaben in umgekehrter Reihenfolge und
  • "0-9" für alle Ziffern.

Einziger Nachteil ist, dass das Minuszeichen selbst als "---" geschrieben werden muss, um nicht als Bereichsoperator verwechselt zu werden.

In der Detail-Darstellung der Alphabete (Klick auf den "…"-Knopf) können die Alphabete in der Kurzschreibweise bearbeitet werden.


Mehrere Alphabete

Erlaubt man, dass im Klartext sowohl Großbuchstaben [A-Z] als auch Ziffern [0-9] vorkommen können, kann man 2 Vorgehensweisen unterscheiden:

  1. Gemergtes Gesamt-Alphabet:
    Man fügt die beiden Teilalphabete [A-Z] und [0-9] in einer bestimmten Reihenfolge zu einem neuen Alphabet [A-Z0-9] zusammen. Wenn man hier 'Z' um 3 shiftet, kommt man zur '2'.
  2. Getrennte Teilalphabete:
    Man aber auch alle Transformationen innerhalb des jeweiligen Teilalphabets durchführen. Damit erreicht man, dass ein Großbuchstabe im Klartext auch auf einen Großbuchstaben im verschlüsselten Text abgebildet wird. Wenn man hier 'Z' um 3 shiftet, kommt man zum 'C'.

Getrennte Teilalphabete

Durch die Verwendung von mehreren Alphabeten müssen die Algorithmen nicht Groß- und Kleinbuchstaben unterscheiden.

Der Algorithmus merkt sich, mit welchem Alphabet er die Zahl des Klartextes ermittelt hat. Das gleiche Alphabet wird zur Erzeugung des verschlüsselten Textes verwendet.

Wenn ein Buchstabe in mehreren Alphabeten vorkommt, wird das erste dieser Alphabete verwendet.

Optionen regeln den Fall, wenn ein Buchstabe in keinem Alphabet vorkommt: Standardmäßig wird er nicht verschlüsselt, sondern direkt in die Ausgabe übernommen. Das ist auch der Fall, wenn der Buchstabe im Schlüssel steht. Alternativ können die Nicht-Alphabet-Buchstaben in Schlüssel und Klartext auch herausgefiltert werden, um die Sicherheit zu erhöhen. Dies schränkt jedoch die Lesbarkeit ein.


Beispiel für mehrere Alphabete: Addition bei Vigenère

Hier werden beide Vorgehensweisen behandelt: für getrennte Teilalphabete und für ein gemergtes Alphabet.

Als kleines Beispiel betrachten wir Vigenère mit den folgenden beiden Alphabeten:

  • L1 = "0-9A-F" und
  • L2 = "0-9a-f".

In beiden Vorgehensweisen sollen im Beispiel sowohl Klartext als auch Schlüssel beide aus dem Text "0123456789abcdABCD" bestehen.

Für getrennte Teilalphabete ergibt sich:

  • Dann ist der verschlüsselte Text ziffernweise die kleinste Stelle einer Addition von Klartext und Schlüssel, wenn beide hexadezimale Ziffern sind.
  • Als verschlüsselter Text ergibt sich: "02468ACE02468a468A".
  • Da das erste Alphabet L1 für die Ziffern verwendet wurde, werden aus Ziffern im Klartext immer Ziffern und Großbuchstaben im verschlüsselten Text.
  • Beachte den Unterschied bei 'D' und 'd': Der Indexwert ist jewels derselbe, aber beim 'd' wird L2 verwendet, so dass sich die Ergebnisse im verschlüsselten Text unterscheiden: 'A' und 'a'.

Für ein gemergtes Alphabete ergibt sich als verschlüsselter Text: "02468ACEacACEae024".

Die folgende Tabelle zeigt die Berechnung sowohl für den Fall der getrennten Teilalphabete L1, L2 als auch für ein gemergtes Alphabet L= "0-9A-Fa-f".

 separate alphabetsmerged alphabet
Ckeyind(C)ind(key)ind(out)outind(C)ind(key)ind(out)out
0 0 0 0 0 0 0 0 0 0
1 1 1 1 2 2 1 1 2 2
2 2 2 2 4 4 2 2 4 4
3 3 3 3 6 6 3 3 6 6
4 4 4 4 8 8 4 4 8 8
5 5 5 5 10 A 5 5 10 A
6 6 6 6 12 C 6 6 12 C
7 7 7 7 14 E 7 7 14 E
8 8 8 8 16 = 0 0 8 8 16 a
9 9 9 9 18 = 2 2 9 9 18 c
a a 10 10 20 = 4 4 16 16 32 = 10 A
b b 11 11 22 = 6 6 17 17 34 = 12 C
c c 12 12 24 = 8 8 18 18 36 = 14 E
d d 13 13 26 = 10 a 19 19 38 = 16 a
A A 10 10 20 = 4 4 10 10 20 e
B B 11 11 22 = 6 6 11 11 22 = 0 0
C C 12 12 24 = 8 8 12 12 24 = 2 2
D D 13 13 26 = 10 A 13 13 26 = 4 4

Teil-Alphabete: "0-9A-F", "0-9a-f";

gemergtes Alphabet: "0-9A-Fa-f"

Klartext = Schlüssel = "0123456789abcdABCD"

Vorgehensweise 1: Getrennt: In jedem Teilalphabet wird mod 16 gerechnet (Hex-Addition), da jedes Teilalphabet 16 Elemente enthält, und es wird im selben Teilalphabet geblieben, aus dem der Klartextbuchstabe stammt.

Vorgehensweise 2: Merged: Im Alphabet wird mod 22 gerechnet, da das Alphabet 22 Elemente enthält.


Referenzen