Hill-Chiffre online – verschlüsseln/entschlüsseln
Hill-Chiffre online berechnen: Buchstabenpaare mit einer 2 × 2-Matrix ver- und entschlüsseln. Mit Beispiel und inverser Matrix modulo 26.
Was hat lineare Algebra mit Kryptografie zu tun?
Was ist die Hill-Chiffre?
Die Hill-Chiffre wandelt ganze Buchstabengruppen auf einmal um, und zwar durch Matrizenmultiplikation. In der Fassung des Werkzeugs laufen die Buchstaben paarweise: Jedes Paar wird zu einem Vektor aus zwei Zahlen, der mit der 2 × 2-Schlüsselmatrix multipliziert und modulo 26 reduziert wird.
Wie wird ein Buchstabenpaar berechnet?
Buchstaben werden zu Zahlen von 0 bis 25, dann entstehen zwei Summen: Den ersten Ausgabebuchstaben liefert a×x + b×y, den zweiten c×x + d×y, wobei a, b, c, d die Zahlen der Matrix sind. Beide Summen werden modulo 26 genommen und zurück in Buchstaben verwandelt. Text mit ungerader Länge ergänzt das Werkzeug um ein X.
Beispiel mit der Matrix [3,3;2,5]
Die Nachricht „REBUS“ ergibt mit der voreingestellten Matrix „LC LY TV“. Eine ungerade Buchstabenzahl wird mit X aufgefüllt, verschlüsselt wird also das Paar SX, und das Ergebnis erscheint paarweise. Beim Entschlüsseln entsteht „RE BU SX“ — das ergänzte X muss am Ende selbst entfernt werden.
Zahlenwerte der Buchstaben
Die obere Zeile zeigt den Buchstaben, die untere den Wert, mit dem gerechnet wird. A entspricht null, sodass das Ergebnis nach Multiplikation und Reduktion modulo 26 über dieselbe Tabelle ins Alphabet zurückkehrt.
| Buchstabe | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Wert | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Wie wird der Text entschlüsselt?
Beim Entschlüsseln werden die Buchstabenpaare mit der inversen Matrix modulo 26 multipliziert. Zur Matrix [3,3;2,5] gehört die Inverse [15,17;20,9] — das Werkzeug berechnet sie selbst, sobald der Entschlüsselungsmodus gewählt ist. Nötig ist nur dieselbe Matrix wie beim Verschlüsseln.
Warum taugt nicht jede Matrix als Schlüssel?
Die Matrix muss modulo 26 invertierbar sein, ihre Determinante darf also keinen Teiler mit 26 gemeinsam haben. Die Determinante von [3,3;2,5] ist 9, und der größte gemeinsame Teiler von 9 und 26 ist 1 — der Schlüssel ist gültig. Ist die Determinante durch 2 oder 13 teilbar, wird das Entschlüsseln unmöglich und das Werkzeug liefert kein Ergebnis.
Wie lässt sich die Hill-Chiffre knacken?
Das Verfahren ist linear, deshalb lässt sich aus bekannten Klartext-Geheimtext-Paaren ein Gleichungssystem aufstellen und die Matrix bestimmen. Bei Zweierblöcken können zwei bekannte Paare genügen, wenn ihre Klartextvektoren eine modulo 26 invertierbare Matrix bilden; andernfalls werden weitere Paare benötigt. Fehlt solches Material, hilft die Häufigkeitsanalyse von Buchstabenpaaren. Genau diese Linearität ist die größte Schwäche.
Was verbirgt Hill besser als eine einfache Substitution?
Weil das ganze Paar über das Ergebnis entscheidet, wird derselbe Buchstabe an verschiedenen Stellen zu verschiedenen Geheimtextbuchstaben, und Einzelbuchstabenhäufigkeiten verraten den Text nicht mehr. Stattdessen treten Paarhäufigkeiten hervor: Die Chiffre hält der Analyse besser stand als Caesar, schützt vertrauliche Daten aber trotzdem nicht.
Siehe auch: Caesar-Chiffre · Vigenère-Chiffre
Geschichte der Hill-Chiffre
Lester S. Hill veröffentlichte sein Verfahren 1929 in „The American Mathematical Monthly“. Es war eine der ersten polygraphischen Chiffren, die bewusst auf linearer Algebra aufbauten, und zeigte, dass Kryptografie mit den gewöhnlichen Werkzeugen der Mathematik arbeiten kann. Hill baute sogar ein mechanisches Gerät für diese Umrechnungen.