Seite 1 von 1

Unklarheit bzgl. Merkle Konstruktion

Verfasst: 9. Feb 2016 08:46
von 29917180
Im Buch Einführung in die Kryptografie (5. Auflage) wird bei der Merkle Konstruktion für Hashfunktionen beschrieben, dass man vor jedem (r-1)*j-ten
(j = 1, 2...) Zeichen der Binärentwicklung von |x| (x element {0, 1}*) eine 1 setzt. Jetzt ist mir aber unklar wie gezählt wird, also ob man bei 0 anfängt oder bei 1.
Beispiel: sei r = 4 und Binärentwicklung von |x| = 10000. Ist dann 010 000 -> 1010 1000 oder 01 000 0 -> 101 1000 10 (oder was ganz anderes) richtig?

Re: Unklarheit bzgl. Merkle Konstruktion

Verfasst: 10. Feb 2016 16:12
von PeterZwegat
Hi,

die 5. Auflage scheint an dieser Stelle einen Fehler zu haben. In der neuen Auflage heisst es, dass man vor jedem (r-1)*j-ten (j = 0, 1, 2...) Zeichen eine 1 geschrieben wird.

Dein konkretes Beispiel wird folgendermaßen entwickelt. Nachdem du |x| mit Nullen aufgefüllt hast erhälst du richtigerweise den String s = 010 000. Da |s| = 6 musst du gemäß der oben gegebenen Formel vor das 0. und 3. Zeichen eine 1 schreiben, also vor die unterstrichenen Zeichen. Somit erhälst du 10101000.