Fragen zur Musterlösung für Ex 04

Moderator: Post Quantum Cryptography

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Fragen zur Musterlösung für Ex 04

Beitrag von Richie » 20. Feb 2010 15:16

Hi,

zunächst eine kleine Anmerkung: Ich glaube, dass die Lösung zur T2 b) nicht ganz stimmt, denn die Signaturgrößen werden nicht genau doppelt so groß, da die Länge des Auth-Paths jeweils nur H/2 ist und nicht H.

Jetzt zu meiner eigentlichen Frage:
T3 a) Wie zur Hölle kommt man auf diese Formel? Fangt ihr bei 0 oder 1 an die Bits zu zählen (sprich: ist bei i = 3, h_i = 2 oder h_i = 3?). Habe ich die Hashes der untersten Ebene gespeichert oder nicht?
Egal ob es 2 oder 3 ist, ich komme mit der Formel nicht auf die manuell ermittelten Werte. Wäre super, wenn das nochmal jemand kurz erklären könnte, denn die Erklärung aus der Musterlösung ist nicht nur knapp sondern auch kryptisch ("You need H hash calls to compute the new (left) node in the authentication path which has the biggest height." wie jetzt? Egal wo ich im Baum bin, ich brauche immer H hash calls um den neuen Knoten zu berechnen? für i = 0 brauche ich maximal einen Aufruf, um v_0[0] = h(y_0) zu errechnen)
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fragen zur Musterlösung für Ex 04

Beitrag von Patr0rc » 20. Feb 2010 16:18

Richie hat geschrieben:zunächst eine kleine Anmerkung: Ich glaube, dass die Lösung zur T2 b) nicht ganz stimmt, denn die Signaturgrößen werden nicht genau doppelt so groß, da die Länge des Auth-Paths jeweils nur H/2 ist und nicht H.
Dies ist richtig. Sie ist nur ein wenig größer.

Zu der anderen Frage weiß ich im Moment die helfende Antwort leider selbst nicht.

Es gab aber welche in der Übung, die die Formel verstanden haben. Wäre schön, wenn diejenigen sich dazu melden und ein wenig Erklärung abgeben würden.

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Fragen zur Musterlösung für Ex 04

Beitrag von blowfish » 22. Feb 2010 01:03

vergleicht man die authentication paths von zwei aufeinanderfolgenden signaturen, kann man folgendes beobachten (von oben nach unten betrachtet): der "obere" teil bleibt gleich, dann kommt genau ein knoten, der von rechts nach links "wechselt" und alle folgenden knoten "wechseln" von links nach rechts. in der übung wird die höhe des einen knoten, der von rechts nach links "wechselt", und damit auch sein index im authentication path, mit \(h_i\) bezeichnet. der neue knoten kann mit \(h_i\) evaluationen der hashfunktion aus dem alten authentication path berechnet werden (das macht der verifizierer z.b. auch beim verifizieren der \(i\)-ten signatur). daher kommt das \(h_i\) in der formel. da die anderen knoten von links nach rechts "wechseln", können wir keinerlei informationen aus dem alten authentication path nutzen und müssen die kompletten unterbäume für diese neu berechnen. das führt zu der summe in der formel (für die berechnung eines baumes der höhe \(h\) muss man \(2^{h+1}-1\) knoten berechnen).
ich hoffe, es ist eingermaßen klar geworden, was ich sagen will.

ps: entschuldigt bitte die formell inkorrekte bezeichnung des "wechselns" von knoten. mir ist keine bessere beschreibung des vorganges eingefallen.
Ein Hemd ist Einstellungssache!

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Fragen zur Musterlösung für Ex 04

Beitrag von Patr0rc » 22. Feb 2010 13:25

Hierzu ein erklärender Hinweis von Richard in der unten angehängten Datei:
Dateianhänge
Ex04Hinweis.pdf
(85.02 KiB) 56-mal heruntergeladen

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Fragen zur Musterlösung für Ex 04

Beitrag von Richie » 22. Feb 2010 13:28

Hey!

Super vielen Dank euch beiden (dreien eigentlich...). Das ist jetzt um einiges klarer geworden.
There are only 10 types of people in the world:
Those who understand binary and those who don't

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Fragen zur Musterlösung für Ex 04

Beitrag von Richie » 23. Feb 2010 15:59

Gibt es einen Grund, warum die Musterlösung zur 4 plötzlich offline ist?
There are only 10 types of people in the world:
Those who understand binary and those who don't

Antworten

Zurück zu „Post-Quantum Cryptography“