中編です。前編はこちらから。なんか大きくなってしまったので前・中・後の三つに分けます。scryptの実装を詳しく見ていきたいと思います。

何度も言いますがこれはどこか高速化できないかな～ということでコードを実装してみているだけで使用するならライブラリを呼び出せば済みますし、自分のプログラムで使いたいなら出回っているBSDライセンスのコードでも内部に含めればそれで終わりです。でもそんなことをしたくないので実装してみているわけです。

ちなみにこの説明は実質英語で書かれている各論文を日本語訳しているようなものなのでそれぞれのアルゴリズムで日本語の意味がとれない場合も読む価値が無いわけではないと思います。特に個別解説になっているのがうれしいところですか。

外部のアルゴリズムを紹介

前編でも書きましたが使用する外部のアルゴリズムは以下のものがあります。

PBKDF2

RFC2898に定義されているパスワード文字列を特定の鍵と乱数列を作り出す方式を使って別のデータ(派生鍵)へと変換するアルゴリズムです。出力されるデータサイズもある程度自由に決めることができる(その前に定義されているPBKDF1は指定したハッシュ方式のビット長までしか出力できない)のも特徴です。

まず、一つ目の注意点。元の説明文には「疑似乱数列」を使っている、と書かれていますが実際は鍵付きハッシュを使うことが多いようです。このとき、「パスワード文字列が鍵側、ソルト側がテキスト側」になることに気をつけましょう。アルゴリズムでは「ソルト+巡回数」を使用するのでテキスト側の方が使い勝手がいいのでしょうね。

もう一つは「ソルト+巡回数の巡回数をデータ変換すると4byteのビックエンディアン」です。記述が妙に分かりづらいですので解説しておきます。なお、scryptでPBKDF2を使っている箇所の巡回回数は1回だけなのでscrypt用に組むのであればループを展開して記述した方が早いです。

scrypt内では処理されるブロック生成と処理後のブロック結合の両方で使用します。意外と重要な関数ですね。

HMAC-SHA256

HMACはRFC2104、SHA256はFIPS180に書いてあるのでそちらを参考に。すでに組んであったので解説は書きません。SHA256はBitcoinでも使っているので高速化を考えているならすでにあるかもしれませんね。scrypt内では上記のPBKDF2に疑似乱数列生成処理として与えます。

Salsa20/8

これもハッシュアルゴリズムのうちの一つです。ただしハッシュアルゴリズムとして使われるよりストリーム暗号のアルゴリズムとして用いられることが多いようです。scrypt内ではハッシュ処理扱いなのでハッシュとして組んだ方が見やすいですが、そうでないならストリーム暗号として組んだ方が使い勝手がいいかもしれません。

内部的には32bit x(4×4 matrix)で、このマトリクスについてずらしながら(リトルエンディアン変換、)左巡回シフト、32bit加算、排他的論理和(、リトルエンディアン逆変換)を処理単位として組み合わせた処理を行います。定数系は使わないようなのですべてが0のデータを処理するとすべて0がかえってきます。

一応Salsa20が本体で、/8はその処理を制限している(ラウンド数を8に限定している)ルーチンです。本来のラウンド数は20となります。ラウンド数のカウントがややっこしいですが、列処理、行処理それぞれで1ラウンドという扱いなので8だと(列処理、行処理)x4となります。この辺は論文(?)内でわざわざ処理単位を「QuarterRound(1/4ラウンド)」、列処理と行処理をあわせたものを「DoubleRound(2倍ラウンド)」という書き方をしているので少し計算すれば分かると思います。・・・初めに分からなかった人がここに一人・・・。

ハッシュ処理として使用する場合はパディングなどの定義が厳密にない(64byte単位で処理することを目的としているため。一応データが48byteと32byteの時に限りあるともいえるが・・・)ので使いやすいように定めてしまえばいいと思います。まあ、SHA系のように最後にロードしたバイト数をパディングする用に実装するとscryptでは使えなくなってしまうので。

scrypt内ではブロック撹拌時に撹拌用ハッシュ処理として使われます。このハッシュが64byteであると言うことを使いますので注意しましょう。

後編は内部で説明されている処理を組み合わせていく

これらを実装、あるいは使えるようになっていないと以降はかなり難しいです。特にルーチンの置き換えがややこしいことこの上ないです。私も実装してみて各ルーチン間の連絡が訳が分からなくなりそうだったので・・・。