kleine theorie: komprimierung durch MD5 möglich?

[loki1985]

hi folks!

mir ist da letzt eine theorie eingefallen, die ich hier mal erleutern möchte.
ich will herausfinden ob das möglich wäre.
sollte diese theorie bereits andersweitig existieren dann tut mir das leid, habe mal gegoogelt und nichts gefunden.

also: die theorie ist, dass sich anhand von MD5-hashs eine datenreduktion um die hälfte (eventuell sogar höherer faktor) machen liesse, also eine kompression.
natürlich anzuwenden bei bereits gepackten daten (RAR, BZ2).

ein MD5-hash besteht ja aus 32 charaktären, diese liessen sich aber direkt in hex in 16 bytes speichern.

vorgehen: ich speichere statt 32 bytes daten den 16 byte langen hash davon.
anhand eines lookup-tables, der sämtliche möglichen werte von 32 byte-stellen enthält, könnte ich dann den wert der originaldaten herausbekommen, vorausgesetzt dass jeder dieser werte einen einzigartigen MD5-wert erzeugt (also niemals 2 verschiedene kombinationen denselben hash erzeugen). ich weiss dass das MD5-verfahren bereits "geknackt" wurde, also gleiche hashs für unterschiedliche zeichenfolgen erzeugt wurden. sollten diese jedoch erst bei grösseren zeichenfolgen als 32 stellen auftreten, wäre das ja kein problem.
selbst wenn könnte man ausnahme-regeln definieren.

problem: diese art der kompression wäre auf jeden fall das langsamste das die welt je gesehen hat, also ohne quantencomputer ungeniessbar

also: ist diese idee vollkommen idiotisch und weltfremd, oder vielleicht doch ein klitzekleines bisschen interessant?

gruss,

---loki

[Shade Of Mine]

Viel besser ist eine kompression auf ein paar bytes.

du erstellst einne zentralen server. wenn du jetzt etwas packst, schickst du diese daten an den server und bekommst eine id zurück. und schon fertig.

mit dem ersten byte hätte man bereits 256 verschiedene sachen komprimiert. geil, oder? irgendwann wird diese id zwar zu lange werden, aber dann macht man das selbe eben nochmal.

und bedenke: du kannst 100TB daten in 5bytes komprimieren. wahnsinn.

statt einen extra server dafür zu haben, kann man das natürlich auch in ein programm packen, dass man regelmäßig updaten muss...

btw: ja, es ist absoluter blödsinn.
LUTs werden schon verwendet, aber wenn due LUT um soviele dimensionen größer ist, als die zu komprimierenden daten, lohnt es sich einfach nicht.

und die LUT jedesmal on-the-fly berechnen spart zwar platz, kostet aber doch etwas zeit...

[loki1985]

ok, hast ja recht. geht ja gar nicht, für doppelt so viele strings unterschiedliche hashs zu bekommen.

aber, neue unsinnige idee: wenn man dazu noch ein anderes hash-system verwendet? als z.b. MD5 + CRC32 (oder was besseres, neueres) ???

[the_alien]

Mal ne andere Frage:
Ich dachte einen Hash kann man nicht rückwärts rechnen, was hab ich also davon? Ich könnte die Daten ja garnichtmehr entpacken, oder?

[loki1985]

hash --> lookuptable --> wert.

würde vermutlich pro hash mehr als 1 möglicher wert existieren.

gepaart mit nem 2. hash (z.b. CRC32) KÖNNTE es sein dass sich von allen möglichen werten dann der echte rausfinden liesse.

der lookuptable wird einfach gebaut indem man von (0) bis (maximum) hashes errechnet und eben abspeichert....

[Bashar]

loki1985 schrieb:

also: ist diese idee vollkommen idiotisch und weltfremd, oder vielleicht doch ein klitzekleines bisschen interessant?

Völlig unsinnig. Hast du dich schonmal ansatzweise damit befasst, was Packverfahren tun, und warum das funktioniert?

[net 0]

loki1985 schrieb:

der lookuptable wird einfach gebaut indem man von (0) bis (maximum) hashes errechnet und eben abspeichert....

und wenn man, so wie er's vorschlägt, eine lookup table für alle kombinationen von 32bytes braucht, dann ist die mal eben 256^32 etwa 1.2*10^77 einträge gross

[the_alien]

Dann doch lieber ungepackt als so einen Packer

[loki1985]

mensch, es geht dabei doch einzig und alleine um die theorie, ob es möglich wäre etc.....

[the_alien]

loki1985 schrieb:

mensch, es geht dabei doch einzig und alleine um die theorie, ob es möglich wäre etc.....

Hmmm, wenns normale Ascii Zeichen sind würde es gehen, sobald du Unicode hast müssen rein rechnerisch doch gleiche Hashes für unterschiedliche Strings rauskommen. Ganz davon ab, dass so eine Lookup Tabelle unmöglich wäre

[loki1985]

the_alien schrieb:

davon ab, dass so eine Lookup Tabelle unmöglich wäre

... du hast es nur nicht richtig verstanden

[junix]

Ich glaube eher DU hast nicht verstanden.... Siehe Bashars posting...

[loki1985]

ich kann nur sagen dass ich mich bereits mit der theorie von huffman und dem Lempel-Ziv-Algorythmus beschäftigt habe....

und dann soll er mir einfach begründen, weshalb ein derartiger lookup-table unmöglich wäre. er wäre zwar lahm, aber schneller als das on-the-fly-berechnen via MD5.

[Bashar]

loki1985 schrieb:

ich kann nur sagen dass ich mich bereits mit der theorie von huffman und dem Lempel-Ziv-Algorythmus beschäftigt habe....

Aber nicht mit der Theorie hinter dem Packen allgemein. Warum man überhaupt aus einer Bitsequenz eine kürzere machen kann, ohne Informationen zu verlieren. Welche Voraussetzungen dafür gegeben sind usw. Mach mal folgendes Gedankenexperiment: Du nimmst deinen Packer und wendest ihn iterativ auf sein eigenes Ergebnis an. Wenn er jedesmal die Daten auf die Hälfte komprimiert, hast du irgendwann nur noch 1 Bit. Dass man das nicht wieder entpacken kann liegt auf der Hand. Folgerung: Kein Packer kann beliebige Daten komprimieren.

[loki1985]

exakt. diese erkenntnis ist mir auch schon gekommen (wäre trotzdem cool, einen film auf 1,44"-diskette zu kriegen )

aber meine überlegung ist ja auch keine regulärer ansatz zum komprimieren.
zudem in heutiger zeit fernab von nützlich, da man so für ein paar hundert byte vermutlich tage zum dekomprimieren bräuchte.

die frage ob sich ein eindeutiges und einzig richtiges ergebnis "entpacken" lässt ist hier eben die frage und bin ich mir nicht im geringsten sicher...

daher die idee, für einen datenarray oder mehr technisch verschiedene hashs zu speichern....
lohnt sich nur wenn die daten grösser sind als alle hashs zusammen, aber je grösser die daten desto höher die gefahr, ein falsches ergebnis zu erhalten (glaube ich mal zumindest)...

/ADD: ich glaube absolut nicht dass meine überlegung tatsächlich funktioniert, denn sonst hätte sie schon irgendjemand präsentiert.

wie gesagt, ist nur so eine gedankliche spielerei.

[Bashar]

loki1985 schrieb:

aber meine überlegung ist ja auch keine regulärer ansatz zum komprimieren.

Doch, in der Beziehung schon. Der Ausgang des Gedankenexperiments hängt ja nicht davon ab, ob der Packer in irgendeiner Art und Weise regulär ist.

[ness]

Und mal ganz davon abgesehen, es sollte jedem mit gesundem Menschenverstand auffallen, dass kein Algorithmus aus allen 2³² Kombinationen verschiedene Werte errechnen soll, die er auf 2¹⁶ Möglichkeiten abbildet.

[loki1985]

ness schrieb:

Und mal ganz davon abgesehen, es sollte jedem mit gesundem Menschenverstand auffallen, dass kein Algorithmus aus allen 2³² Kombinationen verschiedene Werte errechnen soll, die er auf 2¹⁶ Möglichkeiten abbildet.

eben, daher auch die idee mit mindestens 2 "technisch" unterschiedlichen algorythmen, z.b. MD5 UND CRC32 (wobei ich mal denke dass CRC32 schon zu alt und "billig" ist)....

[net 0]

loki1985 schrieb:

eben, daher auch die idee mit mindestens 2 "technisch" unterschiedlichen algorythmen, z.b. MD5 UND CRC32 (wobei ich mal denke dass CRC32 schon zu alt und "billig" ist)....

crc ist nicht billig. das ist auf speed ausgelegt. anders als md5 wo's darum geht möglichst wenig mehrdeutigkeiten zu haben

[loki1985]

ok, ich habe da nicht so den durchblick. nur eben bräuchte mann für so einen test ein system welches auf möglichst wenige gleiche hashes ausgelegt ist....