圧縮アルゴリズムが常に 2 つの異なるファイル セットに対して一意の出力を生成するかどうかを知りたいです。
たとえば、A と B の 2 つのファイルがあり、これらの各ファイルに圧縮アルゴリズム (たとえば、PKZIP など - これは任意の圧縮アルゴリズムである可能性があります) を適用して、それぞれ A.zip と B.zip を取得するとします。A.zip は、A と B のいくつかの組み合わせについて、バイナリ レベルで B.zip と完全に同一である可能性がありますか?これが不可能な場合、一意性を保証することに関して、圧縮が暗号化ハッシュと同等であると安全に想定できますか? ? 一方、可能であれば、サンプル A および B ファイルと、この二重性を検証するために使用する圧縮アルゴリズムを提供していただけませんか?
可逆圧縮 (ZIP ファイルで使用されるような) は、ファイルごとに常に異なる出力を生成します。そうしないと、元のデータを確実に復元することができなくなります。ただし、出力データは任意のサイズである可能性があり、一部の入力では、元の入力よりも大きくなります。そのため、これは通常、固定サイズの出力を必要とするハッシュとしてはあまり役に立ちません。
非可逆圧縮 (MP3、JPEG など) は、異なる入力に対して同じ出力を生成する可能性があります。そのため、元のデータを復元することはできませんが、それに似たものを取得できます。このため、鳩の巣の原理は問題ではなく、多くの場合、目的の出力サイズを指定することで、出力サイズが縮小されることを保証できます。ただし、類似しているがわずかに異なる入力は同じ出力を生成することが多いため、これはハッシュにも役立ちません。ハッシュでは、入力に小さな変更を加えて出力に大きな変更を加える必要があるためです。
それは不可能。圧縮されたファイルが同一である場合、それらを解凍すると、どのようにして異なる結果が生成されるのでしょうか?
確かに、非可逆圧縮では、すでに述べたのと同じ出力が得られます。
しかし、言及されていない非常に重要な点は、暗号化ハッシュを元に戻す（または2つの異なる入力を介して同じハッシュを再現する）のは非常に難しいということです。このため、zipのような可逆圧縮アルゴリズムは、暗号化ハッシュとしては不適切です。
fを圧縮アルゴリズムとします。圧縮AしBて同じファイルを生成する場合、一部のCに対して f(A) = f(B) = Cです。ここで、f'を解凍アルゴリズムとします。次にf'(f(A)) = f'(C) = f'(f(B)) . したがって、f'は同じファイルに解凍します。A.zipB.zip
したがって、fは価値のない圧縮アルゴリズム (全単射ではないため) であるかA、B実際には同じファイルです。(価値がないというのは、ロスレス圧縮の価値がないという意味です!)
他の質問については、ロスレス圧縮アルゴリズムは定義上、ハッシュ関数hがドメインAを (一般的に) 小さいドメインBにマップするため、ハッシュ アルゴリズムではないことに注意してください。したがって、ロスレス圧縮関数fは全単射であると断言しましたが、hを全単射にすることはできません。
暗号化ハッシュ関数には、非常に特殊な要件があります。それは、それらを逆にすることを非常に困難にすることです。定義上、圧縮は簡単に反転できるため、暗号化ハッシュには非常に適していません。
編集：
上記で「定義による」と言うときは、従来の定義を意味することに注意してください。厳密に言えば、MD5、SHA-1なども圧縮アルゴリズムと見なすことができます。
圧縮関数は単射である必要があります。つまり、各入力が一意の出力にマップされます。これが真実でない場合、アルゴリズムは A または B に解凍するかどうかをどのように判断するのでしょうか?
これはロスレス (データ) 圧縮の場合にのみ当てはまることに注意してください。たとえば、2 つの画像を圧縮して同じ結果を得ることができますが、最初から画像が非常に近い場合に限られます。
まあ、あなたの質問はちょっと一般的ですが、ファイルベースの圧縮アルゴリズム（1つのことのpkzipタグ）を示しているので、いいえ. 2 つの異なる可逆圧縮アルゴリズムが、異なる入力から同じ出力を生成する方法はありません。
ただし、JPEG などの非可逆圧縮アルゴリズムの場合、もちろん可能性はありますが、ファイルは最初はほとんど同じです。
たとえば、.PNG ファイルを取得して .JPEG として保存し、1 つのピクセルを変更してチャネルの 1 つで 1 度明るくまたは暗くし、.JPEG として再保存すると、2 つの同一のファイルが得られる可能性があります。 、わずかではありますが、入力は異なっていましたが。
つまり、ロスレス アルゴリズムは、いいえ、それはあり得ません。不可逆アルゴリズムの場合、はい。
明らかなはずです:圧縮ファイルが同一である場合、圧縮解除プログラムは、圧縮ファイルから A を作成するか B を作成するかをどのように知ることができますか??
ただし、長さが可変になるため、これは使用可能なハッシュにはなりません。
アルゴリズムがまともな暗号化ハッシュであるためには、入力の局所的な小さな変化が出力の大きな分散変化を引き起こすはずです。また、ハッシュ関数は、任意のサイズの入力から固定サイズの出力へのマッピングです。