Hill-Chiffre

Die Hill-Chiffre gehört in die klassische Kryptographie, genauer in den Bereich der polyalphabetische Substitution, basierend auf linearer Algebra. Erfunden wurde sie von Lester S. Hill im Jahr 1929. Dieser war Professor am Hunter College in New York City und publizierte diese Methode erstmals in seinem Artikel „Cryptography in an Algebraic Alphabet“. Der Kryptograph war zu dieser Zeit der erste polyalphabetische Kryptograph, der praktisch (wenn auch kaum) an mehr als drei Symbolen zugleich operieren kann. Die folgenden Absätze setzen ein grundsätzliches Wissen der Matrizen voraus.

Verschlüsselung

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

Die Matrix, die zur Verschlüsselung verwendet wurde, ist der Chiffrier-Schlüssel und sollte zufällig aus der Menge der invertierbaren n×n-Matrizen (modulo 26) gewählt werden. Die Chiffre kann natürlich zu einem Alphabet mit beliebiger Anzahl von Buchstaben angepasst werden; alle arithmetischen Operationen müssen dann aber modulo der Anzahl der Buchstaben statt modulo 26 durchgeführt werden. Betrachtet man nun die Meldung „ACT“ und den Schlüssel als Matrix (bzw. in Buchstaben „GYBNQKURP“):

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

Da A = 0, C = 2 und T = 19 ist, besteht die Botschaft aus dem Vektor:

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

Damit wird der verschlüsselte Vektor 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 von „POH“. Angenommen, dass unsere Botschaft nun „CAT“ ist:

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

Dieses Mal wird die gleiche Verschlüsselungsmatrix verwendet, aber die Berechnung zeigt:

${\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 von „FIN“ entspricht. Jeder Buchstabe hat sich geändert. Die Hill-Chiffre erreicht nun Shannons Diffusion und eine n-dimensionale Hill-Chiffre kann auf einmal über n Symbole diffundieren.

Entschlüsselung

Um den Geheimtext zu entschlüsseln, multiplizieren wir den Text mit der inversen Matrix 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 den vorher verschlüsselten Geheimtext „POH“ darauf 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 den Klartext „ACT“, unserem Ausgangswort.

Noch nicht besprochen wurde die Problematik, die in der Auswahl der Verschlüsselungsmatrix besteht. Nicht alle besitzen eine inverse Matrizen (siehe invertierbare Matrix). Eine Matrix kann zu einer inversen werden, wenn, und nur wenn, die Determinante nicht Null ist und keine gemeinsamen Faktoren mit der modularen Basis haben, d. h., dass die Determinante und die Modulo-Zahl keine gemeinsamen Teiler haben dürfen. Wenn man jetzt, wie oben, in modulo 26 operiert, muss die Determinante ungleich Null sein und darf auch nicht durch 2 oder 13 teilbar sein. Sollte die Determinante Null oder die Faktoren mit der modularen Basis gleich sein, dann kann die Matrix nicht für die Hill-Chiffre angewendet werden. Eine andere Matrix muss gewählt werden, sonst ist der Geheimtext nicht mehr zu decodieren. Glücklicherweise sind die Matrizen, die auf diese Bedingungen zutreffen, relativ häufig. Vom obigen Beispiel sei die Verschlüsselungsmatrix:

${\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}}$

Durch modulo 26 ist die Determinante 25. Da 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, so dass die aufwändige Bestimmung der inversen Matrix entfällt, da $A^{-1}=A$ ist.

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.

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"