Lösungen der Gleichungen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
hier die Aufgabe:
Y=A [mm] \circ [/mm] x über [mm] \IZ_{26} [/mm] der Blocklänge b=2. Ein Klartextblock [mm] (x_{1}.x_{2})\in \IZ_{26} \times \IZ_{26} [/mm] wird mit einer geheimen invertierbaren [mm] (2\times2)-Matrix A=\pmat{ a_{11} & a_{12} \\ a_{21} & a_{22} } [/mm] über [mm] \IZ_{26} [/mm] wie folgt verschlüsselt.
[mm] (y_{1},y_{2)}^{T}=\vektor{y_{1} \\ y_{1}}= [/mm] A [mm] \times\vektor{x_{1} \\ x_{1}} [/mm] =A [mm] \times (x_{1},x_{2)}^{T}.
[/mm]
Mittels einer solchen Chiffre sei der Klartext DIEFFIE zu NMYNAG verschlüsselt worden.
Bestimmen Sie aus diesem klartext-Chiffretext-Paar die zugrundeliegende Matrix A sowie die Entschlüsselungsmatrig die inverse von A.
Hinweis Das lateinische Alphabet wird in üblicher Weise mit [mm] \IZ_{26} [/mm] identifiiert
Das T steht für Transponiert
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:04 Mo 09.02.2009 | | Autor: | rainerS |
Hallo!
> hier die Aufgabe:
>
> Y=A [mm]\circ[/mm] x über [mm]\IZ_{26}[/mm] der Blocklänge b=2. Ein
> Klartextblock [mm](x_{1}.x_{2})\in \IZ_{26} \times \IZ_{26}[/mm]
> wird mit einer geheimen invertierbaren [mm](2\times2)-Matrix A=\pmat{ a_{11} & a_{12} \\ a_{21} & a_{22} }[/mm]
> über [mm]\IZ_{26}[/mm] wie folgt verschlüsselt.
>
> [mm](y_{1},y_{2})^{T}=\vektor{y_{1} \\ y_{1}}= A \times\vektor{x_{1} \\ x_{1}} =A \times (x_{1},x_{2})^{T}.[/mm]
>
> Mittels einer solchen Chiffre sei der Klartext DIEFFIE zu
> NMYNAG verschlüsselt worden.
Das kann nicht sein, denn der Klartext hat 7 Buchstaben, der Geheimtext nur 6.
> Bestimmen Sie aus diesem klartext-Chiffretext-Paar die
> zugrundeliegende Matrix A sowie die Entschlüsselungsmatrig
> die inverse von A.
>
> Hinweis Das lateinische Alphabet wird in üblicher Weise mit
> [mm]\IZ_{26}[/mm] identifiiert
>
> Das T steht für Transponiert
Was hast du denn für eigene Lösungsansätze?
Viele Grüße
Rainer
|
|
|
| |
|
° Vorraussetzung
$ [mm] \vektor{y_{1} \\ y_{2}}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{x_{1} \\ x_{2}} [/mm] $
°Aufgabe
$ [mm] \vektor{13 \\12}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{3 \\ 8} [/mm] $
$ [mm] \vektor{24 \\13}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{5 \\ 5} [/mm] $
$ [mm] \vektor{0 \\6}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{8 \\ 4} [/mm] $
° Lösung
$ [mm] 13=3a_{11}+8a_{12} [/mm] $
$ [mm] 12=3a_{21}+8a_{22} [/mm] $
$ [mm] 24=5a_{11}+5a_{12} [/mm] $
$ [mm] 13=5a_{21}+5a_{22} [/mm] $
$ [mm] 0=8a_{11}+4a_{12} [/mm] $
$ [mm] 6=8a_{21}+4a_{22} [/mm] $
° 2.Lösungsschritt
$ [mm] 3a_{11}+8a_{12}=13\Rightarrow a_{11}=\bruch{13}{3}-\bruch{8}{3}a_{12} [/mm] $
$ [mm] 3a_{21}+8a_{22}=12\Rightarrow a_{21}=4-\bruch{8}{3}a_{22} [/mm] $
Mir fehlen noch $ [mm] a_{12} [/mm] $ und $ [mm] a_{22} [/mm] $
Hinweis Klartext : DIFFIE es war ein e zuviel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:20 Di 10.02.2009 | | Autor: | rainerS |
Hallo!
> ° Vorraussetzung
>
> [mm]\vektor{y_{1} \\ y_{2}}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{x_{1} \\ x_{2}}[/mm]
>
> °Aufgabe
>
> [mm]\vektor{13 \\12}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{3 \\ 8}[/mm]
>
> [mm]\vektor{24 \\13}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{5 \\ 5}[/mm]
>
> [mm]\vektor{0 \\6}=\pmat{ a_{11} & a_{12}\\ a_{21} & a_{22}}\cdot{}\vektor{8 \\ 4}[/mm]
>
> ° Lösung
>
> [mm]13=3a_{11}+8a_{12}[/mm]
> [mm]12=3a_{21}+8a_{22}[/mm]
>
> [mm]24=5a_{11}+5a_{12}[/mm]
> [mm]13=5a_{21}+5a_{22}[/mm]
>
> [mm]0=8a_{11}+4a_{12}[/mm]
> [mm]6=8a_{21}+4a_{22}[/mm]
Das stimmt so nicht: die Rechnungen geschehen doch in [mm] $\IZ_{26}$, [/mm] also zum Beispiel
[mm] 13\equiv 3a_{11}+8a_{12} \pmod{26} [/mm], [mm]12\equiv 3a_{21}+8a_{22}\pmod{26} [/mm]
usw.
> ° 2.Lösungsschritt
>
> [mm]3a_{11}+8a_{12}=13\Rightarrow a_{11}=\bruch{13}{3}-\bruch{8}{3}a_{12}[/mm]
>
> [mm]3a_{21}+8a_{22}=12\Rightarrow a_{21}=4-\bruch{8}{3}a_{22}[/mm]
Das geht sogar [mm] ($\pmod{26}$), [/mm] weil 3 in [mm] $\IZ_{26}$ [/mm] das Inverse 9 hat [mm] ($9*3\equiv [/mm] 1 [mm] \pmod{26}$), [/mm] aber durch 2 und 13 und ihre Vielfache kannst du nicht teilen.
Also ist:
[mm] a_{11} \equiv 13*9 - 8*9 a_{12} \equiv 13 + 6 a_{12}\pmod{26} [/mm]
[mm] a_{21} \equiv 4-8*9a_{22} \equiv 4 + 6 a_{22}\pmod{26} [/mm]
>
> Mir fehlen noch [mm]a_{12}[/mm] und [mm]a_{22}[/mm]
Setze [mm] $a_{11}$ [/mm] und [mm] $a_{21}$ [/mm] in die anderen vier Gleichungen ein!
Viele Grüße
Rainer
|
|
|
| |
|
Wie kommst du rechnerisch auf den Wert 9
ich habe die Aufgabe gelöst und bin der Meinung das die Aufgabe gar nicht lösbar ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:14 Mi 11.02.2009 | | Autor: | rainerS |
Hallo!
> Wie kommst du rechnerisch auf den Wert 9
Das habe ich doch in meiner letzten Antwort geschrieben: $ [mm] 9\cdot{}3=27 \equiv [/mm] 1 [mm] \pmod{26} [/mm] $.
>
> ich habe die Aufgabe gelöst und bin der Meinung das die
> Aufgabe gar nicht lösbar ist.
Na, in diesem Satz widersprichst du dir selbst. 
Die Aufgabe hat eine eindeutige Lösung.
Tipp: addiere die 1. zur 3. Gleichung und subtrahiere die 5. Ebenso 2. + 4. - 6.
Viele Grüße
Rainer
|
|
|
| |
|
Ich habe dank deiner Unterstützung die Matrix [mm] A=\pmat{ 3 & 7 \\ 12 & 10 }
[/mm]
Jetzt habe ich nur noch das Problem die Inverse Matrix zu A berechnen. Ich weis das ich mit modulo rechnen muss.
Trotztem finde ich kein ergebnis
Nochmals danke für deine Unterstützung
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:26 Mi 11.02.2009 | | Autor: | rainerS |
Hallo!
> Ich habe dank deiner Unterstützung die Matrix [mm]A=\pmat{ 3 & 7 \\ 12 & 10 }[/mm]
Die untere Zeile stimmt nicht; deine 4. Gleichung ist nicht erfüllt: $5*12+5*10 = 100 [mm] \equiv [/mm] 6 [mm] \pmod{26}$, [/mm] es muss aber 13 herauskommen.
> Jetzt habe ich nur noch das Problem die Inverse Matrix zu A
> berechnen. Ich weis das ich mit modulo rechnen muss.
Du kannst entweder die inverse Matrix modulo 26 berechnen, oder die Ausgangsgleichungen umkehren, also zum Beispiel
[mm]\vektor{3\\8} = A^{-1}* \vektor{13\\12} [/mm]
Viele Grüße
Rainer
|
|
|
| |
|
Hi
kannst du mir zeigen wie man das mit modulo 26 berechnet
Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:35 Mi 11.02.2009 | | Autor: | rainerS |
Hallo!
> Hi
>
> kannst du mir zeigen wie man das mit modulo 26 berechnet
Die inverse Matrix ist doch
[mm] \bruch{1}{\det(A)} \begin{pmatrix} a_{22} & -a_{12} \\ -a_{21} & a_{11} \end{pmatrix} [/mm]
und das gilt auch hier; du musst nur alle Operationen modulo 26 ausführen.
Der einzige ein bischen aufwändige Schritt ist die Berechnung des Inversen der Determinante. Wenn die ein Vielfaches von 2 oder 13 ist, existiert das Inverse nicht. In den anderen 12 Fällen kann man es mit Durchprobieren schnell herausbringen, oder den Euklidischen Algorithmus verwenden.
Hast du denn jetzt die richtige Matrix ausgerechnet?
(Tipp: Die Determinante ist 11, und [mm] $11*19\equiv [/mm] 1 [mm] \pmod{26}$.)
[/mm]
Viele Grüße
Rainer
|
|
|
| |
|
Wo holst du die 19 her
Wie berechnest du die Determinante
ich hatte die Dterminate wie im Raum R berechnet
Determinante Habe ich so berchnet 3*10=30 mod(30,26)=4 und
13*7=91 [mm] mod(91,26)=13\Rightarrow [/mm] 4-13=-9 mod(-9,26)=17
Damit habe ich Det(A)=17
Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:55 Mi 11.02.2009 | | Autor: | rainerS |
Hallo!
> Wo holst du die 19 her
Habe ich doch geschrieben: im Zweifelsfall ausprobieren; es gibt ja nur 12 Möglichkeiten.
>
> Wie berechnest du die Determinante
>
> ich hatte die Dterminate wie im Raum R berechnet
>
> Determinante Habe ich so berchnet 3*10=30 mod(30,26)=4 und
> 13*7=91 [mm]mod(91,26)=13\Rightarrow[/mm] 4-13=-9 mod(-9,26)=17
> Damit habe ich Det(A)=17
Aber die Matrix ist falsch.
Viele Grüße
Rainer
|
|
|
| |
|
Die Matrix heißt [mm] doch\pmat{ 3 & 7 \\ 8 & 5 }
[/mm]
Meine Determinate ist 11
Kannst du mich helfen bei [mm] A^{-1}:\bruch{1}{11}\pmat{ 17 & 23 \\ 4 & 5 }
[/mm]
sind diese Werte richtig.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:58 Do 12.02.2009 | | Autor: | rainerS |
Hallo!
> Die Matrix heißt [mm]doch\pmat{ 3 & 7 \\ 8 & 5 }[/mm]
Richtig.
> Meine Determinate ist 11
Auch richtig.
> Kannst du mich helfen bei [mm]A^{-1}:\bruch{1}{11}\pmat{ 17 & 23 \\ 4 & 5 }[/mm]
Die Inverse ist [mm] $A^{-1}= \pmat{ 17 & 23 \\ 4 & 5 }$.
[/mm]
Viele Grüße
Rainer
|
|
|
| |
|
> Wie kommst du rechnerisch auf den Wert 9
>
> ich habe die Aufgabe gelöst und bin der Meinung das die
> Aufgabe gar nicht lösbar ist.
Hallo,
als Du Deine Aufgabe an anderer Stelle gepostet hattest, war ja gar nicht klar, daß sie mod 26 gerechnet werden soll. Wir hatten dort doch in [mm] \IR [/mm] gerechnet!
Dieses Detail kann für die Lösung durchaus Unterschiede machen.
|
|
|
|
