Hill-Chiffre

Die Hill-Chiffre ist ein Verschlüsselungsverfahren der klassischen Kryptographie. Sie ist eine polyalphabetische Substitution, basierend auf linearer Algebra. Erfunden wurde sie 1929 von Lester S. Hill, der Professor am Hunter College in New York City war und diese Methode erstmals in seinem Artikel „Cryptography in an Algebraic Alphabet“ publizierte.^[1] Der Klartext wird in Blöcke aus je $n$ aufeinanderfolgenden Zeichen unterteilt, und jeder Block wird durch Multiplikation mit einer $n\times n$ Matrix als Ganzes substituiert. Die Hill-Chiffre war zu dieser Zeit das einzige polyalphabetische Verfahren, das theoretisch (wenn auch kaum in der Praxis) auf mehr als drei Klartextzeichen zugleich ( $n>3$ ) operieren konnte.

Verschlüsselung

Jeder Buchstabe wird von einer Zahl modulo 26 repräsentiert. Meist wird die einfache Zuordnung A = 0, B = 1, …, Z = 25 verwendet, aber dies ist nicht zwingend. Um eine Botschaft zu verschlüsseln, wird ein Block von n Buchstaben (als n-Komponenten Vektor) mit einer invertierbaren n×n-Matrix – wieder modulo 26 – multipliziert. Um die Nachricht zu entschlüsseln, wird jeder Block mit dem Inversen der Matrix, die zur Verschlüsselung verwendet wurde, multipliziert.^[2]

Die Matrix, die zur Verschlüsselung verwendet wurde, ist der Schlüssel und sollte zufällig aus der Menge der invertierbaren n×n-Matrizen (modulo 26) gewählt werden. Die Chiffre kann natürlich an ein Alphabet mit beliebiger Anzahl $m$ von Buchstaben (abweichend von 26) angepasst werden. Alle arithmetischen Operationen müssen dann entsprechend modulo $m$ erfolgen. Außerdem lässt sich die Länge $n$ der Blöcke frei wählen, woraus sich die Größe der Matrizen und damit die Schlüssellänge ergibt.

In folgendem Beispiel wählen wir $n=3$ und den Schlüssel „GYBNQKURP“, der folgende Matrix ergibt, in die die Schlüsselbuchstaben als Zahlen codiert eingetragen werden:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}

Wir betrachten den Klartextblock „ACT“. Da A = 0, C = 2 und T = 19, ist der Klartextvektor:

{\begin{pmatrix}0\\2\\19\end{pmatrix}}

Damit wird der Geheimtextvektor berechnet:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}

Dies entspricht dem Geheimtext „POH“. Angenommen, dass unsere Botschaft nun „CAT“ ist:

{\begin{pmatrix}2\\0\\19\end{pmatrix}}

Mit der gleichen Verschlüsselungsmatrix wie oben ergibt sich:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}\equiv {\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}

was dem Chiffretext „FIN“ entspricht. Weil jeder Geheimtextbuchstabe aus allen drei Klartextbuchstaben berechnet wird, ändert sich jeder Buchstabe. Die Hill-Chiffre bewirkt also Diffusion über alle n Zeichen eines Blocks.

Entschlüsselung

Um den Geheimtext zu entschlüsseln, multiplizieren wir ihn mit der inversen Matrix zu der Verschlüsselungsmatrix (in Buchstaben ist diese „IFKVIVVMI“). (Um eine inverse Matrix zu berechnen, siehe Matrixinversion.) Dies ist die inverse Matrix der Verschlüsselungsmatrix aus dem vorigen Beispiel:

{\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\pmod {26}}

Wenn man sie auf den vorher verschlüsselten Geheimtext „POH“ anwendet, erhält man:

{\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}\equiv {\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}

Dadurch erhält man wieder den Klartext „ACT“.^[3]

Als Verschlüsselungsmatrix muss eine invertierbare Matrix gewählt werden, damit dazu auch eine Entschlüsselungsmatrix existiert. Eine Matrix mit Ganzzahlen kann modulo $m$ invertiert werden dann und nur dann, wenn ihre Determinante ungleich Null und teilerfremd zur modularen Basis $m$ ist, d. h., dass die Determinante und $m$ keine gemeinsamen Teiler haben dürfen. Wenn wie oben $m=26$ ist, darf die Determinante nicht durch 2 oder 13 teilbar sein, sonst ist der Geheimtext nicht mehr zu decodieren. Glücklicherweise sind die Matrizen, die diese Bedingungen erfüllen, relativ häufig. Die Determinante der obigen Verschlüsselungsmatrix ist:

{\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}\equiv 6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)\equiv 441\equiv 25{\pmod {26}}

Da die Determinante 25 keine gemeinsamen Faktoren mit der Modulo-Zahl 26 hat, kann diese Matrix für die Hill-Chiffre verwendet werden. Das Risiko, dass die Determinante gemeinsame Faktoren mit der modularen Basis hat, kann vermindert werden, wenn man als modulare Basis eine Primzahl verwendet. Folglich ist eine nützliche Variante der Hill-Chiffre, noch drei Symbole zum Alphabet hinzuzufügen (z. B. Fragezeichen, Leerzeichen und Punkt) um auf die Primzahl 29 als modulare Basis zu kommen.

Es ist auch möglich, für die Verschlüsselungsmatrix $A$ eine involutive Matrix zu wählen, die mit ihrer Inversen identisch ist, also $A^{-1}=A$ . Damit entfällt die aufwändige Bestimmung der inversen Matrix.

Sicherheit

Schlüsselraum

Für ein Alphabet mit $m=\prod _{i}{p_{i}^{k_{i}}}$ Buchstaben ( $p_{i}$ sind verschiedene Primzahlen, also $m$ in Primfaktorzerlegung) umfasst der Schlüsselraum für n × n – Matrizen

\prod _{i}\left({p_{i}^{(k_{i}-1)n^{2}}\prod _{j=0}^{n-1}\left(p_{i}^{n}-p_{i}^{j}\right)}\right)

Schlüssel.^[3]

Der Schlüsselraum ist deshalb für Schlüssel einer Größenordnung am größten, wenn man $m$ als Primzahlpotenz wählt, also $m=p^{k}$ .

Die Hill-Chiffre ist völlig linear und daher für einen Angriff mit bekanntem Klartext anfällig. Es genügen $n$ Paare von Klartext- und Geheimtextvektoren, um ein lineares Gleichungssystem aufzustellen, mit dem die Verschlüsselungsmatrix in der Regel berechnet werden kann. Im ungünstigsten Fall braucht man ein wenig mehr als $n$ Paare, um eine eindeutige Lösung zu erhalten.

Siehe auch

Playfair-Verschlüsselung

Weblinks

„Hill Chiffre“ erklärt, kodiert und dekodiert
„Hill Cipher Web App“ kodiert und dekodiert die eingegebenen Botschaften und zeigt die verwendeten Matrizen
„Hill Cipher Explained“ veranschaulicht die lineare Algebra hinter der Hill-Chiffrierung
„Hill's Cipher Calculator“

Quellen

↑ Lester S. Hill: Cryptography in an Algebraic Alphabet. In: The American Mathematical Monthly. Band 36, Nr. 6, Juni 1929, S. 306, doi:10.2307/2298294 (marksmath.com [PDF; abgerufen am 11. Juni 2014]).
↑ Ryan Doyle: Hill’s Cipher: Linear Algebra in Cryptography (PDF-Datei).
↑ ^a ^b Jeffrey Overbey, William Traves and Jerzy Wojdylo: On The Keyspace Of The Hill Cipher. Cryptologia (PDF; 143 kB).

[Cryptography_in_an_Algebraic_Alphabet-1] Lester S. Hill: Cryptography in an Algebraic Alphabet. In: The American Mathematical Monthly. Band 36, Nr. 6, Juni 1929, S. 306, doi:10.2307/2298294 (marksmath.com [PDF; abgerufen am 11. Juni 2014]).

[Linear_Algebra_in_Cryptography-2] Ryan Doyle: Hill’s Cipher: Linear Algebra in Cryptography (PDF-Datei).

[On_the_Keyspace_of_the_Hill_Cipher-3] Jeffrey Overbey, William Traves and Jerzy Wojdylo: On The Keyspace Of The Hill Cipher. Cryptologia (PDF; 143 kB).

[1]

[2]

[3]