Ferienübung F5 Rabin

Moderator: Einführung in die Kryptographie

cwb38
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 125
Registriert: 4. Okt 2010 15:53

Ferienübung F5 Rabin

Beitrag von cwb38 » 23. Dez 2012 19:29

Hallo,

ich habe zwei Fragen zu dieser Aufgabe:
1. Ist das Lösungswort in Binär- oder Dezimalschreibweise anzugeben?
2. Wenn ich meine vier Klartexte zur Probe verschlüssele erhalte ich eine Zahl, die nicht meinem Codewort entspricht. Ich habe außerdem für jeden erlaubten Klartext überprüft, ob es mit ihm möglich ist, mein Codewort zu treffen, mit dem Ergebnis, dass mein Codewort nicht in der Menge der Schlüsseltexte enthalten ist. Ist es für die Bewertung also o.k., wenn die Probe nicht aufgeht?

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Ferienübung F5 Rabin

Beitrag von Domac » 23. Dez 2012 21:41

Servus!

zu 1) Ich habe das Lösungswort noch nicht eingetragen, aber nur in Dezimal berechnet und würde sagen… es steht nichts da, also schreibs auf wie du willst ^^ (denke die meisten werden es dezimal machen)

zu 2) Ich habe das gleiche Problem… da bin ich ja beruhigt, dass ich da nicht der einzige bin. Oder wir beide sollten beunruhigt sein…! :-D

Gruß

PS.: Wie zur Hölle löst man Aufgabe 4? Die Matrix A ist (wenn ich mir Übung und Buch anschaue) unterschiedlich.
Extend my dropbox space (here).
Thanks!

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Ferienübung F5 Rabin

Beitrag von SupeRalF » 28. Dez 2012 17:36

Domac hat geschrieben:Wie zur Hölle löst man Aufgabe 4? Die Matrix A ist (wenn ich mir Übung und Buch anschaue) unterschiedlich.
Also ich habe jetzt die Matrix aus dem Buch verwendet. Warum aber Buch und Übung unterschiedlich sind kann ich mir nicht erklären.
cwb38 hat geschrieben:Wenn ich meine vier Klartexte zur Probe verschlüssele erhalte ich eine Zahl, die nicht meinem Codewort entspricht
Also wenn ich meine Klartexte verschlüssele, dann erhalte ich bei allen 4 Klartexten mein Codewort zurück. Genau so soll es ja sein; ich schätze also ihr beide habt einen Fehler gemacht.

Nun habe ich aber 4 Klartexte, von denen 2 negativ sind. Wie berechne ich denn jetzt XOR mit diesen? nutze ich ein 32bit 2er komplement für die negativen Zahlen?

Gruß
SupeRalF

[Edit]:
die negativen Zahlen scheinen sich (mod n) zu ergeben, sind also dann nicht mehr negativ. dann werde ich wohl jetzt einfach meine Klartexte auf gut glück durchnummerieren, eine Vorgabe was nun m0 sein soll habe ich nicht gefunden.

justme
Neuling
Neuling
Beiträge: 8
Registriert: 4. Okt 2010 20:59

Re: Ferienübung F5 Rabin

Beitrag von justme » 30. Dez 2012 11:59

zu 2) ist bei mir auch so. Habe mich strikt ans Buch gehalten und die Werte auch nochmal per Tool überprüfen lassen, angeblich stimmen sie.
Gibs da vlt irgendwelche Bedingungen, auf die man zusätzlich achten muss? Meine Ergebnisse ergeben auch irgendwie Sinn.

Verschlüssel ich meine Ergebnisse m0 bis m3, erhalte ich immer eine Zahl c1. Jetzt ist mp und mq sowohl für c1 als auch für mein Codewort identisch. Für beide müssen also auch dieselben Werte m0 bis m3 rauskommen. Zudem ist c1 mod q mein Codewort (wobei das vlt auch Zufall ist?)

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: Ferienübung F5 Rabin

Beitrag von DB_420 » 31. Dez 2012 02:02

justme hat geschrieben:zu 2) ist bei mir auch so. Habe mich strikt ans Buch gehalten und die Werte auch nochmal per Tool überprüfen lassen, angeblich stimmen sie.
Gibs da vlt irgendwelche Bedingungen, auf die man zusätzlich achten muss? Meine Ergebnisse ergeben auch irgendwie Sinn.

Verschlüssel ich meine Ergebnisse m0 bis m3, erhalte ich immer eine Zahl c1. Jetzt ist mp und mq sowohl für c1 als auch für mein Codewort identisch. Für beide müssen also auch dieselben Werte m0 bis m3 rauskommen. Zudem ist c1 mod q mein Codewort (wobei das vlt auch Zufall ist?)
So ist es bei mir ebenfalls, mit der Ausnahme, dass c1 mod q eben nicht mein Codewort ergibt.
Genauso wie bei cwb38 ist es bei mir auch nicht möglich, das Codewort als Kryptotext zu erhalten.
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)

dunlaith
Erstie
Erstie
Beiträge: 12
Registriert: 3. Jan 2013 15:46

Re: Ferienübung F5 Rabin

Beitrag von dunlaith » 3. Jan 2013 15:54

Hallo,

ich habe nochmal eine Frage zum Erstellen des Lösungswortes: das wird ja durch \(l = m_{0} \otimes m_{1} \otimes m_{2} \otimes m_{3}\) gibildet - aber was bedeutet das Zeichen \(\otimes\)? Ich habe jetzt schon einige Zeit danach gesucht, aber leider keine zufriedenstellende Antwort gefunden...

Ich hoffe, ihr könnt mir da weiterhelfen :wink:
Liebe Grüße
dunlaith

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Ferienübung F5 Rabin

Beitrag von olg » 3. Jan 2013 16:51

dunlaith hat geschrieben:Hallo,

ich habe nochmal eine Frage zum Erstellen des Lösungswortes: das wird ja durch \(l = m_{0} \otimes m_{1} \otimes m_{2} \otimes m_{3}\) gibildet - aber was bedeutet das Zeichen \(\otimes\)? Ich habe jetzt schon einige Zeit danach gesucht, aber leider keine zufriedenstellende Antwort gefunden...
Ich habe das jetzt als XOR gedeutet, aber \otimes ist ja nicht eindeutig auf XOR definiert. Könnte das auch Konkatenation sein?
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

dunlaith
Erstie
Erstie
Beiträge: 12
Registriert: 3. Jan 2013 15:46

Re: Ferienübung F5 Rabin

Beitrag von dunlaith » 3. Jan 2013 16:58

Hi,

nagut, dann hätte man ja auch \(\oplus\) schreiben können (statt \(\otimes\)) wenn tatsächlich ein XOR gemeint ist. Aber ich denke, mit dem Vorschlag kann ich was anfangen - dankeschön :)
Konkatenation ist eigentlich das Zeichen hier: \(\circ\)

Viele Grüße

Christian M.
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 14. Okt 2008 17:16

Re: Ferienübung F5 Rabin

Beitrag von Christian M. » 12. Jan 2013 16:11

\(\otimes\) bezeichnet das Tensorprodukt: http://de.wikipedia.org/wiki/Tensorprodukt
Das ist hier aber vermutlich wenig hilfreich; ich denke dass die Aufgabenstellung so gemeint ist, dass ein XOR (\(\oplus\)) aller vier Klartexte gemeint ist (damit ist es dann egal, in welcher Reihenfolge die Klartexte numeriert werden). In der vorigen Version der Übung stand noch \(l = m_0 \oplus m_1 + m_2 \oplus m_3\) da.

dunlaith
Erstie
Erstie
Beiträge: 12
Registriert: 3. Jan 2013 15:46

Re: Ferienübung F5 Rabin

Beitrag von dunlaith » 12. Jan 2013 17:14

Hi,

hatte mir überlegt in die Aufgabe zu schreiben, dass ich das \(\otimes\) als XOR gedeutet hab... bzw. wollte evtl. Montags nochmal direkt (bei einem Tutor) nachfragen...

Viele Grüße
dunlaith

j4n
Neuling
Neuling
Beiträge: 2
Registriert: 11. Okt 2012 10:49

Re: Ferienübung F5 Rabin

Beitrag von j4n » 14. Jan 2013 17:39

Wie interpretiert ihr nun das Zeichen?

mfg j4n

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Ferienübung F5 Rabin

Beitrag von olg » 15. Jan 2013 09:19

Ich habe als Lösungswort das Ergebnis des bitweisen XOR aller möglichen Lösungen angegeben:
\(\text{Lösungswort: } s \oplus -s \oplus r \oplus -r\).
(jede negative Lösung dabei zunächst auf die positive Restklasse mod n abgebildet).

Da bei der Abgabe ja auch der Rechenweg und die vier möglichen Lösungen angegeben sind, sollte bei deren Korrektheit auch kein großes Problem bei 'Falschinterpretation' des \(\otimes\) aufkommen... :)
Zuletzt geändert von olg am 15. Jan 2013 11:13, insgesamt 1-mal geändert.
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Ferienübung F5 Rabin

Beitrag von kbraden » 15. Jan 2013 10:48

olg hat geschrieben:Ich habe als Lösungswort das Ergebnis des bitweisen XOR aller möglichen Lösungen angegeben:
\(\text{Lösungswort: } s \oplus -s \oplus r \oplus -r\). (und jedes negative Ergebnis dabei zunächst auf die positive Restklasse mod n abgebildet).
Das wurde mir in der Sprechstunde heute so bestaetigt.

StatistikGibbon
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 6. Mär 2011 09:12

Re: Ferienübung F5 Rabin

Beitrag von StatistikGibbon » 17. Jan 2013 15:24

Ich habe es nochmal überprüft, manche Codewörter können bei bestimmten n nicht erreicht werden. Deshalb ist das Ergebnis nicht unbedingt falsch :) Ist bei mir genau so.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: Ferienübung F5 Rabin

Beitrag von Dennis Albrecht » 17. Jan 2013 23:15

Es gibt seit einiger Zeit ne neue Version des Aufgabenblattes, wonach genau das in drei von vier Fällen der Fall ist.

Gruß

Antworten

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