Musterlösung Zahlentheorie

Moderator: Einführung in die Kryptographie

Minker
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 28. Sep 2009 16:11

Musterlösung Zahlentheorie

Beitrag von Minker » 1. Jan 2012 18:09

Ich habe eine Frage zum Lösungsvorschlag für Aufgabe (14). Dort steht "Die DDH-Annahme ist stärker als die CDH-Annahme (impliziert diese also)". Im Satz danach wird allerdings beschrieben, wie man aus einem Angreifer gegen CDH einen gegen DDH konstruieren könnte. Ist das nicht eine Begründung dafür, dass CDH stärker ist als DDH, also CDH => DDH. Das würde für mich auch intuitiv mehr Sinn machen.
Ist da was in der Lösung vertauscht, oder stehe ich irgendwie auf dem Schlauch?

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Musterlösung Zahlentheorie

Beitrag von Maeher » 1. Jan 2012 19:00

Überlege es dir so:

Du nimmst an es existiert ein Angreifer \(\mathcal{A}\) gegen CDH und du kannst den benutzen um einen Angreifer \(\mathcal{B}\) gegen DDH zu bauen.
ABER: Wenn die DDH-Annahme korrekt ist, kann \(\mathcal{B}\) garnicht existieren.
Da du aber \(\mathcal{B}\) aus \(\mathcal{A}\) bauen kannst, kann somit auch \(\mathcal{A}\) nicht existieren.

Das bedeutet dann, wenn DDH-Annahme korrekt ist, kann es keinen Angreifer gegen CDH geben, also \(DDH \Rightarrow CDH\).

Man kann sich das ganze so vorstellen, dass du bei einer "stärkeren" Annahme "mehr" annimmt als bei einer "schwachen".

Bei DDH nimmst du intuitiv mehr an als bei CDH, denn es könnte ja gut möglich sein, dass du zwar entscheiden kannst OB ein Wert die richtige Form hat, wenn man ihn dir sagt, du ihn deswegen aber noch lange nicht selber berechnen kannst.

Minker
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 28. Sep 2009 16:11

Re: Musterlösung Zahlentheorie

Beitrag von Minker » 2. Jan 2012 09:18

Das klingt logisch :-).
Vielen Dank für die schnelle Antwort!

kruse
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 15. Okt 2009 15:10
Kontaktdaten:

Re: Musterlösung Zahlentheorie

Beitrag von kruse » 30. Jan 2012 12:35

Hi,
ich hab gerade zur Klausurvorbereitung nochmal angefangen die Zahlentheorieaufgaben zu machen. Bei Afug. (11) steht log(zur basis g) 2 = 3, da 3^3 = 9 = 2 mod 7 !
3^3 = 9 ??? Da ist doch ein Fehler oder?
Gruß Karsten

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: Musterlösung Zahlentheorie

Beitrag von FeG » 30. Jan 2012 19:22

kruse hat geschrieben:3^3 = 9 ??? Da ist doch ein Fehler oder?
Allerdings, natürlich muss es lauten \(\log_g 2 = 2\), da \(3^2 = 9 = 2 \; mod \; 7\).

Ich schicke die korrigierte Musterlösung gleich an Prof. Fischlin, kann aber nicht versprechen, wie schnell sie online ist. Der Fehler dürfte aber auch niemanden katastrophal aus dem Konzept bringen :wink:

Gruß
Felix

Antworten

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