MD5の実装を読んでみる

簡単なパスワード認証を作ってる関係で、MD5のアルゴリズムについて調べてた。MD5というのはファイルの同一性チェックや電子署名、UNIXのパスワード認証なんかにも使われているハッシュ関数である。

アルゴリズムの詳細は、以下のページで分かりやすく解説されている。

• MD5の計算方法 - BK class
• MD5 - Studying HTTP

MD5の計算は大雑把に言って4つのステップに分けられる。

1. パディングの付加
2. 入力データサイズの付加
3. 計算用バッファの初期化
4. 2.と3.のデータを基に計算

基本的には定義通りに計算を進めていくだけなんだけど、自分で実装しようとして引っかかったのはデータの取り扱い。入出力するデータ型をunsigned char、計算で使う数値型をunsigned long intとすると、両者のデータ型を相互変換するアルゴリズムに少し工夫が必要か。

まだまだC言語初心者だから、RFC1321のサンプルプログラムには参考にすべき点が色々あった。その中でも特に参考になったのがMD5を計算する関数の構成。

MD5を算出するデータっていうのは、短い文字列の場合もあれば、GB単位の巨大ファイルの場合もあるわけで、単純に入力データをメモリに全て格納して計算するっていうわけにはいかない。そこで、このプログラムではMD5を計算する処理を初期化と計算と後処理に分けて、contextという構造体を巧みに使いながら、入力データを適宜分割して計算できるようになってる。

たとえば、サイズが1GBのファイルのMD5ハッシュを計算するとき、サンプルプログラムは以下のような手順で計算を行う。

1. contextの初期化
2. ファイルを1KBごとに分割し、それぞれの部分を処理しつつcontextを更新
3. contextのデータを整えて、最終的なハッシュ値を出力

つまり、入力データが何GBであろうと、計算に必要なメモリは1KBだけだからとってもウマー。本業のプログラマってすげーな。