www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKrypto,Kodierungstheorie,ComputeralgebraLösungen der Gleichungen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Krypto,Kodierungstheorie,Computeralgebra" - Lösungen der Gleichungen
Lösungen der Gleichungen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:09 Mo 09.02.2009
Autor: Christopf

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

        
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:21 Mo 09.02.2009
Autor: Christopf

° 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

Bezug
                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:05 Mi 11.02.2009
Autor: Christopf

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.

Bezug
                                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:15 Mi 11.02.2009
Autor: Christopf

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

Bezug
                                                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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



Bezug
                                                        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:45 Mi 11.02.2009
Autor: Christopf

Hi

kannst du mir zeigen wie man das mit modulo 26 berechnet

Danke

Bezug
                                                                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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



Bezug
                                                                        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:44 Mi 11.02.2009
Autor: Christopf

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

Bezug
                                                                                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                                        
Bezug
Lösungen der Gleichungen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:01 Mi 11.02.2009
Autor: Christopf

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.


Bezug
                                                                                                
Bezug
Lösungen der Gleichungen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                
Bezug
Lösungen der Gleichungen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:26 Mi 11.02.2009
Autor: angela.h.b.


> 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.




Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]