UTF-8 encoded Translated into Japanese language by Yuuki OKANO. 日本語訳 陸野 優樹 Email: marimo@wdic.org 翻訳 1999年12月29日 / translation 29 December 1999 修正 2006年12月09日 / correction 09 December 2006 日本語に訳された文書に関する著作権は訳者に帰属します。 著作権についてはオリジナルに記載された著作権全文に従います。 配布についてはオリジナルと同様に無制限です。 内容は不定期に更新されます。 最新の内容は http://www.akanko.net/marimo/rfc/ にあります。 この文書は rfc1321 を訳者(marimo@wdic.org)が個人的な好奇心で適当に翻 訳したものです。したがって、翻訳の正確さなどは全く保証いたしません。誤 訳や根本的な勘違いなどが多く含まれていると思います。正確な情報が必要な 場合は英語原文も合わせてお読みください。誤字・誤訳など翻訳内容について の指摘は、いつでも歓迎します。 Network Working Group R. Rivest Request for Comments: 1321 MIT Laboratory for Computer Science and RSA Data Security, Inc. April 1992 MD5 メッセージ-ダイジェスト アルゴリズム このメモの位置づけ このメモは情報をインターネットコミュニティに提供する。それは、イン ターネット標準を指定しない。このメモの配布は無制限である。 承認 我々は、大いに役立つコメントと提案をくれた、Don Coppersmith, Burt Kaliski, Ralph Merkle, David Chaum, そして Noam Nisan に感謝する。 目次 1. 実行の要約 2. 専門用語と表記法 3. MD5アルゴリズム記述 3.1. [ステップ1] パディングビットの付加 3.2. [ステップ2] 長さの付加 3.3. [ステップ3] MD バッファの初期化 3.4. [ステップ4] 16ワード長のブロックメッセージの処理 3.5. [ステップ5] 出力 4. 要約 5. MD4とMD5の違い 参考資料 付録 A - 参照インプリメンテーション セキュリティ対策 奥付 （訳注：本訳は都合上ページを振っていないので、上記のページ番号はす べて消した。読みづらい点はご容赦） 1. 実行の要約 このドキュメントは、 MD5 メッセージ‐ダイジェストアルゴリズムにつ いて記述されている。このアルゴリズムは、任意の長さのメッセージを入力 すると、入力に対する128ビットの "指紋" や "メッセージダイジェスト" を作り出力する。 同じメッセージダイジェストを持つ2つのメッセージを生産する、もしく は、与えられた前指定されたターゲットメッセージダイジェストを持つあら ゆるメッセージを生産することは、計算上不可能であるということが推測さ れる。MD5 アルゴリズムは、大きいファイルが RSA のような公開鍵暗号化 によるプライベートな秘密鍵によって暗号化される前に、安全な方法におい て "圧縮されなければならない" ディジタル署名アプリケーションのために 意図されたものである。 MD5アルゴリズムは、32ビットマシンでも十分高速なように設計されてい る。さらに、MD5アルゴリズムは巨大な置換テーブルを全く必要としない; アルゴリズムは非常にコンパクトにコード化できる。 MD5アルゴリズムは、MD4メッセージダイジェストアルゴリズムの拡張であ る [1,2]。MD5 は MD4 より少し遅いが、設計は、より "保守的" である。 現存する重要なレビューによって正当化されるより、MD4がおそらく更に迅 速に使用のために採用されつつあると考えられたため、MD5は設計された; MD4は非常に高速になるよう設計されていたため、それは、首尾よい暗号分 析的攻撃の危険に対しては「心配」である。MD5 は少し調子を落として、よ り優れた究極のセキュリティの可能性のため、スピードは少しあきらめた。 それは、様々な評論家によりされたいくつかの提案を組み込み、付加的な最 適化を含んでいる。MD5 アルゴリズムは、標準化のためのレビュー、及び採 用のためのパブリックドメインに配置されつつある。 OSIベースのアプリケーションのために、MD5のオブジェクト識別子は md5 OBJECT IDENTIFIER ::= iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5} X.509タイプのアルゴリズム識別子 [3] には、MD5 のためのパラメータは タイプ NULL を持っているべきである。 2. 専門用語と表記法 この文書では "ワード" は 32ビットであり、"バイト" は8ビットである。 一連のビットは、最初個々の連続的なグループの8ビットが個々のバイトリ ストの最上位ビットによってバイトと解釈される一連のバイトとして自然な 方法で解釈できる。 同様に、一連のバイトは、最下位バイトが最初に与えられ、個々の連続的 なグループの4バイトがワードと解釈される一連の32ビットワードと解釈で きる。 x_i は "x sub i" を示す。もし下付き文字を表現する際は、中カッコで それを x_{i+1} のように囲む。同様に、x^i が i-th の x 乗を示すよう に、上付き文字をべき乗として用いる。 記号 "+" はワードの追加を示す (すなわち modulo-2^32 加算)。 X <<< s は、32ビット値で、X を s ビット分回転シフト(ローテート)す ることを表わす。not (X) は X の補数を示す。そして、X ∨ Y は X と Y の包含的論理和(OR)を示す。X xor Y は X と Y の排他的論理和(XOR) を 示し、XY は X と Y の論理積(AND) を示す。 3. MD5アルゴリズム記述 まず始めに、bビットのメッセージを入力として持ち、そのメッセージダ イジェストを求めたいと考える。ここで、b は0以上の正の整数で、必ずし も8の倍数(つまりバイト単位)である必要はない。また、それは恣意的に巨 大かもしれない。我々は、次の通り書き留められたメッセージのビットを想 像している: m_0 m_1 ... m_{b-1} 以下の5つのステップは、メッセージのメッセージダイジェストを計算す るために実行される。 3.1 [ステップ1] パディングビットの付加 メッセージが "パディング" (拡張) されるので、その長さ(ビット)は、 448、モジュロ512 に適合している。すなわち、それが 512ビットの倍数長 であることに対し、ほんの 64ビットのメッセージを遠慮がちに拡張する。 たとえメッセージ長が 448、モジュロ512に適合していても、パディングは 常に実行される。 パディングは次の通り実行される: 一つの "1" ビットがメッセージに付 加され、それから "0" ビットが付加される。パディングされたメッセージ のビット長さは 448、モジュロ512に適合する。全体で、最低でも1ビット、 最大で512ビットが付加される。 3.2 [ステップ2] 長さの付加 b (パディングビットが追加される前のメッセージ長)の64ビット表現は、 前のステップの結果に付加される。ありそうもないイベントにおいて、その b は 2^64 を超えるが、その際には b の下位 64 ビットが使われる(これら のビットは、最初に前の規定に従って2つの 32ビットワード、そして、付加 された下位ワードとして付加される)。 この時に、結果として生じるメッセージ(ビットとbによってパディングさ れた後)は、512ビットの正確な倍数である長さを持っている。同等に、この メッセージは 16(32ビット)のワードの正確な倍数である長さを持っている。 M[0 ... N-1] は、Nが16の倍数である結果として生じているメッセージの ワードを示す。 3.3 [ステップ3] 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 98 ワード D: 76 54 32 10 3.4 [ステップ4] 16ワード長のブロックメッセージの処理 まず最初に、3つの32ビットワードを入力し、1つの32ビットワードを出力 する 4つの補助関数を定義する。 F(X,Y,Z) = XY ∨ not(X) Z G(X,Y,Z) = XZ ∨ Y not(Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X ∨ not(Z)) 各ビットポジションにおいて、F は条件分岐の役割を果たす: もし X な らば Y、さもなくば Z である。関数Fは、XY以来の ∨ の代わりに + を用い て定義され、そして not(X)Z は、同じビットポジションに 1 のものを決し て持たない。もし X、Y、Z のビットが独立で公平ならば、個々のビットの F（X、Y、Z）が独立であり公平であることに注意することは興味深い。 X、Y、Z の対応したビットが独立で、公平である時、G(X,Y,Z), H(X,Y,Z), そして I(X,Y,Z) の個々のビットは独立で、公平である。そのような時、そ れらの出力を X、Y、Z のビットから示すために "bitwise parallel" にお いてそれらが作動するという点で、関数G、H、Iは、関数Fと類似している。 関数 H がその入力の bit-wise "xor" または "パリティ" 関数であること に注意しなさい。 このステップは64要素テーブル T[1 ... 64] sin関数から構成される。 T[i] に、iがラジアンにあり abs(sin(i)) の 4294967296倍の整数部分と 等しいテーブルの i-th 要素を示す。テーブル要素は付録を参照のこと。 下記をしなさい: /* 各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 [ステップ5] 出力 A, B, C, D というメッセージダイジェストが産み出される。すなわち、A の下位バイトから開始され、Dの上位バイトによって終わる。 これは、 MD5 の記述を完了する。Cにおける参照インプリメンテーション については付録において与えられる。 4. 要約 MD5メッセージダイジェストアルゴリズムは、実装が容易で、任意の長さ のメッセージから "fingerprint" (指紋) またはメッセージダイジェストが 提供される。同じメッセージダイジェストを持つ 2 つのメッセージに追い つくことの難易度が 2^64 オペレーションのオーダにあり、かつ、あらゆる メッセージに追いつくことの難易度があるメッセージダイジェストを持って いることが 2^128 オペレーションのオーダにあるということが推測される。 MD5アルゴリズムは脆弱性のために慎重に吟味された。しかし、それは相対 的に新しいアルゴリズムであり、そして、この分類のどのような新しい提案 によるケースと同様に、より一層のセキュリティ分析は当然である。 5. MD4とMD5の違い 以下はMD4とMD5の違いである: 1. 4番目のラウンドが追加された。 2. 現在の各ステップは一意の付加的定数を持っている。 3. ラウンド2の機能gは、gをあまり均整がとれた状態にしないよう に、(XY ∨ XZ ∨ YZ) から (XZ ∨ Y not(Z)) に変更された。 4. 現在の各ステップに、前のステップの結果を加える。これは、 更に速い「なだれ効果」を促進する。 5. ラウンド2と3でアクセスされるオーダは、これらのパターンが 相互に少なくなるように、変更された。 6. 更に速い「なだれ効果」をもたらすために、各ラウンドにおける シフト量は、かなり最適化された。シフト量はラウンドごとに異 なる。 参考資料 [1] Rivest, R., "The MD4 Message Digest Algorithm", RFC 1320, MIT and RSA Data Security, Inc., April 1992. [2] Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90 Proceedings, pages 303-311, Springer-Verlag, 1991. [3] CCITT Recommendation X.509 (1988), "The Directory - Authentication Framework." 付録 A - 参照インプリメンテーション この付録は、RSAREF から取り去られた以下のファイルを含んでいる: プライバシー強化メールのための暗号法のツールキット: global.h -- グローバルヘッダファイル md5.h -- MD5のためのヘッダファイル md5c.c -- MD5のためのソースコード RSAREFの詳細については 宛に電子メールを。 付録は以下のファイルも含む： mddriver.c -- MD2, MD4, およびMD5のためのテストドライバ ドライバはMD5のためにデフォルトで編集するが、もしCコンパイラのコマ ンドラインにおいてシンボルMDが2または4として定義されるならば、MD2ま たはMD4のために編集できるであろう。 インプリメンテーションはポータブルで、多くの異なるプラットフォーム に取り組めるはずである。だが、特別なプラットフォームでのインプリメン ト、読者に残された演習を最適化することは、難しいことではない。例えば 32ビットワードの最下位アドレスのバイトが最下位であり、アラインメント 制限が全くない "little-endian" プラットフォームについて、MD5Transform において解読する呼び出しは、役を当てられることと交換できる。 A.1 global.h /* GLOBAL.H - RSAREFタイプと定数 */ /* もしコンパイラがファンクション引数プロトタイピングをサポートするな ら、PROTOTYPES はそれに設定されるべきである。 それがCコンパイラフラグによってまだ定義されていなかったならば、デフォ ルトで PROTOTYPES は 0 になる。 */ #ifndef PROTOTYPES #define PROTOTYPES 0 #endif /* POINTERは一般的なポインタタイプを定義する */ typedef unsigned char *POINTER; /* UINT2 は2バイトワードを定義する */ typedef unsigned short int UINT2; /* UINT4 は4バイトワードを定義する */ typedef unsigned long int UINT4; /* PROTO_LIST は、PROTOTYPES の定義上に応じて定義される。 PROTOTYPES を使っていれば、PROTO_LIST はリストを返す、さもなくば、 それは空のリストを返す。 */ #if PROTOTYPES #define PROTO_LIST(list) list #else #define PROTO_LIST(list) () #endif A.2 md5.h /* MD5.H - MD5C.Cのためのヘッダファイル */ /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All rights reserved. もしそれそれが、このソフトウェアまたはこの機能に言及するか、または参照 を付けているすべての素材の「RSA Data Security, Inc. MD5 メッセージダイ ジェストアルゴリズム」と確認されるならば、このソフトウェアをコピーし、 用いるためにライセンスは与えられる。 ライセンスは、同じく得られたワークに言及するか、もしくは参照を付け る材料全てにおいて「RSA Data Security, Inc. MD5 メッセージダイジェスト アルゴリズムから得られた」ように、そのような作品が確認される限り、派生 した仕事を行って、使うことを認められる。 RSA Data Security, Inc. は、どのような特定の目的のためにでも、このソフ トウェアの市販性またはこのソフトウェアの適合性についての説明は行なわな い。それは、あらゆる表現や暗黙の保証なしで "ありのまま" 供給される。 これらの通知は、このドキュメンテーションおよび／またはソフトウェアのど のような部分のどのようなコピーにおいても保たれねばならない。 */ /* MD5 前後関係. */ typedef struct { UINT4 state[4]; /* state (ABCD) */ UINT4 count[2]; /* ビット数、モジュロ2＾64 (lsb first) */ unsigned char buffer[64]; /* input buffer */ } MD5_CTX; void MD5Init PROTO_LIST ((MD5_CTX *)); void MD5Update PROTO_LIST ((MD5_CTX *, unsigned char *, unsigned int)); void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *)); A.3 md5c.c /* MD5C.C - RSA Data Security, Inc., MD5 メッセージダイジェスト アルゴリズム */ /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All rights reserved. もしそれそれが、このソフトウェアまたはこの機能に言及するか、または参照 を付けているすべての素材の「RSA Data Security, Inc. MD5 メッセージダイ ジェストアルゴリズム」と確認されるならば、このソフトウェアをコピーし、 用いるためにライセンスは与えられる。 ライセンスは、同じく得られたワークに言及するか、もしくは参照を付け る材料全てにおいて「RSA Data Security, Inc. MD5 メッセージダイジェスト アルゴリズムから得られた」ように、そのような作品が確認される限り、派生 した仕事を行って、使うことを認められる。 RSA Data Security, Inc. は、どのような特定の目的のためにでも、このソフ トウェアの市販性またはこのソフトウェアの適合性についての説明は行なわな い。それは、あらゆる表現や暗黙の保証なしで "ありのまま" 供給される。 これらの通知は、このドキュメンテーションおよび／またはソフトウェアのど のような部分のどのようなコピーにおいても保たれねばならない。 */ #include "global.h" #include "md5.h" /* MD5Transformルーチンのための定数. */ #define S11 7 #define S12 12 #define S13 17 #define S14 22 #define S21 5 #define S22 9 #define S23 14 #define S24 20 #define S31 4 #define S32 11 #define S33 16 #define S34 23 #define S41 6 #define S42 10 #define S43 15 #define S44 21 static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64])); static void Encode PROTO_LIST ((unsigned char *, UINT4 *, unsigned int)); static void Decode PROTO_LIST ((UINT4 *, unsigned char *, unsigned int)); static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int)); static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int)); static unsigned char PADDING[64] = { 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /* F, G, H そして I は、基本的な MD5 関数である. */ #define F(x, y, z) (((x) & (y)) | ((~x) & (z))) #define G(x, y, z) (((x) & (z)) | ((y) & (~z))) #define H(x, y, z) ((x) ^ (y) ^ (z)) #define I(x, y, z) ((y) ^ ((x) | (~z))) /* ROTATE_LEFTは x を左にnビット回転させる。 */ #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) /* FF, GG, HH および II は、ラウンド 1, 2, 3, および 4 で変形される。 回転は、再計算を防止するため、付加と分離している。 */ #define FF(a, b, c, d, x, s, ac) { \ (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \ (a) = ROTATE_LEFT ((a), (s)); \ (a) += (b); \ } #define GG(a, b, c, d, x, s, ac) { \ (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \ (a) = ROTATE_LEFT ((a), (s)); \ (a) += (b); \ } #define HH(a, b, c, d, x, s, ac) { \ (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \ (a) = ROTATE_LEFT ((a), (s)); \ (a) += (b); \ } #define II(a, b, c, d, x, s, ac) { \ (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \ (a) = ROTATE_LEFT ((a), (s)); \ (a) += (b); \ } /* MD5 初期設定. 新しいコンテクストを書き、MD5オペレーションを開始する。 */ void MD5Init (context) MD5_CTX *context; /* コンテクスト */ { context->count[0] = context->count[1] = 0; /* Load magic initialization constants. */ context->state[0] = 0x67452301; context->state[1] = 0xefcdab89; context->state[2] = 0x98badcfe; context->state[3] = 0x10325476; } /* MD5ブロックアップデートオペレーション. MD5メッセージダイジェストオペ レーションを続けて、別のメッセージブロックを処理し、コンテクストをアッ プデートする。 */ void MD5Update (context, input, inputLen) MD5_CTX *context; /* コンテクスト */ unsigned char *input; /* 入力ブロック */ unsigned int inputLen; /* 入力ブロック長 */ { unsigned int i, index, partLen; /* バイト mod 64の値を計算する */ index = (unsigned int)((context->count[0] >> 3) & 0x3F); /* ビットの数をアップデートする */ if ((context->count[0] += ((UINT4)inputLen << 3)) < ((UINT4)inputLen << 3)) context->count[1]++; context->count[1] += ((UINT4)inputLen >> 29); partLen = 64 - index; /* 何度でも変換することができる。 */ if (inputLen >= partLen) { MD5_memcpy ((POINTER)&context->buffer[index], (POINTER)input, partLen); MD5Transform (context->state, context->buffer); for (i = partLen; i + 63 < inputLen; i += 64) MD5Transform (context->state, &input[i]); index = 0; } else i = 0; /* 残った入力をバッファする */ MD5_memcpy ((POINTER)&context->buffer[index], (POINTER)&input[i], inputLen-i); } /* MD5は完了する. MD5メッセージダイジェスト処理が完了したら、メッセージ ダイジェストを書き、コンテクストをゼロクリアする。 */ void MD5Final (digest, context) unsigned char digest[16]; /* メッセージダイジェスト */ MD5_CTX *context; /* コンテクスト */ { unsigned char bits[8]; unsigned int index, padLen; /* ビット数を保存する */ Encode (bits, context->count, 8); /* 56 mod 64 に引き伸ばす */ index = (unsigned int)((context->count[0] >> 3) & 0x3f); padLen = (index < 56) ? (56 - index) : (120 - index); MD5Update (context, PADDING, padLen); /* 長さを付加する (パディングの前に) */ MD5Update (context, bits, 8); /* ダイジェストの状態を蓄積 */ Encode (digest, context->state, 16); /* 機密情報をゼロクリアする */ MD5_memset ((POINTER)context, 0, sizeof (*context)); } /* MD5の基本的な変換。ブロックに基づく変化状態。 */ static void MD5Transform (state, block) UINT4 state[4]; unsigned char block[64]; { UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; Decode (x, block, 64); /* Round 1 */ FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */ FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */ FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */ FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */ FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */ FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */ FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */ FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */ FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */ FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */ FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */ FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */ FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */ FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */ FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */ FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */ /* Round 2 */ GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */ GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */ GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */ GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */ GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */ GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */ GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */ GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */ GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */ GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */ GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */ GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */ GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */ GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */ GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */ GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */ /* Round 3 */ HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */ HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */ HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */ HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */ HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */ HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */ HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */ HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */ HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */ HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */ HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */ HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */ HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */ HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */ HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */ HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */ /* Round 4 */ II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */ II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */ II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */ II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */ II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */ II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */ II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */ II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */ II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */ II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */ II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */ II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */ II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */ II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */ II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */ II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */ state[0] += a; state[1] += b; state[2] += c; state[3] += d; /* 機密情報のゼロクリア */ MD5_memset ((POINTER)x, 0, sizeof (x)); } /* 符号化された入力 (UINT4) を出力に (unsigned char)。lenは 4の倍数であると仮定する。 */ static void Encode (output, input, len) unsigned char *output; UINT4 *input; unsigned int len; { unsigned int i, j; for (i = 0, j = 0; j < len; i++, j += 4) { output[j] = (unsigned char)(input[i] & 0xff); output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); } } /* デコードした入力(unsigned char) を出力 (UINT4) へ。len は4の倍数であ ると仮定する。 */ static void Decode (output, input, len) UINT4 *output; unsigned char *input; unsigned int len; { unsigned int i, j; for (i = 0, j = 0; j < len; i++, j += 4) output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); } /* 注意: もし可能なら "for loop" を標準の memcpy と交換せよ。 */ static void MD5_memcpy (output, input, len) POINTER output; POINTER input; unsigned int len; { unsigned int i; for (i = 0; i < len; i++) output[i] = input[i]; } /* 注意: もし可能なら "for loop" を標準の memset と交換せよ。 */ static void MD5_memset (output, value, len) POINTER output; int value; unsigned int len; { unsigned int i; for (i = 0; i < len; i++) ((char *)output)[i] = (char)value; } A.4 mddriver.c /* MDDRIVER.C - MD2、MD4、MD5 用のテストドライバ */ /* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All rights reserved. RSA Data Security, Inc. は、どのような特定の目的のためにでも、このソフ トウェアの市販性またはこのソフトウェアの適合性についての説明は行なわな い。それは、あらゆる表現や暗黙の保証なしで "ありのまま" 供給される。 これらの通知は、このドキュメンテーションおよび／またはソフトウェアのど のような部分のどのようなコピーにおいても保たれねばならない。 */ /* もしそれがCコンパイラフラグによって定義されていなかったなら、デフォ ルトで MD は MD5 になる。 */ #ifndef MD #define MD MD5 #endif #include #include #include #include "global.h" #if MD == 2 #include "md2.h" #endif #if MD == 4 #include "md4.h" #endif #if MD == 5 #include "md5.h" #endif /* テストブロック長、テストブロック数 */ #define TEST_BLOCK_LEN 1000 #define TEST_BLOCK_COUNT 1000 static void MDString PROTO_LIST ((char *)); static void MDTimeTrial PROTO_LIST ((void)); static void MDTestSuite PROTO_LIST ((void)); static void MDFile PROTO_LIST ((char *)); static void MDFilter PROTO_LIST ((void)); static void MDPrint PROTO_LIST ((unsigned char [16])); #if MD == 2 #define MD_CTX MD2_CTX #define MDInit MD2Init #define MDUpdate MD2Update #define MDFinal MD2Final #endif #if MD == 4 #define MD_CTX MD4_CTX #define MDInit MD4Init #define MDUpdate MD4Update #define MDFinal MD4Final #endif #if MD == 5 #define MD_CTX MD5_CTX #define MDInit MD5Init #define MDUpdate MD5Update #define MDFinal MD5Final #endif /* メインドライバ. 引数 (組み合わせは任意): -sstring - ダイジェスト文字列 -t - 実行タイムトライアル -x - 実行テストスクリプト filename - ダイジェストファイル (none) - ダイジェスト標準入力 */ int main (argc, argv) int argc; char *argv[]; { int i; if (argc > 1) for (i = 1; i < argc; i++) if (argv[i][0] == '-' && argv[i][1] == 's') MDString (argv[i] + 2); else if (strcmp (argv[i], "-t") == 0) MDTimeTrial (); else if (strcmp (argv[i], "-x") == 0) MDTestSuite (); else MDFile (argv[i]); else MDFilter (); return (0); } /* ダイジェスト文字列と結果をプリントする */ static void MDString (string) char *string; { MD_CTX context; unsigned char digest[16]; unsigned int len = strlen (string); MDInit (&context); MDUpdate (&context, string, len); MDFinal (digest, &context); printf ("MD%d (\"%s\") = ", MD, string); MDPrint (digest); printf ("\n"); } /* TEST_BLOCK_COUNT TEST_BLOCK_LENバイトブロックの処理時間を測定 */ static void MDTimeTrial () { MD_CTX context; time_t endTime, startTime; unsigned char block[TEST_BLOCK_LEN], digest[16]; unsigned int i; printf ("MD%d time trial. Digesting %d %d-byte blocks ...", MD, TEST_BLOCK_LEN, TEST_BLOCK_COUNT); /* Initialize block */ for (i = 0; i < TEST_BLOCK_LEN; i++) block[i] = (unsigned char)(i & 0xff); /* Start timer */ time (&startTime); /* Digest blocks */ MDInit (&context); for (i = 0; i < TEST_BLOCK_COUNT; i++) MDUpdate (&context, block, TEST_BLOCK_LEN); MDFinal (digest, &context); /* Stop timer */ time (&endTime); printf (" done\n"); printf ("Digest = "); MDPrint (digest); printf ("\nTime = %ld seconds\n", (long)(endTime-startTime)); printf ("Speed = %ld bytes/second\n", (long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime)); } /* ダイジェスト文字列参照スイートと結果をプリントする */ static void MDTestSuite () { printf ("MD%d test suite:\n", MD); MDString (""); MDString ("a"); MDString ("abc"); MDString ("message digest"); MDString ("abcdefghijklmnopqrstuvwxyz"); MDString ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); MDString ("1234567890123456789012345678901234567890\ 1234567890123456789012345678901234567890"); } /* ダイジェストファイルと結果をプリントする */ static void MDFile (filename) char *filename; { FILE *file; MD_CTX context; int len; unsigned char buffer[1024], digest[16]; if ((file = fopen (filename, "rb")) == NULL) printf ("%s can't be opened\n", filename); else { MDInit (&context); while (len = fread (buffer, 1, 1024, file)) MDUpdate (&context, buffer, len); MDFinal (digest, &context); fclose (file); printf ("MD%d (%s) = ", MD, filename); MDPrint (digest); printf ("\n"); } } /* ダイジェスト標準入力と結果をプリントする */ static void MDFilter () { MD_CTX context; int len; unsigned char buffer[16], digest[16]; MDInit (&context); while (len = fread (buffer, 1, 16, stdin)) MDUpdate (&context, buffer, len); MDFinal (digest, &context); MDPrint (digest); printf ("\n"); } /* メッセージダイジェストを 16進でプリントする. */ static void MDPrint (digest) unsigned char digest[16]; { unsigned int i; for (i = 0; i < 16; i++) printf ("%02x", digest[i]); } A.5 テストスイート MD5テストスイート（ドライバオプション "-x"）は、以下の結果をプリン トするべきだ: MD5 test suite: MD5 ("") = d41d8cd98f00b204e9800998ecf8427e MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661 MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72 MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0 MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f MD5 ("123456789012345678901234567890123456789012345678901234567890123456 78901234567890") = 57edf4a22be3c955ac49da2e2107b67a セキュリティ対策 このメモにおいて議論されたセキュリティのレベルは、MD5および公開鍵暗 号に基づく非常に高いセキュリティハイブリッド電子署名計画を実装するの に十分であると考えられる。 奥付 Ronald L. Rivest Massachusetts Institute of Technology Laboratory for Computer Science NE43-324 545 Technology Square Cambridge, MA 02139-1986 Phone: (617) 253-5880 EMail: rivest@theory.lcs.mit.edu