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

先ほどの投稿（[
「数字6桁パスワードのMD5ハッシュ値の総当たり」Scalaは1.70秒だった](http://qiita.com/nmatsui/items/dd70fd57d81bdd935f79)）では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++で実装してみました。

```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"``を加える必要がありましたね。

```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で書けばよかった。。。いろいろ面倒になったので、バッファも固定サイズにしてしまっています。

```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)** に変更します。

```c: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素晴らしい。