Multiplikativ

Vereinfachte Variante der affinen Chiffre

Optionen:
Alphabete:
0
0

Jedem Buchstaben des verwendeten Alphabets wird ein Wert zugeordnet. Wird das Alphabet mit den Großbuchstaben A-Z verwendet, ergibt sich diese Zuordnung:

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
                         
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Nun wird ein Schlüssel gewählt von 1 bis 26. Anschließend wird jeder Buchstabe der Botschaft mit diesem Schlüssel multipliziert. Zum Veranschaulichen sei die Botschaft „GEHEIMNIS“ und der Schlüssel 3. Der erste Buchstabe G entspricht der Sechs. 6*3=18. Der 18te Buchstabe im verwendeten Alphabet entspricht wiederum dem S. Der erste Buchstabe der chiffrierten Botschaft ist also S. Die restlichen Buchstaben werden nach demselben Schema verschlüsselt. Bei dem M würde sich 12*3=36 ergeben. Da 36 größer ist als die Länge des verwendeten Alphabets, wird 36 modulo 26 berechnet. Es ergibt sich ein Rest von 10, was dem K entspricht. Wird „GEHEIMNIS“ komplett auf diese Weise verschlüsselt, lautet der chiffrierte Text: „SMVMYKNYC“.

Wie auch bei der Caesar-Chiffre wird jeder Buchstabe permanent auf einen anderen festen Buchstaben abgebildet. Auch wenn dieses Verfahren komplizierter erscheint, ist es nicht sicherer als die Caesar-Chiffre. Genau genommen ist es sogar noch unsicherer, denn die Anzahl der möglichen Schlüssel ist bei genauerer Betrachtung geringer als bei der Caesar-Chiffre.

Details:

Angenommen als Schlüssel würde die 2 verwendet. In dem Fall ist C=2 -> 2*2 = 4 -> der Buchstabe C wird als E chiffriert. Analog wäre P=15 -> 15*2 = 30 -> 30 modulo 26 = 4 -> der Buchstabe P wird ebenfalls als E chiffriert. Dies würde dazu führen, dass in einem chiffrierten Text, in dem der Buchstabe E vorkommt, nicht mehr bestimmt werden kann, ob es sich ursprünglich um ein C oder P gehandelt hat. Daher sind für die Chiffrierung nur zu der Alphabetlänge teilerfremde Schlüssel zulässig. Bei einer Alphabetlänge von 26 sind dies die zwölf Schlüssel: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 und 25.

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