衝突 (計算機科学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

計算機科学における衝突(collision)とは、2つの異なるデータから生成したハッシュ値チェックサムフィンガープリントメッセージダイジェストなどが同じ値になることを言う。

非常に大きな集合から比較的短いビット列への写像、例えば「考えられる人名全て」や「コンピュータ上で作成されうるファイル全て」から256bitのビット列への写像においては、衝突の発生をゼロにすることはできない。これは鳩の巣原理の一例である。

衝突が発生した際の影響度は応用分野によって異なる。例えば、相同DNA配列や、ほぼ同じ内容の音声ファイルなど、よく似たデータを同一視するためにハッシュ関数とフィンガープリントを使用する場合、ハッシュ関数はそのようなデータに対してコリジョンを発生させる確率ができる限り大きくなるように設計される。 一方、チェックサムなどはよく似た入力に対してコリジョンを発生させる確率ができる限り小さくなるように設計され、全く異なるデータ間でのコリジョンについては特に意識されない。

上記のような差はあるが、ほとんどの分野においてコリジョンは望ましくない結果とされる。ハッシュテーブルにおいて、コリジョンはルックアップ処理のコストを増加させる。プロキシサーバやファイルのバックアップシステムにおいて不要なファイルの保存や転送を省略するためにはフィンガープリントが使用されるが、ここでの衝突は不適切な処理やデータ消失の原因になりうる。 暗号学的ハッシュ関数に対して衝突攻撃が成功した場合、コンピュータや通信システムのセキュリティが弱体化する。このような問題を避けるため、様々な分野においてコリジョンの発生確率が低くなるようなアルゴリズムの開発に努力が注がれている。

関連項目[編集]