Ich würde gerne wissen, ob Kompressionsalgorithmen immer eine eindeutige Ausgabe für zwei verschiedene Sätze von Dateien erzeugen.
Sagen wir, ich habe zwei Dateien A und B und sage, dass ich für jede dieser Dateien einen Komprimierungsalgorithmus anwende (zum Beispiel wie 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?
Die verlustfreie Komprimierung (wie sie in ZIP-Dateien verwendet wird) 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 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 erhalten ähnliche Informationen. Aus diesem Grund ist das Fachprinzip kein Problem, und so können Sie oft garantieren, dass es die Ausgabegröße reduziert sogar die gewünschte Ausgabegröße angeben. Da ähnliche, aber leicht unterschiedliche Eingaben oft die gleiche Ausgabe erzeugen, ist dies auch für das Hashing nicht hilfreich, da Hashing kleine Änderungen in der Eingabe erfordert, um große Änderungen in der Ausgabe zu erzeugen.
Es ist nicht möglich. Wenn die komprimierten Dateien identisch sind, wie könnten sie beim Dekomprimieren unterschiedliche Ergebnisse erzeugen?
Natürlich kann eine verlustbehaftete Komprimierung die gleiche Ausgabe wie bereits erwähnt liefern.
Aber ich denke, ein sehr wichtiger Punkt, der nicht erwähnt wurde, ist, dass kryptografische Hashes sehr schwer rückgängig zu machen sind (oder denselben Hash über zwei verschiedene Eingaben reproduzieren). Aus diesem Grund wären verlustfreie und damit reversible Kompressionsalgorithmen wie z. B. Reißverschlüsse als kryptographischer Hash ungeeignet.
Sei f ein Komprimierungsalgorithmus. Wenn das Komprimieren von A und B die gleiche Datei ergibt, dann f (A) = f (B) = C für einige C . Lassen Sie nun f ' den Dekompressionsalgorithmus sein. dann f '(f (A)) = f' (C) = f '(f (B)) . Daher dekomprimiert f ' A.zip und B.zip auf die gleiche Datei.
Also ist entweder f ein wertloser Komprimierungsalgorithmus (weil es keine Bijektion ist), oder A und B sind tatsächlich die gleiche Datei. (Wenn ich wertlos sage, meine ich wertlos für verlustfreie Komprimierung!)
Beachten Sie, dass ein verlustfreier Komprimierungsalgorithmus definitionsgemäß nicht als Hashing-Algorithmus ist, da eine Hash-Funktion h eine Domäne A
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 brauchbaren Hash, da die Länge variabel ist.
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 zu A oder B dekomprimiert?
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.
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.
Aber für verlustbehaftete Kompressionsalgorithmen, wie JPEG, ist das natürlich eine Möglichkeit, aber dann wären die Dateien von Anfang an 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 um 1 Grad heller oder dunkler zu machen, speichern Sie es erneut als .JPEG, und Sie haben eine Chance, die Sie haben 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.
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.
BEARBEITEN:
Beachten Sie, dass ich, wenn ich "per definitionem" sage, mit konventioneller Definition meine. Streng genommen könnten MD5, SHA-1 usw. ebenfalls als Komprimierungsalgorithmen betrachtet werden.
Es ist nur möglich verlustbehaftete Komprimierung -Algorithmen (im Gegensatz zu lose Datenkomprimierung ). Theoretisch könnten sie für ähnliche (aber immer noch andere) Eingabedaten das gleiche Ergebnis liefern.
Damit ein Algorithmus ein anständiger kryptografischer Hashwert ist, sollte eine kleine lokalisierte Änderung der Eingabe zu einer starken, dispersiven Änderung der Ausgabe führen. Außerdem ist eine Hash-Funktion eine Zuordnung von einer beliebig großen Eingabe zu einer Ausgabe fester Größe.
Tags und Links algorithm compression hash unique