Hallo liebe Community!

Ich habe mal eine Frage. Ist es möglich mit einem Hashalgorithmus 8 Byte auf weniger Bytes zu verkleinern? Es muss dabei nicht wieder umkehrbar sein. Das wichtigste ist das es eine hohe Wahrscheinlichkeit hat das es eindeutig ist und keine doppelten Schlüssel auftreten bei unterschiedlichen 8 Bytes Codes.


MFG Wolf

Hallo Alphawolf1988,

klar ist das möglich. Die Wahrscheinlichkeit eines Clashes wird natürlich immer größer, je mehr der 256 unterschiedlichen Eingabewerte tatsächlich auftreten und je weniger Bits der Hash hat.

Wenn du z.B. einen Hash hast, der nur aus einem Bit besteht (z.B. 0 für gerade und 1 für ungerade Werte), aber nur zwei Eingabewerte vorkommen und sichergestellt ist, dass der eine gerade und der andere ungerade ist, hast du trotz der geringen Größe des Hashs keine Clashes. Wenn du aber viele gleichwahrscheinliche Eingabewerte hast, kann es selbst bei einem 7-bit Hash schon viele Clashes geben. Es kommt also immer auf die Situation ab.

Mit jedem Bit, dass du weglässt, halbiert sich die Anzahl der verschiedenen Hashwerte, obwohl die Anzahl der (möglichen) Eingabewerte natürlich immer gleich bleibt. Mit einem weggelassenen Bit müssen sich also im Schnitt zwei Eingabewerte einen Hash-Wert teilen. Bei zwei weggelassenen Bits sind es vier und bei drei acht, bei vier 16 usw.

herbivore

Herbivore hat das jetzt toll erklärt ^^

@Alphawolf:

Für was benötigst du die Hashfunktion? Wenn du sie zum kryptographischen Hashen benötigst, würd ich auf MD5 oder SHA1 aufbauen.

Also ich brauche das für folgendes:

Ich zerlege eine Datei in 8 Byte große Stücke und bilde zu jedem Stück einen Crypt Wert. Das Problem dabei ist halt das am besten gar keine Clashes bei dem Verfahren auftreten dürfen (was man aber nicht verhindern kann) aber ich weiß schon wie ich das umgehe. (Ich arbeite derzeit an einem Komprimierungsverfahren)

MFG Wolf

Hi

Ich nehm mal an, du willst eine hashbasierte Kompression basteln, die die Daten durch die Hashfunktion immer komprimiert, unabhängig von den Ausgangsdaten?

Wie herbivore schon schrieb, es ist nicht möglich aus 8 Byte weniger zu machen, ohne dabei Daten zu verlieren und nicht aus zwei verschiedenen Datenblöcken den selben Hashwert zu machen.

Sagen wir mal, du machst auch 8 Byte durch eine Hashfunktion 6 Byte. Dann hast du theorethisch (falls die Funktion die Werte gleich verteilt) pro Ausgangswert 2^16 Ausgangswerte, die denselben Hash ergeben.

Du kannst hier relativ viel zu dem Thema perfekte Kompression nachlesen: http://www.faqs.org/faqs/compression-faq/part1/section-8.html

oder verstehe ich dich falsch?

lg, Emiswelt