In der klassischen Kryptographie ist die Hill-Chiffre ein Polygraphie Substitutions-Chiffre auf der Basis der linearen Algebra. Lester S. Hill im Jahre 1929 erfunden wurde, war es das erste Polygraphie Chiffre, in der es sinnvoll, auf mehr als drei Symbole auf einmal zu betreiben. Die folgende Diskussion nimmt eine elementare Kenntnisse von Matrizen.

Betrieb

Jeder Buchstabe wird durch eine Anzahl modulo 26 dargestellt, um eine Nachricht zu verschlüsseln, wird jeder Block von N Briefe durch einen invertierbaren n × n-Matrix multipliziert, wieder Modulus 26. Um die Nachricht zu entschlüsseln, wird jeder Block durch die Inverse der Matrix verwendet multipliziert für die Verschlüsselung.

Die Matrix für die Verschlüsselung verwendet wird, ist der Verschlüsselungsschlüssel, und es sollte nach dem Zufallsprinzip aus der Menge der invertierbaren n × n Matrizen gewählt werden. Die Chiffre kann natürlich zu einem Alphabet mit einer beliebigen Anzahl von Buchstaben angepasst werden kann; Alle arithmetischen muss nur getan modulo der Anzahl der Buchstaben anstelle von Modulo 26 werden.

Betrachten Sie die Meldung 'ACT', und den Schlüssel im Handumdrehen:

Seit 'A' 0 ist, ist "C" 2 und "T" beträgt 19, die Botschaft ist der Vektor:

Wodurch die verschlüsselte Vektors gegeben ist durch:

Dies entspricht einer Ciphertext "POH. Nehmen wir nun an, dass unsere Botschaft ist statt "CAT", oder:

Dieses Mal ist die verschlüsselte Vektor gegeben durch:

Dies entspricht einer Ciphertext "FIN". Jeder Buchstabe hat sich geändert. Die Hill-Chiffre hat Shannons Diffusion erreicht, und eine n-dimensionale Hill-Chiffre kann vollständig über n Symbole auf einmal zu diffundieren.

Decryption

Um zu entschlüsseln, wenden wir uns den Chiffretext zurück in einen Vektor, dann einfach mit der inversen Matrix der Tastenmatrix zu multiplizieren. Wir finden, dass, Modulo 26 ist die Inverse der Matrix in dem vorherigen Beispiel verwendet:

Unter dem vorherigen Beispiel Schlüsseltext der "POH", erhalten wir:

das bringt uns zurück zu 'ACT', so wie wir es uns erhofft.

Wir haben noch nicht diskutiert zwei Komplikationen, die in die Auswahl der Verschlüsselungsmatrix existieren. Nicht alle Matrizen haben eine umgekehrte. Die Matrix wird eine inverse, wenn und nur wenn ihre Determinante nicht Null ist. Auch im Fall der Hill-Chiffre, die Determinante der Verschlüsselungsmatrix dürfen keine gemeinsamen Faktoren mit der modularen Basis. Wenn wir also zu arbeiten modulo 26, wie oben, die Determinante muss ungleich Null sein und darf nicht durch 2 teilbar sein oder 13. Wenn die Determinante gleich 0 ist, oder hat Gemeinsamkeiten mit der modularen Basis, dann kann die Matrix nicht im Hill verwendet werden Chiffre, und eine andere Matrix gewählt werden. Glücklicherweise sind die Matrizen, die die Bedingungen in der Hill-Chiffre verwendet werden, erfüllen ziemlich häufig.

Für unser Beispiel Tastenmatrix:

So, modulo 26, die Determinante 25. Da es keine gemeinsamen Faktoren mit 26, kann diese Matrix für die Hill-Chiffre verwendet werden.

Das Risiko der Determinante mit gemeinsamen Faktoren, die mit dem Modul können, indem sie den Modul prime beseitigt werden. Folglich eine nützliche Variante der Hill-Chiffre fügt 3 zusätzliche Symbole, um das Modul auf 29 zu erhöhen.

Beispiel

Lassen

sein, den Schlüssel und nehme an, die Klartextnachricht ist Hilfe. Dann ist dieser Klartext wird von zwei Paaren vertreten

Dann berechnen wir

und weiter Verschlüsselung wie folgt:

Die Matrix K ist umkehrbar, folglich existiert derart, daß. Zur Entschlüsselung zu implementieren, berechnen wir

Dann berechnen wir

Deshalb

.

Sicherheit

Leider ist die Grund Hill-Chiffre anfällig für einen Known-Plaintext-Angriff, da sie vollständig linear ist. Ein Gegner, der Text / Verschlüsselungstext Zeichenpaare und fängt können ein lineares System, das leicht gelöst werden können; wenn es passiert, dass dieses System unbestimmt ist, ist es lediglich erforderlich, einige weitere Text / Verschlüsselungstext Paare hinzuzufügen. Berechnung dieser Lösung durch Standard linearen Algebra Algorithmen erfolgt dann sehr wenig Zeit.

Während Matrizenmultiplikation allein nicht in einem sicheren Verschlüsselungs Folge ist es immer noch ein nützlicher Schritt, wenn es mit anderen nichtlinearen Operationen kombiniert werden, da die Matrixmultiplikation kann die Diffusion bereitzustellen. Zum Beispiel kann eine geeignet gewählte Matrix daß kleine Unterschiede zu gewährleisten, bevor die Matrixmultiplikation wird in großen Unterschieden nach der Matrixmultiplikation führen. Einige moderne Chiffren verwenden in der Tat eine Matrixmultiplikation Schritt, um die Diffusion zu schaffen. Beispielsweise ist die MixColumns Schritt AES eine Matrixmultiplikation. Die Funktion g in Twofish ist eine Kombination von nicht-linearen S-Boxen mit einem sorgfältig ausgewählten Matrixmultiplikation. Kürzlich versuchten einige Publikationen die Hill-Chiffre sicherer zu machen.

Schlüsselgröße

Die Schlüsselgröße der binäre Logarithmus der Anzahl der möglichen Schlüssel. Es Matrizen der Dimension n · n. So oder etwa auf der Schlüsselgröße der Hill-Chiffre mit n × n Matrizen eine obere Schranke. Dies ist nur eine obere Grenze, da nicht jeder Matrix invertierbar und somit verwendbar als Schlüssel. Über den chinesischen Restsatz kann die Anzahl der invertierbaren Matrizen berechnet werden. Dh eine Matrix invertierbar modulo 26, wenn und nur wenn sie invertierbar ist sowohl modulo 2 und modulo 13. Die Anzahl der invertierbare n × n Matrizen modulo 2 gleich der Ordnung des allgemeinen linearen Gruppe GL. es ist

Ebenso kann die Anzahl der invertierbaren Matrizen modulo 13)

Die Anzahl der invertierbare Matrizes modulo 26 ist das Produkt dieser beiden Zahlen. Daher ist

Zusätzlich scheint es vernünftig, zu viele Nullen in der Tasten-Matrix zu vermeiden, da sie die Diffusion zu reduzieren. Der Nettoeffekt ist, dass die wirksame Schlüsselraums eines basischen Hill cipher geht. Für einen 5 × 5-Hill-Chiffre, das heißt etwa 114 Bits. Natürlich ist Schlüsselsuche nicht die effizienteste bekannte Angriff.

Mechanische Umsetzung

Beim Betrieb von 2 Symbole auf einmal bietet eine Hill-Chiffre keinen besonderen Vorteil gegenüber Playfair oder bifid Chiffre, und in der Tat ist schwächer als entweder, und etwas mehr mühsam mit Bleistift und Papier arbeiten. Da die Dimension zunimmt, wird schnell die Chiffre unmöglich für einen Menschen mit der Hand bedienen.

A Hill-Chiffre der Dimension 6 wurde mechanisch realisiert. Hill und ein Partner ein Patent für dieses Gerät, das eine 6 × 6 Matrix-Multiplikation Modulo-26 durchgeführt unter Verwendung eines Systems von Zahnrädern und Ketten ausgezeichnet.

Einem geheimen lineare Schritt, gefolgt von der breiten diffusive Schritt von der Maschine, gefolgt von einer dritten Geheimnis lineare Schritt: Leider wurden die Getriebeanordnungen für eine bestimmte Maschine, so wurde dreifache Verschlüsselung für die Sicherheit empfiehlt fixiert. Eine solche Kombination war eigentlich sehr leistungsfähig für 1929 und gibt an, dass Hill versteht offenbar die Konzepte von einem Meet-in-the-Middle-Angriff als auch Unordnung und Verbreitung. Leider hat seine Maschine nicht verkaufen.