Ist es möglich, dass Komprimierungsalgorithmen für zwei verschiedene Dateien eine identische Ausgabe erzeugen?

Question

Ich würde gerne wissen, ob Komprimierungsalgorithmen für zwei verschiedene Dateisätze immer eine eindeutige Ausgabe erzeugen.

Angenommen, ich habe zwei Dateien A und B und wende einen Komprimierungsalgorithmus (z. B. PKZIP - das kann jeder beliebige Komprimierungsalgorithmus sein) für jede dieser Dateien an, um A.zip bzw. B.zip zu erhalten. Ist es möglich, dass A.zip auf binärer Ebene für eine bestimmte Kombination von A und B genau mit B.zip identisch ist? Wenn dies nicht möglich ist, können wir dann davon ausgehen, dass die Komprimierung gleichwertig mit kryptografischem Hashing ist, wenn es darum geht, Einzigartigkeit zu garantieren? Falls dies jedoch möglich ist, könnten Sie mir bitte eine Beispieldatei von A und B zusammen mit dem Kompressionsalgorithmus zur Verfügung stellen, um diese Duplizität zu überprüfen?

Answer 1

Eine verlustfreie Komprimierung (wie sie in ZIP-Dateien verwendet wird) führt immer zu unterschiedlichen Ergebnissen für verschiedene Dateien - andernfalls könnten Sie die Originaldaten nicht zuverlässig wiederherstellen. Die Ausgabedaten können jedoch eine beliebige Größe haben - und bei einigen Eingaben werden sie größer sein als die ursprüngliche Eingabe. Daher ist dies in der Regel nicht sehr nützlich für einen Hash, der im Allgemeinen eine Ausgabe mit fester Größe erfordert.

Eine verlustbehaftete Komprimierung (z. B. MP3, JPEG usw.) kann für verschiedene Eingaben dieselbe Ausgabe erzeugen - Sie können also die ursprünglichen Daten nicht wiederherstellen, sondern erhalten stattdessen etwas, das ihnen ähnelt. Aus diesem Grund ist die Schubladenprinzip ist kein Problem, und so können Sie garantieren, dass es die Ausgabegröße reduziert, oft sogar unter Angabe der gewünschten Ausgabegröße. Da jedoch ähnliche, aber leicht unterschiedliche Eingaben oft die gleiche Ausgabe erzeugen, ist dies auch für Hashing nicht sinnvoll, da Hashing kleine Änderungen in der Eingabe erfordert, um große Änderungen in der Ausgabe zu erzeugen.

Answer 2

Das ist nicht möglich. Wenn die komprimierten Dateien identisch wären, wie könnten sie dann beim Dekomprimieren unterschiedliche Ergebnisse liefern?

Answer 3

Natürlich kann eine verlustbehaftete Komprimierung das gleiche Ergebnis liefern, wie bereits erwähnt.

Ein wichtiger Punkt, der noch nicht erwähnt wurde, ist meiner Meinung nach, dass kryptografische Hashes nur sehr schwer umkehrbar sein sollten (oder dass derselbe Hash über zwei verschiedene Eingaben reproduziert werden kann). Aus diesem Grund wären verlustfreie und damit umkehrbare Komprimierungsalgorithmen wie zips als kryptographischer Hash ungeeignet.

Answer 4

Sea f ein Komprimierungsalgorithmus sein. Wenn die Komprimierung A y B die gleiche Datei ergibt, dann f(A) = f(B) = C für einige C . Nun, lassen Sie f' sei der Dekomprimierungsalgorithmus. dann f'(f(A)) = f'(C) = f'(f(B)) . Folglich, f' dekomprimiert A.zip y B.zip in dieselbe Datei.

Also, entweder f ein wertloser Komprimierungsalgorithmus ist (weil es sich nicht um eine Bijektion handelt), oder A y B sind in der Tat dieselbe Datei. (Wenn ich sage wertlos, meine ich wertlos für verlustfreie Komprimierung!)

Zu Ihrer anderen Frage ist zu sagen, dass ein verlustfreier Komprimierungsalgorithmus per Definition no als Hashing-Algorithmus, da eine Hashing-Funktion h bildet einen Bereich A auf einem (im Allgemeinen) kleineren Gebiet B . Daher h kann nicht eine Bijektion sein, während wir gerade behauptet haben, dass unsere verlustfreie Kompressionsfunktion f es eine Bijektion.

Answer 5

Es sollte offensichtlich sein: Wenn die komprimierten Dateien identisch sind, wie kann der Dekomprimierer dann wissen, ob er A oder B daraus machen soll?

Dies ergibt jedoch keinen brauchbaren Hash, da die Länge variabel ist.