私は多数のファイルをハッシュしており、ハッシュの衝突を避けるために、ファイルの元のサイズも保存しています。これにより、ハッシュの衝突があったとしても、ファイル サイズも同じになる可能性はほとんどありません。この音 (ハッシュの衝突はどのようなサイズでも同じように発生する可能性があります) ですか、それとも別の情報が必要ですか (衝突がオリジナルと同じ長さである可能性が高い場合)。
または、より一般的には、元のファイルのサイズに関係なく、すべてのファイルが特定のハッシュを生成する可能性は同じですか?
ハッシュ関数は通常、すべての結果バケットにデータを均等に分散するように記述されています。
ファイルが利用可能なサイズの固定範囲に均等に分散されていると仮定した場合、ファイルには1024（2 ^ 10）の均等に分散された個別のサイズしかないとします。せいぜいファイルサイズを保存することは、異なるファイルサイズの数だけ衝突の可能性を減らすだけです。
注：2 ^ 32の均等に分散された個別のサイズであると想定できますが、それでも残りの計算は変更されません。
MD5での衝突の一般的な確率は（たとえば）であると一般に認められています1/(2^128)。
特にハッシュ関数に組み込まれているものがない限り、そうではありません。Xの確率が任意の2つのランダムな値{ 、}P(MD5(X) == MD5(X+1)) と同じままであるような有効なものが与えられます。つまり、、、およびの任意の値に対して==です。YZP(MD5(Y) == MD5(Z))P(MD5(X) == MD5(X+1))1/(2^128)XYZ
これを2^10の個別のファイルと組み合わせると、ファイルサイズを保存することで、アイテムが異なるかどうかを示す最大10ビットが追加されます（これも、ファイルがすべての値に均等に分散されていることを前提としています）。
したがって、最善の場合は、Nバイト未満の一意の値に対してさらにNバイトのストレージを追加するだけです（Nを超えることはできません）。したがって、ファイルサイズを保存するよりも、ハッシュ値のデータが均等に分散される可能性が高いため、代わりにSHA-1/2などを使用してハッシュ関数から返されるバイト数を増やすことをお勧めします。
つまり、MD5が衝突に十分でない場合は、より強力なハッシュを使用します。より強力なハッシュが遅すぎる場合は、MD5などの衝突の可能性が低い高速ハッシュを使用してから、SHA-1などの低速ハッシュを使用します。またはSHA256を使用して衝突の可能性を減らしますが、SHA256が十分に高速で、スペースの2倍が問題にならない場合は、おそらくSHA256を使用する必要があります。
ハッシュ関数によって異なりますが、一般に、サイズが同じでコンテンツが異なるファイルは、サイズが異なるファイルと同じハッシュを生成する可能性が低くなります。それでも、ファイルサイズの保存などの独自のソリューションに賭けるよりも、より大きなスペースを持つ実績のあるハッシュ (たとえば、CRC32 の代わりに MD5、または MD5 の代わりに SHA1) を使用する方がおそらくクリーンです。
ハッシュ関数は、衝突が発生しにくいように設計されています。そうしないと、効果がありません。1 について絶対に信じられない
ほどの
ハッシュ衝突がある場合: number_of_possible_hashes ファイルサイズについては何も言わない確率。
ハッシュの衝突について二重に確認したい場合は、同じファイルに対して 2 つの異なるハッシュを計算できます。ハッシュ + ファイル サイズを保存するよりもエラーが発生しにくくなります。
ハッシュのサイズは、元のデータのサイズに関係なく同じです。可能なハッシュの数は限られているため、理論的には、サイズが異なる 2 つのファイルが同じハッシュを持つ可能性があります。ただし、これは、同じサイズの 2 つのファイルが同じハッシュを持つ可能性があることも意味します。
暗号化ハッシュのファミリー (MD5、SHA-x など) の要点は、衝突をほとんど起こりそうにないようにすることです。公式の法的手続きは、故意に衝突を作り出すことが非現実的であることに依存する準備ができているという考えです。したがって、実際には、これらのハッシュのサスペンダーにベルトを追加することは、スペースと CPU 時間を無駄に使用することになります。