MD5 - 日々量産

いまさらだけどC言語でMD5 アルゴリズムを実装してみた。

参考
The MD5 Message-Digest Algorithm
セキュリティ関連 RFC：IPA 独立行政法人情報処理推進機構
 IPAが公開しているRFCの日本語訳は英語ができない僕には参考になります。
MD5だけでなく、ほかにもたくさんあります。

md5.h

typedef unsigned int  MD5_UINT32; // Unsigned 32bit 
typedef unsigned char MD5_BYTE  ; // Unsigned 8bit =1byte

// MD5 構造体
typedef struct md5{
	MD5_UINT32 md5[4]; // Md5値
	MD5_BYTE   tmp[64];// 64byteのキャッシュ領域
	MD5_UINT32 length; // 対象のサイズ
	MD5_BYTE i; // キャッシュ位置の参照用の添え字
} MD5;

// MD5初期化関数
void md5_init(MD5 *p);
// MD5対象データ入力関数
void md5_add(MD5 *p, const MD5_BYTE *d, MD5_UINT32 length);
// MD5終了処理関数
void md5_finish(MD5 *p);

// 16進数文字列出力関数
const char * md5_hexstr(MD5 *p);
// ファイルからMD5(16進数文字列)を取得。失敗でNULL
const char * file2md5(const char *filename);


////////////////////////////////////////////////////


// MD5構造体初期化
void md5_init(MD5 *p){
	p->md5[0] = 0x67452301;
	p->md5[1] = 0xEFCDAB89;
	p->md5[2] = 0x98BADCFE;
	p->md5[3] = 0x10325476;
	p->length = 0;
	p->i      = 0;
}

// 現在のデータからMD5を求める計算を行う
// 計算後、p->iはリセットされる。
static void _md5_calc(MD5 *p){
	enum{
		// Tn = 4294967296.0 * abs(sin(n))
		T1  = 0xD76AA478, T2  = 0xE8C7B756, T3  = 0x242070DB, T4  = 0xC1BDCEEE,
		T5  = 0xF57C0FAF, T6  = 0x4787C62A, T7  = 0xA8304613, T8  = 0xFD469501,
		T9  = 0x698098D8, T10 = 0x8B44F7AF, T11 = 0xFFFF5BB1, T12 = 0x895CD7BE,
		T13 = 0x6B901122, T14 = 0xFD987193, T15 = 0xA679438E, T16 = 0x49B40821,
		
		T17 = 0xF61E2562, T18 = 0xC040B340, T19 = 0x265E5A51, T20 = 0xE9B6C7AA,
		T21 = 0xD62F105D, T22 = 0x02441453, T23 = 0xD8A1E681, T24 = 0xE7D3FBC8,
		T25 = 0x21E1CDE6, T26 = 0xC33707D6, T27 = 0xF4D50D87, T28 = 0x455A14ED,
		T29 = 0xA9E3E905, T30 = 0xFCEFA3F8, T31 = 0x676F02D9, T32 = 0x8D2A4C8A,
		
		T33 = 0xFFFA3942, T34 = 0x8771F681, T35 = 0x6D9D6122, T36 = 0xFDE5380C,
		T37 = 0xA4BEEA44, T38 = 0x4BDECFA9, T39 = 0xF6BB4B60, T40 = 0xBEBFBC70,
		T41 = 0x289B7EC6, T42 = 0xEAA127FA, T43 = 0xD4EF3085, T44 = 0x04881D05,
		T45 = 0xD9D4D039, T46 = 0xE6DB99E5, T47 = 0x1FA27CF8, T48 = 0xC4AC5665,
		
		T49 = 0xF4292244, T50 = 0x432AFF97, T51 = 0xAB9423A7, T52 = 0xFC93A039,
		T53 = 0x655B59C3, T54 = 0x8F0CCC92, T55 = 0xFFEFF47D, T56 = 0x85845DD1,
		T57 = 0x6FA87E4F, T58 = 0xFE2CE6E0, T59 = 0xA3014314, T60 = 0x4E0811A1,
		T61 = 0xF7537E82, T62 = 0xBD3AF235, T63 = 0x2AD7D2BB, T64 = 0xEB86D391
	};
	// 一時領域
	MD5_UINT32 x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15;
	// 現在の値をコピー
	MD5_UINT32 a = p->md5[0];
	MD5_UINT32 b = p->md5[1];
	MD5_UINT32 c = p->md5[2];
	MD5_UINT32 d = p->md5[3];
	
#define F(p,n) ( (p)[(n)+0] | (p)[(n)+1]<<8 | (p)[(n)+2]<<16 | (p)[(n)+3]<<24 )
	x0 = F(p->tmp,  0<<2);
	x1 = F(p->tmp,  1<<2);
	x2 = F(p->tmp,  2<<2);
	x3 = F(p->tmp,  3<<2);
	x4 = F(p->tmp,  4<<2);
	x5 = F(p->tmp,  5<<2);
	x6 = F(p->tmp,  6<<2);
	x7 = F(p->tmp,  7<<2);
	x8 = F(p->tmp,  8<<2);
	x9 = F(p->tmp,  9<<2);
	x10= F(p->tmp, 10<<2);
	x11= F(p->tmp, 11<<2);
	x12= F(p->tmp, 12<<2);
	x13= F(p->tmp, 13<<2);
	x14= F(p->tmp, 14<<2);
	x15= F(p->tmp, 15<<2);
#undef F
	
#define SHIFT(a,s) ((a)<<(s)|(a)>>(32-(s)))

#define FF(a,b,c,d,x,t,s) (a)+=(x)+(t)+(((b)&(c))|(~(b)&(d))); (a)=(b)+SHIFT(a,s)
	FF(a,b,c,d, x0,  T1 ,  7); FF(d,a,b,c, x1 , T2 , 12); FF(c,d,a,b, x2 , T3 , 17); FF(b,c,d,a, x3 , T4 , 22);
	FF(a,b,c,d, x4 , T5 ,  7); FF(d,a,b,c, x5 , T6 , 12); FF(c,d,a,b, x6 , T7 , 17); FF(b,c,d,a, x7 , T8 , 22);
	FF(a,b,c,d, x8 , T9 ,  7); FF(d,a,b,c, x9 , T10, 12); FF(c,d,a,b, x10, T11, 17); FF(b,c,d,a, x11, T12, 22);
	FF(a,b,c,d, x12, T13,  7); FF(d,a,b,c, x13, T14, 12); FF(c,d,a,b, x14, T15, 17); FF(b,c,d,a, x15, T16, 22);
#undef FF
	
#define GG(a,b,c,d,x,t,s) (a)+=(x)+(t)+(((b)&(d))|((c)&~(d))); (a)=(b)+SHIFT(a,s)
	GG(a,b,c,d, x1 , T17,  5); GG(d,a,b,c, x6 , T18,  9); GG(c,d,a,b, x11, T19, 14); GG(b,c,d,a, x0 , T20, 20);
	GG(a,b,c,d, x5 , T21,  5); GG(d,a,b,c, x10, T22,  9); GG(c,d,a,b, x15, T23, 14); GG(b,c,d,a, x4 , T24, 20);
	GG(a,b,c,d, x9 , T25,  5); GG(d,a,b,c, x14, T26,  9); GG(c,d,a,b, x3 , T27, 14); GG(b,c,d,a, x8 , T28, 20);
	GG(a,b,c,d, x13, T29,  5); GG(d,a,b,c, x2 , T30,  9); GG(c,d,a,b, x7 , T31, 14); GG(b,c,d,a, x12, T32, 20);
#undef GG
	
#define HH(a,b,c,d,x,t,s) (a)+=(x)+(t)+((b)^(c)^(d)); (a)=(b)+SHIFT(a,s)
	HH(a,b,c,d, x5 , T33,  4); HH(d,a,b,c, x8 , T34, 11); HH(c,d,a,b, x11, T35, 16); HH(b,c,d,a, x14, T36, 23);
	HH(a,b,c,d, x1 , T37,  4); HH(d,a,b,c, x4 , T38, 11); HH(c,d,a,b, x7 , T39, 16); HH(b,c,d,a, x10, T40, 23);
	HH(a,b,c,d, x13, T41,  4); HH(d,a,b,c, x0 , T42, 11); HH(c,d,a,b, x3 , T43, 16); HH(b,c,d,a, x6 , T44, 23);
	HH(a,b,c,d, x9 , T45,  4); HH(d,a,b,c, x12, T46, 11); HH(c,d,a,b, x15, T47, 16); HH(b,c,d,a, x2 , T48, 23);
#undef HH
	
#define II(a,b,c,d,x,t,s) (a)+=(x)+(t)+((c)^((b)|~(d))); (a)=(b)+SHIFT(a,s)
	II(a,b,c,d, x0 , T49,  6); II(d,a,b,c, x7 , T50, 10); II(c,d,a,b, x14, T51, 15); II(b,c,d,a, x5 , T52, 21);
	II(a,b,c,d, x12, T53,  6); II(d,a,b,c, x3 , T54, 10); II(c,d,a,b, x10, T55, 15); II(b,c,d,a, x1 , T56, 21);
	II(a,b,c,d, x8 , T57,  6); II(d,a,b,c, x15, T58, 10); II(c,d,a,b, x6 , T59, 15); II(b,c,d,a, x13, T60, 21);
	II(a,b,c,d, x4 , T61,  6); II(d,a,b,c, x11, T62, 10); II(c,d,a,b, x2 , T63, 15); II(b,c,d,a, x9 , T64, 21);
#undef FF

#undef SHIFT
	
	p->md5[0] += a;
	p->md5[1] += b;
	p->md5[2] += c;
	p->md5[3] += d;
	p->i = 0;
}


#ifdef _STRING_H_
// データをmd5に読み込ませる(use memcpy)
void md5_add(MD5 *p, const MD5_BYTE *d, MD5_UINT32 length){
	p->length += length;
	while(length){
		if(length <= 64-p->i){ 
			memcpy(p->tmp+p->i, d, length);
			p->i += length;
			length = 0;
			if(p->i == 64) _md5_calc(p);
		}else{
			memcpy(p->tmp+p->i, d, 64-p->i);
			length -= 64-p->i;
			d += 64-p->i;
			_md5_calc(p);
		}
	}
}
#else

// データをmd5に読み込ませる(no memcpy)
void md5_add(MD5 *p, const MD5_BYTE *d, MD5_UINT32 length){
	p->length += length;
	while(length--){
		p->tmp[p->i++] = *d++;
		if(p->i == 64) _md5_calc(p);
	}
}

#endif

// MD5の最後の処理
void md5_finish(MD5 *p){
	MD5_UINT32 n;
	p->tmp[p->i++] = 0x80; // 終端文字 0x80
	
	// 56byteより大きい場合、64byteまで0x00埋めをして、一度算出
	if(p->i > 56){
#ifdef _STRING_H_
		memset(&p->tmp[p->i], 0, 64-p->i);
#else
		while(p->i < 64) p->tmp[p->i++] = 0x00; // 1byteづつ
#endif		
		_md5_calc(p);
	}
	
	// 56byte未満なら56byte(448bit)目まで0で穴埋め
#ifdef _STRING_H_
	if(p->i < 56) memset(p->tmp+p->i, '\0', 56-p->i); p->i = 56;
#else
	while(p->i < 56) p->tmp[p->i++] = 0x00; // 1byteづつ
#endif

	// 最後の64bit(8byte)の処理
	// データ長(読み込んだデータサイズ(bit)を64bitで表現)
	// 上位32bitにデータ長の下位32bit,）
	n =  p->length << 3;
	p->tmp[p->i++] = n      & 0xFF;
	p->tmp[p->i++] =(n>> 8) & 0xFF;
	p->tmp[p->i++] =(n>>16) & 0xFF;
	p->tmp[p->i++] = n>>24  & 0xFF;
	
	// 下位32bitにデータ長の上位32bit
	n = p->length >> (32 - 3);
	p->tmp[p->i++] = n      & 0xFF;
	p->tmp[p->i++] =(n>> 8) & 0xFF;
	p->tmp[p->i++] =(n>>16) & 0xFF;
	p->tmp[p->i++] = n>>24  & 0xFF;
	
	// 最終計算
	_md5_calc(p);
}

/// 補助関数 /////////////////////////////////

// 16進数出力(TENUKI)
const char * md5_hexstr(MD5 *p){
	static char str[32+1];
	MD5_BYTE *byte = (MD5_BYTE *)p->md5;
	sprintf( str, 
		"%02X%02X%02X%02X" "%02X%02X%02X%02X"
		"%02X%02X%02X%02X" "%02X%02X%02X%02X",
		byte[0], byte[1], byte[2], byte[3],
		byte[4], byte[5], byte[6], byte[7],
		byte[8], byte[9], byte[10],byte[11],
		byte[12],byte[13],byte[14],byte[15]
	);
	return str;
}

// 指定ファイルのMD5を取得する。
const char * file2md5(const char *filename){
	#define BUFFER 4096
	MD5 md5;
	MD5_BYTE buffer[BUFFER];
	MD5_UINT32 length;
	FILE *fp = fopen(filename, "rb");
	if(fp == NULL){ return NULL; }
	md5_init(&md5);
	while(length = fread(buffer, 1, BUFFER, fp)) md5_add(&md5, buffer, length);
	md5_finish(&md5);
	fclose(fp);
	return md5_hexstr(&md5);
}

使い方

/* コマンドライン引数からファイル名を受け取り、そのMD5を表示する */
#include <stdio.h>
#include <string.h>

#include "md5.h"

int main(int argc, char **argv){
	if(argc >= 2){
		const char *p = file2md5(argv[1]);
		if(p != NULL){
			printf("%s", p);
		}
	}
	return 0;
}

メモ

2MBのメモリがあれば処理いけます！
4GBを超えるファイルの算出は不可能。
ビッグエンディアンな環境では動かない予感。
string.hにあるmemcpy等の関数を使うことで約25%ぐらい早くなったので、
string.hを読み込んだ場合とそうでない場合の処理を分けた。
RFCでの実装がbit単位で扱うような実装方法で、後半ちょっとよくわからなかったので、
byte単位でしか処理できない前提として実装したら、ちょっとマシになったと思う。

一番処理に時間がかかるのはmd5_addの部分で、入力データに対し64byte単位のコピーしかできない。
ファイルのMD5値を算出する関数は別でつくり、一時領域も大きくして、
freadするときは直接そっちに取り込んで、_md5_calcでその領域分を繰り返し処理させるほうが早くなりそう。

56byte目まで0x00で埋める処理は、memsetを使いたくない場合、UINT32が4byte長とした時、

while(p->i < 56) *(UINT32 *)&p->tmp[p->i] = 0x00, p->i+=4;

とすることでも、ちょっと早く処理できる。32bitマシンは4byte単位の操作が得意だから。
ちなみにキャストにかかるコストはコンパイラのみで実行時には響かない。
値を代入するのではなく0x00で埋めるだけなので、ビッグエンディアンもリトルエンディアンも関係ない。

4GBのファイルまでしか処理できないというのは、これはlengthが32bitを採用していることからなのだが、
32bit型にunsigned intと決め撃ちしていることから、型に対して知識が薄いわけです。
というのも、型はコンパイラによって違うことがあるから。いちいち覚えていないわけです。
符号なし64bit整数型はunsigned long longでいいんだろうか。コンパイラの対応も知りたい。
本来ならunsigned long intとするべきでしょう。RFCもunsigned long int 型を使ってますし。
まぁunsigned intで動いてるからいいや、といういい加減な気持ちがｒｙ

ほかの考え方としては、p->length += length;の後にでも、if(p->length < length) とでもして、
加算したはずなのに加えた値より小さくなった、とすれば、オーバーフローを検知して、あふれた分を1加算しておけば、
4GB*あふれた分+p->lengthとでもやって64bitを使わずとも表現できそうですが、
これは加算が正常に行われた上でのオーバーフローを検知する必要があります。
たとえば1byteの加算、0xFF + 0xFFを行った結果、0x1FEとなりますが、1byteで表現できる範囲を超えているので、
1byteの表現に収まるようにした結果、0xFEとなることが保障されていれば、この方法でいけますが、
どのコンパイラどの環境でも同様に動作するのか、までは突き止められなかったので、やってません。
またそんなことするぐらいなら、lengthに32bitではなく64bitを持たせることを考えるほうが、
条件分岐が1個減るし、加算処理も1個減るしで数倍簡単ですよねーっていう。