42

CRC32 はハッシュ関数として使用できますか? このアプローチの欠点はありますか? トレードオフはありますか?

4

3 に答える 3

46

CRC32は、ハッシュ アルゴリズムとして非常にうまく機能します。CRCの要点は、できるだけ少ない衝突でバイト ストリームをハッシュすることです。とはいえ、考慮すべき点がいくつかあります。

  • CRC は安全ではありません。安全なハッシュのためには、計算コストの高いアルゴリズムが必要です。

  • さまざまなプロパティを持つさまざまな CRC フレーバーが存在します。適切なアルゴリズムを使用していることを確認してください。たとえば、ハッシュ多項式 0x11EDC6F41 (CRC32C) を使用するのが最適な汎用の選択です。

  • ハッシュ速度/品質のトレードオフとして、x86 CRC32 命令に勝るものはありません。ただし、この命令は古い CPU には存在しないため、移植性の問題に注意してください。

- - 編集 - -

Mark Adler は、 Bret Mulvey によるハッシュ評価に役立つ記事へのリンクを提供しました。この記事で提供されているソース コードを使用して、CRC32C と Jenkins96 の両方に対して「バケット テスト」を実行しました。これらの表は、真に一様な分布が測定結果よりも偶然に悪化する確率を示しています。したがって、数字が大きいほど良いです。筆者は、0.05 以下を弱いと考え、0.01 以下を非常に弱いと考えました。私はこのすべてについて著者を完全に信頼しており、結果を報告しているだけです.

CRC32C が Jenkins96 よりも優れたパフォーマンスを示したすべてのインスタンスに * を付けました。この単純な集計では、CRC32C は 96 回中 54 回、Jenkins96 よりも均一なハッシュでした。 特にx86 CRC32 命令を使用できる場合、速度と品質のトレードオフは優れています。

CRC32C (0x1EDC6F41)

       統一キー テキスト キー スパース キー

ビット 下位 上位 下位 上位 下位 上位
 1 0.671 *0.671 *1.000 0.120 *0.572 *0.572
 2 *0.706 *0.165 *0.729 *0.919 0.277 0.440
 3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542
 4 0.573 0.332 0.433 0.462 *0.855 0.393
 5 0.023 *0.681 0.470 0.907 0.266 0.059
 6 *0.145 *0.523 0.354 *0.172 *0.336 0.588
 7 0.424 0.722 0.172 *0.736 0.184 *0.842
 8 *0.767 0.507 *0.533 0.437 0.337 0.321
 9 0.480 0.725 *0.753 *0.807 *0.618 0.025
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003
12 *0.979 *0.239 *0.709 0.786 0.171 *0.865
13 *0.515 0.395 0.192 0.600 0.869 *0.238
14 0.089 *0.609 0.055 *0.414 *0.286 *0.398
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300
16 0.015 *0.946 *0.467 0.459 0.372 *0.793

そして、記事の著者が優れたハッシュであると考えた Jenkins96 の場合:

ジェンキンス96

      統一キー テキスト キー スパース キー

ビット 下位 上位 下位 上位 下位 上位
 1 0.888 0.572 0.090 0.322 0.090 0.203
 2 0.198 0.027 0.505 0.447 0.729 0.825
 3 0.444 0.510 0.360 0.444 0.467 0.540
 4 0.974 0.783 0.724 0.971 0.439 0.902
 5 0.308 0.383 0.686 0.940 0.424 0.119
 6 0.138 0.505 0.907 0.103 0.300 0.891
 7 0.710 0.956 0.202 0.407 0.792 0.506
 8 0.031 0.552 0.229 0.573 0.407 0.688
 9 0.682 0.990 0.276 0.075 0.269 0.543
10 0.382 0.933 0.038 0.559 0.746 0.511
11 0.043 0.918 0.101 0.290 0.584 0.822
12 0.895 0.036 0.207 0.966 0.486 0.533
13 0.290 0.872 0.902 0.934 0.877 0.155
14 0.859 0.568 0.428 0.027 0.136 0.265
15 0.290 0.420 0.915 0.465 0.532 0.059
16 0.155 0.922 0.036 0.577 0.545 0.336

---- 編集 ---- 古いリンクを修正し、マイナーなクリーンアップを行いました。

于 2012-06-09T15:26:01.907 に答える
8

Mark Adler が「crc32 はハッシュへの入力ビットの分散が不十分である」と言った理由がわかりません。crc32 ハッシュには、入力ビットと完全に等しい単一ビットはありません。ハッシュの任意のビットは、入力ビットの線形結合です。次に、crc は常に同じ数の異なる入力シーケンスを特定のハッシュ値に均等にマッピングします。たとえば、1000 ビット長のメッセージがある場合、crc32 の後に、特定のハッシュ値を生成する 2^(1000-32) シーケンスを常に見つけることができます。

セキュリティ機能が必要ない場合は、crc が完全にハッシュとして機能します。

実際には、crc-256 などの長い crc が必要な場合は、他の安全でないハッシュ関数の方が crc よりも簡単かもしれません。

于 2015-02-27T01:58:15.137 に答える