MD5 - standard

この文書では、MD5メッセージダイジェストアルゴリズムについて説明します。このアルゴリズムは、任意の長さのメッセージを入力として受け取り、128ビットの「フィンガープリント」または「メッセージダイジェスト」を出力します。同じメッセージダイジェストを持つ2つのメッセージを生成すること、あるいは特定のターゲットメッセージダイジェストを持つ任意のメッセージを生成することは、計算量的に不可能であると推測されています。MD5アルゴリズムは、RSAなどの公開鍵暗号システムを用いて秘密鍵で暗号化する前に、大容量ファイルを安全な方法で「圧縮」する必要があるデジタル署名アプリケーションを対象としています。

MD5アルゴリズムは、32ビットマシン上で非常に高速に動作するように設計されています。さらに、MD5アルゴリズムは大規模な置換テーブルを必要としないため、非常にコンパクトにコーディングできます。

MD5アルゴリズムは、MD4メッセージダイジェストアルゴリズム1,2の拡張版です。MD5はMD4よりもわずかに低速ですが、より「保守的」な設計となっています。 MD5は、MD4が既存の批判的なレビューで正当化されるよりも早く実用化されている可能性があると感じられたため、設計されました。MD4は非常に高速に設計されたため、暗号解読攻撃が成功するリスクという点で「限界」にありました。MD5は速度を少し犠牲にすることで、究極のセキュリティを実現する可能性を大幅に高めています。様々なレビュー担当者からの提案を取り入れ、追加の最適化も行われています。MD5アルゴリズムは、レビューと標準規格としての採用の可能性のためにパブリックドメインに公開されています。

OSIベースのアプリケーションの場合、MD5のオブジェクト識別子は

md5 OBJECT IDENTIFIER ::=

iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}

X.509型AlgorithmIdentifier 3において、MD5のパラメータはNULL型である必要があります。

2. 用語と表記

この文書では、「ワード」は32ビットの量、「バイト」は8ビットの量です。ビットのシーケンスは、バイトのシーケンスとして自然に解釈できます。この場合、連続する8ビットの各グループは、各バイトの上位（最上位）ビットを先頭に1バイトとして解釈されます。同様に、バイトのシーケンスは32ビットのワードのシーケンスとして解釈できます。この場合、連続する4バイトの各グループは、下位（最下位）バイトを先頭に1ワードとして解釈されます。

x_i は「x sub i」を表します。添字が式の場合は、x_{i+1} のように中括弧で囲みます。同様に、上付き文字（べき乗）には ^ を使用します。つまり、x^i は x の i 乗を表します。

記号「+」はワードの加算（つまり、2^32 を法とする加算）を表します。 X <<< s は、X を s ビット左に循環シフト（回転）して得られる 32 ビット値を表します。not(X) は X のビット補数を表し、X v Y は X と Y のビット OR を表します。X xor Y は X と Y のビット XOR を表し、XY は X と Y のビット AND を表します。

3. MD5アルゴリズムの説明

まず、bビットのメッセージを入力として持ち、そのメッセージダイジェストを求めたいとします。ここで、bは任意の非負整数です。bは0であってもよく、8の倍数である必要はなく、任意の大きさであっても構いません。メッセージのビットは以下のように記述されていると仮定します。

m_0 m_1 ... m_{b-1}

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

3.1 ステップ 1. パディングビットの追加

メッセージは、その長さ（ビット数）が 448 を法として 512 を法として一致するように「パディング」（拡張）されます。つまり、メッセージは 512 ビットの倍数から 64 ビットだけ短いように拡張されます。メッセージの長さが既に 448 を法として 512 を法として一致している場合でも、パディングは常に実行されます。

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

3.2 ステップ2. 長さの追加

b（パディングビットが追加される前のメッセージの長さ）の64ビット表現が、前のステップの結果に追加されます。万が一、bが2^64より大きい場合は、bの下位64ビットのみが使用されます。（これらのビットは2つの32ビットワードとして追加され、前述の規則に従って下位ワードから追加されます。）

この時点で、結果のメッセージ（ビットとbでパディングした後）の長さは512ビットの正確な倍数になります。つまり、このメッセージの長さは16（32ビット）ワードの正確な倍数になります。結果のメッセージのワード数をM0 ... N-1とします。ここで、Nは16の倍数です。

3.3 ステップ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 ステップ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は条件文として機能します。if X then Y else Zです。XYとnot(X)Zは同じビット位置に1を持つことがないため、関数Fは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は、入力のビット単位の「排他的論理和」または「パリティ」関数であることに注意してください。

この手順では、正弦関数から構築された64要素のテーブルT1 ... 64を使用します。Tiはテーブルのi番目の要素を表し、これは4294967296×abs(sin(i))の整数部に等しくなります（iはラジアン単位）。テーブルの要素は付録に記載されています。

以下を実行します。