メインコンテンツまでスキップ

3. MD5 Algorithm Description (MD5アルゴリズムの説明)

bビットのメッセージを入力として持ち、そのメッセージダイジェストを求めたいと仮定します。ここで、bは任意の非負整数であり、bはゼロであっても良く、8の倍数である必要はなく、任意に大きくてもかまいません。メッセージのビットが次のように書き下されていると想像します。

m_0 m_1 ... m_{b-1}

メッセージのメッセージダイジェストを計算するために、次の5つのステップが実行されます。

3.1 Step 1. Append Padding Bits (ステップ1. パディングビットの追加)​

メッセージは「パディング (Padding)」(拡張) され、その長さ (ビット単位) が448を法として合同になります。つまり、メッセージは512ビットの倍数より64ビット少なくなるように拡張されます。パディングは、メッセージの長さがすでに448を法として合同である場合でも常に実行されます。

パディングは次のように実行されます。単一の「1」ビットがメッセージに追加され、次に「0」ビットが追加されて、パディングされたメッセージの長さ (ビット単位) が448を法として合同になります。合計で、少なくとも1ビット、最大512ビットが追加されます。

3.2 Step 2. Append Length (ステップ2. 長さの追加)​

b (パディングビットが追加される前のメッセージの長さ) の64ビット表現が、前のステップの結果に追加されます。bが2^64より大きいという unlikely なイベントでは、bの下位64ビットのみが使用されます。(これらのビットは、2つの32ビットワードとして追加され、前の規則に従って下位ワードが最初に追加されます。)

この時点で、結果のメッセージ (ビットとbでパディングされた後) の長さは、512ビットの正確な倍数になります。同等に、このメッセージの長さは、16個の (32ビット) ワードの正確な倍数です。結果のメッセージのワードをM[0 ... N-1]と表記します。ここで、Nは16の倍数です。

3.3 Step 3. Initialize MD Buffer (ステップ3. MDバッファの初期化)​

メッセージダイジェストを計算するために、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

3.4 Step 4. Process Message in 16-Word Blocks (ステップ4. 16ワードブロック単位でのメッセージ処理)​

まず、それぞれが入力として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))

各ビット位置において、Fは条件付きとして機能します。XならばY、そうでなければZ。関数Fは、XYとnot(X)Zが同じビット位置に1を持つことは決してないため、vの代わりに+を使用して定義することもできます。X、Y、Zのビットが独立で偏りがない場合、F(X,Y,Z)の各ビットも独立で偏りがないことは興味深いことです。

関数G、H、Iは関数Fと似ており、X、Y、Zのビットから出力を「ビット単位並列」に生成し、X、Y、Zの対応するビットが独立で偏りがない場合、G(X,Y,Z)、H(X,Y,Z)、I(X,Y,Z)の各ビットも独立で偏りがなくなるようにします。関数Hは、その入力のビット単位の「xor」または「パリティ」関数であることに注意してください。

このステップでは、サイン関数から構築された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 /* of loop on j */

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

  /* ラウンド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]

  /* ラウンド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]

  /* ラウンド3。 */
  /* [abcd k s t]は操作を表します
       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]

  /* ラウンド4。 */
  /* [abcd k s t]は操作を表します
       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 /* of loop on i */

3.5 Step 5. Output (ステップ5. 出力)​

出力として生成されるメッセージダイジェストは、A、B、C、Dです。つまり、Aの下位バイトから始まり、Dの上位バイトで終わります。

これでMD5の説明は完了です。参照実装のCコードは付録に示されています。

に最終更新