質問: 255byte以内のURLに対してMD5でハッシュを得たときに、それがコリジョンを起こす場合はありますでしょうか。 255byte程度の短い文字列に対してであればコリジョンが発生しないと聞いたのですが根拠となる情報があれば教えてください。
回答: TextPage/Misc/Tower of Hanoi まず、MD5にしろSHA1にしろ、コリジョンの可能性は0ではありません。 コリジョンの無いハッシュ関数があったとしたら・・・それはハノイの塔アーカイバですよ。 MD5 - Wikipedia, the free encyclopedia 255byte以下なら~も嘘です。 そのような偏りがあったとしたら、入力と出力が独立で無いことを意味し、 ‘よい’ハッシュ関数と呼ぶことはできません。 また、MD5のソースを読んでも長さが関係ないことは直感的にわかるかと。 大雑把に言えば、128bitで割った余りを求めているようなものなので。 http://www.google.com/search?hl=ja&lr=&q=site:www.radium... Google ハッシュ関数についてはRadium Software Developmentさんで連載されていたので、 そちらも参考になさるとよろしいかと。 完全ハッシュ関数なんかは使われる機会もあるのではないでしょうか。 Hashing(1-5) さて、URLの空間が、計算しやすくするために0xFF^256として、2048bitですか、 これをMD5なら128bit、SHA1なら160bitに‘圧縮’するわけですが、 よくできたハッシュ関数ならば入力の空間の大きさは関係ありません。 たとえ与える平文空間がハッシュ関数の平文空間に対してに偏りがあったとしても、 出力である暗号文空間では均等に分布するはずですから。 結局のところ、用いているハッシュ関数がよくできている、という仮定をおく限り、 その衝突可能性は与えられた入力の数のみに依存します。 Yahoo! Search blog: Our Blog is Growing Up � And So Has Our Index Yahooが前にインデックス数が192億とか発表していましたので、1兆(=40bit)としましょう。 先述のRadium Software DevelopmentさんでBob Jenkins 氏の言葉が引用されていましたが、曰く、 「2^n 個のキーに関して,衝突の可能性を 1/(2^m) 程度に抑えたいならば, 2(n+m) ビットのハッシュ値を用いる必要があります。」 だそうです。 #このへんの詳細は「バースデイパラドックス」とかで。 つまり、80bitのハッシュ関数を用いれば衝突確率は1/2になります。 MD5ですと128bitですから、1/(2^88)程度ということになりますね。 2^88個のパラレルワールドのうち、たった一つのみで衝突が起きる、と。 この世界で衝突が起きると思いますか? Cyclic redundancy check - Wikipedia, the free encyclopedia これでも衝突が怖いのでしたら、ハッシュ関数のグレードを落として他の方法と併用した方がいいでしょう。 CRC32やchecksumのような速いがおよそハッシュ関数とは呼べないものを使った上で、B-Treeとか。 これならば衝突可能性はゼロになりますからね。