LoginSignup
22

More than 5 years have passed since last update.

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

Last updated at Posted at 2014-02-15

先ほどの投稿(
「数字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素晴らしい。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
22