Hill-verschlüsselungsverfahren dekodieren

Question

Aufgabe:

Geheimtext: LJNJNUJNJNYBNZXDVLLVARJIQUAFMIGLSNDAXAECKHAHFOAOAHFRUTODN

Der Klartext beginnt mit: LITERATUREMP

Der Klartext wurde mit Hilfe einer (3,3)-Matrix über ℤ₂₆ berechnet (Hill-Verschlüsselungsverfahren).

Bestimmen Sie die für die Verschlüsselung genutze Matrix.

Problem/Ansatz:

LITERATUR als Zahlen, A=0, B=1,...

LIT, ERA, TUR = \( \begin{pmatrix} 11  \\ 8 \\ 19 \end{pmatrix} \) , \( \begin{pmatrix} 4 \\ 17 \\ 0\end{pmatrix} \) , \( \begin{pmatrix} 19  \\ 20 \\ 17 \end{pmatrix} \)

LJN, JNU, JNJ = \( \begin{pmatrix} 11  \\ 9 \\ 13 \end{pmatrix} \), \( \begin{pmatrix} 9  \\ 13 \\ 20 \end{pmatrix} \) , \( \begin{pmatrix} 9  \\ 13 \\ 9 \end{pmatrix} \)

Meine Idee:

Die inverse Matrix des Geheimwortes (LJNJNUJNJ)  * der Matrix des Klartextes (LITERATUR) ergibt die Schlüsselmatrix.

\( \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} \) = \( \begin{pmatrix} 11 & 9 & 13 \\ 9 & 13 & 20 \\ 9 & 13 & 9 \end{pmatrix} \)^-1  * \( \begin{pmatrix} 11 & 8 & 19 \\ 4 & 17 & 0 \\ 19 & 20 & 17 \end{pmatrix} \)  ( mod 26 )

Det(\( \begin{pmatrix} 11 & 9 & 13 \\ 9 & 13 & 20 \\ 9 & 13 & 9 \end{pmatrix} \)) = -579 = 19 mod 26

Jetzt suche ich das Inverse Element der Determinante.

Unter Anwendung des Erweitertet euklidischen Algorithmus komme ich auf 11 mod 26 ⇒

11 mod 26 ist das Inverse Element zu 19 mod 26.

Jetzt brauche ich die Adjunktive von \( \begin{pmatrix} 11 & 9 & 13 \\ 9 & 13 & 20 \\ 9 & 13 & 9 \end{pmatrix} \), da komme ich auf

\( \begin{pmatrix} 25 & 23 & 5 \\ 4 & 10 & 11 \\ 17 & 11 & 6 \end{pmatrix} \) = \( \begin{pmatrix} 25 & 4 & 17 \\ 23 & 10 & 11 \\ 5 & 11 & 6 \end{pmatrix} \)^T  = Adj^T

Auf die Inverse Matrix H^-1 komme ich durch H^-1 = det(x^-1 ) *  Adj ^T  (mod 26)

= \( \begin{pmatrix} 15 & 18 & 5 \\ 19 & 6 & 17 \\ 3 & 17 & 14 \end{pmatrix} \)

Also sollte die Schlüsselmatrix wie oben beschrieben durch:

\( \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} \) = \( \begin{pmatrix} 15 & 18 & 5 \\ 19 & 6 & 17 \\ 3 & 17 & 14 \end{pmatrix} \) * \( \begin{pmatrix} 11 & 8 & 19 \\ 4 & 17 & 0 \\ 19 & 20 & 17 \end{pmatrix} \) ( mod 26 )

zu berechnen sein.

Meine Schlüsselmatrix sieht wie folgt aus:

\( \begin{pmatrix} 20 & 6 & 6 \\ 10 & 22 & 0 \\ 3 & 21 & 9 \end{pmatrix} \), ist halt nur leider falsch.

Rechne ich Schlüsselmatrix * LIT = \( \begin{pmatrix} 11  \\ 8 \\ 19 \end{pmatrix} \) sollte eigentlich

LJN also gleich \( \begin{pmatrix} 11  \\ 9 \\ 13 \end{pmatrix} \) rauskommen, natürlich noch mod 26.

Tut es aber nicht.

Answer 1

Hallo Lars,

Die Determinante der Matrix $$A = \begin{pmatrix}11& 9& 13\\ 9& 13& 20\\ 9& 13& 9\end{pmatrix}$$ ist $$\begin{aligned}\det(A) = -682 \equiv 20 \mod 26\end{aligned}$$und damit hat sie die \(2\) als gemeinsamen Teiler mit der 26. \(A\) ist also in \(\mathbb Z_{26}\) nicht invertierbar.

Entweder stimmt Dein Geheimtext nicht oder die Blockgröße ist eine andere oder es ist gar keine Hill-Verschlüsselung.

Die von Dir berechnete Inverse ist keine, was sich auch leicht durch Multiplikation mit \(A\) überprüfen lässt.

Comments

Das ist der Kopierte Geheimtext:

LJNJNUJNJNYBNZXDVLLVARJIQUAFMIGLSNDAXAECKHAHFOAOAHFRUTODN

\( \begin{pmatrix} L \\ J \\ N\end{pmatrix} \)  = \( \begin{pmatrix} 11  \\ 9 \\ 13\end{pmatrix} \) Damit müsste das doch Stimmen, in der Aufgabe steht wörtlich "... mit dem Hill-Verschlüsselungsverfahren .." 

Beide Matrizen, die des Klartextes und die des Geheimwortes sind nicht invertierbar jetzt habe ich ehrlich gesagt keinen Ansatz mehr.

---

... und die Blockgröße ist \(3\) und es ist \(\mathbb Z_{26}\) und nicht vielleicht \(\mathbb Z_{27}\)? - ansonsten kann ich Dir auch nicht weiter helfen :-/

---

"...mit einer (3, 3)-Matrix über Z₂₆ berechnet"

Naja da weiß ich leider auch nicht weiter, aber kannst du denn bestätigen, dass der Ansatz so richtig ist? Also könnte man es so machen?

---

... Also könnte man es so machen?

Nicht ganz. Du schriebst:

Auf die Inverse Matrix H^-1 komme ich durch H^-1 = det(x^-1 ) *  Adj ^T (mod 26)

entweder ist das falsch, oder ich verstehe es nicht. Was ist \(x\) und was ist \(\text{Adj}\). Deine 'Inverse' war ja auch falsch.
Ansonsten ist Dein Ansatz richtig.

Ich würde die Inverse mit dem Gauß'schen Algorithmus berechnen. Dann sieht man auch sehr schnell, dass es keine Lösung gibt:$$\begin{array}{ccc|ccc}11& 9& 13& 1& 0& 0\\ 9& 13& 20& 0& 1& 0\\ 9& 13& 9& 0& 0& 1\end{array}$$Im ersten Schritt multipliziert man die erste Zeile mit \(19\)...$$11 \cdot 19 \equiv 1 \mod 26$$...damit links oben eine \(1\) steht und dann addiere ich das \(26-9=17\)-fache der ersten Zeile zu den beiden anderen Zeilen hinzu, damit in der ersten Spalte die \(0\)'en stehen bleiben:$$\begin{array}{ccc|ccc}1& 15& 13& 19& 0& 0\\ 0& 8& 7& 11& 1& 0\\ 0& 8& 22& 11& 0& 1\end{array}$$Jetzt stehen in der letzten Zeile links nur gerade Zahlen. Und für die existieren in \(\mathbb Z_{26}\) keine Inversen - man kommt also dort nie auf eine \(1\).

Bleibt noch die Frage, ob es nicht mehr als eine Lösung gibt. Das wäre auch mit einer nicht invertierbaren Matrix möglich. Ich habe ein wenig herumgerechnet, aber IMHO gibt es gar keine Lösung.

---

Also die Determinante habe ich mit dem Satz von Sarrus berechenet, aber da muss mir wohl irgendwo ein Fehler unterlaufen sein. Hätte nochmal prüfen sollen.

Die Formel die ich zur Berechnung der Inversen kenne lautet:

A^-1 = \( \frac{1}{det(A)} \) * Adjunktive(A) und da ich mit der Inversen Determiante rechne wird aus \( \frac{1}{det(A)} \) halt (det(A))^-1  .

Werde mal das Internet durchforsten um vielleicht eine Antwort zufinden, trotzdem vielen danke für deine Hilfe!

Lasse den Post noch offen, vielleicht hat noch jemand eine Idee :)

€: Die Schreibweise mit dem det(x^-1) habe ich irgendwo aufgenommen, ist warscheinlich nicht so schlau und das ^t bei der Adjunktive kann man denke ich auch weglassen.

---

Oh ja passt; siehe Adjunkte. Das hatte ich vor grauer Vorzeit auch mal gewusst ;-)