PythonでMD5を車輪の再開発してみた

やっと出来た。
なんか合わない…と思ったらunsigned intの最大値を超えてビット演算してた。
　

ソース

#!/usr/local/bin/python
# set encoding=utf-8

import math


# define

def F(x, y, z):
	return ((x & y) | (~x & z))

def G(x, y, z):
	return ((x & z) | (y & ~z))

def H(x, y, z):
	return (x ^ y ^ z)

def I(x, y, z):
	return (y ^ (x | ~z))

def ROTATE_LEFT(x, n):
	x &= 0xffffffff
	return ((x << n) | (x >> (32-n)))

def FF(a, b, c, d, x, s, ac):
	a += F(b, c, d) + x + ac
	a = ROTATE_LEFT(a, s)
	a += b
	return a & 0xffffffff

def GG(a, b, c, d, x, s, ac):
	a += G(b, c, d) + x + ac
	a = ROTATE_LEFT(a, s)
	a += b
	return a & 0xffffffff

def HH(a, b, c, d, x, s, ac):
	a += H(b, c, d) + x + ac
	a = ROTATE_LEFT(a, s)
	a += b
	return a & 0xffffffff

def II(a, b, c, d, x, s, ac):
	a += I(b, c, d) + x + ac
	a = ROTATE_LEFT(a, s)
	a += b
	return a & 0xffffffff


# T

def makeT():
	T = []
	for i in range(1, 65):
		val = 0x100000000 * math.fabs(math.sin(i))
		T.append(int(val))
	return T


# md5

def md5_hex(s):
	h = md5_core(s)
	return digest_hex(h)

def md5_core(s):
	# パディングビット付加
	bit_len = len(s) * 8
	s += chr(0x80)

	i = len(s) % 64
	if 56<i:
		i -= 64

	for j in range(i, 56):
		s += chr(0)

	# 長さ付加
	for j in range(0, 8):
		s += chr((bit_len >> (j*8)) & 0xff)

	# バッファの初期化
	a = 0x67452301
	b = 0xefcdab89
	c = 0x98badcfe
	d = 0x10325476

	# ワードブロックごとのメッセージ処理
	while 0<len(s):
		block = s[0:64]
		s = s[64:]

		x = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

		for i in range(0, 16):
			for j in range(0, 4):
				x[i] += (ord(block[i*4+j]) << (j*8))

		aa = a
		bb = b
		cc = c
		dd = d

		# FF

		a = FF(a, b, c, d, x[ 0],  7, T[ 0])
		d = FF(d, a, b, c, x[ 1], 12, T[ 1])
		c = FF(c, d, a, b, x[ 2], 17, T[ 2])
		b = FF(b, c, d, a, x[ 3], 22, T[ 3])

		a = FF(a, b, c, d, x[ 4],  7, T[ 4])
		d = FF(d, a, b, c, x[ 5], 12, T[ 5])
		c = FF(c, d, a, b, x[ 6], 17, T[ 6])
		b = FF(b, c, d, a, x[ 7], 22, T[ 7])

		a = FF(a, b, c, d, x[ 8],  7, T[ 8])
		d = FF(d, a, b, c, x[ 9], 12, T[ 9])
		c = FF(c, d, a, b, x[10], 17, T[10])
		b = FF(b, c, d, a, x[11], 22, T[11])

		a = FF(a, b, c, d, x[12],  7, T[12])
		d = FF(d, a, b, c, x[13], 12, T[13])
		c = FF(c, d, a, b, x[14], 17, T[14])
		b = FF(b, c, d, a, x[15], 22, T[15])

		# GG

		a = GG(a, b, c, d, x[ 1],  5, T[16])
		d = GG(d, a, b, c, x[ 6],  9, T[17])
		c = GG(c, d, a, b, x[11], 14, T[18])
		b = GG(b, c, d, a, x[ 0], 20, T[19])

		a = GG(a, b, c, d, x[ 5],  5, T[20])
		d = GG(d, a, b, c, x[10],  9, T[21])
		c = GG(c, d, a, b, x[15], 14, T[22])
		b = GG(b, c, d, a, x[ 4], 20, T[23])

		a = GG(a, b, c, d, x[ 9],  5, T[24])
		d = GG(d, a, b, c, x[14],  9, T[25])
		c = GG(c, d, a, b, x[ 3], 14, T[26])
		b = GG(b, c, d, a, x[ 8], 20, T[27])

		a = GG(a, b, c, d, x[13],  5, T[28])
		d = GG(d, a, b, c, x[ 2],  9, T[29])
		c = GG(c, d, a, b, x[ 7], 14, T[30])
		b = GG(b, c, d, a, x[12], 20, T[31])

		# HH

		a = HH(a, b, c, d, x[ 5],  4, T[32])
		d = HH(d, a, b, c, x[ 8], 11, T[33])
		c = HH(c, d, a, b, x[11], 16, T[34])
		b = HH(b, c, d, a, x[14], 23, T[35])

		a = HH(a, b, c, d, x[ 1],  4, T[36])
		d = HH(d, a, b, c, x[ 4], 11, T[37])
		c = HH(c, d, a, b, x[ 7], 16, T[38])
		b = HH(b, c, d, a, x[10], 23, T[39])

		a = HH(a, b, c, d, x[13],  4, T[40])
		d = HH(d, a, b, c, x[ 0], 11, T[41])
		c = HH(c, d, a, b, x[ 3], 16, T[42])
		b = HH(b, c, d, a, x[ 6], 23, T[43])

		a = HH(a, b, c, d, x[ 9],  4, T[44])
		d = HH(d, a, b, c, x[12], 11, T[45])
		c = HH(c, d, a, b, x[15], 16, T[46])
		b = HH(b, c, d, a, x[ 2], 23, T[47])

		# II

		a = II(a, b, c, d, x[ 0],  6, T[48])
		d = II(d, a, b, c, x[ 7], 10, T[49])
		c = II(c, d, a, b, x[14], 15, T[50])
		b = II(b, c, d, a, x[ 5], 21, T[51])

		a = II(a, b, c, d, x[12],  6, T[52])
		d = II(d, a, b, c, x[ 3], 10, T[53])
		c = II(c, d, a, b, x[10], 15, T[54])
		b = II(b, c, d, a, x[ 1], 21, T[55])

		a = II(a, b, c, d, x[ 8],  6, T[56])
		d = II(d, a, b, c, x[15], 10, T[57])
		c = II(c, d, a, b, x[ 6], 15, T[58])
		b = II(b, c, d, a, x[13], 21, T[59])

		a = II(a, b, c, d, x[ 4],  6, T[60])
		d = II(d, a, b, c, x[11], 10, T[61])
		c = II(c, d, a, b, x[ 2], 15, T[62])
		b = II(b, c, d, a, x[ 9], 21, T[63])

		a += aa
		b += bb
		c += cc
		d += dd

	return [a, b, c, d]


def digest_hex(h):
	md5 = ''
	for v in h:
		for i in range(0, 4):
			md5 += '%02x' % ((v >> (i*8)) & 0xff)
	return md5



T = makeT()

s = 'あいうえお'
print md5_hex(s)

実行結果

$ python md5.py 
86deb27a32903da70a7b2348fcf36bc3

参考URL

MD5の計算方法 - BK class
http://www14.ocn.ne.jp/~bkclass/doc_md5.html
　
[Studying HTTP] MD5
http://www.studyinghttp.net/md5
　
暗号化アルゴリズムを実感しよう
http://www.geocities.co.jp/SiliconValley-Oakland/8878/lab17/lab17.html
　
as3crypto - Project Hosting on Google Code
http://code.google.com/p/as3crypto/