Happy-New-Year-Aufgabe ist online

Moderator: Einführung in die Kryptographie

poetter
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 22. Sep 2009 16:20

Happy-New-Year-Aufgabe ist online

Beitrag 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

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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...

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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.
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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.
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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?

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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.
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Happy-New-Year-Aufgabe ist online

Beitrag von Demmi »

Kann mir mal jemand den Unterschied zwischen den Aufgaben 1 b,c und d erklären?
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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).
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Happy-New-Year-Aufgabe ist online

Beitrag 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.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Antworten

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