Ferienübung

Moderator: Einführung in die Kryptographie

d3non
Erstie
Erstie
Beiträge: 22
Registriert: 23. Mai 2009 19:20

Re: Ferienübung

Beitrag von d3non »

shookd hat geschrieben:Hi,
versuchs doch mal mit Polynomdivision und dann weiter mit Zurückeinsetzen. Das Zurückeinsetzen geht jedoch mit dem Erweiterten Euklid einfacher.
Ja, ich glaube ich hab es (in etwa so^^) hinbekommen.
Müssen wir die Determinantenberechnung und die Addition dann auch auf dem AES-Körper machen? Ich vermute es mal, weil ich sonst eine 3stellige Hexzahl heraus bekomme^^

bayar
Erstie
Erstie
Beiträge: 14
Registriert: 20. Okt 2009 12:32

Re: Ferienübung

Beitrag von bayar »

Ja, ich glaube ich hab es (in etwa so^^) hinbekommen.
Müssen wir die Determinantenberechnung und die Addition dann auch auf dem AES-Körper machen? Ich vermute es mal, weil ich sonst eine 3stellige Hexzahl heraus bekomme^^
Wie sicher bist du denn?
ich habe mit dem Erweiterten Euklid kF^-1 gut rausgerechnet. Nach der Determinantenberechnung und der Addition hab auch 3stellige Hexzahl bekommen und hab bißchen gewundert, da in der Aufgabenstellung "... Lösung als 2stellige HEX... " angeben soll.

zu F4:
Soll man M nach 4.11.6 im Buch (Seite 82) vorgestellten Verfahren berechnen? Oder nur einfach die Inverse der gegeben Matrix ausrechnen?

mazbu
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Nov 2008 23:44

Re: Ferienübung

Beitrag von mazbu »

auch zu F4 : muss man Chinesischen Restsatz bei der Berechnung von Inverse Matrix anwenden?

shookd
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 20. Aug 2009 21:00

Re: Ferienübung

Beitrag von shookd »

Also ganz unverbindlich. Beim erweiterten Euklid dürfte nur ein Polynom höchstens 7. Grades rauskommen und Addition ist eine XOR Operation. Da kann doch keine dreistellige Hexzahl rauskommen.

bayar
Erstie
Erstie
Beiträge: 14
Registriert: 20. Okt 2009 12:32

Re: Ferienübung

Beitrag von bayar »

shookd hat geschrieben:Also ganz unverbindlich. Beim erweiterten Euklid dürfte nur ein Polynom höchstens 7. Grades rauskommen und Addition ist eine XOR Operation. Da kann doch keine dreistellige Hexzahl rauskommen.
Also, bin einverstanden dass "Beim erweiterten Euklid dürfte nur ein Polynom höchstens 7. Grades rauskommen".

Nach meiner Meinung, 01 inHEX = 1, 02 inHEX= x, 03 inHEX = x+1 und angenommen, ich hab k^f = x+1 Bsp. aus dem Buch S. 54. Dann ist ein Polynom
k^f-1= x^7+x^6+x^5+x^4+x^2+x. l =det(...) + k^f-1 = ((x+1)1 + (x+1)x) + x^7+x^6+x^5+x^4+x^2+x usw. . Dann hab ich ein Polynom höchstens 7. Grades.
Umwandlung in HEX hab dann 2stellige Hex.-zahl. So meinst du shookd?

shookd
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 20. Aug 2009 21:00

Re: Ferienübung

Beitrag von shookd »

Genau, so in der Richtung hab ich das auch :)

bayar
Erstie
Erstie
Beiträge: 14
Registriert: 20. Okt 2009 12:32

Re: Ferienübung

Beitrag von bayar »

Im Buch (5. Aufl.) auf der Seite 44 in Zeile 3 (Bsp. 3.15.1) ist ein Vorzeichenfehler: Es muss -2*y3... nicht 2*y3, damit y3=3 sein kann, denke ich.

Eine Verständnisfrage:

Warum hat man auf diesem Bsp. bei y1 und y2 als absolut kleinste Lösung bezeichnet und -1 berechnet? Bei y3=3 plötzlich als "die kleinste nicht negative Lösung". Wollte der Prof. auf bestimmtes hinweisen? Oder ist nur unglüchlicher Ausdruck?

Man kann genau so umgekehrt berechen und bei y1 und y2 "die kleinste nicht negative Lösung" finden . Oder?

Gruß

bayar.

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Ferienübung

Beitrag von mantra »

bayar hat geschrieben:Im Buch (5. Aufl.) auf der Seite 44 in Zeile 3 (Bsp. 3.15.1) ist ein Vorzeichenfehler: Es muss -2*y3... nicht 2*y3, damit y3=3 sein kann, denke ich.
Wieso? Es ist doch \(M_3\equiv12 \equiv 2 mod 5\) und man muss daher \(2*y_3 \equiv 1 mod 5\) lösen. \(2*3\equiv 6\equiv 1 mod 5\).
Eine Verständnisfrage:

Warum hat man auf diesem Bsp. bei y1 und y2 als absolut kleinste Lösung bezeichnet und -1 berechnet? Bei y3=3 plötzlich als "die kleinste nicht negative Lösung". Wollte der Prof. auf bestimmtes hinweisen? Oder ist nur unglüchlicher Ausdruck?

Man kann genau so umgekehrt berechen und bei y1 und y2 "die kleinste nicht negative Lösung" finden . Oder?

Gruß

bayar.
Das kann ich auch nicht genau sagen, aber y3 ist in dem Beispiel irrelevant für die Berechnung von x und wenn man x berechnet, hat man potentiell kleinere Ergebnisse, wenn man mit den absolut kleinsten Lösungen rechnet, statt mit den kleinsten nicht negativen Lösungen.

bayar
Erstie
Erstie
Beiträge: 14
Registriert: 20. Okt 2009 12:32

Re: Ferienübung

Beitrag von bayar »

Hi,
kann einer mir bei F3 helfen? M modulo m Matrix hab ich.
Dann hab ich erst M - (...k...) abgezogen und davon die det(...) berechnet. Den rausgekomme Zahl zB. (55 mod385) hab als a1, a2 und a3 betrachtet.
Da man y1, y2 und y3 ohne a(i) berechnen kann, als y1= -1, y2= -5 und y3= -5.
Wenn ich alles wiedereinsetze, bekomme ich immer noch X= 55mod 385 raus.

Was mache ich falsch? sollte ich als a(i) =55 nicht nehmen?

Kann jemand mir auf der Sprunge helfen?

Danke im Voraus!

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Ferienübung

Beitrag von mantra »

Der Sinn war, dass du nicht erst die große Determinante berechnest, sondern direkt nur durch Lösen der Kongruenz (Determinanten mod 5,7,11) die Determinante herausfindest.

Antworten

Zurück zu „Einführung in die Kryptographie“