Seite 1 von 1

Happy-New-Year-Aufgabe ist online

Verfasst: 10. Dez 2009 13:59
von poetter
Die HNY-Aufgabe steht im moodle zum Download bereit. Sie kann nach
Neujahr abgegeben werden, die Bewertung fließt als Bonus in die
Klausur mit ein.

Hier noch drei Werte aus der Programmieraufgabe zum copy-und-pasten:
p = 200900000000000000000000000000000001287
c1 = 130887051639107331259328284802777390119
c2 = 81433340497186374824116114588406118541

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 14. Dez 2009 22:02
von Osterlaus
Ich bin gerade ein wenig verwirrt über die inkonsistente Benennung der Variablen zwischen Folien und Übung. In Aufgabe 5c) ging das noch, von ModInv(a,p) in der Aufgabe konnte ich gut auf ModInv(a,N) in den Folien übersetzen. Bei 5f) wirds aber echt knifflig: KGen in den Folien bekommt nur \(1^\kappa\) übergeben, in der Übung sollen es drei Parameter p, q und g sein. Auch über die Definition von GenG ist mir nicht klar, welcher der Parameter nun welchen Zweck erfüllen soll...

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 14. Dez 2009 23:32
von taufrisch
Naja, ich würde mal sagen statt \((\mathbb{G}, \mathrm{g}, \mathrm{Q})\leftarrow\mathrm{GenG}(1^\kappa)\) nimmst Du wie vorgegeben \((\mathbb{G}, \mathrm{g}, \mathrm{Q}):=(\left<g\right>, g, \left|\left<g\right>\right|) = (\mathcal{G}, g, q)\).

GenG ist ein Gruppengenerator (siehe Seite 33 auf Foliensatz 7), bekommt nur den Sicherheitsparameter \(1^\kappa\) — was einfach die Schlüssellänge ist (in unserem Fall \(\kappa\approx128\)) — und würfelt passend dazu eine zyklische Gruppe mit den genannten Eigenschaften aus. Mußt Du aber nicht machen, ist ja eben schon vorgegeben.

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 20. Dez 2009 18:43
von Osterlaus
taufrisch hat geschrieben:Naja, ich würde mal sagen statt \((\mathbb{G}, \mathrm{g}, \mathrm{Q})\leftarrow\mathrm{GenG}(1^\kappa)\) nimmst Du wie vorgegeben \((\mathbb{G}, \mathrm{g}, \mathrm{Q}):=(\left<g\right>, g, \left|\left<g\right>\right|) = (\mathcal{G}, g, q)\).
Okay. Und wofür übergebe ich der Funktion dann das p? Mit q und g erzeuge ich dann ja den Schlüssel, aber p scheint mir recht überflüssig.

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 20. Dez 2009 19:04
von taufrisch
Osterlaus hat geschrieben:Okay. Und wofür übergebe ich der Funktion dann das p? Mit q und g erzeuge ich dann ja den Schlüssel, aber p scheint mir recht überflüssig.
Versuch' doch mal in \(\mathcal{G}\) zu rechnen, wenn Du \(p\) nicht kennst. Irgendwie mußt Du \(\mathcal{G}\) ja im Programm darstellen, die Gruppe als Menge mit vollständiger Verknüpfungstafel ist da etwas unhandlich.

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 20. Dez 2009 20:11
von Osterlaus
taufrisch hat geschrieben:
Osterlaus hat geschrieben:Okay. Und wofür übergebe ich der Funktion dann das p? Mit q und g erzeuge ich dann ja den Schlüssel, aber p scheint mir recht überflüssig.
Versuch' doch mal in \(\mathcal{G}\) zu rechnen, wenn Du \(p\) nicht kennst. Irgendwie mußt Du \(\mathcal{G}\) ja im Programm darstellen, die Gruppe als Menge mit vollständiger Verknüpfungstafel ist da etwas unhandlich.
So ganz blicke ich doch noch nicht durch, glaube ich. Den Elgamal-Schlüssel generiere ich doch, indem ich ein x mit \(0 < x < q\) wähle. Dann bestimme ich \(h = g^x\) und gebe die Ausgabe von GenG, h und x zurück - lass mich raten, der Knoten in meinem Kopf ist das p, weil ich alles mod p rechnen muss?

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 21. Dez 2009 16:03
von taufrisch
Osterlaus hat geschrieben:Dann bestimme ich \(h = g^x\) und gebe die Ausgabe von GenG, h und x zurück - lass mich raten, der Knoten in meinem Kopf ist das p, weil ich alles mod p rechnen muss?
Jupp, in der Aufgabe ist \(\mathcal{G}\) eine Untergruppe von \(\mathbb{Z}_p^*\), Du rechnest also mit Restklassen modulo \(p\). Muß man natürlich nicht so machen, einfach
\(\mathcal{G}:=\mathbb{Z}_q^*\) für ein geeignetes \(q\) wie zum Beispiel in RFC 3526 ginge auch, hier ist das aber so vorgegeben.

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 8. Jan 2010 17:32
von Demmi
Kann mir mal jemand den Unterschied zwischen den Aufgaben 1 b,c und d erklären?

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 8. Jan 2010 17:52
von taufrisch
Demmi hat geschrieben:Kann mir mal jemand den Unterschied zwischen den Aufgaben 1 b,c und d erklären?
1b) \(H^1\) kollisionsresitent \(\Rightarrow H^{1\parallel2}\) kollisionsresitent (mit Beweis und Abschätzung)

1c) \(H^2\) kollisionsresitent \(\Rightarrow H^{1\parallel2}\) kollisionsresitent (ohne Beweis, mit Abschätzung)

1d) \(H^1\) oder \(H^2\) kollisionsresitent \(\Rightarrow H^{1\parallel2}\) kollisionsresitent (mit Beweis durch Abschätzung).

Re: Happy-New-Year-Aufgabe ist online

Verfasst: 9. Jan 2010 17:55
von Demmi
Hm, danke für die Antwort. Leider weiß ich immer noch nicht so recht, was ich da konkret beweisen soll. Die Abschätzung hab ich, glaub ich zumindest, soweit hinbekommen.
Irgendwie ist das alles das selbe.
Edit: Hm, jemand hätte das Wort Reduktionsbeweis mal fett machen und doppelt unterstreichen sollen ;) Ich habs jetzt hinbekommen, war auch gar nicht so schwer.