FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

MD5の実装を読んでみる

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

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

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だけだからとってもウマー。本業のプログラマってすげーな。