Hill-Verschlüsselungsverfahren (Menü Ver-/Entschlüsseln \ Symmetrisch (klassisch))
Das Hill-Verschlüsselungsverfahren wurde 1929 von Lester Hill erfunden. Es war eines der ersten Verfahren, welche sich der Mathematik bedienten (lineare Abbildungen, die in Matrixform geschrieben werden können). Durch die Benutzung der Mathematik versprach man sich ein Mehr an Sicherheit.
Das Hill-Verschlüsselungsverfahren benötigt einen Schlüssel und den Klartext. Auch der Schlüssel darf nur aus den Zeichen des Klartextalphabets (siehe Dialog Textoptionen) bestehen. Außerdem ist der Schlüssel eine quadratische Matrix, d.h. die Matrix hat genauso viele Zeile wie Spalten. Diese Anzahl bezeichnet man auch als Dimension der Matrix. Der Schlüssel muss im Dialog Schlüssel für Hill Verschlüsselungsverfahren eingegeben werden.
Der Klartext wird in Blöcke gleicher Größe (ein Block besteht aus so vielen Zeilen, wie der Schlüssel Zeilen hat) unterteilt.
Der letzte Block besteht unter Umständen aus zu wenigen Zeichen: In diesem Fall wird auf die Länge der Matrixdimension aufgefüllt -- und zwar standardmäßig mit den kleinsten Zeichen des benutzten Alphabets (das muss nicht das Zeichen mit dem kleinsten ASCII -Wert sein, z.B. wenn das Alphabet folgendermaßen definiert ist: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789").
Mathematisch gesehen beruht das Hill-Verschlüsselungsverfahren auf der Matrizenmultiplikation mit der Matrix A=(a[i,j]) für i und j zwischen 1 und n. Dabei werden sowohl der Klartext und der verschlüsselte Text als auch der Schlüssel als Zahlen interpretiert (zum Beispiel A=0, B=1, C=2, ...); die Interpretation hängt von der Reihenfolge der zu verschlüsselnden Zeichen im Dialog Textoptionen ab. Wenn der Schlüssel die Dimension n x n hat, so ergibt sich ein Block des verschlüsselten Textes v[1] ... v[n] aus einem Block des Klartextes k[1] ... k[n] durch die folgende Formel:
v[j] = Summe für i von 1 bis n von k[i] * a[i,j], für j zwischen 1 und n.
Ist ein Klartext mit der Matrix A verschlüsselt, so wird der verschlüsselte Text mit der inversen Matrix zur Verschlüsselungsmatrix A modulo Anzahl der zu verschlüsselnden Zeichen entschlüsselt.
Daher sind auch nicht alle Kombinationen beliebiger Zeichen als Schlüssel zu verwenden. Es macht keinen Sinn, eine nicht invertierbare Matrix (eine Matrix, zu der die inverse Matrix nicht existiert) als Schlüssel zuzulassen, da eine Entschlüsselung dann nicht möglich ist. Daher weist das Programm einen solchen Schlüssel zurück. Da es speziell bei Schlüsseln größerer Dimension schwierig ist, einen Schlüssel zu erraten, der einer invertierbaren Matrix entspricht (siehe dazu die Tabelle unten), gibt es die Möglichkeit, über den Knopf Zufälliger Schlüssel im Dialog Schlüssel für Hill Verschlüsselungsverfahren einen Schlüssel erzeugen zu lassen, der einer invertierbaren Matrix entspricht.
Das Hill-Verschlüsselungsverfahren ist also eine lineare Transformation des Klartextes. Daher ist es möglich, den Schlüssel über einen Known-Plaintext-Angriff zu ermitteln. In CrypTool ist ein Known-Plaintext-Angriff für das Hill Verschlüsselungsverfahren enthalten.
Ein Beispiel zum Hill Verschlüsselungsverfahren und zum Known-Plaintext-Angriff befindet sich im Kapitel Szenarien.
Empirische Ermittlung der Anzahl von invertierbaren Matrizen modulo verschiedener Zahlen:
Beispiele für verschiedene Anzahl zu verschlüsselnder Zeichen:
Modul 10: Es werden nur Ziffern verschlüsselt.
Modul 26: Es werden nur Groß- oder Kleinbuchstaben verschlüsselt.
Modul 52: Es werden nur Groß- und Kleinbuchstaben verschlüsselt.
Modul 62: Es werden nur Groß-, Kleinbuchstaben und Ziffern verschlüsselt.
Modul 71: Es werden nur Groß-, Kleinbuchstaben, Ziffern und Satzzeichen verschlüsselt.
Dimension: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Modul: 4: | 51 % | 38 % | 33 % | 31 % | 30 % | 30 % | 29 % | 29 % | 29 % | 28 % |
Modul: 5: | 81 % | 77 % | 76 % | 76 % | 76 % | 76 % | 76 % | 76 % | 76 % | 76 % |
Modul: 6: | 34 % | 22 % | 19 % | 17 % | 17 % | 17 % | 16 % | 16 % | 16 % | 16 % |
Modul: 7: | 86 % | 84 % | 84 % | 84 % | 84 % | 84 % | 84 % | 84 % | 84 % | 84 % |
Modul: 10: | 40 % | 29 % | 25 % | 24 % | 23 % | 23 % | 22 % | 22 % | 22 % | 22 % |
Modul: 26: | 46 % | 34 % | 30 % | 28 % | 27 % | 27 % | 27 % | 26 % | 26 % | 26 % |
Modul: 35: | 69 % | 64 % | 64 % | 64 % | 64 % | 64 % | 64 % | 64 % | 64 % | 64 % |
Modul: 36: | 33 % | 22 % | 19 % | 17 % | 16 % | 17 % | 16 % | 16 % | 16 % | 16 % |
Modul: 52: | 46 % | 35 % | 30 % | 29 % | 28 % | 27 % | 27 % | 27 % | 26 % | 27 % |
Modul: 62: | 49 % | 36 % | 32 % | 30 % | 29 % | 28 % | 28 % | 29 % | 27 % | 27 % |
Modul: 71: | 99 % | 99 % | 99 % | 99 % | 99 % | 99 % | 99 % | 99 % | 99 % | 99 % |
Diese Werte lassen vermuten, dass die Anzahl der invertierbaren Matrizen von der Anzahl der Teiler des Moduls abzuhängen; Primzahlen haben nur zwei Teiler und ein hoher Prozentsatz der Matrizen ist invertierbar. Außerdem scheint die Anzahl der invertierbaren Matrizen mit zunehmender Dimension kleiner zu werden.