Dozing
creation with digital methods

探した日本語訳がわかりにくかったので、アルゴリズムだけ訳しました。といってもこれも稚拙な訳ですが。
ネタとしては古いんですけど他のハッシュにも応用されてるんで資料として一応。

3 MD5アルゴリズム解説

入力としてbビットのメッセージがあり、そのメッセージダイジェストを見つけたいとする。ここでbは任意の非負の整数とする。（bは0かもしれない）そしてbは8の倍数である必要は無い。さらに任意の大きさである。メッセージのビット列は次のように書かれるものとする。

m0 , m1 , ... mb-1

メッセージのMDを計算するために次の5つのステップが行われる。

3.1 STEP1 パディングビットの追加

メッセージはパディング（拡張）される。それはメッセージの長さが（ビット数で）モジュロ512で448に一致する長さになるようにする。つまり、メッセージは512ビットの整数倍の長さからちょうど64ビット足りない長さになるよう拡張される。たとえメッセージの長さが既にモジュロ512で448に一致する長さであっても、パディングは常に実行される。

パディングは次のように実行される。1つの「1」ビットがメッセージに追加される。そしてパディングされたメッセージのビット長がモジュロ512で448と一致するように0が追加され、最大で512ビットが追加される。

3.2 STEP2 長さの追加

bの64ビット表現（パディングビットが追加される前の長さ）が前ステップの最後に追加される。bが264を超えるというありそうに無い出来事の場合、bの下位64ビットが使われる。（これらのビットは2つの32ビットワードとして追加される。そして、前の規約に従って、下位のワードを最初に追加する）

訳注：前の規約というのは、複数バイトではリトルエンディアン。バイト内ではMSBを先に格納する規約。「ワード」という言葉は何も付かなければ32ビットワードと解釈する。

この点において、結果のメッセージ（bとパディング後のメッセージ）は正確に512ビットの倍数の長さを持つ。同じように、このメッセージは正確に16（32）ビットワードの倍数の長さを持つ。

M［0...N-1］を結果のメッセージのワード群を表すものとする。ここで、Nは16の倍数である。

3.3 STEP3 MDバッファの初期化

メッセージダイジェストを計算するために4つのワードバッファ（A、B、C、D）が使われる。ここでA、B、C、Dの各々は32ビットレジスタである。これらのレジスタは16進数で次のような値で初期化される。（下位バイトを最初に書いてある）

  • ワード A： 01 23 45 67
  • ワード B： 89 AB CD EF
  • ワード C： FE DC BA 89
  • ワード D： 76 54 32 10

3.4 STEP4 16ワードブロックでメッセージ処理

最初に4つの補助関数を定義する。これらは各々入力として3つの32ビットワードを取り、出力として1つの32ビットワードを生成する。

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

訳注： 「X v Y」はXとYの論理和。「XY」はXとYの論理積。「not(X)」はXの否定。「xor」は排他的論理和。「+」はmodulo32ビットの和。

各々のビット位置において、Fは条件式のように振舞う。（もしXならばY、そうでなければZ。XYとnot(X)Zは同じビット位置で同時に1を取り得ないので、vの代わりに+を使ってFを定義する事ができる。）X、Y、Zのビットが独立で不偏であれば、F(X , Y , Z)の各々のビットも独立で不偏になるであろう事に注目するのは興味深い。

X、Y、Zのビットから出力を生成するために「ビット幅では平行」に振舞うという点で、X、Y、Zに対応しているビットが独立で不偏であれば、G、H、Iの各々のビットも独立で不偏になるという、その方法においては、関数G、H、Iも関数Fと似ている。関数Hは入力のビット幅「xor」もしくは「パリティ」関数であることに注意する。

このステップでは64要素のテーブル T[1...64]を使用する。これはsin関数から作られる。T[i]はテーブルのi番目の要素で、abs(sin(i))の4294967296（100000000h）倍の整数部分に等しい。ここで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 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]
/* Round 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 /* iのループ末端 */

3.5 STEP5 出力

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

これでMD5の解説は完了する。Cによる実装は付録を参照されたい。

<noembed><noembed><noembed>