Seite 1 von 1

Fragen zur Musterlösung für Ex 04

Verfasst: 20. Feb 2010 15:16
von Richie
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)

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

Verfasst: 20. Feb 2010 16:18
von Patr0rc
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.

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

Verfasst: 22. Feb 2010 01:03
von blowfish
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.

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

Verfasst: 22. Feb 2010 13:25
von Patr0rc
Hierzu ein erklärender Hinweis von Richard in der unten angehängten Datei:

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

Verfasst: 22. Feb 2010 13:28
von Richie
Hey!

Super vielen Dank euch beiden (dreien eigentlich...). Das ist jetzt um einiges klarer geworden.

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

Verfasst: 23. Feb 2010 15:59
von Richie
Gibt es einen Grund, warum die Musterlösung zur 4 plötzlich offline ist?