Hill-Chiffre in Python programmieren und angreifen
Die Hill-Chiffre (1929) ist anfällig für eine Known-Plaintext-Attacke. Wir haben die Chiffre in Python nachprogrammiert, um den Angriff ausprobieren zu können.
(Bild: KI, Collage c’t)
- Dr. Peter Uelkes
Die Hill-Chiffre hat als eine der ersten mathematischen Chiffren den Weg zu modernen Systemen wie RSA und ECDSA geebnet. Die Geschichte, Funktionsweise und Hintergründe der Hill-Chiffre haben wir ausführlich an anderer Stelle vorgestellt. Daher hier nur in aller Kürze: Bei der Hill-Chiffre zerlegt man den Klartext in gleich lange Fragmente, etwa der Länge n. Die fasst man dann als Vektor auf und multipliziert jeden Schnipsel mit einer n × n-Matrix, die als Schlüssel dient.
Beim Erzeugen der Schlüsselmatrix achtet man darauf, dass sie invertierbar ist, denn ihre Inverse wird zum Entschlüsseln benötigt. Alle Rechenoperationen finden modulo N statt, wobei N die Größe des verwendeten Alphabets ist. Es zeigt sich, dass das Verfahren mit wachsender Schlüssellänge schnell sehr robust gegen übliche Angriffe wie Häufigkeitsanalysen ist. Allerdings ist es anfällig gegen Known-Plaintext-Attacken und hat sich deshalb in der Praxis nicht durchgesetzt. Mit einem bekannten Paar aus Klartext und Chiffrat kann man den verwendeten Schlüssel rekonstruieren und mit ihm kodierte Botschaften entschlüsseln.
- Um einen Beispielangriff auf die Hill-Chiffre zu demonstrieren, haben wir die Chiffre der Leichtigkeit halber in Python implementiert.
- Dazu braucht man einige mathematische Hilfsfunktionen – die man in anderen kryptografischen Projekten wiederverwerten kann.
- Einmal erledigt, steht Ihrer ersten Known-Plaintext-Attacke nichts mehr im Wege.
Weil die Chiffre auf Matrizen basiert, wäre das händische Nachrechnen recht aufwendig. Deshalb haben wir die Hill-Chiffre in Python nachprogrammiert, um sie anschließend leichter angreifen zu können. Ganz nebenbei lernen Sie so, wie man für die Kryptografie essenzielle mathematische Verfahren programmiert, etwa das Multiplizieren von Matrizen oder die modulare Inverse einer Matrix.
Das war die Leseprobe unseres heise-Plus-Artikels "Hill-Chiffre in Python programmieren und angreifen". Mit einem heise-Plus-Abo können Sie den ganzen Artikel lesen.
