[JoGu]

Kryptologie

Die HILL-Chiffre
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Beschreibung

Alphabet: S = Z/nZ, also ein endlicher Ring.

Schlüsselraum: K = GLl(Z/nZ), die multiplikative Gruppe der invertierbaren l×l-Matrizen.

Verschlüsselung blockweise, wobei l die Blocklänge ist: Für k Î GLl(Z/nZ) und (a1, ..., al) Î Sl ist

[Formel]

oder in ausgeschriebener Form

[Formel]

Entschlüsselung mit der inversen Matrix:

[Formel]

Verwandte Chiffren

Spezialfall: Wird k als die Permutationsmatrix Ps gewählt, so ist fk die Blocktransposition zu s.

Verallgemeinerung: Die affine Chiffre. Hier wird ein Schlüssel

(k, b) Î GLl(Z/nZ) × (Z/nZ)l
gewählt; verschlüsselt wird nach der Formel
c = ka + b.

Hier ist als Spezialfall die BELASO-Chiffre mit Schlüssel b enthalten, wenn man k als Einheitsmatrix wählt.

Beispiel

Sei l = 2 und

[Formel]

Dann ist Det k = 77 - 24 = 51 º -1 (mod 26) und

[Formel]

Zur Umrechnung von Buchstaben in Zahlen mod 26 braucht man die Tabelle 

  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
  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

Damit wird der Klartext Herr = (7,4,17,17) verschlüsselt zu

[Formel]
[Formel]

also fk(Herr) = (5,23,11,14) = FXLO.

Zur Probe die Entschlüsselung:

[Formel]

Bewertung

+Wesentlich stärker als die Blocktransposition und die BELASO-Chiffre.
+Geheimtexte sehr gut gleichverteilt; Angriff mit nichts als Geheimtext fast unmöglich.
-Sehr anfällig für Angriff mit bekanntem Klartext.

Die HILL-Chiffre wurde 1929 von Lester HILL [Bild] vorgeschlagen und erregte einiges Aufsehen (vor allem bei Mathematikern), wurde aber nie ernsthaft eingesetzt.

Ihre eigentliche Bedeutung liegt darin, dass hier erstmals systematisch algebraische Methoden in die Kryptologie eingeführt wurden, und dass sie deutlich macht, welche Bedeutung Linearität für die Kryptoanalyse hat.

Autor: Klaus Pommerening, 3. Februar 2000; letzte Änderung: 12. August 2002.

E-Mail an Pommerening@imsd.uni-mainz.de.