Lösen modularer Gleichungen für Angriff auf Hill-Chiffre

31.12.2012, 13:50

tejubin

Lösen modularer Gleichungen für Angriff auf Hill-Chiffre

Meine Frage:
Hallo Leute!

Zunächst einmal, ich versuche einen mit der Hill-Chiffre verschlüsselten Text zu entschlüsseln. Für die Verschlüsselung wurde eine $\begin{eqnarray*} 2 \times 2 \end{eqnarray*}$ -Matrix verwendet. Zusätzlich bekommt man als Hinweis, dass die Bi-Gramme "CH" (entspricht $\begin{eqnarray*} \begin{pmatrix} 2 \\ 7 \end{pmatrix} \end{eqnarray*}$ ) und "EI" ( entspricht $\begin{eqnarray*} \begin{pmatrix} 4 \\ 8 \end{pmatrix} \end{eqnarray*}$ ) im Klartext am häufigsten vorkommen.

Eine Häufigkeitsanalyse der Bi-Gramme im Geheimtext ergibt, dass das häufigste Bi-Gramm "QP" ( $\begin{eqnarray*} \begin{pmatrix} 16 \\ 15 \end{pmatrix} \end{eqnarray*}$ ) ist. Zusätzlich erscheinen vier Bi-Gramme mit gleicher Häufigkeit ("TC", "MT","IL","BZ" $\begin{eqnarray*} = \begin{pmatrix} 19 \\ 2 \end{pmatrix},\ \begin{pmatrix} 12 \\ 19 \end{pmatrix},\ \begin{pmatrix} 8 \\ 11 \end{pmatrix},\ \begin{pmatrix} 1 \\ 25 \end{pmatrix} \end{eqnarray*}$ ).

Meine Ideen:
Mein Ansatz ist der folgende:

$\begin{eqnarray*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot \begin{pmatrix} 2 \\ 7 \end{pmatrix} = \begin{pmatrix} 16 \\ 15 \end{pmatrix} \end{eqnarray*}$ wenn "CH" auf "QP" abgebildet wird durch die Verschlüsselungsmatrix $\begin{eqnarray*} H = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{eqnarray*}$ . Zusätzlich wird dann ja noch "EI" abgebildet, sagen wir auf "TC":
$\begin{eqnarray*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot \begin{pmatrix} 4 \\ 8 \end{pmatrix} = \begin{pmatrix} 19 \\ 2 \end{pmatrix} \end{eqnarray*}$ .
Hiermit möchte ich nun versuchen die Matrix $\begin{eqnarray*} H \end{eqnarray*}$ zu bestimmen. Ich habe:

$\begin{eqnarray*} 4a + 8b &\equiv 19\ \text{mod}\ 26 2a + 7b &\equiv 16\ \text{mod}\ 26 \end{eqnarray*}$

beim Betrachten der jeweils ersten Zeile.
Dieses Gleichungssystem ist aber nicht lösbar, denn durch Abziehen des doppelten der zweiten Zeile von der ersten gelange ich zu

$\begin{eqnarray*} 20b &\equiv 13\ \text{mod}\ 26 \end{eqnarray*}$

und $\begin{eqnarray*} 20 \end{eqnarray*}$ hat keine Inverse modulo $\begin{eqnarray*} 26 \end{eqnarray*}$ . Dieses Phänomen tritt bei jedweder Kombination von Abbildung von "CH" und "EI" auf, ist anscheinend somit unabhängig davon, wovon diese jeweils abgebildet werden. Es scheint mir, ich habe etwas grundlegend falsch gemacht. Wenn mir jemand auf die Sprünge helfen könnte, wäre das super!

31.12.2012, 14:38

Dopap

Auf diesen Beitrag antworten »

ich sehe 2 Ansätze:

1.) eine oder 2 Klartext-Kompromittierungen werden wohl nicht genügen. Ich vermute mal, dass mindestens 4 davon nötig sind.

2.) die Hillmatrix ist nicht einfach irgendeine Matrix mit 4 unabhängigen Elementen.
zur Herstellung sind einige Schritte erforderlich:

H=(eine untere reguläre Dreiecksmatrix) x (der transponierten oberen regulären Dreiecksmatrix) modulo 26.

$\begin{eqnarray*} H=\begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix}\cdot \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix} \text{modulo 26} \end{eqnarray*}$

das könnte weiterhelfen.

31.12.2012, 14:49

tejubin

Auf diesen Beitrag antworten »

Danke für deine Antwort.

Zunächst wissen wir über die Matrix $\begin{eqnarray*} H = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{eqnarray*}$ dass diese invertierbar ist. Somit gilt $\begin{eqnarray*} \gcd{(ab - cd,26)} = 1 \end{eqnarray*}$ , mehr benötigt man meines Wissens nach nicht. Jede invertierbare Matrix ist ein möglicher Schlüssel der Hill-Chiffre.

Zu deinem anderen Punkt: Wir haben von der Professorin erfahren, dass diese Tipps ("CH" und "EI" am häufigsten im Klartext) ausreichend sind und man nun mit Hilfe vom Lösen geeigneter modularer Gleichungssysteme auf die Matrix $\begin{eqnarray*} H \end{eqnarray*}$ schließen kann. Somit dann auf die Inverse und den Klartext.

Was sind denn die weiteren Anforderung an die Hill-Matrix deines Wissens nach?

Grüße

31.12.2012, 14:54

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
1.) eine oder 2 Klartext-Kompromittierungen werden wohl nicht genügen. Ich vermute mal, dass mindestens 4 davon nötig sind.

Tatsächlich resultieren die 2 Bi-gramme mit bekannter Verschlüsselung in 4 Kongruenzen mod 26... Wo ist also das Problem? verwirrt

Zitat:

Original von Dopap
2.) die Hillmatrix ist nicht einfach irgendeine Matrix mit 4 unabhängigen Elementen.
zur Herstellung sind einige Schritte erforderlich:

H=(eine untere reguläre Dreiecksmatrix) x (der transponierten oberen regulären Dreiecksmatrix) modulo 26.

$\begin{eqnarray*} H=\begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix}\cdot \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix} \text{modulo 26} \end{eqnarray*}$

das könnte weiterhelfen.

Definitiv nicht, denn dann gäbe es ja für H höchstens 26 Möglichkeiten, je nach Wert von a mod 26, oder hab ich da was mißverstanden? verwirrt

31.12.2012, 14:55

tejubin

Auf diesen Beitrag antworten »

Genau so sehe ich das auch. Nur verstehe ich noch nicht, was ich genau falsch gemacht habe..

31.12.2012, 15:20

Mystic

Auf diesen Beitrag antworten »

RE: Lösen modularer Gleichungen für Angriff auf Hill-Chiffre
Ich hab leider im Moment auch nicht die Zeit, alle Möglichkeiten durchzuprobieren, verstehe aber nicht, wieso du solche Zuordnungen wie z.B.

$\begin{eqnarray*} \binom 48 \mapsto \binom {19}2 \end{eqnarray*}$

überhaupt betrachtest, denn die Gleichung

$\begin{eqnarray*} 4a+8b=19 \mod 26 \end{eqnarray*}$

ist ja schon ein offensichtlicher Widerspruch, da die linke Seite durch 4 teilbar ist, der ggT(4, 26)=2 aber die rechte Seite der Kongruenz nicht teilt...

Daher kommt von vornherein nur

$\begin{eqnarray*} \binom 48 \mapsto \binom {16}{15} \end{eqnarray*}$ oder $\begin{eqnarray*} \binom {12}{19} \end{eqnarray*}$ oder $\begin{eqnarray*} \binom {8}{11} \end{eqnarray*}$

in Frage... Versuch vielleicht mit ähnlichen Betrachtungen bez. c und d weitere Einschränkungen zu gewinnen...

31.12.2012, 15:44

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Definitiv nicht, denn dann gäbe es ja für H höchstens 26 Möglichkeiten, je nach Wert von a mod 26, oder hab ich da was mißverstanden? verwirrt

Nein, da hast du recht. Ich bin zu sehr von der Praxis mit Hillmatrizen von z.B. 256 Elementen ausgegangen.

31.12.2012, 15:55

Mystic

Auf diesen Beitrag antworten »

Seh übrigens gerade, dass als Bild von

$\begin{eqnarray*} \binom 48 \end{eqnarray*}$

keines der angebotenen in Frage kommt... Da hast entweder einen Rechenfehler oder du musst die Liste der häufigsten Bigramme im Chiffre erweitern...

31.12.2012, 16:16

tejubin

Auf diesen Beitrag antworten »

Danke für den Tipp, ich gucke mir das im neuen Jahr mal an! Euch einen guten Rutsch und vielen Dank für die Hilfe bisher! smile

31.12.2012, 18:33

Dopap

Auf diesen Beitrag antworten »

falls es von Interesse ist , ein Beispiel für eine Konstruktion im Falle N=3, was immer noch viel zu klein ist, da Angriffe über Häufigkeiten auch hier noch möglich wären.
---------------------------------------------------------------
sei $\begin{eqnarray*} D=\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 5 & 2 & 1 \end{pmatrix} \end{eqnarray*}$
man wähle in der Diagonalen Einsen. Ansonsten egal. ( bis auf die Nullen)

$\begin{eqnarray*} D^T=\begin{pmatrix} 1 & 3 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} D\cdot D^T=\begin{pmatrix} 1 & 3 & 5 \\ 3 & 10 & 17 \\ 5 & 17 & 30 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} D\cdot D^T \text {mod}~ 26= C=\begin{pmatrix} 1 & 3 & 5 \\ 3 & 10 & 17 \\ 5 & 17 & 4 \end{pmatrix} \end{eqnarray*}$
zum Verschlüsseln.
---------------------------------------
Die Hillinverse:

$\begin{eqnarray*} INV(D)= \begin{pmatrix} 1 & 0 & 0\\ -3 & 1 & 0 \\ 1 & -2 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} INV(D^T)= \begin{pmatrix} 1 & -3 & 1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} INV(D)\cdot INV(D^T)=\begin{pmatrix} 11 & -5 & 1 \\ -5 & 5 & -2 \\ 1 & -2 & 1 \end{pmatrix} \end{eqnarray*}$

und jetzt noch Modulo 26:

$\begin{eqnarray*} M= \begin{pmatrix} 11 & 21 & 1 \\ 21 & 5 & 24 \\ 1 & 24 & 1 \end{pmatrix} \end{eqnarray*}$ zum Entschlüsseln.

guten Rutsch!

01.01.2013, 18:19

tejubin

Auf diesen Beitrag antworten »

RE: Lösen modularer Gleichungen für Angriff auf Hill-Chiffre

Zitat:

Original von tejubin
Dieses Gleichungssystem ist aber nicht lösbar, denn durch Abziehen des doppelten der zweiten Zeile von der ersten gelange ich zu

$\begin{eqnarray*} 20b &\equiv 13\ \text{mod}\ 26 \end{eqnarray*}$

und $\begin{eqnarray*} 20 \end{eqnarray*}$ hat keine Inverse modulo $\begin{eqnarray*} 26 \end{eqnarray*}$ .

Ich stand auf dem Schlauch, es stimmt zwar, dass dieses Gleichungssystem nicht lösbar ist, aber nicht weil $\begin{eqnarray*} 20 \end{eqnarray*}$ keine Inverse in $\begin{eqnarray*} \mathbb{Z}_{26} \end{eqnarray*}$ hat, sondern weil der ggT $\begin{eqnarray*} (20,26) = 2 \end{eqnarray*}$ nicht die $\begin{eqnarray*} 13 \end{eqnarray*}$ teilt. Dieses trifft nicht bei anderen Zuordnungskombinationen auf. Ich dachte, es läge an der Nichtinvertierbarkeit von $\begin{eqnarray*} 20 \end{eqnarray*}$ .

Damit mache ich nun weiter..

Neue Frage »

Antworten »

Lösen modularer Gleichungen für Angriff auf Hill-Chiffre

Verwandte Themen