Kryptologie I.8 Lineare Chiffren

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

Lineare Chiffren wurden von dem Mathematiker Lester HILL [Bild] 1929 vorgeschlagen und erregten einiges Aufsehen (vor allem bei Mathematikern); sie wurden aber wegen ihrer allzu offensichtlichen Schwächen nie ernsthaft eingesetzt. Ihre eigentliche Bedeutung liegt darin, dass hier erstmals systematisch algebraische Methoden in die Kryptologie eingeführt wurden, und dass dabei deutlich wurde, welche Bedeutung Linearität für die Kryptoanalyse hat.

Jack LEVINE erwähnte später, dass er diese Art von Chiffrierung schon 1924 als Schüler benützt hätte.

Diese Chiffren verwenden lineare Algebra (oder Matrizenrechnung) über dem Ring der ganzen Zahlen Z oder seinen endlichen Restklassenringen Z/nZ. Daher hier zunächst ein zahlentheoretisch-algebraischer Einschub:

1. Der euklidische Algorithmus [PDF].
2. Analyse des euklidischen Algorithmus [PDF].
3. Kongruenzdivision [PDF].
4. Der chinesische Restalgorithmus [PDF].
5. Die Eulersche Phi-Funktion [PDF].
6. Matrizen über Ringen [PDF].
7. Ganzzahlige Elimination [PDF].
8. Die HILL-Chiffre [PDF].
9. Die Anzahl invertierbarer Matrizen über Restklassenringen [PDF].
10. Die Kryptoanalyse der HILL-Chiffre [PDF].

Fazit

Linearität in einer Chiffre macht sie extrem anfällig für einen Angriff mit bekanntem Klartext, weil lineare Gleichungssysteme so leicht lösbar sind - zumindest über den Ringen, in denen man praktisch rechnen kann.

Also wird man für die Konstruktion von sicheren Chiffren zur Vermeidung von Angriffen mit bekanntem Klartext auf Nichtlinearität setzen: Algebraische Gleichungen höheren Grades sind sehr viel schwerer lösbar. Daher der Merksatz: