「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタ

先ほどの投稿（
「数字6桁パスワードのMD5ハッシュ値の総当たり」Scalaは1.70秒だった）ではScalaで書いてみましたが、最終的に1秒を切ることができませんでした。なんだか悔しいので、Cでガリガリ実装してOpenMP化してみることにします。

MD5アルゴリズムの実装をどうしようか

.net framework 4.5の場合、System.Security.Cryptography.MD5が提供されています。なのでC#からでもC++/CLIからでもさくっと実装することができるでしょう。しかし速度を求めてC実装をしようとしている時に、.net frameworkを使うのはなにかに負ける気がします。
opensslライブラリにもMD5ハッシュ関数がありますが、開発環境がWindowsである関係上、環境構築が面倒です。

ということで、下記で公開されているC実装を利用させてもらうことにしました。
http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5

環境

Winodws7 Pro SP1 64bit/Corei7-3770K/Visual Studio Express 2013 for Windows Desktop

C++で実装してみた

ということで、まずはC++で実装してみました。

MD5FindPassword.cpp

#include <iostream>
#include <sstream>
#include <iomanip>
#include "md5.h"

#define MD5_DIGEST_LENGTH 16

int main(int argc, char* argv[])
{
	if (argc != 3) return 1;

	const char* SALT = argv[1];
	const char* PW = argv[2];

	unsigned char hash[MD5_DIGEST_LENGTH];
	MD5_CTX ctx;
	std::stringstream origin, result;

	for (int i = 0; i < 1000000; i++) {
		origin.str("");
		origin << SALT << "$" << std::setw(6) << std::setfill('0') << i;

		MD5_Init(&ctx);
		MD5_Update(&ctx, origin.str().c_str(), (unsigned long)origin.str().size());
		MD5_Final(hash, &ctx);

		result.str("");
		for (int j = 0; j < MD5_DIGEST_LENGTH; j++) {
			result << std::setw(2) << std::setfill('0')<< std::hex << int(hash[j]);
		}
		if (result.str() == PW) {
			std::cout << "match";
			std::cout << "[" << std::setw(6) << std::setfill('0') << i << "]";
			std::cout << std::endl;
		}
	}
	return 0;
}

おっと、ビルドエラーになりました。md5.cで実装されている以下の関数を解決できないようです。

• void MD5_Init(MD5_CTX *ctx)
• MD5_Update(MD5_CTX *ctx, const void *data, unsigned long size)
• MD5_Final(unsigned char *result, MD5_CTX *ctx)

上記で公開されているライブラリはC用なので、md5.hにextern "C"を加える必要がありましたね。

md5.h

#ifdef HAVE_OPENSSL
#include <openssl/md5.h>
#elif !defined(_MD5_H)
#define _MD5_H

/* Any 32-bit or wider unsigned integer data type will do */
typedef unsigned int MD5_u32plus;

typedef struct {
	MD5_u32plus lo, hi;
	MD5_u32plus a, b, c, d;
	unsigned char buffer[64];
	MD5_u32plus block[16];
} MD5_CTX;

//extern void MD5_Init(MD5_CTX *ctx);
//extern void MD5_Update(MD5_CTX *ctx, const void *data, unsigned long size);
//extern void MD5_Final(unsigned char *result, MD5_CTX *ctx);

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
	extern void MD5_Init(MD5_CTX *ctx);
	extern void MD5_Update(MD5_CTX *ctx, const void *data, unsigned long size);
	extern void MD5_Final(unsigned char *result, MD5_CTX *ctx);
#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif

さて、実行してみると・・・あれっ 7.30秒？？
・・・streamまわりのメモリチューニングをしなければいけない気がします。が面倒なのでさくっとC++はあきらめC実装にしてしまいます。

Cで実装してみた

md5.hの修正も必要ありませんし、最初からCで書けばよかった。。。いろいろ面倒になったので、バッファも固定サイズにしてしまっています。

MD5FindPassword.c

#include <stdio.h>
#include <string.h>
#include "md5.h"

#define MD5_DIGEST_LENGTH 16

int main(int argc, char* argv[])
{
	char origin[256];
	char hex[3];
	char result[MD5_DIGEST_LENGTH * 2 + 1];
	unsigned char hash[MD5_DIGEST_LENGTH];
	MD5_CTX ctx;
	int i, j;

	if (argc != 3) return 1;

	char* SALT = argv[1];
	char* PW = argv[2];

	for (i = 0; i < 1000000; i++) {
		result[0] = '\0';
		sprintf_s(origin, sizeof(origin), "%s$%06d", SALT, i);

		MD5_Init(&ctx);
		MD5_Update(&ctx, origin, (unsigned long)strlen(origin));
		MD5_Final(hash, &ctx);
		for (j = 0; j < MD5_DIGEST_LENGTH; j++) {
			sprintf_s(hex, sizeof(hex), "%02x", hash[j]);
			strcat_s(result, sizeof(result), hex);
		}
		if (strcmp(result, PW) == 0) {
			printf("match[%06d]\n", i);
		}
	}

	return 0;
}

2.89秒でした。うーん、やはりシングルスレッドでは1秒を切ることができませんか。
ということで、OpenMPで並列化してみましょう。

OpenMP化してみた

最近のVisualStudioは、特に追加ライブラリを導入しなくともOpenMP化することができます。便利ですね。
メニューから［プロジェクト］>［(プロジェクト名)のプロパティ］>［構成プロパティ］>［C/C++］>［言語］とたどり、［OpenMPのサポート］を はい(/openmp) に変更します。

MD5FindPassword_OpenMP.c

#include <stdio.h>
#include <string.h>
#include <omp.h>
#include "md5.h"

#define MD5_DIGEST_LENGTH 16

int main(int argc, char* argv[])
{
	char origin[256];
	char hex[3];
	char result[MD5_DIGEST_LENGTH * 2 + 1];
	unsigned char hash[MD5_DIGEST_LENGTH];
	MD5_CTX ctx;
	int i, j;

	if (argc != 3) return 1;
	char* SALT = argv[1];
	char* PW = argv[2];

	#pragma omp parallel private(origin, hex, result, hash, ctx, i, j)
	{
		#pragma omp for
		for (i = 0; i < 1000000; i++) {
			result[0] = '\0';
			sprintf_s(origin, sizeof(origin), "%s$%06d", SALT, i);

			MD5_Init(&ctx);
			MD5_Update(&ctx, origin, (unsigned long)strlen(origin));
			MD5_Final(hash, &ctx);
			for (j = 0; j < MD5_DIGEST_LENGTH; j++) {
				sprintf_s(hex, sizeof(hex), "%02x", hash[j]);
				strcat_s(result, sizeof(result), hex);
			}
			if (strcmp(result, PW) == 0) {
				printf("match[%06d]\n", i);
			}
		}
	}

	return 0;
}

pragmaを2つ書くだけで、並列化できます。これだけで、0.70秒になりました。OpenMP素晴らしい。

まとめ

パターン	秒
C++でstringstream	7.30
Cでsprintf_sとstrcat_s	2.89
OpenMPで並列化	0.70

私はまだC++力の修行が足りませんね。しかしOpenMP素晴らしい。