Hill-Chiffre

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Hill-Chiffre gehört in die klassische Kryptographie, genauer in den Bereich der monoalphabetischen 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“.[1] Der Kryptograph war zu dieser Zeit der erste monoalphabetische 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[2][Bearbeiten]

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}

Dies 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[3][Bearbeiten]

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\cdot15-10\cdot17)-24(13\cdot15-10\cdot20)+1(13\cdot17-16\cdot20) \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.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Quellen[Bearbeiten]

  1.  Lester S. Hill: Cryptography in an Algebraic Alphabet. In: The American Mathematical Monthly. 36, Nr. 6, 1929, S. 306, doi:10.2307/2298294 (PDF, abgerufen am 11. Juni 2014).
  2. Ryan Doyle: Hill’s Cipher: Linear Algebra in Cryptography (PDF-Datei).
  3. Jeffrey Overbey, William Traves and Jerzy Wojdylo: On The Keyspace Of The Hill Cipher. Cryptologia (PDF-Datei).