数学自由研究 > MD5のアルゴリズム

MD5のアルゴリズム

はじめに

データの完全性チェックなどによく使用される代表的な暗号学的ハッシュ関数のMD5（Message Digest Algorithm 5）のアルゴリズムについて解説したいと思います。任意の長さのデータの入力に対し、128ビットのハッシュ値を出力するMD5ですが、内部のアルゴリズムは意外にもそれほど難しくありません。

定数と関数の定義

まず、計算用のバッファとして、4つの符号無し32ビット整数A、B、C、Dを初期化しておきます。この4つのバッファが、入力値にしたがって次々と書き換えられていき、最終的にMD5の出力となります。0xで始まる数は、十六進法表記です。

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

次に、計算に使用する定数テーブルT_n (n = 1, 2, 3, ... , 64)を次のように定義します。

T_n=\lfloor2^{32}\cdot|\sin n|\rfloor\hspace{5mm} (n=1,2,3,\cdots,64)

|sinn|は0以上1未満の数なので、T_nは全て0以上2^{32}未満の整数、すなわち、符号無し32ビット整数となります。

さらに、4つの関数を定義します。いずれも、3つの符号無し32ビット整数を引数に受け取り、1つの符号無し32ビット整数を返す関数です。関数中の記号「&」「|」「^」「~」は、各種プログラミング言語にならい、ビット演算を表すものとします。つまり、「x & y」はxとyのビットごとの論理積、「x | y」はxとyのビットごとの論理和、「x ^ y」はxとyのビットごとの排他的論理和、「~x」はxのビットごとの否定を表します。

F1(x,y,z) = (x & y) | (~x & z)
F2(x,y,z) = (x & z) | (y & ~z)
F3(x,y,z) = x ^ y ^ z
F4(x,y,z) = y^ (x | ~z)

事前準備

入力ビット列に対するパディング
図1-入力ビット列に対するパディング
ビットとワード
図2-ビットとワード

まず、入力として、b (≥ 0)ビットのビット列が与えられます（図1の(1)）。最初に、ビット列の長さを一定単位にするため、パディングが行われます。具体的には、b + p ≡ 448 (mod 512)となるようにpビットを末尾に付け加えます（図1の(2)）。このときのpビットの内訳は、1ビット目が1、それ以降は全て0とします。パディングは、最初のビット列の長さbにかかわらず、必ず行います。よって、パディングの長さpは最低で1、最高で512となります。この時点で、ビット列の長さは、512の倍数にあと64ビットだけ足りない数になっているはずです。

これ以降、ビット列は32ビット（4バイト）ごとに区切ったワード列として考えます。1ワードは32ビット（4バイト）です。ワード列として考える際に注意しなければならないのは、ワード列に積んだり、ワード列から取り出したりするときに、バイト順を逆にするということです。例えば、0x01234567という32ビット数をワード列に積むと「0x67 0x45 0x23 0x01」という4バイトをこの順番に積んだのと同じことになります。逆に、ワード列から「0x01 0x23 0x45 0x67」という1ワード（4バイト）を取り出すと、それは0x67452301という32ビット数を表します（図2）。

さて、ビット列は、512の倍数にあと64ビット足りない長さになっていました。ワード数で考えると、16の倍数にあと2ワード足りない長さです。その残りの2ワードとして、元のビット列の長さbの下位64ビットを積みます（図1の(3)）。例えば、bの下位64ビットが、0x0123456789ABCDEFならば「0xEF 0xCD 0xAB 0x89」「0x67 0x45 0x23 0x01」という2ワード（8バイト）をこの順に積みます。ちなみに2^{64}ビットの長さのデータというのは普段出会うことはないでしょう。2^{64}ビット＝2^{61}バイト＝2EiB＝約230万テラバイトです。

こうして、bビットのビット列は、b + p + 64ビット、すなわちN = (b + p + 64) / 32ワードのワード列になりました。b + p + 64は512の倍数であるため、Nは必ず16の倍数となります。

ハッシュ値の計算

事前準備を終えたワード列を、先頭から順に16ワードずつ最後まで処理していきます。

ビットローテート
図3-ビットローテート

ワード列から取り出した16ワードを、X_0 ～ X_{15}の16個の32ビット数とします。また、この時点でのバッファの値A、B、C、Dを一時的にA'、B'、C'、D'に保存しておきます。

ここで、次の処理を行なうことをP_n(abcd, k, s, i)で表します。ここに「x <<< y」は、32ビット数xを左方向へyビットだけビットローテート（環状ビットシフト、図3）することを意味します。なお、加算によって上位ビットが32ビットの範囲からあふれた場合は捨てて、常に32ビット数として取り扱います。

a = b + ((a + Fn(b, c, d) + Xk + Ti) <<< s)

そして、次の64の処理を行なって、バッファを更新していきます。

P1(ABCD, 0, 7, 1); P1(DABC, 1,12, 2); P1(CDAB, 2,17, 3); P1(BCDA, 3,22, 4);
P1(ABCD, 4, 7, 5); P1(DABC, 5,12, 6); P1(CDAB, 6,17, 7); P1(BCDA, 7,22, 8);
P1(ABCD, 8, 7, 9); P1(DABC, 9,12,10); P1(CDAB,10,17,11); P1(BCDA,11,22,12);
P1(ABCD,12, 7,13); P1(DABC,13,12,14); P1(CDAB,14,17,15); P1(BCDA,15,22,16);

P2(ABCD, 1, 5,17); P2(DABC, 6, 9,18); P2(CDAB,11,14,19); P2(BCDA, 0,20,20);
P2(ABCD, 5, 5,21); P2(DABC,10, 9,22); P2(CDAB,15,14,23); P2(BCDA, 4,20,24);
P2(ABCD, 9, 5,25); P2(DABC,14, 9,26); P2(CDAB, 3,14,27); P2(BCDA, 8,20,28);
P2(ABCD,13, 5,29); P2(DABC, 2, 9,30); P2(CDAB, 7,14,31); P2(BCDA,12,20,32);

P3(ABCD, 5, 4,33); P3(DABC, 8,11,34); P3(CDAB,11,16,35); P3(BCDA,14,23,36);
P3(ABCD, 1, 4,37); P3(DABC, 4,11,38); P3(CDAB, 7,16,39); P3(BCDA,10,23,40);
P3(ABCD,13, 4,41); P3(DABC, 0,11,42); P3(CDAB, 3,16,43); P3(BCDA, 6,23,44);
P3(ABCD, 9, 4,45); P3(DABC,12,11,46); P3(CDAB,15,16,47); P3(BCDA, 2,23,48);

P4(ABCD, 0, 6,49); P4(DABC, 7,10,50); P4(CDAB,14,15,51); P4(BCDA, 5,21,52);
P4(ABCD,12, 6,53); P4(DABC, 3,10,54); P4(CDAB,10,15,55); P4(BCDA, 1,21,56);
P4(ABCD, 8, 6,57); P4(DABC,15,10,58); P4(CDAB, 6,15,59); P4(BCDA,13,21,60);
P4(ABCD, 4, 6,61); P4(DABC,11,10,62); P4(CDAB, 2,15,63); P4(BCDA, 9,21,64);

保存しておいた処理前のバッファの値A'、B'、C'、D'と、更新されたバッファの値A、B、C、Dをそれぞれ足し合わせ、それらを次のバッファの値A、B、C、Dとします。

これで16ワードの処理は終わりです。ワード列にまだワードが残っていれば、次の16ワードに対してくり返し上記の処理を行なっていきます。

ハッシュ値の出力

ワード列の最後まで処理し終えたら、その時点でのバッファの値A、B、C、DがMD5の出力となります。出力は、A、B、C、Dの順に続けて、バイト順を逆にして出力します。例えば、A =0x00112233、B =0x44556677、C =0x8899AABB、D =0xCCDDEEFFという結果になったら、MD5値は、3322110077665544bbaa9988ffeeddccという32文字の文字列となります。

主な参考文献

更新履歴

©2013 Azicore - 数学自由研究へ戻る - 鯵の鯖トップ