この頁では、HTTPでも利用されている一方向関数のMD5のアルゴリズムをRFC1321を読みながら解説します。 また、MD5の代替アルゴリズムとなりうるSHA-1についても紹介します。
与えられた値から固定長のデータを生成するための関数をハッシュ関数と言い、それによって生成される値はハッシュ値、あるいはメッセージダイジェストと呼ばれます。 ハッシュ関数は一方向関数であり、逆変換できないので、ハッシュ値から原文を再現することはできず、また同じハッシュ値を持つ異なるデータを作成することも極めて困難、現実的には不可能となります。 HTTPで利用されるハッシュ関数としては、MD5というものがあり、以下のような局面で利用されます。
MD5は、RFC 1321として広く公開されているアルゴリズムです。 アルゴリズムの概要については、section 1をご覧ください。
この文書は、MD5 メッセージダイジェストアルゴリズムについて記述するものである。 このアルゴリズムは、任意の長さのメッセージを入力とし、その入力についての 128 ビットの "指紋" あるいは "メッセージダイジェスト" と呼ばれるものを出力する。 同じメッセージダイジェストをもたらす 2 つのメッセージを生成する事、あるいは指定された対象メッセージダイジェストとなるメッセージを生成する事は、計算上実行不可能であると推測される。 MD5 アルゴリズムは、電子署名アプリケーションについて意図されており、ここでは、大きなファイルは RSA のような公開鍵暗号方式におけるプライベート (秘密) 鍵で暗号化される前に、セキュアな方法にて "圧縮" されなければならない。
MD5 アルゴリズムは、32 ビットマシンで非常に速く処理できるように設計されている。 加えて、MD5 アルゴリズムは、大きな置換テーブルを必要としない; すなわち、非常にコンパクトにこのアルゴリズムをコード化する事ができる。
つまり、MD5を非常に簡単に言うと「“任意のデータ”から128桁の2進数列を作成し、その数列は多くの場合同じものとはならない」というものになります。 このため、HTTPでは、ダイジェスト認証で使用するパスワードの不可逆変換、あるいはHTTPを通じて大きなバイナリデータをダウンロードする時に、「そのデータが壊れていないか」あるいは「第三者に改変されていないか」などを調べるための“指紋（fingerprint）”として利用されています。
MD5 のアルゴリズムは、以下のようになっています。
MD5 を実装する際は、そのアルゴリズムがリトルエンディアンである事に注意して下さい。
リトルエンディアンとは、データを下位バイトから順に並べる方式を言います。
例えば、“01”“23”“45”“67”という 4 バイトのデータがあるとして、リトルエンディアンの場合はこれを 0x67452301 のように格納します。
(※) 逆に、0x01234567 のように、データを上位バイトから並べる方式をビッグエンディアンと言います。
まず、メッセージ長を 512 ビットの整数倍にするため、パディングを施します。
メッセージは、"パディングされ" (拡張され) て、その (ビットにおける) 長さは、512 を法とした時の 448 とされる。 すなわち、そのメッセージは拡張され、512 の倍数のビット長に対して、ちょうど 64 ビットだけ足りない。 このパディングは、たとえメッセージの長さが既に、512 を法とした時の 448 に一致していても常に実行される。
パディングは、以下のように実行される: 単一の "1" ビットがメッセージに付加され、次にパディングされたメッセージのビットの長さが、512 を法とした時の 448 になるように "0" の値を持つビットを付加する。 全ての場合で、最小 1 ビット、最大 512 ビットが付加される。
メッセージの例として、abc という文字列を考えます。 まず、この abc をビット列に直し、その後規則に従ってパディングすると、次のようになります。
<a> <b> <c> 1 | 448ビット目まで埋める | 01100001 01100010 01100011 1 0000000 0000000 .. 00000000
このように、元のメッセージにまず 1 というビットを加え、それからメッセージ長が (512 の倍数 - 64) ビットになるように 0 のビットを加えていきます。
Step 1. の結果に、パディングする前のメッセージ長の下位 64 ビットを付加します。 この時、下位 32 ビットを先に付加するという事に注意します。
b (パディングビットが付加される前のメッセージの長さ) の 64 ビット表記が、この前のステップの結果に付加される。 b が 2^64 よりも大きいというありそうもない場合においては、b の下位 64 ビットのみが使用される。 (これらのビットは 2 つの 32 ビットワードとして付加され、慣例に従い下位ワードが最初に付加される。)
ここで、(ビットと b の長さをパディングした後に) 結果的に生成されるメッセージは、ちょうど 512 ビットの倍数の長さとなる。 すなわち、このメッセージは 16 (32ビット) ワードの倍数の長さとなる。 ここで、M[0 ... N-1] は結果のメッセージのワードを意味するものとし、N は 16 の倍数である。
先の abc の例で言えば、これは 3 バイト = 24 ビットなので、次のようになります。
<a> <b> <c> 1 | 448ビット目まで埋める | 24 0 01100001 01100010 01100011 1 0000000 0000000 .. 00000000 00011000 00000000
さて、このまま 2 進数で考えるのは数字が多くて不便なので、これを 16 進数に纏めてみましょう。
<a> <b> <c> 1 | 448ビット目まで埋める | 24 0 2進数 01100001 01100010 01100011 1 0000000 0000000 .. 00000000 00011000 00000000 16進数 6 1 6 2 6 3 8 0 0 0 00 0 0 1 8 0 0
以上より、Step 1. と Step 2. の規則は以下のように言い換える事ができます。
メッセージ長を 64 バイトの整数倍にするため、元のメッセージにまず 0x80を加え、それからメッセージ長が (64 の倍数 - 8) バイトになるように、0x00 を加えていきます。
この結果に、(パディングする前のメッセージ長) * 8 の 16 進数を付加します。
この時、下位 4 バイトを先に付加するという事に注意します。
メッセージダイジェストを計算するために、(A, B, C, D) という 4 つの 8 バイトバッファを用意します。
メッセージダイジェストを計算するために 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
これもまた、下位バイトから格納するので、実際にコンピュータで計算させる時は次のような値を代入するとよいでしょう。
A = 0x67452301 B = 0xefcdab89 C = 0x98badcfe D = 0x10325476
(※) このような変数は連鎖変数 (chaining variable) と呼ばれます。
Step 2. で作ったパディング済メッセージを 16 ワードずつ、すなわち 64 バイトずつ処理していきます。
なお、以下において、XY は「論理積」、v は「論理和」、not は「ビット反転」、xor は「排他的論理和」、X <<< s は「X を s ビット左に回転」という事を意味するとします。
「回転」について、例えば (10000000 01010011 01010010 01010001 <<< 8) は、(01010011 01010010 01010001 10000000) となります。
初めに、それぞれ、3 つの 32 ビットワードを入力とし、1 つの 32 ビットワードを出力するような 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))(中略)
このステップでは、sin 関数から構成される 64 の要素を持つテーブル T[1 ... 64] を使用する。 T[i] はテーブルの i 番目の要素とし、4294967296 と abs(sin(i)) の積の整数部に等しいものとする。 ここで、i の単位はラジアンである。
以下を実行する:
/* 各 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 のループについて */
まず、F, G, H, I という 4 つの補助関数と、T[i] = int(2^32 * abs(sin(i))) を定義します。
但し、i の単位はラジアンです。
ここから、Step 2. で作ったパディング済メッセージを 16 ワードずつ処理していきます。
X[j] (0 <= j <= 15) というテーブルに 4 バイトずつ格納していきます。
ここでも、下位バイトを先に格納するので注意して下さい。
abc の例で言えば、X[0] = 0x80636261 となります。
[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]
[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]
[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]
[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]
Step 4. で計算した MD を出力します。
出力として生成されるメッセージダイジェストは、A, B, C, D である。 すなわち、A の下位バイトから始まり、D の高位バイトにて終わる。
MD は、A, B, C, D を並べた 32 バイトのデータとなりますが、Step 4. が終わった時点では A, B, C, D は以下のようになっています。
A = 0x98500190 B = 0xb04fd23c C = 0x7d3f96c6 D = 0x727fe128
ここでも各データは下位バイトから順に並べるという事に注意すれば、求める MD は次のようになります。
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
ところで、異なるデータのメッセージダイジェスト値が同じ値になる事は、衝突を起こすと表現されます。 一般に、ダイジェスト値が衝突を起こすような文字列を探すために必要な試行回数は、ビット数 N に対して、2N/2 程度であるとされています。 従って、MD5 では、およそ 264、すなわち 1845 京 (1 京 = 10000 兆) 回程度を試せば、同じダイジェスト値を得られる計算になりますが、現在ではより少ない試行回数で MD5 を衝突を起こせる事がわかっています。
そこで、より強固な安全性を提供するために、最近では MD5 の代わりに SHA-1 というアルゴリズムがよく使用されています。 SHA-1 は、MD5 と同じ MD4 を元に作られていますが、MD5 より長い 160 ビットのダイジェストを生成します。 従って、同じダイジェスト値を得るためには、およそ 280、すなわち 12089 垓 (1 垓 = 10000 京) 回程度の試行が必要という事になり、文字通り桁違いに大変になります。
(※) 但し、現在では SHA-1 でも、それより少ない試行回数で衝突を起こす方法が発表されています。
HTTP における MD5 の使用局面の一つである「メッセージの完全性を確かめる」という事のために、現在は Content-MD5 が使用されているわけですが、ここで SHA-1 を使うために RFC 3230 が提案されています。
ダイジェストアルゴリズムは、特定のダイジェスト計算法を示すために使用される。 アルゴリズムによっては、一つ以上の引数を与えるかもしれない。
digest-algorithm = token"parameter" の BNF は、RFC 2616 [4] にて使用される通りである。 全てのdigest-algorithm 値は大文字・小文字を区別しない。
Internet Assigned Numbers Authority (IANA) は、digest-algorithm 値のレジストリの役割を果たす。 最初に、レジストリは以下のトークンを含む:
- MD5
- RFC 1321 [15] にて詳述されるような、MD5 アルゴリズム。 このアルゴリズムの出力は、base64 エンコーディング [1] を使用してエンコードされる。
- SHA
- SHA-1 アルゴリズム [12]。 このアルゴリズムの出力は、base64 エンコーディング [1] を使用してエンコードされる。
- UNIXsum
- Single UNIX Specification, Version 2 [13] にて定義されるような、UNIX の "sum" コマンドによって計算されるアルゴリズム。 このアルゴリズムの出力は、16 ビットチェックサムを表現するための ASCII 十進数文字列であり、UNIX "sum" コマンドの出力の最初の語である。
- UNIXcksum
- Single UNIX Specification, Version 2 [13] にて定義されるような、UNIX の "cksum" コマンドによって計算されるアルゴリズム。 このアルゴリズムの出力は、32 ビット CRC を表現するための ASCII 数字文字列であり、UNIX "cksum" コマンドの出力の最初の語である。
もし他の digest-algorithm 値が定義される場合、関連付けられるエンコーディングは、引用文字列として表されなければならない。 あるいはエンコーディングに用いられる文字セット中に ";" か "," を含んでいてはならない。
ここでは、使用できるアルゴリズムとして、UNIX の sum や cksum も考慮されています。
(※) 但し、この仕組みを実装している HTTP アプリケーションは現在のところ、ほとんどないでしょう。
, All Rights Reserved.
