Frage zu Hill-Chiffre

31.10.2012, 18:44

petermueller

Frage zu Hill-Chiffre

Meine Frage:
- Gegeben sei der Schlüssel
$\begin{eqnarray*} \begin{pmatrix} 1 & 2 \\ 3 & 4\end{pmatrix} \end{eqnarray*}$
Finden Sie zwei Nachrichten, die dieselbe Chiffre erzeugen.

-Gegeben sei der Chiffretext GEZXDS, der mit einer 2x2 Matrix verschlüsselt wurde. Der Klartext ist solved. Berechnen Sie den Schlüssel.

Meine Ideen:
1) Ok den ersten Punkt würde ich wahrscheinlich noch hinkriegen. Allerdings höchstens mit probieren, habe grad keinen so rihtigen Ansatz
Das Alphabet bilde ich auf Zahlen ab, also (a = 0, b = 1, c = 2, ...)
Zum verschlüsseln habe ich dann die Formel:
$\begin{eqnarray*} c = m * k mod 26 \end{eqnarray*}$
also für ab = (0 1):
$\begin{eqnarray*} c = (0 & 1) * \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} mod 26 = (3 & 4) \end{eqnarray*}$
Wenn ich nun wieder $\begin{eqnarray*} (3 & 4) \end{eqnarray*}$ erhalten will bei selbem Key, wie käme ich da ran? Gleichungssystem aufstellen?
$\begin{eqnarray*} c = (x & y) * \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} mod 26 = (3 & 4) \end{eqnarray*}$ ?

2) Zum Entschlüssel brauche ich $\begin{eqnarray*} k^{-1} \end{eqnarray*}$ , weder k noch die inverse ist aber ja gegeben. Die Entschlüsselungsformel ist: $\begin{eqnarray*} m=c*k^{-1} & mod & 26 \end{eqnarray*}$
Also:
(18 14 11 21 4 3) = (6 4 25 23 3 18)*k^(-1) mod 26

Da habe ich wohl auch noch ein Verständnisproblem, wie verschlüssel ich mit der Matrix aus 1) denn überhaupt Nachrichten, die länger als zwei Zeichen sind?! unglücklich

01.11.2012, 23:19

chris_78

Auf diesen Beitrag antworten »

Vorweg, ich hatte mit dem Thema bislang noch nie zu tun, habe mir das aber aus Interese mal angesehen.

Als erstes finde ich da als Gleichung überall $\begin{eqnarray*} (k * m) mod 26=c \end{eqnarray*}$
Also Darstellung der Nachricht m als Spaltenvektor. Müsste natürlich auch so gehen, wie Du es machst, aber das führt ja durchaus zu einer anderen Chiffre.

Zu 1) Zwei Nachrichten, die dieselbe Ciffre erzeugen:
Meiner Meinung nach kann es das bei gleichbleibendem Schlüssel und Modulo nicht geben. Außerdem will ich ja vom Chiffre-Text wieder zum Originaltext kommen. Es müsste ja dann mehere mögliche Originaltext geben, wenn 2 Originaltexte dieselbe Chiffre erzeugen.

Zu 2)
Stimmt mit einer 2x2 Matrix kann ich nur 2 Zeichen verschlüsseln. Nachrichten die länger sind, zerlegt man deshalb in 2er-Blöcke, also SO wurde zu GE, LV zu ZX und ED zu DS.
Daraus kann man dann für den 1. Block folgende Gelichungen aufstellen:
$\begin{eqnarray*} \begin{pmatrix} a & b \\ c & d \end{pmatrix}* \begin{pmatrix} 18 \\ 14 \end{pmatrix} mod 26 =\begin{pmatrix} 6 \\ 4 \end{pmatrix} \end{eqnarray*}$ (Verschlüsselung)

$\begin{eqnarray*} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}* \begin{pmatrix} 6 \\ 4 \end{pmatrix} mod 26 =\begin{pmatrix} 18 \\ 14 \end{pmatrix} \end{eqnarray*}$ (Entschlüsselung mit der inversen Matrix)

Für die anderen beiden Blöcke ebenso. Wie man dieses Gleichungssystem dann am besten von Hand löst, weiß ich noch nicht, aber ich werde mal darüber nachdenken

03.11.2012, 18:15

petermueller

Auf diesen Beitrag antworten »

Joa ob man c = m*k mod 26 oder c = k*m mod 26 ist eigentlich egal, man muss nur zum ver/entschlüsseln die gleiche Reihenfolge anwenden. In unserer Vorlesung wurds eben andersrum gemacht, als z.B. auf Wiki Augenzwinkern

Wirklich weiter bin ich allerdings noch nicht ... Ist wahrscheinlich auch noch ganz einfach...

03.11.2012, 22:37

Dopap

Auf diesen Beitrag antworten »

die Hillinverse ist bestimmt nicht die Inverse.
das erkennt man an der Konstruktion. Beispiel N=3

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.

aber wie berechne ich aus Matrix C die Matrix M , wenn überhaupt ?

05.11.2012, 05:33

chris_78

Auf diesen Beitrag antworten »

Zitat:

Original von petermueller
Joa ob man c = m*k mod 26 oder c = k*m mod 26 ist eigentlich egal, man muss nur zum ver/entschlüsseln die gleiche Reihenfolge anwenden. In unserer Vorlesung wurds eben andersrum gemacht, als z.B. auf Wiki Augenzwinkern

Ich hatte außer bei wiki auch noch auf 3-4 andere Seiten bzw Uni-Skripten geschaut, wo es überall gleich war, weswegen ich fälschlicherweise davon ausging, dass dies so Standard sei. Habs mittlerweile aber auch anders entdeckt Augenzwinkern

Dopap hat natürlich Recht, mit der Inversen, da muss ja auch der Modulo beachtet werden. Hammer

Nichtdestotrotz sollte das auch ohne Einbeziehen der Inversen gehen.
Ich erhalte doch aus dem 1. Block:
$\begin{eqnarray*} \begin{pmatrix} 18 & 14 \end{pmatrix} * \begin{pmatrix} a & b \\ c & d \end{pmatrix} mod 26 =\begin{pmatrix} 6 &4 \end{pmatrix} \end{eqnarray*}$
Also (18a+14c) mod26=6
und (18b+14d) mod26=4

Für die anderen beiden Blöcke folgt analog:
(11a+21c) mod26=25
(11b+21d) mod26=23

(4a+3c) mod26=3
(4b+3d)mod26=18

Mit Hilfe von excel habe ich da recht schnell die Lösungen finden können (a=12 und c=11)
Wie man da per Hand am besten rangeht weiß ich nicht.

Aber es gilt doch dann

I 18a+14c-6=k*26
II 11a+21c-25=m*26
III 4a+3c-6=n*26

mit a, c, k, n, m ganzzahlig
und a, c größergleich 0 und kleinergleich 25

Gleichung I*2-III*9 führt zu
c+15=2k*26-9n*26
bzw
c+15=26(2k-9n)

Da k und n ganzahlig sind ist auch das Ergebnis der Klammer ganzzahlig. c+15 ist also ein Vielfaches von 26. Nun soll c aber zwischen 0 und 25 liegen. c+15 ist damit höchstens 40 und das einzige echte Vielfache von 26 das daher in Frage käme ist 1*26=26. Also ist c=26-15=11
Ähnlich könnte man da bestimmt auch die weiteren Werte bestimmen

05.11.2012, 16:45

petermueller

Auf diesen Beitrag antworten »

joo die Gleichungen habe ich auch aufgestellt bekommen und 11 und 12 habe ich mit cryptool auch berechnet, allerdings habe ich keine Ahnung, wie man da per Hand hinkommt unglücklich

06.11.2012, 12:13

chris_78

Auf diesen Beitrag antworten »

Also für c habe ich ja schon eine Möglichkeit gezeigt wie man da per Hand hinkommen kann. d bekommt man analog.
Gibt aber bestimmt noch bessere Möglichkeiten da vorzugehen.
Und a könnte man z.B. erhalten, indem man erstmal für c den errechneten Wert in Gleichung III einsetzt. Ergibt dann:

4a+30=n*26

mit a und n ganzzahlig und $\begin{eqnarray*} 0 \le a \le 25 \end{eqnarray*}$
Gesucht sind also Vielfache von 26 die 4a+30 ergeben. Da aber $\begin{eqnarray*} 0 \le a \le 25 \end{eqnarray*}$ müssen diese Vielfachen im Intervall von 30 bis 134 liegen. Da kommen schon nur 52, 78, 104 und 130 in Frage. Aber nur 78 und 130 führen zu ganzzahligen Lösungen von a (78=4*12+30 ; 130=4*25+30).

Durch einfaches Einsetzen von c=11 und den möglichen Lösungen von a (12 oder 25) in Gleichung II, sieht man, dass nur a=12 eine ganzzahlige Lösung für m ergibt.

Auf gleiche Vorgehensweise könnte man auch eine Lösung b für b erhalten

08.11.2012, 13:26

petermueller

Auf diesen Beitrag antworten »

brr ich bin noch am rechnen ... ;>

bei der matrix aus teil eins gibt es aber doch ne menge an nachrichten, die die gleiche chiffre erzeugen ;>
"ab" (0 1) und "no" (13 14) bringen jeweils "de" (3 4) als ergebnis.
Gleiches gilt für z.B. "CD" und "PQ", die bringen beide (11 16).
Also scheinen alle Buchstaben, die 13 Stellen auseinander liegen, die gleiche Chiffre zu liefern ...
Aber wieso das so ist oder wie man das allgemein formulieren kann, habe ich keine Idee...

für den zweiten teil muss ich eine matrix finden, für die gilt:
ggT(26, det(m)) = 1
dann ist die matrix ganzzahlig und invertierbar.

habe jetzt die gleichungen:
4b + 3d = 18
11b + 21d = 23
18b + 14d = 4

4a + 3c = 3
11a + 21c = 25
18a + 14c = 6

aufgestellt und alle 9 Kombinationen durchprobiert ... ich komme zwar auch mal auf a=12 aber nie auf eine matrix, die komplett ganzzahlig ist unglücklich

09.11.2012, 10:44

chris_78

Auf diesen Beitrag antworten »

stimmt bei 1) hast du recht und ja auch beispiele gebracht.
das liegt aber an der schlüssel-matrix, die ja gar nicht als hill-schlüssel in frage kommt beim modulo 26.

zu 2)
bei deinen Gleichungen vergisst du, dass das immer modulo 26 ist und kommst deshalb auch zu einem Gleichungssystem wie ich es aufgeführt hatte. Hast du dir überhaupt mal angeschaut was ich geschrieben hatte?

Hab mir aber ja durchaus schon gedacht, dass das auch noch anders gehen muss und bin hier in einem Skript fündig geworden.

10.11.2012, 00:18

Dopap

Auf diesen Beitrag antworten »

ja logisch, eine Kompromittierung von Klartext und Crypt ist immer Gift.

Und hier sind doch L kompromittierende Blöcke vorgesehen.

Beispiel: wenn ich mit einer 20x20 Hillmatrix verschlüssele, ist die Kompromittierung eines Blockes noch nicht gravierend.

Trotzdem setze ich für länger bestehende Verbindungen Elgamail(*) ein.

Jeder Klartextblock wird dann zufällig in einen Cryptblock verschlüsselt.

Nachteil: doppelte Nachrichtenlänge, erheblich mehr Rechenaufwand

(*) könnte man auch so umschreiben: polyalphabetische Blockchiffre

Neue Frage »

Antworten »

Frage zu Hill-Chiffre

Verwandte Themen