MD5の計算方法

MD5は認証やデジタル署名などに使用されるハッシュ関数です。 そのアルゴリズムが規定されているRFC1321の補足説明です。

• 注意事項
• 概略
• アルゴリズム
• サンプルプログラム
• 雑記
• 参考資料

注意事項

以降の説明は次の条件で行っています。

• 1バイトは8ビットとする。
• 1ワードは4バイト(32ビット)とする。
• 理解しやすくするためバイト単位で説明をする。
• C言語を対象にして説明をする。
• longは4バイトの整数の変数とする。
• unsigned longは4バイトの符号なし整数の変数とする。

概略

アルゴリズムは5つのステップでなりたっています。

ステップ1. メッセージの拡張

算出対象のメッセージを切りのいい長さまで拡張します。

ステップ2. メッセージに長さ付加

ステップ1の結果に元のメッセージの長さ（ビット長）を付加します。

ステップ3. バッファの初期化

計算に使用するバッファ（算出値の保持変数A, B, C, D）を初期化します。

ステップ4. 算出処理

• 補助関数を定義します。
• 計算用数値配列を準備します。
• MD5の値を算出します。
  
  • メッセージを64バイト毎のブロックに分割します。
  • 各ブロック毎に64回の演算を行います。

ステップ5. 出力

バッファの値を結果として出力します。

[拡大]

アルゴリズム

MD5は以下の方法で算出します。

ステップ1. メッセージの拡張

算出対象のメッセージを切りのいい長さまで拡張します。

【引用】
メッセージは、「パディングされ」(拡張され)て、その長さ(ビット)は、512 を法としたときの 448 とされる。 すなわち、メッセージは拡張されることにより、512 の倍数のビット長に対して、ちょうど 64 ビットだけ足りない長さにされる。 このパディングは常に実行される。 メッセージの長さが、既に 512 を法としたときの 448 に一致していても実行される。

パディングは、次のように実行される。“1”の値を持つ 1つのビットをメッセージに付加し、次に“0”の値を持つビットを付加して、パディングされたメッセージのビットの長さが、512 を法としたときの 448 になるようにする。 最小で 1 ビッ ト、最大で 512 ビットが付加される。

メッセージを拡張しそのバイト数を64で割った余りが56になるようにします。 拡張は元のメッセージの末尾に0x80、それ以降に0x00のデータを付加して行われます。 例えば“abc”というメッセージの場合には、最初に0x80の1バイト、次に0x00が52バイト付加されます。

[拡大]

拡張は必ず行われます。これは元のメッセージ長を64で割った際のあまりがちょうど56であった場合でも拡張されるということです。メッセージ長が56バイトならば120バイトに、120バイトなら184バイトに拡張されます。

最小で1バイト(0x80の1バイト)、最大で64バイトのデータが付加されて拡張されます。

ステップ2. メッセージに長さ付加

ステップ1の結果に元のメッセージの長さ（ビット長）を付加します。

【引用】
b (すなわちパディングビットが付加される前のメッセージの長さ)の 64 ビットにおける表記が、前のステップの結果に付加される。 可能性の低いイベントであるが、b が 2^64 よりも大きい場合、b の下位 64 ビットのみを使用する。 (これらのビットは、32ビットワード 2 つとして付加される。慣例に従い、下位ワードが最初に付加される。)

ここで、(ビットとbの長さをパディングした後に)結果的に生成されるメッセージは、512 ビットの倍数の長さとなる。 同様に、このメッセージは 16(32ビット) ワードの倍数の長さとなる。 ここで、M[0 ... N-1] は、結果として生成されるメッセージを表すものとする。N は、16 の倍数である。

元のメッセージのビット長を8バイトの整数値にして、その下位バイトから順にステップ1で拡張したメッセージの末尾へ付加します。その結果としてメッセージのバイト数は64の倍数となります。

[拡大]

例えば“abc”というメッセージの場合には、そのビット長24をステップ1の結果に付加します。

[拡大]

※ メッセージの拡張手順をまとめると以下のようになります。

1. 1バイトのデータ(0x80)を足す。(必須)
2. メッセージのバイト数を64で割った余りが56となるように0x00を足す。
3. 元のメッセージのビット数を8バイトの整数値にしてその下位バイトから順に足す。(必須)

ステップ3. バッファの初期化

計算に使用するバッファ（算出値の保持変数A, B, C, D）を初期化します。

【引用】
4 つのワードバッファ (A、B、C、D) が、メッセージダイジェストを計算するのに使用される。 ここで、A、B、C、D は、32 ビットのレジスタである。 これらのレジスタは、16進で表される以下の値で、下位バイトから順番に初期化される。

    word A: 01 23 45 67
    word B: 89 ab cd ef
    word C: fe dc ba 98
    word D: 76 54 32 10

MD5の値を格納する為に4バイトの変数を4つ確保し、それを指定された値で初期化します。

unsigned long int A = 0x67452301;
unsigned long int B = 0xefcdab89;
unsigned long int C = 0x98badcfe;
unsigned long int D = 0x10325476;

ステップ4. 算出処理

MD5の値を算出します。

補助関数の定義

【引用】
最初に、32 ビットワード 3つを入力とし、32 ビットワード 1つを出力する 4つの補助関数を定義する。

    F(X,Y,Z) = XY v not(X) Z
    G(X,Y,Z) = XZ v Y not(Z)
    H(X,Y,Z) = X xor Y xor Z
    I(X,Y,Z) = Y xor (X v not(Z))

    ・XY は、ビットに関する X と Yの AND を意味する。
    ・X v Yは、ビットに関する X と Y の OR を意味する。
    ・not(X) は、X に関する補数を意味する。
    ・X xor Yは、ビットに関する X と Y の XOR を意味する。

まず、算出に使用するF, G, H, Iの4つの補助関数を定義します。 これは実際のコーディングを見た方が理解しやすいです。

#define F(x,y,z)  (((x) & (y)) | ((~x) & (z)))  /* 第1段階の演算で使用 */
#define G(x,y,z)  (((x) & (z)) | ((y) & (~z)))  /* 第2段階の演算で使用 */
#define H(x,y,z)  ((x) ^ (y) ^ (z))             /* 第3段階の演算で使用 */
#define I(x,y,z)  ((y) ^ ((x) | (~z)))          /* 第4段階の演算で使用 */

計算用数値配列の準備

【引用】
このステップでは、64 の要素を持つテーブル T[1 ... 64] を使用する。 これは、sin 関数から生成されたものである。 T[i] は、テーブルの第 i 要素を意味し、 4294967296 と abs(sin(i)) の積の整数部に等しい。 ただし、i の単位は、ラジアンである。 テーブルの各要素は、補遺で与えられている。

次に、要素数64の配列T[1..64]を準備します。 その第i番目の要素は、4294967296 と abs(sin(i)) の積の整数部で初期化します。 ただし、実際には高速化のために都度に計算するのではなく、計算済みの値を定数として使用します。

unsigned long int T[64+1];
int i;

for (i = 1; i <= 64; i++) {
    T[i] = 4294967296 * fabs(sin(i));    /* fabsを使用 */
}

算出処理

【引用】
 /* それぞれの 16 ワードブロックを処理する */
 For i = 0 to N/16-1 do

     /* ブロック i を X にコピーする */
     For j = 0 to 15 do
         Set X[j] to M[i*16+j].
     end  /* j のループの終了 */

     /* A を AA として、B を BB として、C を CC として、 */
     /* D を DD として保存する                           */
     AA = A
     BB = B
     CC = C
     DD = D

     /* Round 1.                                         */
     /* 以下の演算を、[abcd k s i] で表す：              */
     /*     a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s) */
     /* 次の16の処理を実行する                           */
     [ABCD  0 7  1] [DABC  1 12  2] [CDAB  2 17  3] [BCDA  3 22  4]
     [ABCD  4 7  5] [DABC  5 12  6] [CDAB  6 17  7] [BCDA  7 22  8]
     [ABCD  8 7  9] [DABC  9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
     [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

     /* Round 2.                                         */
     /* 以下の演算を、[abcd k s i] で表す：              */
     /*     a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s) */
     /* 次の16の処理を実行する                           */
     [ABCD  1 5 17] [DABC  6 9 18] [CDAB 11 14 19] [BCDA  0 20 20]
     [ABCD  5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA  4 20 24]
     [ABCD  9 5 25] [DABC 14 9 26] [CDAB  3 14 27] [BCDA  8 20 28]
     [ABCD 13 5 29] [DABC  2 9 30] [CDAB  7 14 31] [BCDA 12 20 32]

     /* Round 3.                                         */
     /* 以下の演算を、[abcd k s i] で表す：              */
     /*     a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s) */
     /* 次の16の処理を実行する                           */
     [ABCD  5 4 33] [DABC  8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
     [ABCD  1 4 37] [DABC  4 11 38] [CDAB  7 16 39] [BCDA 10 23 40]
     [ABCD 13 4 41] [DABC  0 11 42] [CDAB  3 16 43] [BCDA  6 23 44]
     [ABCD  9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA  2 23 48]

     /* Round 4.                                         */
     /* 以下の演算を、[abcd k s i] で表す：              */
     /*     a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s) */
     /* 次の16の処理を実行する                           */
     [ABCD  0 6 49] [DABC  7 10 50] [CDAB 14 15 51] [BCDA  5 21 52]
     [ABCD 12 6 53] [DABC  3 10 54] [CDAB 10 15 55] [BCDA  1 21 56]
     [ABCD  8 6 57] [DABC 15 10 58] [CDAB  6 15 59] [BCDA 13 21 60]
     [ABCD  4 6 61] [DABC 11 10 62] [CDAB  2 15 63] [BCDA  9 21 64]

     /* そして次の加算を実行する。                       */
     /* (このブロックが開始される前に保持していた値で、  */
     /*  4つのレジスタが加算される。)                    */
     A = A + AA
     B = B + BB
     C = C + CC
     D = D + DD

 end  /* i のループの終了 */

メッセージを64バイト毎のブロックに分割し、その各々を要素数が16の4バイト整数の配列Xにセットします。 この際にXの各要素にはメッセージの下位バイトから順にセットします。

unsigned long int X[16];    /* 配列X */

[拡大]

unsigned long int AA = A;
unsigned long int BB = B;
unsigned long int CC = C;
unsigned long int DD = D;

 1〜16回目：第1段階の演算 F
17〜32回目：第2段階の演算 G
33〜48回目：第3段階の演算 H
49〜64回目：第4段階の演算 I

/* ROTATE_LEFT : xをnビット左にシフトする */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

#define F(x,y,z)   (((x) & (y)) | ((~x) & (z)))

#define FF(a, b, c, d, x, s, ac) { \
    (a) += F((b), (c), (d)) + (x) + (unsigned long int)(ac); \
    (a) = ROTATE_LEFT((a), (s)); \
    (a) += (b); \
}

FF(A, B, C, D, X[ 0],  7, T[ 1]);   /*  1 */
FF(D, A, B, C, X[ 1], 12, T[ 2]);   /*  2 */
FF(C, D, A, B, X[ 2], 17, T[ 3]);   /*  3 */
FF(B, C, D, A, X[ 3], 22, T[ 4]);   /*  4 */
FF(A, B, C, D, X[ 4],  7, T[ 5]);   /*  5 */
FF(D, A, B, C, X[ 5], 12, T[ 6]);   /*  6 */
FF(C, D, A, B, X[ 6], 17, T[ 7]);   /*  7 */
FF(B, C, D, A, X[ 7], 22, T[ 8]);   /*  8 */
FF(A, B, C, D, X[ 8],  7, T[ 9]);   /*  9 */
FF(D, A, B, C, X[ 9], 12, T[10]);   /* 10 */
FF(C, D, A, B, X[10], 17, T[11]);   /* 11 */
FF(B, C, D, A, X[11], 22, T[12]);   /* 12 */
FF(A, B, C, D, X[12],  7, T[13]);   /* 13 */
FF(D, A, B, C, X[13], 12, T[14]);   /* 14 */
FF(C, D, A, B, X[14], 17, T[15]);   /* 15 */
FF(B, C, D, A, X[15], 22, T[16]);   /* 16 */

#define G(x,y,z)   (((x) & (z)) | ((y) & (~z)))

#define GG(a, b, c, d, x, s, ac) { \
    (a) += G((b), (c), (d)) + (x) + (unsigned long int)(ac); \
    (a) = ROTATE_LEFT((a), (s)); \
    (a) += (b); \
}

GG(A, B, C, D, X[ 1],  5, T[17]);   /* 17 */
GG(D, A, B, C, X[ 6],  9, T[18]);   /* 18 */
GG(C, D, A, B, X[11], 14, T[19]);   /* 19 */
GG(B, C, D, A, X[ 0], 20, T[20]);   /* 20 */
GG(A, B, C, D, X[ 5],  5, T[21]);   /* 21 */
GG(D, A, B, C, X[10],  9, T[22]);   /* 22 */
GG(C, D, A, B, X[15], 14, T[23]);   /* 23 */
GG(B, C, D, A, X[ 4], 20, T[24]);   /* 24 */
GG(A, B, C, D, X[ 9],  5, T[25]);   /* 25 */
GG(D, A, B, C, X[14],  9, T[26]);   /* 26 */
GG(C, D, A, B, X[ 3], 14, T[27]);   /* 27 */
GG(B, C, D, A, X[ 8], 20, T[28]);   /* 28 */
GG(A, B, C, D, X[13],  5, T[29]);   /* 29 */
GG(D, A, B, C, X[ 2],  9, T[30]);   /* 30 */
GG(C, D, A, B, X[ 7], 14, T[31]);   /* 31 */
GG(B, C, D, A, X[12], 20, T[32]);   /* 32 */

#define H(x,y,z)   ((x) ^ (y) ^ (z))

#define HH(a, b, c, d, x, s, ac) { \
    (a) += H((b), (c), (d)) + (x) + (unsigned long int)(ac); \
    (a) = ROTATE_LEFT((a), (s)); \
    (a) += (b); \
}

HH(A, B, C, D, X[ 5],  4, T[33]);    /* 33 */
HH(D, A, B, C, X[ 8], 11, T[34]);    /* 34 */
HH(C, D, A, B, X[11], 16, T[35]);    /* 35 */
HH(B, C, D, A, X[14], 23, T[36]);    /* 36 */
HH(A, B, C, D, X[ 1],  4, T[37]);    /* 37 */
HH(D, A, B, C, X[ 4], 11, T[38]);    /* 38 */
HH(C, D, A, B, X[ 7], 16, T[39]);    /* 39 */
HH(B, C, D, A, X[10], 23, T[40]);    /* 40 */
HH(A, B, C, D, X[13],  4, T[41]);    /* 41 */
HH(D, A, B, C, X[ 0], 11, T[42]);    /* 42 */
HH(C, D, A, B, X[ 3], 16, T[43]);    /* 43 */
HH(B, C, D, A, X[ 6], 23, T[44]);    /* 44 */
HH(A, B, C, D, X[ 9],  4, T[45]);    /* 45 */
HH(D, A, B, C, X[12], 11, T[46]);    /* 46 */
HH(C, D, A, B, X[15], 16, T[47]);    /* 47 */
HH(B, C, D, A, X[ 2], 23, T[48]);    /* 48 */

#define I(x,y,z)   ((y) ^ ((x) | (~z)))

#define II(a, b, c, d, x, s, ac) { \
    (a) += I((b), (c), (d)) + (x) + (unsigned long int)(ac); \
    (a) = ROTATE_LEFT((a), (s)); \
    (a) += (b); \
}

II(A, B, C, D, X[ 0],  6, T[49]);    /* 49 */
II(D, A, B, C, X[ 7], 10, T[50]);    /* 50 */
II(C, D, A, B, X[14], 15, T[51]);    /* 51 */
II(B, C, D, A, X[ 5], 21, T[52]);    /* 52 */
II(A, B, C, D, X[12],  6, T[53]);    /* 53 */
II(D, A, B, C, X[ 3], 10, T[54]);    /* 54 */
II(C, D, A, B, X[10], 15, T[55]);    /* 55 */
II(B, C, D, A, X[ 1], 21, T[56]);    /* 56 */
II(A, B, C, D, X[ 8],  6, T[57]);    /* 57 */
II(D, A, B, C, X[15], 10, T[58]);    /* 58 */
II(C, D, A, B, X[ 6], 15, T[59]);    /* 59 */
II(B, C, D, A, X[13], 21, T[60]);    /* 60 */
II(A, B, C, D, X[ 4],  6, T[61]);    /* 61 */
II(D, A, B, C, X[11], 10, T[62]);    /* 62 */
II(C, D, A, B, X[ 2], 15, T[63]);    /* 63 */
II(B, C, D, A, X[ 9], 21, T[64]);    /* 64 */

A = A + AA;
B = B + BB;
C = C + CC;
D = D + DD;

ステップ5. 出力

バッファの値を結果として出力します。

【引用】
出力として生成されるメッセージダイジェストは、A、B、C、D である。 すなわち、下位バイト A から始まり、高位バイト D で終わる。

演算を行った結果のA, B, C, Dの値を、それぞれの下位バイトから順に16進数で出力します。

[拡大]

サンプルプログラム

RFC1321にはサンプルプログラムが付記されています。

ソースファイル：

md5_src.zip (クリックでSkyDriveへ移動します) 6KB  MD5：518d1058af7d689418942e7e3721f212

Windows版実行ファイル：

md5_exe.zip (クリックでSkyDriveへ移動します) 22KB  MD5：94151a5081972917185fc5b3a5b583b5

ソースファイルをコンパイルする際には、MD=5のマクロを定義してください。

% gcc -DMD=5 mddriver.c md5c.c -omd5

C:\> cl /DMD=5 mddriver.c md5c.c -omd5

サンプルプログラムは以下のように使用します。

使い方: md5 [ -sstring -t -x ] [ ファイル名... ]
    -sstring    : 文字列を指定してそのMD5の値を算出します。
    -t          : タイムトライアルを実行します。
    -x          : テストスクリプトを実行します。
    ファイル名  : ファイルを指定してそのMD5の値を算出します。(複数可)
    (引数無し)  : 標準入力から読み込みます。

雑記

正直に言って専門家でないと良くわかりません。 RFC1321もいかにもな感じでわかりにくいです。 英語版Wikipediaが比較的簡単ですが、これで理解できない場合には手を出さない方が良いと思われます。 （フランス語版の図も参考にしてください）

多くの言語では標準で関数（メソッド）が用意されていますので、それを利用するのが正解でしょう。 やはり自前で、という場合でもRFC1321のサンプルの流用で事足ります。

MD5を利用する時には注意してください。現在ではその脆弱性が問われており、SHAなどへの移行が進んでいます。

参考資料

• MD5 (Wikipedia)
  http://en.wikipedia.org/wiki/MD5 [Wikipedia]
• MD5 メッセージダイジェストアルゴリズム (RFC1321の日本語訳)
  http://www.ipa.go.jp/security/rfc/RFC1321JA.html [IPA]
• 本サイトのbkhashesはMD5, SHA-1, SHA-512など各種のハッシュ値を算出するプログラムです。