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

### 面白そうなので、参加してみた
これは、[パスワード問合せシステムを作る (clojureのreducers)](http://qiita.com/kawasima/items/ef75f317605ce800a839)に端を発する企画（？）でJALのパスワードの管理システムを現実的な範囲で達成可能な方法を妄想するものです。

今更とか時代遅れとか言わないでください。

### 過去の業績(順不同)

* [パスワード問合せシステムを作る (clojureのreducers)](http://qiita.com/kawasima/items/ef75f317605ce800a839)
* [数字6桁パスワードのハッシュ値の総当たり、PHPなら約0.25秒で終わるよ](http://z.tokumaru.org/2014/02/6php025.html)
* [数字6桁パスワードのハッシュ値の総当たり、Perlでも約0.25秒で終わるよ](http://shimx.hateblo.jp/entry/2014/02/10/190132)
* [数字６桁パスワードの総当たり JavaScript(node.js)編](http://qiita.com/seiketkm@github/items/7fddd2445b58d1b6dc4c)
* [「数字6桁パスワードのMD5ハッシュ値の総当たり」Scalaは1.70秒だった](http://qiita.com/nmatsui/items/dd70fd57d81bdd935f79)
* [「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタ](http://qiita.com/nmatsui/items/8a33941072668f3ac55b)

一覧に漏れがあった場合はお知らせください。追加させていただきます。

ここに、全く輝かない記録が付け加わります。

# 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にしてあります。
使ったコードは[ここ](https://github.com/soyiharu/md5_time_trial)に置いてあります。

###シングルスレッド版

```py: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()
```

###マルチスレッド版

```py: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回ずつ繰り返して時間を計ります。

```bash
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でした。([ソースコード](https://github.com/soyiharu/md5_time_trial/blob/master/MD5FindPassword_OpenMP.c))

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

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

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

```py:
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++かな。