md4.pyを作る
id:Voluntasに「リハビリ用の緩いボールを投げて」って言ったらmd4を作れと言われたので作る。
RFC 1320 - The MD4 Message-Digest Algorithm日本語
まずもってPythonで32ビットな整数を扱うコードを書くとうっかりlongへの昇格を起こしてつまずきそうな香りがぷんぷんとするので、まずは予防線を張ってみる。
def assert_type_of_return_is(typ): def _wrap(func): def _wrapped(*args, **kw): ret = func(*args, **kw) if not isinstance(ret, typ): raise AssertionError return ret return _wrapped return _wrap @assert_type_of_return_is(int) def add(x, y): return x + y print add(1, 2) print 2 ** 31 print add(2 ** 31, 2 ** 31)
3つめのprintでオーバーフローが起きてlongへ昇格されるので、期待されていた「返り値はint」という契約を満たせなくなるのでAssertionErrorを投げて死ぬ。
HEAD_BIT = int((1 << 31) - 1) def split(value, mask): x = value & mask y = value & ~mask return x, y @assert_type_of_return_is(int) def add(x, y): h1, t1 = split(x, HEAD_BIT) h2, t2 = split(y, HEAD_BIT) return (t1 + t2) ^ h1 ^ h2 @assert_type_of_return_is(int) def rot(x, s): mask = int((1 << (32 - s)) - 1) t, h = split(x, mask) return (t << s) + (h >> (32 - s))
まぁ、longにはみ出してからintに切り落としてもよかったんだけどちょっとしたこだわり。
A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210 # F(X,Y,Z) = XY v not(X) Z # G(X,Y,Z) = XY v XZ v YZ # H(X,Y,Z) = X xor Y xor Z def F(x, y, z): return x & y | ~x & z def G(x, y, z): return x & y | x & z | y & z def H(x, y, z): return x ^ y ^ z
ABCDのバイトオーダーが逆じゃないかという気がするけど、これは後でテストコードがfailしたら直す。
うは、これって実はPythonで書くよりCで書く方が楽じゃないか。
/* 以下の演算を、[abcd k s] で表す：
a = (a + F(b,c,d) + X[k]) <<< s. */
/* 次の16の処理を実行する */
[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
破壊的代入をくくりだすとか…うーん、ワードバッファは辞書にするか。
wb = dict( A = 0x01234567, B = 0x89abcdef, C = 0xfedcba98, D = 0x76543210, )
実装終わった。
def digest(data): buf = padding(data) for iblock in range(len(buf) / 16): xs = buf[iblock * 16:iblock * 16 + 16] old_wb = copy(wb) def round1(abcd, k, s): """a = (a + F(b,c,d) + X[k]) <<< s.""" dst = a a, b, c, d = (wb[k] for k in abcd) wb[dst] = rot(add(add(a, F(b, c, d), xs[k])), s) map(round1, [ ("ABCD", 0, 3), ("DABC", 1, 7), ("CDAB", 2, 11), ("BCDA", 3, 19), ("ABCD", 4, 3), ("DABC", 5, 7), ("CDAB", 6, 11), ("BCDA", 7, 19), ("ABCD", 8, 3), ("DABC", 9, 7), ("CDAB", 10, 11), ("BCDA", 11, 19), ("ABCD", 12, 3), ("DABC", 13, 7), ("CDAB", 14, 11), ("BCDA", 15, 19), ]) def round2(abcd, k, s): """a = (a + G(b,c,d) + X[k] + 5A827999) <<< s.""" dst = a a, b, c, d = (wb[k] for k in abcd) wb[dst] = rot(add(add(add(a, G(b, c, d)), xs[k]), 0x5A827999), s) map(round2, [ ("ABCD", 0, 3), ("DABC", 4, 5), ("CDAB", 8, 9), ("BCDA", 12, 13), ("ABCD", 1, 3), ("DABC", 5, 5), ("CDAB", 9, 9), ("BCDA", 13, 13), ("ABCD", 2, 3), ("DABC", 6, 5), ("CDAB", 10, 9), ("BCDA", 14, 13), ("ABCD", 3, 3), ("DABC", 7, 5), ("CDAB", 11, 9), ("BCDA", 15, 13), ]) def round3(abcd, k, s): """a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s.""" dst = a a, b, c, d = (wb[k] for k in abcd) wb[dst] = rot(add(add(add(a, H(b, c, d)), xs[k]), 0x6ED9EBA1), s) map(round3, [ ("ABCD", 0, 3), ("DABC", 8, 9), ("CDAB", 4, 11), ("BCDA", 12, 15), ("ABCD", 2, 3), ("DABC", 10, 9), ("CDAB", 6, 11), ("BCDA", 14, 15), ("ABCD", 1, 3), ("DABC", 9, 9), ("CDAB", 5, 11), ("BCDA", 13, 15), ("ABCD", 3, 3), ("DABC", 11, 9), ("CDAB", 7, 11), ("BCDA", 15, 15), ]) for k in "ABCD": wb[k] = add(wb[k], old_wb[k]) print [hex(wb[k]) for k in "ABCD"]
ほぼ疑似コード通りの実装だ。そして案の定結果が間違っているのでここから楽しいデバッグの時間です（ぉ
とりあえず
def padding(s):
"add padding bits and length"
buf = [ord(c) for x in s]
buf.append(HEAD_BIT)
- while len(buf) % 16 == 15:
+ while len(buf) % 16 != 15:
buf.append(0)
- def round1(abcd, k, s): + def round1((abcd, k, s)): - dst = a + dst = abcd[0]
他2カ所
あー、しまった。unsignedじゃないから最上位ビットが立っているときには負の値にしないとPythonのintの範囲には収まらないぞ。
めんどうになったのでやめた(ぇ
id:VoluntasにPyUnsignedIntクラスを作るしかないかな、って言ったら
http://www.geocities.com/rozmanov/python/u32.html
これを紹介された。ひどいw
