Matrix finden: Hill-Chiffre

Neue Frage »

18.03.2025, 19:43

Malcang

Auf diesen Beitrag antworten »

Matrix finden: Hill-Chiffre

Hallo zusammen smile

ich habe eine Frage zu dieser Aufgabe (wobei es diesmal nicht um die Chiffrierung geht smile

)
[attach]58204[/attach]

Die Hill-Chiffre ist einfach definiert durch $\begin{eqnarray*} A\cdot x = m \end{eqnarray*}$ , in dem Falle also
$\begin{eqnarray*} A\cdot\begin{pmatrix} 3 \\ 8 \end{pmatrix} = \begin{pmatrix} 24 \\ 23 \end{pmatrix} \end{eqnarray*}$ , $\begin{eqnarray*} A\cdot\begin{pmatrix} 4 \\ 18 \end{pmatrix} = \begin{pmatrix} 22 \\ 14 \end{pmatrix} \end{eqnarray*}$ und so weiter.
Nun könnte ich mir ja zwei Vektoren nehmen und zu einer Matrix zusammenfassen, z.B.
$\begin{eqnarray*} A\cdot\begin{pmatrix} 3 & 4\\ 8 & 18 \end{pmatrix} = \begin{pmatrix} 24 & 22 \\ 23 & 14 \end{pmatrix} \end{eqnarray*}$ , und dann über die inverse Matrix gehen.
Das ist aber hier nicht so einfach möglich, da $\begin{eqnarray*} \det \cdot\begin{pmatrix} 3 & 4\\ 8 & 18 \end{pmatrix} \end{eqnarray*}$ nicht teilerfremd zu $\begin{eqnarray*} 26 \end{eqnarray*}$ ist.
Durch Ausprobieren habe ich herausgefunden, dass es aber mit $\begin{eqnarray*} \begin{pmatrix} 3 & 8\\ 8 & 13 \end{pmatrix} \end{eqnarray*}$ geht, also das erste und letzte Paar betrachtet.

Aber ginge das ohne Berechnung der Determinante schneller? Oder anders: Wie könnte ich sehen, dass es mit dem erstgenannten Versuch nicht klappt bzw. mit dem letztgenannten schon?

18.03.2025, 20:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
$\begin{eqnarray*} A\cdot\begin{pmatrix} 3 \\ 8 \end{pmatrix} = \begin{pmatrix} 24 \\ 23 \end{pmatrix} \end{eqnarray*}$ , $\begin{eqnarray*} A\cdot\begin{pmatrix} 4 \\ 18 \end{pmatrix} = \begin{pmatrix} 22 \\ 14 \end{pmatrix} \end{eqnarray*}$

Die Lösung dieses Systems ist nicht eindeutig: Z.B. könnte man die zweite Gleichung "durch 2" teilen, was in $\begin{eqnarray*} \mathbb{Z}_{26} \end{eqnarray*}$ dann in vier mögliche Gleichungen mündet

$\begin{eqnarray*} A\cdot\begin{pmatrix} 2 \\ 9 \end{pmatrix} = \begin{pmatrix} 11+13u \\ 7+13v \end{pmatrix} \end{eqnarray*}$ mit $\begin{eqnarray*} u,v\in\{0,1\} \end{eqnarray*}$

Die entstehende Matrix-Gleichung

$\begin{eqnarray*} A\cdot\begin{pmatrix} 3 & 2\\ 8 & 9 \end{pmatrix} = \begin{pmatrix} 24 & 11+13u \\ 23 & 7+13v \end{pmatrix} \end{eqnarray*}$

dürfte dann aber für feste $\begin{eqnarray*} u,v \end{eqnarray*}$ eindeutig in $\begin{eqnarray*} \mathbb{Z}_{26} \end{eqnarray*}$ lösbar sein.

----------------------------------------------

Ist natürlich richtig, dass man sich besser gleich zwei Vektoren sucht mit einer Determinante, die teilerfremd zu 26 ist. Das kann offenbar allenfalls mit Vektoren $\begin{eqnarray*} x \end{eqnarray*}$ geschehen, wo der ggT der Komponenten teilerfremd zu 26 ist - insbesondere dürfen also nicht beide Komponenten gerade sein - womit die Paare Nr. 2 und 3 von vornherein als untauglich ausscheiden.

18.03.2025, 21:10

URL

Auf diesen Beitrag antworten »

Die Idee finde ich gut, und viel mehr als HALs Ausführungen fällt mir auch nicht mehr ein.

Zitat:

Das kann offenbar allenfalls mit Vektoren x geschehen, wo der ggT der Komponenten teilerfremd zu 26 ist

Ein Vektor, bei dem das nicht gilt, ist ja quasi ein Nullvektor Augenzwinkern

Daher ist es plausibel, dass ein solcher Vektor in einer Matrix quasi für eine Nullspalte sorgt und damit die Invertierbarkeit der Matrix zerstört.
Analog kann man natürlich für quasi Nullzeilen der Matrix argumentieren. Aus dem Grund scheidet dann die Wahl von $\begin{eqnarray*} \begin{pmatrix}24\\23\end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} \begin{pmatrix}10\\13\end{pmatrix} \end{eqnarray*}$ aus. Der ggT der ersten Komponenten ist nicht teilerfremd zu 26.
Damit bleiben nur noch zwei Konstellationen zur Auswahl.

19.03.2025, 08:53

HAL 9000

Auf diesen Beitrag antworten »

Technisch gesehen handelt es sich hier um ein überbestimmtes lineares Gleichungssystem für $\begin{eqnarray*} 2^2=4 \end{eqnarray*}$ Variablen:

Durch "Umarrangieren" kann man $\begin{eqnarray*} A = \begin{pmatrix} a_1 & a_2\\ a_3 & a_4\end{pmatrix} \end{eqnarray*}$ identifizieren mit dem Vektor $\begin{eqnarray*} a = \left(a_1,a_2,a_3,a_4\right)^T\in \mathbb{Z}_{26}^4 \end{eqnarray*}$ .

Gleichung $\begin{eqnarray*} A\cdot \begin{pmatrix} 3\\ 8\end{pmatrix} = \begin{pmatrix} 24\\ 23\end{pmatrix} \end{eqnarray*}$ wird dann zur Gleichung $\begin{eqnarray*} \begin{pmatrix} 3 & 8 & 0 & 0\\ 0 & 0 & 3 & 8\end{pmatrix}\cdot a = \begin{pmatrix} 24\\ 23\end{pmatrix} \end{eqnarray*}$ .

Bei deinen fünf Chiffre-Paaren hat man dann insgesamt zehn Gleichungen, d.h. ein $\begin{eqnarray*} 10\times 4 \end{eqnarray*}$ -Gleichungssystem für $\begin{eqnarray*} a \end{eqnarray*}$ (vereinfacht sind es zwei $\begin{eqnarray*} 5\times 2 \end{eqnarray*}$ -Gleichungssysteme für die beiden "Hälften" von $\begin{eqnarray*} a \end{eqnarray*}$ ) - das meine ich mit "überbestimmt". Sofern kein Fehler in den Chiffre-Paaren vorliegt, sollte es aber eine Lösung haben.

19.03.2025, 09:04

Malcang

Auf diesen Beitrag antworten »

Guten Morgen zusammen,

danke für eure Hilfen!!

HAL, das war schonmal ein guter Hinweis dass ich mich notwendigerweise an Koeffizienten orientiere, die selbst teilerfremd zu $\begin{eqnarray*} 26 \end{eqnarray*}$ sind.

Eine Lösung gibt es übrigens, diese ist $\begin{eqnarray*} A = \begin{pmatrix} 14 & 1 \\ 9 & 6 \end{pmatrix} \end{eqnarray*}$

Neue Frage »

Antworten »

Matrix finden: Hill-Chiffre

Verwandte Themen