[ MD5 メッセージダイジェストアルゴリズム ] 動作確認は Linux + gcc で行っています。MD5に関する詳細は RFC1321(MD5 message digest Algorythm) を参照してください。基本的には RFC にあるプ ログラムを元に解読していきますが、RFC にあるプログラムをそのまま使用す ると2003年現在のコンパイラでは怒られる可能性がありますので（笑）プログ ラムには多少の変更が加えられています。 MD5概要を説明しますが、詳細は RFC を見て下さい。 例えば1544bitsの長さの文字列(平文)を入力する。 +-----------+-----------+-----------+-----------+ | 512bits | 512bits | 512bits | 512bits | +-----------+-----------+-----------+-----------+ <-----入力した文字列(1544bits)-------> < Pad > < n > 暗号化処理は512bitsずつ行われます。最後の(64bytes)512bitsを拡大します。 +-----------------------------------------------+ | 64bytes(512bits) | +-----------------------------------------------+ 1bytes--> <----Padding(55bytes)-----> <-n(8bytes)-> 文字列が512bitsの倍数になるようにPaddingが追加され最後の8bytesが入力し た文字列の長さつまり1544を8bytes(64bits)で表した数値となります。もし文 字列の長さの数値が64bitsで表せない時は下位64bitsがその対象となります。 こういう形で512bitsの倍数として、512bitsずつ暗号化処理していきます。暗 号化処理は具体的に言うと MD5Transform関数 です。この関数の処理は言葉で 説明することが困難なものなので、ソースを見てください。 ソースは以下です。 http://ruffnex.oc.to/kenji/src/md5.c これからはこれを元に話を進めます。 [kenji@localhost md5]$ gcc -Wall md5.c -o md5 [kenji@localhost md5]$ ./md5 test ("test") = 098f6bcd4621d373cade4e832627b4f6 [kenji@localhost md5]$ 暗号の照合は↓で行いました。 http://www.cc.rim.or.jp/~sanaki/text/free/freejs17.htm /*------------------------------------------------------- RSA Data Security, Inc. MD5 Message-Digest Algorithm -------------------------------------------------------*/ #include typedef unsigned char *POINTER; /* 総括的なポインタ型 */ typedef unsigned long int UINT4; /* 4bytes(32bits)ワード */ typedef struct{ UINT4 state[4]; /* 最終的に出力すべきデータ(ABCD) */ UINT4 count[2]; /* 入力された文字列の長さ(ビット数)が入る */ unsigned char buffer[64]; /* 512bits(64bytes)に区切られた文字列 */ } MD5_CTX; state[4]の 32bits * 4 = 128bits(16bytes) に最終的に出力すべき暗号文が 入ります。MD5は不可逆暗号なのでこの暗号文からはどうやったって平文を求 めることはできないようです。countには入力された文字列(平文)の長さ(単位 はbit)が入ります。bufferには64bytesに区切られた平文が入ります。 /* MD5Transform ルーチンのための定数 */ #define S11 7 #define S12 12 #define S13 17 #define S14 22 ...(省略)... #define II(a, b, c, d, x, s, ac) { \ (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \ (a) = ROTATE_LEFT ((a), (s)); \ (a) += (b); \ } ここにはMD5Transformのためのさまざまな定義が入りますが、もはや数学者の ためのコードといっても過言ではないほど意味不明なので説明できません。ど うやら暗号文からは平文が分からないようにありとあらゆる数学的アルゴリズ ムが組み込まれてるのでしょうけどこういうことは専門家に任せておきましょ う。（笑）もちろんやってることは分かりませんがソースの意味は分かるので 興味のある方は頑張って下さい。 /* MD5_CTX構造体の context を初期化する関数 */ void MD5Init(MD5_CTX *context) { context->count[0] = 0; context->count[1] = 0; context->state[0] = 0x67452301; context->state[1] = 0xefcdab89; context->state[2] = 0x98badcfe; context->state[3] = 0x10325476; } これはcontext構造体の初期化ですね。stateにわけの分からない初期値が入っ てますが、おそらくとてつもない数学的考察の元に考えられた4つの数字なの でしょう。私が関わることでは無いです。（笑） /* UINT4(unsigned long)型を unsigned char型に 変換する */ void Encode(unsigned char *output, UINT4 *input, unsigned int len) { unsigned int i, j; for (i=0, j=0; j < len; i++, j+=4) { output[j] = (unsigned char)( input[i] & 0xff); output[j+1] = (unsigned char)((input[i] >> 8 ) & 0xff); output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); } } /* unsigned char型を UINT4(unsigned long)型に 変換する */ void Decode (UINT4 *output, unsigned char *input, unsigned int len) { unsigned int i, j; for (i = 0, j = 0; j < len; i++, j += 4) output[i] = ( (UINT4)input[j] ) | (((UINT4)input[j+1]) << 8 ) | (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); } エンコードとデコードの処理です。見ればわかると思われますので割愛します。 /* digestを16進で出力 */ void MDPrint(unsigned char *digest) { unsigned int i; for (i=0; i < 16; i++) printf("%02x", digest[i]); } 文字列を16進で出力します。暗号化された文字列を出力する時のみに使用しま す。 /* 暗号化オペレーション(実質的な暗号化のメイン処理) */ void MD5Transform(UINT4 *state, unsigned char *block) { UINT4 a = state[0], b = state[1], c = state[2], d = state[3]; UINT4 x[16]; Decode(x, block, 64); /* ラウンド 1 */ FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */ FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */ ...(省略)... II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */ II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */ state[0] += a; state[1] += b; state[2] += c; state[3] += d; /* xの情報をクリア */ memset((POINTER)x, 0, sizeof(x)); } 暗号化は64bytes(512bits)単位で行われていきます。まずblockからもらった データをDecodeによりUINT4型に変更してa,b,c,d(つまりはstateであり最終的 に出力する文字列)に影響させます。つまり64bytesの文字列はあらゆる数学的 処理の結果state[0]〜state[3]に反映されるということです。 /*--------------------------------------------------------------------- inputからinputLenだけをcontext->bufferに格納する。 同時にcontext->countも更新する。 ---------------------------------------------------------------------*/ void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputLen) { この関数は入力された文字列が最後の64bytes(512bits)以下の長さになるまで 処理を続けます。例えば 602bytes の文字列が渡された場合はそれを 64bytes づつ処理していきます(つまりMD5Transformに渡していきます)そして最後に 602 % 64 =26bytes が残った時点でこの関数は終了します。のこりの 26bytes の暗号化処理はMD5Finalに任せます。 unsigned int i, index, partLen; /*--------------------------------------------------------------------- context->count[0]を1/8倍して(byteに変換して) 64 でわったあまりをindexへ 意味的には index = (unsigned int)((context->count[0] / 8) % 64); と同じ ---------------------------------------------------------------------*/ index = (unsigned int)((context->count[0] >> 3) & 0x3F); 一番最初にこの行が実行されたときは index = 0 となる。 /*--------------------------------------------------------------------- inputLenを8倍して(bitに変換して)それをcontext->count[0]に加算 意味的には if((context->count[0] += ((UINT4)inputLen * 8)) < ((UINT4)inputLen * 8)) と同じ ---------------------------------------------------------------------*/ if((context->count[0] += ((UINT4)inputLen << 3)) < ((UINT4)inputLen << 3)){ context->count[1]++; } さて、ここであれ？と感じませんか？このifの中の処理が実行される ことはありえないでしょう。例え context->count[0] = 0 であり全 体の式がイコールとなったとしても(inputLen << 3)は同値でありif 文の処理は実行されません。どういうことだ？ 実はこれは桁溢れを表しています。context->count[0]はUINT4型です のでunsigned long型です。つまり32bits(4bytes)で表せる値は 0 〜 4294967295 ですね。でももしこれ以上の長さ(単位はbit)の文 字列が入力されたらどうするんだ？context->count[0]は4294967295 を超えたらまた 0 から始まることになります。よって 32bits を超 えた場合にcontext->count[1]を加算して(count[1]は次の桁を表して います)処理を進めさせるということです。 context->count[1] += ((UINT4)inputLen >> 29); 29ってどこからきたんだーとおもわれますが、これは(32-3)と考えら れます。inputLenはbyte単位なのでこれをbitにするためには8倍(つ まり << 3 )としなければならない。その分の3を差し引いて >> 29と するとつまりは32bitsより大きな桁をbit数で算出することができる ということです。 partLen = 64 - index; partLenには64bytesの倍数になるためにはあと何バイト必要かという 値が入ります。 /*--------------------------------------------------------------------- inputLenはinput文字列の長さ。partLenは(現在確認済みの)暗号化すべき文字列 のbyteの長さ(context->count[0] / 8)を64で割った余り(index)を 64から減算した値。つまりcontext->countに、あとpartLenだけ加算すれば context->countは64bytes(512bits)の倍数になるということ。 もしinputがcontext->bufferの残りを埋めることができるなら 埋めた後にMD5Transformを実行する。 ---------------------------------------------------------------------*/ if(inputLen >= partLen){ memcpy((POINTER)&context->buffer[index], (POINTER)input, partLen); MD5Transform(context->state, context->buffer); for(i=partLen; i + 63 < inputLen; i+=64) MD5Transform(context->state, &input[i]); index = 0; }else{ i = 0; } 上の例で示すならば 602 >= (64-0) となるのでif内の処理が実行さ れる。最終的にcontext->stateに還元されることは上記で説明した。 partLenだけbufferに格納してMD5Transformを実行する。それでも inputLenはまだまだ長いのでどんどん64bytesに区切られていき MD5Transformに入れられていき最終的に 26 bytes (つまり64bytes未 満)になった時点で処理が終了する。 memcpy((POINTER)&context->buffer[index], (POINTER)&input[i], inputLen-i); i の中には暗号化処理された文字列の長さが入ってるからそれを inputLenから減算してやればまた暗号化処理していない文字列が context->bufferに格納されることになる。 } /*--------------------------------------------------------------------- ここに処理がくる時には処理されてない残りの文字列が 64bytes以下であるということ。 ---------------------------------------------------------------------*/ void MD5Final(unsigned char *digest, MD5_CTX *context) { unsigned char bits[8]; unsigned int index, padLen; Encode(bits, context->count, 8); この時点で平文の文字列の長さがcontext->countに入ってるはずなの でそれをエンコードして bits にいれる。このbitsを最終的な64bits の最後に追加する。 /*--------------------------------------------------------------------- 処理されていない残りの文字列が 56 以上かどうか？ 56以上ならさらに64bytes増加させそのぶんにPaddingをいれる。 56未満なら56になるまでPaddingをいれる。 意味的には index = (unsigned int)((context->count[0] / 8) % 64); と同じ ---------------------------------------------------------------------*/ index = (unsigned int)((context->count[0] >> 3) & 0x3f); padLen = (index < 56) ? (56 - index) : ((64 + 56) - index); MD5Update(context, PADDING, padLen); パディングの追加を行っている。これを追加したことにより MD5Updateの中で context->buffer が一杯になるとさらなる暗号化の 処理(MD5Transform)を行ってくれる。例えばindexが57(56以上)だっ たなら120 - 57 = 63bytes が PADDINGからcontext->bufferに追加さ れることになり、bufferにはすでに 57bytes が入ってるので buffer が 64bytesを超えることになりその64bytesで暗号化処理を行い、あ たらしくbufferには 63 - (64-57) = 56bytes が入れられることにな る。つまりは64bytesまで8bytes(64bits)となる。 /*--------------------------------------------------------------------- context->buffer最後の8bytesに bits(つまり文字列の長さ[context->count]を付加する) ---------------------------------------------------------------------*/ MD5Update(context, bits, 8); そして、ここで「平文の長さ」を最後の8bytesに入れて それを暗号化処理(MD5Transform)に渡して、最終的な暗号化処理が終 了する。 /*--------------------------------------------------------------------- 最終的にほしいメッセージダイジェスト(暗号化された文字列)が context->stateに入ってるので もらって来て unsigned charに変換する。 ---------------------------------------------------------------------*/ Encode(digest, context->state, 16); 暗号化された文字列をdigestに格納して終了となる。 /* contextをゼロクリアして終了！ */ memset((POINTER)context, 0, sizeof(*context)); } void MDString(char *string) { MD5_CTX context; unsigned char digest[16]; UINT4 len = strlen(string); MD5Init(&context); 初期化する。 MD5Update(&context, string, len); 64bytes未満の長さになるまで暗号化をくり返す。 MD5Final(digest, &context); 最後の64bytesの暗号化をして(もしかしたら最後と最後から２番目の 64bytesの文字列の暗号化かもしれない。)終了。 printf("(\"%s\") = ", string); MDPrint(digest); printf("\n"); 出力！ } int main(int argc, char *argv[]) { MDString(argv[1]); return 0; } 参考資料 RFC1321(MD5 message digest Algorythm) MD5(Message Digest 5) The　Shadow　Penguin　Documents No.16 http://www.shadowpenguin.org/sc_documents/spsdocument16.html End. written by kenji aiko 2003/11/07 Copyright (C) 2003 kenji aiko All Rights Reserved