ハッシュ関数のサンプル（python, hashlib）

■ハッシュ関数の試し。
暗号つながりでハッシュ関数について調べてみた。ハッシュ関数は、ある文字列をインプットすると、一定のデータの長さに変換する関数。MD5とかSHA-256とかある。

例えば、「0」に対してMD5を使って値（ハッシュ値）を出すと、「cfcd208495d565ef66e7dff9f98764da」となる。これは、16進数の32桁なので128ビット（16進数の1文字が、10進数で0-15、2進数で0000 - 1111の4ビット分となる）。

Wikiとかの説明を見てみると、異なる値で同じハッシュ値が出ることもあるそう（衝突）。

MD5は128ビットで固定だけど、SHAKE-128では任意の長さに設定できたので、短いビット数で衝突を見てみる。

pythonのhashlibを使って、下のサンプルコードを作った。

import hashlib

list = []
num = 0

while True:

    target = str(num).encode("utf-8")
    hash = hashlib.shake_128(target)
    result = hash.hexdigest(3)
    num = num + 1
    if result in list:
        print(num)
        print(result)
        break
    else:
        list.append(result)

while文で0から順にハッシュ値を求め、リストに追加していく。追加する際に、リスト内にすでに同じものがあるかチェックし、もしあればそこで終了する。
ビットの長さを変えてどの位で衝突が起こるか見た。

長さ	1回目	2回目	ハッシュ値
1	8	12	ca
2	156	250	704e
3	2058	2937	719bcc
4	52838	81052	cf027be7

長さ5で試すとなかなか終了しないので、4まで。

もとの文字列が同じであれば同じ値になり、さらにハッシュ値から元に戻すことはできない。サーバ側でパスワードをハッシュ値の形で保存するみたいに使われるようだけど（もし漏洩したとしてもパスワードの推測はできない）、別のパスワードが誤って通ってしまう可能性もあるんだろうな。たぶん確率的には無視できるくらい低いだろうけど。