Können Komprimierungsalgorithmen eine identische Ausgabe für zwei verschiedene Dateien erzeugen?

Question

Ich würde gerne wissen, wenn Kompressionsalgorithmen immer eine eindeutige Ausgabe für zwei verschiedene Sätze von Dateien generieren.

Angenommen, ich habe zwei Dateien A und B und sage, dass ich für jede dieser Dateien einen Komprimierungsalgorithmus verwende (zum Beispiel PKZIP - dies könnte jeder Komprimierungsalgorithmus sein), um A.zip bzw. B.zip zu erhalten . Ist es möglich, dass A.zip für eine Kombination von A und B genau identisch mit B.zip auf der binären Ebene ist. Wenn dies nicht möglich ist, können wir sicher annehmen, dass die Komprimierung dem kryptografischen Hashing entspricht, wenn es um die Gewährleistung von Eindeutigkeiten geht ? Auf der anderen Seite, wenn es möglich ist, könnten Sie mir bitte eine Probe A und B-Datei zusammen mit dem Kompressionsalgorithmus zur Verfügung stellen, um diese Duplizität zu überprüfen?

Answer 1

Verlustfreie Komprimierung (wie in ZIP-Dateien verwendet) erzeugt immer unterschiedliche Ausgaben für verschiedene Dateien - andernfalls könnten Sie die ursprünglichen Daten nicht zuverlässig wiederherstellen. Die Ausgabedaten können jedoch eine beliebige Größe haben - und für einige Eingaben ist sie größer als die ursprüngliche Eingabe. Als solches ist dies normalerweise nicht sehr nützlich als ein Hash, der im Allgemeinen eine Ausgabe fester Größe erfordert.

Verlustbehaftete Komprimierung (z. B. MP3, JPEG usw.) kann die gleiche Ausgabe für verschiedene Eingaben erzeugen. Daher können Sie die Originaldaten nicht wiederherstellen, sondern etwas ähnliches erhalten. Aus diesem Grund ist die pigeonhole principle kein Problem, und so können Sie garantieren, dass es die Ausgabegröße reduziert und oft sogar die gewünschte Ausgabegröße angibt. Da ähnliche, aber leicht unterschiedliche Eingaben oft die gleiche Ausgabe erzeugen, ist dies auch für das Hashing nicht nützlich, da das Hashing kleine Änderungen in der Eingabe erfordert, um große Änderungen in der Ausgabe zu erzeugen.

Answer 2

Es ist nicht möglich. Wenn die komprimierten Dateien identisch sind, wie könnten sie beim Dekomprimieren unterschiedliche Ergebnisse erzielen?

Answer 3

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

Dies macht jedoch keinen verwendbaren Hashwert, da die Länge variabel ist.

Answer 4

Komprimierungsfunktionen müssen injektiv sein, dh jeder Eingang wird einem eindeutigen Ausgang zugeordnet. Wenn dies nicht der Fall wäre, wie würde der Algorithmus wissen, ob er zurück in A oder B dekomprimiert werden soll?

Beachten Sie, dass dies nur für die verlustfreie (Daten) Komprimierung gilt. Es ist beispielsweise möglich, 2 Bilder zu komprimieren und das gleiche Ergebnis zu erhalten, allerdings nur, wenn die Bilder sehr nahe beieinander liegen.

Answer 5

Nun, Ihre Frage ist irgendwie allgemein, aber da Sie dateibasierte Komprimierungsalgorithmen angeben (Ihr pkzip-Tag für eine Sache), dann nein. Es gibt keine Möglichkeit, dass zwei verschiedene verlustfreie Komprimierungsalgorithmen dieselbe Ausgabe von verschiedenen Eingaben erzeugen können.

Für verlustbehaftete Komprimierungsalgorithmen, wie JPEG, ist das natürlich eine Möglichkeit, aber dann wären die Dateien fast identisch.

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

Also verlustfreie Algorithmen, nein, das kann nicht passieren. Für verlustbehaftete Algorithmen, ja.

Answer 6

Es sind nur lossy compression Algorithmen möglich (im Gegensatz zu lossless data compression).Theoretisch könnten sie für ähnliche (aber immer noch unterschiedliche) Eingabedaten das gleiche Ergebnis liefern.

Answer 7

Lassen Sie f einen Komprimierungsalgorithmus sein. Wenn das Komprimieren A und B die gleiche Datei ergibt, dann f (A) = f (B) = C, für einige C. Lassen Sie nun f ' den Dekomprimierungsalgorithmus sein. dann f '(f (A)) = f' (C) = f '(f (B)). Daher f ' dekomprimiert A.zip und B.zip in derselben Datei.

Also, entweder f ist ein wertlos Kompressionsalgorithmus (weil es kein Bijektion ist), oder A und B sind in der Tat die gleiche Datei. (Wenn ich wertlos sage, meine ich für verlustfreie Kompression wertlos!)

Was Ihre andere Frage, beachten Sie, dass eine verlustfreie Komprimierung Algorithmus ist per Definition nicht als Algorithmus Hashing, da eine Hashfunktion h eine Domain abbildet A auf einer (allgemein) kleineren Domäne B. Daher hnicht eine Bijektion, während wir nur behauptet, dass unsere lossless Komprimierungsfunktion f eine Bijektion.

Answer 8

Sicher kann verlustreiche Komprimierung die gleiche Ausgabe wie bereits erwähnt geben.

Aber ich denke, ein sehr wichtiger Punkt, der nicht erwähnt wurde, ist, dass kryptografische Hashes sehr schwer rückgängig zu machen sein sollten (oder den gleichen Hash über zwei verschiedene Eingänge zu reproduzieren). Aus diesem Grund wären verlustfreie und damit reversible Kompressionsalgorithmen wie z. B. Reißverschlüsse als kryptographischer Hash ungeeignet.

Answer 9

Kryptografische Hash-Funktionen haben eine sehr spezifische Anforderung: es sehr schwierig zu machen, sie umzukehren. Die Komprimierung ist per Definition leicht zu invertieren, daher ist sie eine sehr schlechte Wahl für einen Krypto-Hash.

EDIT:

Beachten Sie, dass, wenn ich 'per definitionem' sagen oben, ich durch herkömmliche Definition bedeuten. Streng genommen könnten MD5, SHA-1 usw. ebenfalls als Komprimierungsalgorithmen betrachtet werden.

Answer 10

Damit ein Algorithmus ein anständiger kryptografischer Hashwert ist, sollte eine kleine lokalisierte Änderung der Eingabe zu einer großen, dispersiven Änderung der Ausgabe führen. Eine Hash-Funktion ist auch eine Zuordnung von einer beliebig großen Eingabe zu einer Ausgabe fester Größe.