o-mathe | Einstieg - Ein Zahlenadditionsverfahren » Erarbeitung

Erarbeitung - Ein Matrixmultiplikationsverfahren

Zur Orientierung

Die Verschlüsselung mit dem Zahlenadditionsverfahren ist in der Praxis völlig untauglich. Wenn man den Schlüssel und das Verfahren kennt, mit dem eine Nachricht verschlüsselt wurde, dann kann man direkt den Gegenschlüssel erzeugen und mit diesem Gegenschlüssel die Verschlüsselung rückgängig machen.

Leitfrage

Kann man das Matrixprodukt verwenden, um ein besseres Verschlüsselungsverfahren zu entwickeln?

Mit einem Matrixmultiplikationsverfahren verschlüsseln

Wir betrachten hier ein Verschlüsselungsverfahren, das angeleht ist an ein Verfahren, das von Lester Hill im Jahr 1929 entwickelt wurde. Die Grundidee besteht darin, die Zeichen des Quelltextes in Zahlen umzuwandeln, diese Zahlen dann in Matrixform anzuodnen und die entstehende Matrix dann mit einer Schlüsselmatrix zu multiplizieren.

Zum Herunterladen: verschluesselung2a.ggb

Verschlüsselung mit dem Matrixmultiplikationsverfahren

Schritt 1: Schlüsselwahl
Als Schlüssel wird eine quadratische Matrix $S$ gewählt. Im Applet ist das die Schlüsselmatrix $S = (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$ . Weitere Anforderungen an die Schlüsselmatrix werden wir im nächsten Abschnitt thematisieren. Die Größe der Matrix muss vorab festgelegt werden. Im Applet ist eine kleine $2 \times 2$ -Matrix gewählt.

Schritt 2: Codierung
Alle Zeichen des Quelltextes werden in Zahlen umgewandelt. Zur Umwandlung wird die ASCII-Tabelle benutzt. Die Zahlen werden anschließend in Matrixform angeordnet. Die Größe der hierdurch entstehenden Quellcodematrix $M$ muss passend zur Größe der gewählten Schlüsselmatrix $S$ gewählt werden. Im Appletbeispiel muss die Quellcodematrix $2$ Spalten haben, um sie mit der Schlüsselmatrix $S$ multiplizieren zu können. Wenn wie im Appletbeispiel die Matrix mit den Codezahlen nicht ganz ausgefüllt ist, dann wird sie mit Nullen aufgefüllt.

Schritt 3: Verschlüsselung
Die Schlüsselmatrix $S$ wird mit der Quellcodematrix $M$ multipliziert. Man erhält so eine Geheimcodematrix $M^{'}$ mit $M^{'} = S \cdot M$ . Abschließend werden die Zahlen der Geheimcodematrix $M^{'}$ linear angeordnet. Die Liste dieser Zahlen wird als Geheimcodenachricht weitergegeben.

Aufgabe 1

Teste zunächst das Matrixmultiplikationsverfahren mit dem Applet.

Führe dann selbstständig eine Verschlüsselung mit dem Matrixmultiplikationsverfahren durch. Benutze die Schlüsselmatrix $S = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ und verschlüssele die Nachricht Achtung!.

Zur Ermittlung der Codezahlen kannst du das folgende ASCII-Applet benutzen.

Zum Herunterladen: ascii.ggb

Kontrolliere die ermittelte verschlüsselte Nachricht abschließend mit dem Applet oben.

Mit dem Matrixmultiplikationsverfahren entschlüsseln

Die Entschlüsselung beim Matrixmultiplikationsverfahren funktioniert ganz analog zum Verschlüsseln.

Entschlüsselung mit dem Zahlenadditionsverfahren

Schritt 1: Gegenschlüsselwahl
Die eine Gegenschlüsselmatrix $S^{'}$ muss man passend zur Schlüsselmatrix $S$ wählen. Wie man dabei vorgeht, bleibt hier vorerst offen.

Schritt 2: Entschlüsselung
Die Zahlen aus dem Geheimcode werden zunächst in Matrixform angeordnet. Die Größe dieser Geheimcodematrix $M^{'}$ muss passend zur Größe der Gegenschlüsselmatrix $S^{'}$ gewählt werden. Die Gegenschlüsselmatrix $S^{'}$ wird dann mit der Geheimcodematrix $M^{'}$ multipliziert. Man erhält so eine Quellcodematrix $M$ mit $M = S^{'} \cdot M^{'}$ . Die Zahlen dieser Quellcodematrix $M$ werden dann zu einem Quellcode linear angeordnet. Nullen am Ende dieser Zahlenliste werden ggf. entfernt.

Schritt 3: Decodierung
Alle Zahlen aus dem Quellcode werden in Zeichen umgewandelt. Zur Umwandlung wird die ASCII-Tabelle benutzt.

Zum Herunterladen: entschluesselung2a.ggb

Aufgabe 2

Das Entschlüssseln einer Nachricht macht das Verschlüsseln wieder rückgängig. Beim Matrixmultiplikationsverfahren spielen dabei die Schlüsselmatrix $S$ und die Gegenschlüsselmatrix $S^{'}$ eine wichtige Rolle. Die folgende Übersicht verdeutlicht das Zusammenspiel dieser beiden Matrizen zusammen mit der Matrixmultiplikation.

$\begin{array}{cl} \underset{M}{\underset{⏟}{(\begin{matrix} 72 & 97 & 108 \\ 108 & 111 & 0 \end{matrix})}} \\ ↓ & Verschlüsselung mit S \\ \underset{S}{\underset{⏟}{(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})}} \cdot \underset{M}{\underset{⏟}{(\begin{matrix} 72 & 97 & 108 \\ 108 & 111 & 0 \end{matrix})}} \\ ↓ & Entschlüsselung mit S^{'} \\ \underset{S^{'}}{\underset{⏟}{(\begin{matrix} - 2 & 1 \\ 1.5 & - 0.5 \end{matrix})}} \cdot [\underset{S}{\underset{⏟}{(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})}} \cdot \underset{M}{\underset{⏟}{(\begin{matrix} 72 & 97 & 108 \\ 108 & 111 & 0 \end{matrix})}}] \\ ↓ & Umformung mit dem Assoziativgesetz \\ [\underset{E}{\underset{⏟}{\underset{S^{'}}{\underset{⏟}{(\begin{matrix} - 2 & 1 \\ 1.5 & - 0.5 \end{matrix})}} \cdot \underset{S}{\underset{⏟}{(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})}}}}] \cdot \underset{M}{\underset{⏟}{(\begin{matrix} 72 & 97 & 108 \\ 108 & 111 & 0 \end{matrix})}} \end{array}$

(a) Erläutere zunächst alle Schritte in der Übersicht.

(b) Berechne das Produkt $E = S^{'} \cdot S = \underset{E}{\underset{⏟}{\underset{S^{'}}{\underset{⏟}{(\begin{matrix} - 2 & 1 \\ 1.5 & - 0.5 \end{matrix})}} \cdot \underset{S}{\underset{⏟}{(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})}}}} = \dots$ .

(c) Berechne das Produkt $E \cdot M = \underset{E}{\underset{⏟}{(\begin{matrix} \dots & \dots \\ \dots & \dots \end{matrix})}} \cdot \underset{M}{\underset{⏟}{(\begin{matrix} 72 & 97 & 108 \\ 108 & 111 & 0 \end{matrix})}} = \dots$ .

(d) Vergleiche das Matrixmultiplikationsverfahren mit dem Zahlenadditionsverfahren und erläutere die Analogien.

$\begin{array}{ll} C \\ ↓ & Verschlüsselung mit s \\ C + s \\ ↓ & Entschlüsselung mit s^{'} \\ (C + s) + s^{'} \\ ↓ & Umformung mit dem Assoziativgesetz \\ C + (s + s^{'}) \\ ↓ & Gegenschlüsselprinzip: s + s^{'} = 0 bzw. s^{'} = - s \\ C + 0 \\ ↓ & Nullverschiebung \\ C \end{array}$

←Zurück Weiter→