JavaScriptでMD5を実装してみた
2021/04/04更新
「個人的実験」のカテゴリでは、私が個人的な興味に基づいて、単に勉強や考察のためにやってみたことをまとめています。実用性を意識した内容ではありませんので、ご了承下さい。
目次
はじめに
MD5（Message Digest Algorithm 5）は、古くから使われている暗号学的ハッシュ関数の一つである。その仕様はRFC 1321として公開されており、仕様通りに実装するだけであれば意外にもそれほど難しくなく、むしろ手頃な練習問題と言える。JavaScriptを使って自力での実装を試みた。
実装
入力
MD5は、バイト列を入力とする。JavaScriptでバイト列を扱うには、ArrayBufferが使いやすいため、ArrayBufferを受け取る関数を実装するものとする。
後の使用のため、受け取ったArrayBufferからUint8Arrayを作っておく。
const md5 = function(input) {
// inputはArrayBuffer
// ArrayBufferからUint8Arrayを作っておく
const inputArray = new Uint8Array(input);
// 入力の長さ（byte）
const inputLength = input.byteLength;
…
};
なお、MD5の仕様上は、入力はバイト単位でないビット列であってもよいが、コンピュータ上のデータは通常バイト単位となっているため、ここではバイト単位の入力のみを受け付けるものとする。
前処理
まず、入力されたバイト列に対してパディングを行なう。パディングは、バイト列の後ろに9～73バイトを追加して全体のバイト数が64の倍数になるようにする。具体的に考えてみると、例えば、入力が0～55バイトであれば、パディング後のバイト列は64バイト、入力が56～119バイトであれば、パディング後のバイト列は128バイトとなる。パディング後のバイト数は以下の式で求められる。
パディング後のバイト数 = (int((入力のバイト数 + 8) / 64) + 1) * 64
パディング部分の先頭バイトには、固定値0x80を格納する（正確には「パディングの先頭ビットを1にする」であるが、今回はバイト単位で考えているので、常に0x80となる）。また、末尾8バイトには、入力のビット数（＝バイト数×8）をリトルエンディアンの64ビット符号無し整数として格納する。それ以外の部分は全て0とする。
// パディング後のバイト数
const dataLength = (Math.floor((inputLength + 8) / 64) + 1) * 64;
// パディング後のデータを格納する配列
const dataArray = new Uint8Array(dataLength);
// 入力データをコピー
dataArray.set(inputArray);
// リトルエンディアンで扱うためDataViewを用意
const dataView = new DataView(dataArray.buffer);
// パディング部分の先頭に0x80を格納
dataView.setUint8(inputLength, 0x80);
// パディング部分の末尾に入力ビット数をリトルエンディアンで格納
dataView.setUint32(dataLength - 8, inputLength * 8, true);
リトルエンディアン（Wikipedia）というのは、多バイト数値の下位バイトをバイト列の先に置く方式のことである。つまり、0x01234567という数値を格納する場合、バイト列は0x67 0x45 0x23 0x01という順になるということである。これを逆に上位バイトを先にして0x01 0x23 0x45 0x67とする方式はビッグエンディアンという。JavaScriptでは、型付き配列でバイト列と数値の変換を行なうとエンディアンが保証されない（環境に依存する）ため、代わりにエンディアンの指定が可能なDataViewを使う。
JavaScriptでは通常64ビット整数は扱えないため、ビット数の格納は32ビット整数で代用する。すなわち、入力されるバイト列のサイズは、2の32乗ビット = 4Gib（= 512MiB = 536,870,912バイト）未満の範囲内に収まっているものとする。
定数類の定義
次いで、計算に使うための定数や関数を定義する。
まず計算用のバッファとして、4つの32ビット符号無し整数を初期化しておく。このバッファの値が入力データにしたがって次々と更新されていき、最終的にMD5の出力となる。
// 計算用バッファの初期化
const bufferArray = new Uint32Array([0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476]);
計算に使う定数として、sin関数を使って作られる64個の32ビット符号無し整数を以下のように定義する。
// 計算用の定数
const T = new Uint32Array(64); {
for (let i = 0; 64 > i; i++) {
T[i] = Math.floor(0x100000000 * Math.abs(Math.sin(i + 1)));
}
}
さらに、ビット演算を行なう4つの関数を以下のように定義する。&はビットごとの論理積、|はビットごとの論理和、^はビットごとの排他的論理和、~はビットごとの反転（否定）である。計算の優先順位は&の方が|より上である。
// 計算用の関数
const F = [
(x, y, z) => x & y | ~x & z,
(x, y, z) => x & z | y & ~z,
(x, y, z) => x ^ y ^ z,
(x, y, z) => y ^ (x | ~z)
];
メインの計算
いよいよメインの計算に入る。このステップでは、以下の処理をデータの先頭から最後まで順にくり返していく。
その時点での計算用バッファの値を保存しておく（※1）。
パディングを施した入力データから、リトルエンディアンで32ビット符号無し整数を16個ずつ（=64バイトずつ）取り出す。
これから述べる64の計算を行なって、計算用バッファの値を更新する（※2）。
保存してあったバッファの値※1を、更新されたバッファ※2に加える。
パディングを施したデータのバイト数は必ず64の倍数になっているため、64バイトずつ取り出していくと必ず過不足なく最後まで到達できる。なお、パディングの時と同様に、ここでも「リトルエンディアンで取り出す」というのが注意点である。
データのバイト列が以下のように並んでいた場合 0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF … リトルエンディアンで32ビット符号無し整数を取り出すと以下のようになる。 0x67452301, 0xEFCDAB89, …
今、入力データから取り出した16個の32ビット符号無し整数をwords[0]～words[15]とする。また、計算用バッファの4つの値をA、B、C、Dとする。これに対して以下の64の計算を行なう。なお、計算は全て32ビットの範囲内で行なわれるので、加算で桁あふれしたものは切り捨てて32ビットとする。
Pn(XYZW, k, s, i) は以下の操作と定義する。 X = Y + ((X + F[n](Y, Z, W) + words[k] + T[i]) <<< s) P0(ABCD, 0, 7, 0); P0(DABC, 1,12, 1); P0(CDAB, 2,17, 2); P0(BCDA, 3,22, 3); P0(ABCD, 4, 7, 4); P0(DABC, 5,12, 5); P0(CDAB, 6,17, 6); P0(BCDA, 7,22, 7); P0(ABCD, 8, 7, 8); P0(DABC, 9,12, 9); P0(CDAB,10,17,10); P0(BCDA,11,22,11); P0(ABCD,12, 7,12); P0(DABC,13,12,13); P0(CDAB,14,17,14); P0(BCDA,15,22,15); P1(ABCD, 1, 5,16); P1(DABC, 6, 9,17); P1(CDAB,11,14,18); P1(BCDA, 0,20,19); P1(ABCD, 5, 5,20); P1(DABC,10, 9,21); P1(CDAB,15,14,22); P1(BCDA, 4,20,23); P1(ABCD, 9, 5,24); P1(DABC,14, 9,25); P1(CDAB, 3,14,26); P1(BCDA, 8,20,27); P1(ABCD,13, 5,28); P1(DABC, 2, 9,29); P1(CDAB, 7,14,30); P1(BCDA,12,20,31); P2(ABCD, 5, 4,32); P2(DABC, 8,11,33); P2(CDAB,11,16,34); P2(BCDA,14,23,35); P2(ABCD, 1, 4,36); P2(DABC, 4,11,37); P2(CDAB, 7,16,38); P2(BCDA,10,23,39); P2(ABCD,13, 4,40); P2(DABC, 0,11,41); P2(CDAB, 3,16,42); P2(BCDA, 6,23,43); P2(ABCD, 9, 4,44); P2(DABC,12,11,45); P2(CDAB,15,16,46); P2(BCDA, 2,23,47); P3(ABCD, 0, 6,48); P3(DABC, 7,10,49); P3(CDAB,14,15,50); P3(BCDA, 5,21,51); P3(ABCD,12, 6,52); P3(DABC, 3,10,53); P3(CDAB,10,15,54); P3(BCDA, 1,21,55); P3(ABCD, 8, 6,56); P3(DABC,15,10,57); P3(CDAB, 6,15,58); P3(BCDA,13,21,59); P3(ABCD, 4, 6,60); P3(DABC,11,10,61); P3(CDAB, 2,15,62); P3(BCDA, 9,21,63);
計算式の中のx <<< sは、xを左方向へs桁ビットローテートすることを表している。JavaScriptには直接対応する演算子は無いが、ビット演算を組み合わせてx << s | x >>> 32 - sとすれば等価な演算となる。
この64の計算式は、64行そのまま書いても問題無いが、以下の通りある程度規則性があるため、事前に引数となる数字を用意して、for文でコードを短く書くことにする。
iは0～63が順に並んでいるだけである。nはiを16で割った整数部分に等しいので、Math.floor(i / 16)やi >> 4でこちらも簡単に計算できる。Xはiを4で割った余りに応じて、A→D→C→Bと変化しているから(64 - i) % 4で対応するbufferArrayの0～3の要素番号を求めればよい。同様に、Yは(65 - i) % 4、Zは(66 - i) % 4、Wは(63 - i) % 4で対応する要素番号が得られる。kは16個ごとに異なる等差数列となっている。iを16で割った余りをjとすると、最初の16個は0 + 1 * j、次は1 + 5 * j、その次は5 + 3 * j、そして最後は0 + 7 * jで計算できる。sだけは、単純な規則性が見えないため、リテラルとして記述する。
以上をふまえて、64パターンの引数を以下のように用意しておく。
const E = []; {
// kの等差数列の係数
const K = [[0, 1], [1, 5], [5, 3], [0, 7]];
// sに使われる値
const S = [[7, 12, 17, 22], [5, 9, 14, 20], [4, 11, 16, 23], [6, 10, 15, 21]];
// 64パターンの引数を事前に計算しておく
for (let i = 0; 64 > i; i++) {
const n = i >> 4;
E[i] = [
n, // n（0～3）
(64 - i) % 4, // X（0～3）
(65 - i) % 4, // Y（0～3）
(66 - i) % 4, // Z（0～3）
(63 - i) % 4, // W（0～3）
(K[n][0] + i * K[n][1]) % 16, // k（0～15）
S[n][i % 4] // s
];
}
}
これで、メインの計算部分は以下のように書ける。ここでは加算時の桁あふれに対する処理は特にしていないが、JavaScriptの整数演算は53ビットまで可能であり、また、計算式中のビット演算や最終的な出力時に32ビットに切り捨てられるので、特に問題ない。
// バッファを一時保存しておく変数
const temp = new Uint32Array(4);
// 取り出した値を入れる変数
const words = new Uint32Array(16);
// 入力データの最初から最後まで64バイトずつくり返し
for (let i = 0; dataLength > i; i += 64) {
// 1. バッファを一時保存しておく
temp.set(bufferArray);
// 2. 入力データから16個の32ビット符号無し整数を取り出す
for (let j = 0; words.length > j; j++) {
// リトルエンディアンで取り出す必要があるため、DataViewを使う
words[j] = dataView.getUint32(i + j * 4, true);
}
// 3. 64の計算を行なってバッファを更新する
for (let j = 0; 64 > j; j++) {
// 用意しておいた引数用の番号を取得する
const [n, x, y, z, w, k, s] = E[j];
// Pn(XYZW, k, s, i)の計算
const t = bufferArray[x] + F[n](bufferArray[y], bufferArray[z], bufferArray[w]) + words[k] + T[j];
bufferArray[x] = bufferArray[y] + (t << s | t >>> 32 - s);
}
// 4. 保存しておいたバッファの値と合算する
for (let j = 0; bufferArray.length > j; j++) {
bufferArray[j] += temp[j];
}
}
出力
これで計算は完了し、最終的に計算用バッファbufferArrayに入っている値がMD5値となる。通常目にする32文字の十六進数は、計算用バッファの4つの値をリトルエンディアンでバイト列化して先頭から出力したものとなる。
バッファの4つの値が以下のようになっていた場合、 0x00112233 0x44556677 0x8899AABB 0xCCDDEEFF リトルエンディアンでバイト列化すると以下のようになり、 0x33 0x22 0x11 0x00 0x77 0x66 0x55 0x44 0xBB 0xAA 0x99 0x88 0xFF 0xEE 0xDD 0xCC 最終的なMD5文字列は以下となる。 3322110077665544bbaa9988ffeeddcc
コードにすると以下のように書ける。
let output = ''; {
// リトルエンディアンを扱うため、DataViewを用意
const resultView = new DataView(new ArrayBuffer(4));
for (let i = 0; bufferArray.length > i; i++) {
// 32ビット符号無し整数をリトルエンディアンでバイト列化
resultView.setUint32(0, bufferArray[i], true);
// 十六進数にして文字列結合していく
output += resultView.getUint32(0).toString(16).padStart(8, '0');
}
}
// 得られた文字列がMD5値
return output;
// 関数「md5」の終わり
};
確認
出力のテスト
作成した関数md5が本当に正しいMD5の値を返すかどうか確認する。
まず、Linuxのmd5sumコマンドで、いくつかの文字列のMD5値を確認する。
: | md5sum # 空文字列 # d41d8cd98f00b204e9800998ecf8427e *- echo -n 'abc' | md5sum # 900150983cd24fb0d6963f7d28e17f72 *- echo -n '0123456789' | md5sum # 781e5e245d69b566979b86e28d23f2c7 *-
作成した関数md5でも同様に試してみる。今回の実装ではArrayBufferしか受け付けられないため、文字列もArrayBufferにして渡す必要があるが、様々な型を受け取れるようにすれば便利になるだろう。
console.log(md5(new Uint8Array([]).buffer)); // 空文字列 // d41d8cd98f00b204e9800998ecf8427e console.log(md5(new Uint8Array([...'abc'].map(s => s.charCodeAt(0))).buffer)) // 900150983cd24fb0d6963f7d28e17f72 console.log(md5(new Uint8Array([...'0123456789'].map(s => s.charCodeAt(0))).buffer)) // 781e5e245d69b566979b86e28d23f2c7
上記の通り、正しい値が得られている。
任意のファイルを使ったテスト
HTML5のFile APIを使うと、ユーザーが指定したローカルファイルを読み取って、その内容を表すArrayBufferオブジェクトを取得できる。これを今回作成したmd5関数に渡せば、任意のローカルファイルのMD5を調べることができるようになる。
<!-- ファイル選択フォーム --> <p><input type="file" id="file_input"></p> <p>MD5: <span id="result"></span></p>
const input = document.getElementById('file_input');
// ファイルが選択されたら実行
input.addEventListener('change', function() {
const file = input.files[0];
const reader = new FileReader();
reader.onload = function() {
// 得られたArrayBufferをmd5関数に渡す
const md5value = md5(reader.result);
document.getElementById('result').innerHTML = md5value;
};
// FileオブジェクトからArrayBufferを得る
reader.readAsArrayBuffer(file);
});
実際に私のローカル環境（Windows 10 (x64)、Chrome 89、8GB RAM、Intel Core i5-8265U CPU）で適当にいくつかのファイルで試したところ、全てmd5sumコマンドによるMD5値と一致していた。
また、実行速度は、10MB程度のファイルで約500ミリ秒、100MB程度のファイルで約5000ミリ秒（5秒）であった（前処理の節で説明している通り、今回の実装では512MiBまでの入力しか対応していない）。ブラウザ環境ということもあり、ネイティブのmd5sumコマンドなどと比べれば圧倒的に遅いが、ArrayBufferなどの使用によりJavaScriptとしては高速に実行できていると思われる。