ハッシュ関数
原像計算困難性(Preimage Resistance)とは、与えられたハッシュ値に対して、そのハッシュ値を出力するようなハッシュ関数への入力を求めることが困難であるような性質を言う。ただし、異なる入力から同じハッシュ値が得られるため、そのハッシュ値を得られる入力を1つ求めればよい。
チェックサムやフィンガープリント用のアルゴリズムをハッシュ関数として採用することもできる。それらのアルゴリズムの一部は、任意長の文字列データ z から32ビットまたは64ビットのビット列を生成するので、そこから 0 から n-1 のハッシュ値を容易に抽出できる。
この手法は、ハッシュ値の範囲 n がチェックサムやフィンガープリント関数の値域より十分小さい場合に限って、十分一様に分布するハッシュ値を生成する。しかし、一部のチェックサムは雪崩効果が弱いため、用途によっては不向きである。よく使われているCRC32チェックサムは、上位16ビットだけがハッシュ用途に使える。さらに言えば、入力の各ビットはCRC32の1つのビットにのみ影響を与える。したがって、32ビットのチェックサムをそのままハッシュ値に利用する場合は十分な注意が必要である。
↑ https://kotobank.jp/word/要約関数-653412
↑ "Robust Audio Hashing for Content Identification" by Jaap Haitsma, Ton Kalker and Job Oostveen
↑ Bret Mulvey, Hash Functions. Accessed April 11, 2009
↑ A. Z. Broder. Some applications of Rabin's fingerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science, pages 143--152. Springer-Verlag, 1993
↑ Bret Mulvey, Evaluation of CRC32 for Hash Tables, in Hash Functions. Accessed April 10, 2009.
↑ Bret Mulvey, Evaluation of SHA-1 for Hash Tables, in Hash Functions. Accessed April 10, 2009.
↑ Knuth, Donald (1973). The Art of Computer Programming, volume 3, Sorting and Searching. pp. 506–542