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?
Musterlösung Zahlentheorie
Moderator: Einführung in die Kryptographie
Re: Musterlösung Zahlentheorie
Ü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.
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.
Re: Musterlösung Zahlentheorie
Das klingt logisch 
.
Vielen Dank für die schnelle Antwort!
.Vielen Dank für die schnelle Antwort!
Re: Musterlösung Zahlentheorie
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
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
Re: Musterlösung Zahlentheorie
Allerdings, natürlich muss es lauten \(\log_g 2 = 2\), da \(3^2 = 9 = 2 \; mod \; 7\).kruse hat geschrieben:3^3 = 9 ??? Da ist doch ein Fehler oder?
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
Gruß
Felix