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

Komprimierungsfunktionen müssen injektiv sein, d. h. jede Eingabe führt zu einer eindeutigen Ausgabe. Wenn dies nicht der Fall wäre, woher wüsste der Algorithmus dann, ob er nach A oder B dekomprimieren soll?

Beachten Sie, dass dies nur für die verlustfreie (Daten-)Kompression gilt. Es ist zum Beispiel möglich, 2 Bilder zu komprimieren und das gleiche Ergebnis zu erhalten, aber nur, wenn die Bilder zu Beginn sehr ähnlich waren.

Answer 2

Nun, Ihre Frage ist ziemlich allgemein, aber da Sie auf dateibasierte Komprimierungsalgorithmen hinweisen (z.B. Ihr pkzip-Tag), dann nein. Es gibt keine Möglichkeit, dass zwei verschiedene verlustfreie Kompressionsalgorithmen die gleiche Ausgabe aus verschiedenen Eingaben erzeugen können.

Bei verlustbehafteten Komprimierungsalgorithmen wie JPEG ist das natürlich möglich, aber dann wären die Dateien von vornherein fast identisch.

Nehmen Sie beispielsweise eine PNG-Datei, speichern Sie sie als JPEG, ändern Sie ein Pixel, um es in einem der Kanäle um 1 Grad heller oder dunkler zu machen, speichern Sie sie erneut als JPEG, und Sie haben die Chance, dass Sie zwei identische Dateien erhalten, obwohl die Eingabe, wenn auch nur geringfügig, unterschiedlich war.

Also verlustfreie Algorithmen, nein, das kann nicht passieren. Bei verlustbehafteten Algorithmen, ja.

Answer 3

Kryptografische Hash-Funktionen haben eine ganz bestimmte Anforderung: Sie müssen sehr schwer umkehrbar sein. Komprimierung ist per Definition leicht zu invertieren und daher eine sehr schlechte Wahl für einen kryptografischen Hash-Wert.

EDIT :

Wenn ich oben von "per Definition" spreche, meine ich damit die herkömmliche Definition. Streng genommen könnten auch MD5, SHA-1 usw. als Kompressionsalgorithmen betrachtet werden.

Answer 4

Es ist nur möglich für verlustbehaftete Komprimierung Algorithmen (im Gegensatz zu verlustfreie Datenkompression ). Theoretisch könnten sie bei ähnlichen (aber dennoch unterschiedlichen) Eingabedaten das gleiche Ergebnis liefern.

Answer 5

Damit ein Algorithmus ein guter kryptografischer Hash-Wert ist, sollte eine kleine örtliche Änderung der Eingabe eine große Änderung der Ausgabe bewirken. Außerdem ist eine Hash-Funktion eine Abbildung von einer beliebig großen Eingabe auf eine Ausgabe fester Größe.