まず：PBKDF2って？

Password-Based Key Derivation Function 2
salt、ストレッチング回数、暗号化関数、ハッシュ長を指定できる、saltやストレッチングまで含めた関数のこと。
PBKDFの1もちゃんとあるが、こちらは新規アプリケーションには非推奨。MD2（16byte）、MD5、SHA-1（ともに20byte）を使って短いハッシュを導出するもので、DBのカラム長などの問題でPBKDF2にできないアプリ向けに作られた仕様。
BBKDF2では定義上はハッシュ長は無制限。

使用したライブラリ

Java8なら標準APIで使えます。
javax.crypto以下。

エンコードと認証

Java8のjavax.crypto.SecretKeyFactoryのgetInstanceメソッドに暗号化のアルゴリズムが指定でき、PBKDF2With + [擬似乱数関数名] の文字列を指定すれば、PBKDF2が使えます。
今回は"PBKDF2WithHmacSHA256"。

擬似乱数関数名としてHmacSHA1、HmacSHA256以外に何があるのかはわかりません…。
こちらにアルゴリズムとして使える文字列の仕様が載っているのですが、PBKDF2ではHmacsSHA256しか例がなく。
RFC2898ではHmacsSHA1の記載があるくらいです。

プログラム

認証ではBCryptのような専用メソッドが見つからなかったため（API調査不足かもしれません）、再度ハッシュ化して文字列が一致するかを見ています。

String ALGORITHM = "PBKDF2WithHmacSHA256";
String passStr = "password_desu_4";
int iterateCount = 1024;
int keyLengh = 256;

// ハッシュ化
String hashStr = null;
char[] passCharAry = passStr.toCharArray();

try {
	// 鍵の仕様を指定
	PBEKeySpec keySpec = new PBEKeySpec(passCharAry, salt, iterateCount, keyLengh);
	// ハッシュ化
	SecretKeyFactory skf = SecretKeyFactory.getInstance(ALGORITHM);
	SecretKey sk = skf.generateSecret(keySpec);
	byte[] hashByteAry = sk.getEncoded();

	hashStr = DatatypeConverter.printHexBinary(hashByteAry);

} catch (InvalidKeySpecException e) {
	e.printStackTrace();
} catch (NoSuchAlgorithmException e) {
	e.printStackTrace();
}

	System.out.println("original string   : " + passStr);
	System.out.println("encoded by Bcrypt : " + hashStr);


// 認証（OKパターン）
boolean isMatch = false;
String newHashStr;

// パスワードを再度ハッシュ化、さっきのハッシュに一致するかのチェック
try {
	// 鍵の仕様を指定
	PBEKeySpec keySpec = new PBEKeySpec(passCharAry, salt, iterateCount, keyLengh);
	// ハッシュ化
	SecretKeyFactory skf = SecretKeyFactory.getInstance(ALGORITHM);
	SecretKey sk = skf.generateSecret(keySpec);
	byte[] hashByteAry = sk.getEncoded();

	newHashStr = DatatypeConverter.printHexBinary(hashByteAry);
	
	if (newHashStr.equals(hashStr)) { 
		isMatch = true;
	}

	System.out.println("verifying string  : " + passStr);
	System.out.println("result            : " + (isMatch ? "match" : "not match"));		


// 認証（NGパターン）

String wrongPass = "koreha_chigau_4";
passCharAry = wrongPass.toCharArray();

// 別のパスワードをハッシュ化、さっきのハッシュに一致するかのチェック
try {
	// 鍵の仕様を指定
	PBEKeySpec keySpec = new PBEKeySpec(passCharAry, salt, iterateCount, keyLengh);
	// ハッシュ化
	SecretKeyFactory skf = SecretKeyFactory.getInstance(ALGORITHM);
	SecretKey sk = skf.generateSecret(keySpec);
	byte[] hashByteAry = sk.getEncoded();

	newHashStr = DatatypeConverter.printHexBinary(hashByteAry);
	
	if (newHashStr.equals(hashStr)) { 
		isMatch = true;
	}

	System.out.println("verifying string  : " + passStr);
	System.out.println("result            : " + (isMatch ? "match" : "not match"));

実行結果

original string   : password_desu_4
encoded by Bcrypt : 36349DDA39A2B9ABD4C9BACAD4D7CB38901DA5930D4EB94D58EDE565B223CECA
verifying string  : password_desu_4
result            : match
verifying string  : koreha_chigau_4
result            : not match

ストレッチ回数ごとの処理時間

こちらでは回数をintで直接指定します。
Bcryptの方で計測したものとあわせて、2の4乗から20乗までを試しました。

プログラム

認証部分は、PBKDF2Encode(String passStr, byte[] salt, int iterateCount, int keyLengh)とメソッド化して切り出しています。

String passStr = "password_desu_4";
int keyLength = 256;
byte[] salt = getSHA256salt();

// 範囲は暫定で2の4乗から20乗まで（BCryptに合わせた）
for (int strength=4; strength<=20; strength++) {
	
	int iterateCount = (int) Math.pow(2, strength);
	System.out.println("= iterateCount : " + iterateCount + " ========");

	// 開始時刻
	long startTime = (new Date()).getTime();

	PBKDF2Encode(passStr, salt, iterateCount, keyLength);
	
	// ハッシュ化終了時刻
	long endTime = (new Date()).getTime();
	String timeDelta = String.format("%.4f", ((float)(endTime - startTime) / 1000));
	
    System.out.println("encoding time  : " + timeDelta + " sec.");
}

実行結果

SecretKeyFactoryのインスタンスを使いまわしている関係だと思いますが、最初のみ時間がかかり、あとは速いです。

= iterateCount : 16 ========
encoding time  : 0.371 sec.

= iterateCount : 32 ========
encoding time  : 0.001 sec.

= iterateCount : 64 ========
encoding time  : 0.001 sec.

= iterateCount : 128 ========
encoding time  : 0.001 sec.

= iterateCount : 256 ========
encoding time  : 0.002 sec.

= iterateCount : 512 ========
encoding time  : 0.003 sec.

= iterateCount : 1024 ========
encoding time  : 0.006 sec.

= iterateCount : 2048 ========
encoding time  : 0.007 sec.

= iterateCount : 4096 ========
encoding time  : 0.015 sec.

= iterateCount : 8192 ========
encoding time  : 0.029 sec.

= iterateCount : 16384 ========
encoding time  : 0.063 sec.

= iterateCount : 32768 ========
encoding time  : 0.122 sec.

= iterateCount : 65536 ========
encoding time  : 0.237 sec.

= iterateCount : 131072 ========
encoding time  : 0.481 sec.

= iterateCount : 262144 ========
encoding time  : 0.944 sec.

= iterateCount : 524288 ========
encoding time  : 1.878 sec.

= iterateCount : 1048576 ========
encoding time  : 3.732 sec.

これならBCryptでは断念した2の20乗～31乗もいけるのでは？と試した結果、

BCryptとの処理時間の比較

PBKDFの方はインスタンス生成にかかる時間も加味しないといけないため、上記のような繰り返しではなく個別に測定しなおしました。

ストレッチ回数	Bcrypt	PBKDF2
2^10 = 1024	0.118	0.361
2^11 = 2048	0.240	0.423
2^12 = 4098	0.462	0.429
2^13 = 8192	0.924	0.445
2^14 = 16384	1.847	0.575
2^15 = 32768	3.702	0.497
2^16 = 65536	7.440	0.642
2^17 = 131072	14.867	0.901
2^18 = 262144	30.416	1.451
2^19 = 524288	60.659	2.377
（単位：秒）

BCryptのデフォルトである1024回ではBCryptの方が速いのですが、だいたい5000回あたりから横並び、そして逆転が始まるようです。
BCryptはストレッチング回数が倍になれば処理時間も倍になってますが、PBKDF2はそうでもなく、ゆるやかな上昇。

アルゴリズムの問題でしょうか。ライブラリ（と、ライブラリを抱える言語）によってだいぶ違いそうです。

ソース全文はGitHubに

先日のBCryptのも書き換えて一緒にしてしまっており、ここに貼り付けると長いので気になる方がいたらこちらをご参照ください。