[JoGu]

Kryptologie

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

Blocklänge

Die Blocklänge l ist daran zu erkennen, dass alle Geheimtextlängen Vielfache von l sind. Notfalls hilft auch Durchprobieren der in Frage kommenden Längen.

Bekannter Klartext

Zur erfolgreichen Kryptoanalyse reichen in der Regel l bekannte Klartextblöcke, also bekannter Klartext der Länge l². (Das ist ja auch die Länge des Schlüssels.)

Seien (a11, ..., al1), ..., (a1l, ..., all) die bekannten Klartextblöcke mit zugehörigen Geheimtextblöcken (c11, ..., cl1), ..., (c1l, ..., cll).

Daraus ergibt sich die Matrizen-Gleichung

[Formel]

oder kurz geschrieben: KA = C in Mll(Z/nZ). Falls zufällig A invertierbar ist, können wir sofort nach K auflösen und erhalten: den Schlüssel K = CA-1.

Die Matrix-Inversion ist effizient nach Abschnitt 8. Ferner ist A nach Abschnitt 10 mit hoher Wahrscheinlichkeit invertierbar.

Beispiel

In dem Beispiel aus Abschnitt 9 sei der Klartext Herr bekannt. Er bildet zwei Blöcke und somit die Matrix

[Formel]

Deren Determinante ist Det A = 17 × [7·1 - 4·1] = 17·3 = 51 º -1 mod 26; wir haben also Glück gehabt und können Invertieren:

[Formel]

Daraus ergibt sich die Schlüsselmatrix:

[Formel]

Die affine Chiffre und Spezialfälle

Für die affine Chiffre c = ka + b braucht man l+1 bekannte Klartextblöcke a0, ..., al. Daraus erhält man durch Differenzbildung
c1 - c0 = k·(a1 - a0),
...
cl - cl-1 = k·(al - al-1).
Dadurch ist die Kryptoanalyse auf die HILL-Chiffre mit l bekannten Klartextblöcken reduziert.

Fazit

Linearität kann gute statistische Verteilung des Geheimtexts ergeben, macht aber extrem anfällig für bekannten Klartext.

Lineare Gleichungssysteme sind leicht lösbar. Daher wird man zur Vermeidung von Angriffen mit bekanntem Klartext auf Nichtlinearität setzen: Gleichungen höheren Grades sind sehr viel schwerer lösbar.

Bekannter Klartext ist der natürliche Feind der Linearität.

Autor: Klaus Pommerening, 3. Februar 2000; letzte Änderung: 1. Juli 2002.

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