Hill-Chiffre

Verschlüsselung   Entschlüsselung   Angriffe auf Hill-Chiffren   Beispiel   Übungen  

Die Hill-Chiffren gehören zu den Blockchiffren, das heißt es werden jeweils Klartextblöcke einer bestimmten Länge zu Chiffraten einer bestimmten Länge verschlüsselt, wobei speziell bei Hill-Chiffren die Länge eines Klartextblocks gleich der Länge des zugehörigen Chiffrats ist. Als Schlüsselmenge wird die Menge der invertierbaren -Matrizen über benutzt, das heißt über den ganzen Zahlen . Dabei entspricht der Parameter der Blocklänge. Das Inverse einer Matrix existiert genau dann, wenn gilt .

Verschlüsselung

Für einen gegebenen Buchstaben im Klartext wird zunächst anhand der folgenden Tabelle seine Position im Alphabet bestimmt. Das heißt dem -ten Buchstaben im Klartext wird eine Zahl aus zugewiesen, wie es für in der folgenden Tabelle illustriert ist.

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

Sei die Schlüsselmatrix und ein Nachrichtenblock, der als Spaltenvektor

interpretiert wird. Dann ergibt sich das Chiffrat aufgrund der Matrix-Vektor Multiplikation

wobei Addition und Multiplikation in geschieht.

Entschlüsselung

Bestimmt man zur Matrix die inverse Matrix , also eine Matrix der Form

wobei die Einheitsmatrix ist (alle Hauptdiagonalelemente sind gleich Eins und die restlichen Einträge gleich Null), dann lässt sich aus dem Chiffrat die ursprüngliche Nachricht wie folgt bestimmen:

Angriffe auf Hill-Chiffren

Wir wollen kurz zwei mögliche Angriffe auf die Hill-Chiffre beschreiben. Die erste Möglichkeit ist ein chosen plaintext attack. Mit diesem Angriff sind Hill-Chiffren leicht zu brechen, denn wenn man die Einheitsvektoren als Nachrichten wählt, so erhält man mit die -te Spalte der Matrix .

Die zweite Methode ist ein known plaintext attack. Wenn Klartexte und die zugehörigen Kryptogramme , alle aus , zur Verfügung stehen, können wir hoffen, dass oder ein Erzeugendensystem von bilden. Es sollte also zumindest gelten, um den Angriff durchzuführen. Wir benutzen die Ansätze

bzw.

jeweils für und versuchen, eines der beiden Gleichungssysteme nach den Unbekannten bzw. aufzulösen (etwa mit dem Eliminationsverfahren von Gauss). Gelingt dies, so können wir danach mit

bzw.

die -te Spalte der Matrix bzw. der Matrix berechnen.

Wir wollen uns noch kurz überlegen, wieviele Klartext/Kryptogramm-Paare wir benötigen, um die Matrix bzw. ihre inverse Matrix bestimmen zu können, d.h. wie viele solcher Paare nötig sind, um wie besprochen ein Erzeugendensystem zu erhalten. Dazu nehmen wir an, dass die Klartexte unabhängig und gleichverteilt gewählt werden.

Sei ein linearer Unterraum von mit . Die Zufallsgröße sei die Zufallsgröße für das Ziehen eines Klartextes. Für jeden festen Klartext ergibt sich sowie , da die Anzahl der Elemente in gleich ist und jeder -dimensionale lineare Unterraum von genau viele Elemente enthält.

Als nächstes betrachten wir die Zufallsvariable , die die Anzahl zufällig gezogener Klartexte angibt, bis zum ersten Mal ist. Aufgrund der Gleichverteilung der Klartexte hängt der Wert von nicht von der speziellen Wahl des Unterraumes ab und es ergibt sich

da die Wahrscheinlichkeit ist, bei einmaligem Ziehen eines Klartextes nicht im Unterraum zu landen und der Kehrwert der Wahrscheinlichkeit die erwartete Anzahl an Zufallsexperimenten ist, bis das Ereignis zum ersten Mal eintritt.

Nun betrachten wir die erwartete Anzahl an Zufallsexperimenten , um einen -dimensionalen Unterraum, also den ganzen Raum , zu erzeugen. Dazu müssen dimensionale Unterräume und schließlich der -dimensionale Unterraum erzeugt werden. Er ergibt sich also

Man benötigt also wenigstens , aber im Mittel höchstens Klartext/Kryptogramm-Paare, um die Matrix ermitteln zu können. Gehen wir beispielsweise von einer Blocklänge von aus und dem -Zeichen-Alphabet, dann ergibt sich . Schließlich können wir mit der Markov-Ungleichung, die für nichtnegative Zufallsvariablen und reelle Zahlen besagt

abschätzen, wie groß die Wahrscheinlichkeit ist, in diesem Fall mindestens Paare zu benötigen, diese ergibt sich als höchstens .

Beispiel

Verwenden wir die invertierbare Matrix

über zur Verschlüsselung der durch den Buchstaben X auf geradzahlige Länge ergänzten Nachricht "OTTO KOMMT", aus der zunächst die Vektoren

erstellt werden, so erhalten wir die Vektoren

Das Chiffrat lautet also nach einer Rückumwandlung in Buchstaben "FPHC WSCSEZ".

Übungen

Aufgabe 1
Bekannt sei = ("TURING", "UBIXGT").

1. Brechen Sie in einem Known-Plaintext-Angriff die Hill-Chiffre mit der Blocklänge 2 vollständig. Finden Sie dazu die Schlüsselmatrix bzw. deren Inverse und entschlüsseln Sie den restlichen Geheimtext "ENERHLNHAHRM".
2. Warum wurde hier das Alphabet künstlich um ein Zeichen erweitert, so dass es 27 statt 26 Buchstaben umfasst? Welche Anzahl Buchstaben wäre für diese Chiffre optimal?

Aufgabe 2
Bekannt seien folgende 7 plaintext/ciphertext - Paare:

Brechen Sie in einem Known-Plaintext-Angriff die Hill-Chiffre mit der Blocklänge 3 vollständig. Finden Sie dazu die Schlüsselmatrix bzw. deren Inverse .

Aufgabe 3
Gegeben sei eine Hill-Chiffre mit Blocklänge über dem Alphabet , also , und mit der Schlüsselmenge . Bei einer Modifikation dieser Hill-Chiffre nehmen wir als Schlüsselmenge alle Produkte von je zwei Matrizen aus , wobei auch ist. Eine Nachricht wird verschlüsselt zum Chiffrat mit Schlüssel .

Vergleichen Sie diese modifizierte Hill-Chiffre mit der normalen Hill-Chiffre.

Aufgabe 4
Gegeben ist eine modifizierte Hill-Chiffre mit Blocklänge über dem Alphabet und . Die Schlüsselmenge ist nun die Menge aller Matrizen mit Einträgen aus , wobei jede Matrix nur auf der Diagonalen von verschiedene Eintrage besitzt und gilt.

Diskutieren Sie jeweils einen - für den Angreifer möglichst effizienten - chosen plaintext, chosen ciphertext und known plaintext Angriff auf diese Chiffre.

Aufgabe 5
Gegeben sei eine natürliche Zahl . Zufällig gemäß der Gleichverteilung wird eine natürliche Zahl gewählt.

1. Bestimmen Sie die Wahrscheinlichkeit dafür, dass gilt.
2. Berechnen Sie die Wahrscheinlichkeit, wenn die Zahl das Produkt zweier verschiedener Primzahlen und ist. Bei welchen Zahlen und ist diese Wahrscheinlichkeit groß bzw. klein?

Aufgabe 6
Bei einer Hill-Chiffre über gehören zu den Nachrichten und die Chiffrate und .

Berechnen Sie die Verschlüsselungsmatrix .

Aufgabe 7
Die Einträge einer Schlüsselmatrix einer Hill-Chiffre über mit einer Primzahl seien einem Angreifer bis auf den Eintrag an der Position bekannt.

Kann der Angreifer die möglichen Werte für den Eintrag einschränken bzw. diesen eindeutig bestimmen?

Aufgabe 8
In einem Kryptosystem mit Nachrichtenmenge und Chiffratmenge besteht die Schlüsselmenge aus allen Matrizen mit Einträgen aus , wobei jede Zeile und jede Spalte aus genau eine enthält. Die Verschlüsselungsfunktion ist gegeben durch mit und , wobei ein Matrix-Vektorprodukt ist und alle Einträge von jeweils berechnet werden.

1. Wieviele Schlüssel enthält die Schlüsselmenge ?
2. Bestimmen Sie die Entschlüsselungsfunktion für dieses Kryptosystem.

Aufgabe 9
Wir erweitern das Kryptosystem mit aus der vorherigen Aufgabe dahingehend, dass wir als Schlüsselmenge wählen. Die Verschlüsselungsfunktion ist definiert durch mit , und , wobei alle Einträge von jeweils bestimmt werden.

1. Wie viele Schlüssel enthält die Menge ?
2. Bestimmen Sie die zugehörige Entschlüsselungsfunktion.
3. Wie könnte ein Angreifer bei einem chosen plaintext Angriff effizient vorgehen?

Aufgabe 10
Wir betrachten einen chosen plaintext Angriff auf das Kryptosystem aus Aufgabe 8.

Wieviele Nachrichten muss ein Angreifer höchstens wählen, um mit Wissen der entsprechenden Chiffrate den verwendeten Schlüssel eindeutig ermitteln zu können? Versuchen Sie, einen möglichst kleinen Wert für zu bestimmen.

Link zu den Lösungen