図． MD5の手順１,２におけるビット列処理
=========================================
The Shadow Penguin Documents. No. 16
- MD5(Message Digest 5) -
Written by Hariru Feb. 6, 1999
=========================================
１．MD5とは
MD5(Message Digest 5)は、公開鍵の暗号化方式であるRSA(Rivest,Shamir,Adleman)を考案した
３人の中の一人であるR.L.Rivest博士らによって考案された、実装が簡単なメッセージ暗号化
アルゴリズムです。
このアルゴリズムは、任意の長さのメッセージを１２８ビットのメッセージダイジェストに
圧縮変換するもので、POP3をはじめとして、IPの認証、PC UNIXのフリーソフトであるFreeBSDや、
ITU-T勧告のX.500で利用されています。このアルゴリズムの以前のものとしてMD2やMD4があり、
Rivest博士本人の言によれば、現在MD6も進行中です。
２．MD5の処理手順
実際の処理は、次のような５つの処理手順で行います。なお、入力メッセージの文字列はビット列
として取り扱われます。
(1)手順１
ビット列と化した入力メッセージのビット数が、５１２で割ったときのあまりが４４８に
なるように、入力メッセージの後ろに当て物ビット(Padding Bits)を追加します。
この追加するPadは"100･･･"と続くもので、仮に入力メッセージが
４４０ビット長だとすると、８ビットのPad="10000000"が追加されることになります。
次の手順２とともに図に示しますので、参照してください。
(2)手順２
もとの入力メッセージの文字列の長さを６４ビットで表して、手順１で得られたビット列に
追加します。そのとき追加する６４ビットは、下位３２ビット、上位３２ビットの順で
追加します。
これによって新しいメッセージのビット数が、５１２の倍数になるわけです。図を参照。
ちなみに、このビット列は手順４で示す、ブロック[k]を意味します。また、６４ビットで
入力メッセージの長さを表すため、２64ビット
(≒2.30×1018文字)以上の入力メッセージでは
動作を保証していません。ちょっと現実的な文字数ではありませんけどね。
(3)手順３
アルゴリズム演算に使用する４つのワードを、次の値によって初期化します。
ワード A＝0x67452301
ワード B＝0xefcdab89
ワード C＝0x98badcfe
ワード D＝0x10325476
ちなみに"0x"とは１６進数という意味で、１ワードは３２ビット長です。
(4)手順４
ここでは、とある計算を行います。とその前に、その際利用する４つの論理関数を示して
おきます。
関数F(X,Y,Z) = (X AND Y) OR (NOT(X) AND Z)
関数G(X,Y,Z) = (X AND Z) OR (Y AND NOT(Z))
関数H(X,Y,Z) = X XOR Y XOR Z
関数I(X,Y,Z) = Y XOR (X OR NOT(Z))
AND，OR，XOR，NOTはそれぞれ、論理積，論理和，排他的論理和，否定です。これらがわからないと
いう方は、文章の最後に説明してありますのでそちらを参照してください。
さて、前述したある計算というのは次の通りです。
a = b + (( a + 関数f(b,c,d) + ブロック[k] + T[i] ) <<< s )
a,b,c,d ：ワードA,B,C,Dの組み合わせのいずれか
関数f ：関数F,G,H,Iのいずれか
ブロック[k]：手順２の結果を16ワード(512ビット)ずつに区切ったk番目のブロック
Ｔ[i] ：sin(i=1〜64ラジアン)の絶対値に"0x10000000"をかけた整数部のテーブル
<<< ：循環左シフト
s ：ビットシフト数
ワード A，B，C，Dの組み合わせとは４通りあり、[ABCD]，[DABC]，[CDAB]，[BCDA]順の並びで
扱うことになります。また、一つの関数、一つのワードで演算を４回します。そのため、４(４通りの
ワード)×４(演算４回)×４(４つの関数)＝６４回の演算を行うことになります。
とまあ書きましたが、文章じゃわかりにくいのでプログラム的な説明を。
/* 16ワード(512ビット)ごとに処理を行います */
For i = 0 to N/16-1 do
/* 16ワード(512ビット)のメッセージMを、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
/* ラウンド１ */
/* [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]
/* その後、次の足し算を実行してください。(それはこのブロックが
始められる前に、持っていた値によって4つの各々のレジストリを
増加させます) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* iループの終わり */
(5)手順５
生成されたA，B，C，Dから得られるビット列が、メッセージダイジェスト(MD)です。
その順列はAの下位８ビットから始めて、Dの上位８ビットで終わる順列になります。
例で示すなら、次の通りです。
A = A1, A2, A3, A4
B = B1, B2, B3, B4
C = C1, C2, C3, C4
D = D1, D2, D3, D4
↓
MD = A4, A3, A2, A1, B4, B3, ･･･ , D2, D1
このように１２８ビットのビット列が、最終的なメッセージダイジェスト(MD)の出力です。
これでMD5アルゴリズムは、完了となります。
３．プログラム(RFC1321)
ここで紹介するプログラムは、RFC1321の付録A(APPENDIX A)にある、Ｃ言語によるMD5
メッセージダイジェストアルゴリズム処理の参考実装(Reference Implementation)からの
切り抜きです。簡単な訳と説明をつけましたが、詳しく知りたい方は本文の方を参照した方が
確実です。
RFC 1321 ･･･ 付録A - 参照実装より
この付録は、RSAREFから得られたプライバシー強化メイルのための暗号のツールキット
(Cryptographic Toolkit)のファイルを含んでいます。
global.h --- グローバルヘッダーファイル
md5.h --- MD5のためのヘッダーファイル
md5c.c --- MD5のためのソースコード
RSAREFについて、より詳細なことを知りたい方は、rsaref@rsa.comに電子メールを送って
ください。
付録はさらに、次のファイルを含んでいます。
mddriver.c --- MD2、MD4およびMD5のためのテストドライバー
このドライバーをデフォルトでコンパイルすると、MD5アルゴリズムを行います。
しかし、シンボルMDがCコンパイラのコマンドライン上で2または4として定義される場合、
MD2またはMD4のアルゴリズムとしてコンパイルすることができます。
これは携帯型であり、様々な種類のプラットフォームに使われるべきです。
しかしながら、それぞれの特別のプラットフォーム上へ実装して最適化することは、
これを読んだ人に残された課題になります。
実際のプログラムは長くなりますので、まとめてこちらに。
ただし、本文の"mddriver.c"をコンパイルしても動かなかったので、
"mddriver.c"のインクルードの辺りを多少変更させてもらいました。
また実行テストの仕方ですが、それぞれのプログラムを同じディレクトリ上に作って
"mddriver.c"をコンパイル、実行してください。
実行の際つけるオプションは、次の通りです。
引数はいくつか連結することもできます
-sstring - stringをダイジェストする
-t - タイムトライアルを行う
-x - テストスクリプトを行う
filename - 指定したファイルをダイジェストする
(none) - 標準入力をダイジェストする
オプション"-s"を付けて、その後スペースなどせずにそのまま文字列を打ち込んで
実行すると、その文字列のメッセージダイジェストが表示されます。オプション"-t"は
入力メッセージ1000文字とし、MD5を1000回行ってその実行時間を表示するのですが、高速なため
なのかうまく表示されないみたいです。オプション"-x"を付けると、正しく機能して
いるのかテストスクリプトを行います。そのとき得られる結果は、以下の通りになるはずです。
MD5 test suite:
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab9
8d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234
567890") = 57edf4a22be3c955ac49da2e2107b67a
オプションなしでファイル名を入力して実行すると、そのファイルの内容をメッセージ
ダイジェストをして表示します。オプションなしの実行はキーボードからの標準入力ですが、
うまく終了しないみたいなので使わない方がよいでしょう。
〜〜 お わ り 〜〜
論理演算(AND,OR,NOT,XOR) 論理演算にはAND,OR,NOT,XORがあり、ビット単位でそれぞれ次のような演算を行います。 AND OR a b | (a AND b) a b | (a OR b) ---------+----------- ---------+---------- 0 0 | 0 0 0 | 0 0 1 | 0 0 1 | 1 1 0 | 0 1 0 | 1 1 1 | 1 1 1 | 1 NOT XOR a | NOT(a) a b | (a XOR b) ---------+---------- ---------+----------- 0 | 1 0 0 | 0 1 | 0 0 1 | 1 1 0 | 1 1 1 | 0 参考文献 [1]Ronald L.Rivest：RFC 1321 (The MD5 Message-Digest Algorithm)，1992 [2]笠野 英松：通信プロトコル事典，アスキー出版局，1996 [3]金子 俊夫：OPENDESIGN No.14，ＣＱ出版社，1996