Pythonによる「数字6桁パスワードのMD5ハッシュ値の総当たり」

実行環境

os：windows7 Home Premium sp1
cpu：i7-4770T @2.50GHz
Python：3.4.1(Anaconda 2.0.1 (64-bit))

ソースコード

Python3なので、文字列をbyte列に変換する作業が入っています。
cpuは8コアですが、並列数は4にしてあります。
使ったコードはここに置いてあります。

シングルスレッド版

hash_single.py

import time
import hashlib
import sys

def main():
    argv = sys.argv[1:]
    if len(argv) != 2:
        sys.exit(0)

    salt = argv[0]
    hash = argv[1]

    start = time.time()
    for i in range(1000000):
        pw = "{0}${1:06d}".format(salt, i).encode("utf-8")
        tmp = hashlib.md5(pw).hexdigest()
        if hash == tmp:
            print("match[{0:06d}]".format(i))
    end = time.time()
    print("elapsed time:{0}s".format(end - start))

if __name__ == "__main__":
    main()

マルチスレッド版

hash_parallel.py

import time
import hashlib
import sys
from multiprocessing import Pool
from itertools import repeat

def calc_hash(arg):
    hash, salt, i = arg
    tmp = hashlib.md5("{0}${1:06d}".format(salt, i).encode("utf-8")).hexdigest()
    return hash == tmp

def main():
    argv = sys.argv[1:]
    if len(argv) != 2:
        sys.exit(0)

    salt = argv[0]
    hash = argv[1]

    start = time.time()

    pool = Pool(4)
    result = pool.map(calc_hash, zip(repeat(hash), repeat(salt), range(1000000)))
    index = result.index(True)
    print("match[{0:06d}]".format(index))

    end = time.time()
    print("elapsed time:{0}s".format(end - start))

if __name__ == "__main__":
    main()

実行方法

それぞれを5回ずつ繰り返して時間を計ります。

python hash_single.py hoge 4b364677946ccf79f841114e73ccaf4f
python hash_parallel.py hoge 4b364677946ccf79f841114e73ccaf4f

計測結果

	1回目	2回目	3回目	4回目	5回目	平均	標準偏差
シングル版	1.724097967	1.736099005	1.729099035	1.733099937	1.739099026	1.732298994	0.005891065
マルチ版	1.086061954	1.098062992	1.080061913	1.113064051	1.085062027	1.092462587	0.013278723

単位は秒

並列時の実行時間は非並列の63%
※参考
「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタを元に少し変更したものの実行結果(並列数4)は0.912sでした。(ソースコード)

まとめ

並列化で実行時間が63%程度にしかなっていないので、並列化という点では全然ですが、cの場合と16%程度の差まで追いつけたので、Pythonは頑張った方だと思います。
ｃが駄目なだけとも言えなくもないですが。

追記(2014/09/23)

bytearrayなるものの存在を知りました。
pythonの文字列、byte列は変更不可ですが、bytearrayは変更可能です。
これを利用してシングルスレッド版で毎回byte列全体を作り直さずに数字６桁の部分だけを作り直せば速くなるかと思いましたが、０．１秒ほどしか早くならず、期待したほどではありませんでした。

何をしたのかわかる程度に、変更部分を載せておきます。

from itertools import product
pw = bytearray("{0}${1:06d}".format(salt, 0).encode("utf-8"))  # bytearrayを用意
for i, value in enumerate(product(b'0123456789', repeat=6)):
    pw[-6:] = value  # 数字の部分のみ変更

やっぱり、速さを突き詰めるならC/C++かな。

「数字6桁パスワードのMD5ハッシュ値の総当たり」Pythonでやってみた

面白そうなので、参加してみた

過去の業績(順不同)