Bestimmen Sie die Inverse von A mit Hilfe des Gaußschen Algorithmus

Question

Hallo, kann mir bitte jemand bei den einzelnen Aufgaben helfen?

Vielen Dank im Voraus!!

In dieser Aufgabe geht es um eine Anwendung der linearen Algebra in der Kryptographie (ein Beispiel für eine sogenannte Hill-Chiffre \( ) . \) Unser Alphabet bestehe aus den 26 Buchstaben \( \mathrm{A}, \mathrm{B}, \ldots \) \( \mathrm{Z}, \) sowie den Zeichen \( ,(\mathrm{Komma}) .(\text { Punkt }) \) und dem Leerzeichen. Diese identifizieren wir wie folgt mit den Elementen des Körpers \( \mathbb{Z}_{29} \) (wir schreiben im Folgenden nur \( \left.[a] \text { anstelle von }[a]_{29}\right) \):

$$ \left.\begin{array}{l} \left(\begin{array}{ccccccccc} {[0]} & {[1]} & {[2]} & {[3]} & {[4]} & {[5]} & {[6]} & {[7]} & {[8]} & {[9]} & {[10]} \\ A & B & C & D & E & F & G & H & I & J & K \end{array}\right) \\ \left(\left[\begin{array}{cccc} 11] & {[12]} & {[13]} & {[14]} & {[15]} & {[16]} & {[17]} & {[18]} & {[19]} \\ L & M & N & O & P & Q & R & S & T \end{array}\right)\right. \\ \left(\begin{array}{cccc} {[20]} & {[21]} & {[22]} & {[23]} & {[24]} & {[25]} & {[26]} & {[27]} & {[28]} \\ U & V & W & X & Y & Z \end{array}\right. \end{array}\right) $$
Ferner sei
$$ A:=\left(\begin{array}{cc} {[5]} & {[14]} \\ {[12]} & {[8]} \end{array}\right) $$
Ist nun eine Nachricht bestehend aus \( 2 n \) Zeichen gegeben \( ^{1} \), so übersetzen wir diese zunächst gemäß des obigen Schemas in eine Liste aus \( 2 n \) Elementen von \( \mathbb{Z}_{29} \) und teilen diese dann auf in \( n \) Spaltenvektoren \( x_{1}, \ldots, x_{n} \in \mathbb{Z}_{29}^{2} \) Daraus bilden wir dann die Vektoren \( y_{1} \ldots ., y_{n} \in \mathbb{Z}_{29}^{2} \) gemäß \( y_{i}:=A x_{i} \) für \( i=1, \ldots, n . \) Die Einträge \( y_{1}, \ldots, y_{n} \) fügen wir wieder hintereinander zu einer Liste der Länge \( 2 n \) in \( \mathbb{Z}_{29}^{2} \) zusammen und übersetzen diese dann wieder gemäß des obigen Schemas in eine Nachricht in unserem Alphabet. Das ist die verschlüsselte Nachricht.

Zum Entschlüsseln einer gegebenen Nachricht geht man genauso vor, nur dass man mit der Inversen \( A^{-1} \) multipliziert
1) Bestimmen Sie die Inverse von \( A \) mit Hilfe des Gaußschen Algorithmus
2) Verschlüsseln Sie das Wort MATHEMATIK
3) Die verschlüsselte Nachricht laute nun: QX.LSO,BHR Entschlüsseln Sie diese (Geben Sie jeweils Ihre Rechenschritte mit an.)

Answer 1

Ich lass mal die Klassenzeichen [  ] weg und rechne gleich

Modulo 29

5    14      1     0       | * 12
12    8      0     1       | * 5

2     23    12     0
2     11      0     5     2. - 1.

2     23    12     0
0     17    17     5       | *12

Das Inverse von 17 ist 12, wegen 17*12=1

2     23    12     0   
0      1       1     2   | *23

2     23    12     0 
0     23    23    17    1. - 2.

2      0     18    12
0     23    23     17  | : 23

2      0     18    12    : 2 
0      1       1      2

1      0        9     6
0      1       1      2

also inverse Matrix

  9   6
  1   2

Comments

Danke, sehr hilfreiche Antwort!

Wie müsste ich bei der 2. Teilaufgabe vorgehen?

---

Jetzt die Spaltenvektoren bilden, also

aus M wird 12 und aus A wird 0 , also ist der erste Spalte  x1=

12
0

Dann Matrix A mal  12   das gibt  60  also mod 29  dann 2
                                 0                 144                              28

Das ist dann das y1

etc.

---

Dem kann ich irgendwie nicht ganz folgen.

---

Also mal langsamer:

Du hast ja die Anweisung:

Ist nun eine Nachricht bestehend aus 2n Zeichen gegeben, so übersetzen wir diese zunächst gemäß des obigen Schemas in eine Liste aus 2n Elementen von Z₂₉

Für das Wort MATHEMATIK wäre n=5 also 2n=10 und die

"Übersetzung" ist einfach die Folge der Verschlüsselungszahlen

12   0   19  7   4   12   0 19  8   10

Diese soll man ja  nun aufteilen in n Spaltenvektoren

$$\begin{pmatrix} 12\\0 \end{pmatrix}\begin{pmatrix} 19\\7 \end{pmatrix}\begin{pmatrix} 4\\12 \end{pmatrix}\begin{pmatrix} 0\\19 \end{pmatrix}\begin{pmatrix} 8\\10 \end{pmatrix}$$

Jetzt verschlüsseln durch: Matrix A * Spaltenvektor gibt

C TXO FHGC

als verschlüsselte Nachricht. Beachte 28 bedeutet Leerzeichen.