始めに

この記事はAcompany Advent Calendar 2022 16日目です

発端

ハッシュ関数の仕組み等調べてみたところ、opensslの実装を発見。
それを参考に勉強していたが、実装が副作用ライクすぎて嫌になったので、勉強がてらC++で自作、ついでに速度比較をしてみることにした。

この記事の目的

備忘録＋実験記録。
基本的に実用的なライブラリを作成するつもりはないので、学習用途として実装する。
以下を目的として進めていく。

SHA256の理解を深める
opensslの理解を深める
自作sha256がどの程度速度がでるのか検証

SHA256について

最も使われているハッシュ関数と言っても過言ではないやつ。

以下　今回参考にしたもの
SHS論文
 openssl/sha256

実装解説

処理を手順的に書いていき、それらをコードに落としていく。
最終的に総合してクラスの設計にまとめていく。

初期値

SHA2系は最初の初期シードは固定で決められている。
実装時にはクラスのconstexprを使用してstatic定数としてテーブルを用意する形が丸い気がする。

Hash.cpp

    static constexpr size_t BLOCK_SIZE = 64;
    static constexpr std::array<unsigned long, 64> K = {
        0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
        0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
        0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
        0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
        0xe49b69c1UL, 0xefbe4786UL, 0x0fc19dc6UL, 0x240ca1ccUL,
        0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
        0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
        0xc6e00bf3UL, 0xd5a79147UL, 0x06ca6351UL, 0x14292967UL,
        0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
        0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
        0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
        0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
        0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
        0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
        0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
        0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL};
    std::array<unsigned int, 8> H = {0x6a09e667, 0xbb67ae85, 0x3c6ef372,0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19};

　K,Hはどちらも固定値で確保する配列をarrayにした。
正直複雑な処理はしないのでC配列でも良かったが、できる限りモダンな形にしておく。
ちなみにKがハッシュ計算に使う値、HはH0とされているハッシュ値の初期値。
　H0として固定値で保存しても良いが、見たところHを更新していく形なのでそのままHの初期値としておく。

関数群

論文に関数が定義されているので、それを愚直に実装すれば良し。
opensslではマクロで定義されている。
恐らく関数呼び出しのオーバーヘッドを嫌ったのだと思うが、今のコンパイラなら速度的にも十分速いと思うのできちんと関数で定義する。

Hash.cpp

    unsigned int Rot(unsigned int v, int n)
    {
        return (v << n) | (v >> (32 - n));
    }
    unsigned int Shr(unsigned int v, int n)
    {
        return (v >> n);
    }
    unsigned int Sigma0(unsigned int x)
    {
        return Rot(x, 30) ^ Rot(x, 19) ^ Rot(x, 10);
    }
    unsigned int Sigma1(unsigned int x)
    {
        return Rot(x, 26) ^ Rot(x, 21) ^ Rot(x, 7);
    }
    unsigned int sigma0(unsigned int x)
    {
        return Rot(x, 25) ^ Rot(x, 14) ^ Shr(x, 3);
    }
    unsigned int sigma1(unsigned int x)
    {
        return Rot(x, 15) ^ Rot(x, 13) ^ Rot(x, 10);
    }
    unsigned int Ch(unsigned int x, unsigned int y, unsigned int z)
    {
        return (x & y) ^ (~x & z);
    }
    unsigned int Maj(unsigned int x, unsigned int y, unsigned int z)
    {
        return (x & y) ^ (y & z) ^ (x & z);
    }

特に説明すべき点はないが、opensslでは右シフトはマクロが作られておらずそのまま右シフトになっている。

openssl/sha256.c

#  define sigma0(x)       (ROTATE((x),25) ^ ROTATE((x),14) ^ ((x)>>3))

opensslでは命令セットで使用できるものがあれば、そちらをインラインアセンブラで呼び出して高速化しようとしている模様。
ない場合は上記のマクロ。

openssl/sha256.c

# ifndef PEDANTIC
#  if defined(__GNUC__) && __GNUC__>=2 && \
      !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)
#   if defined(__riscv_zknh)
#    define sigma0(x) ({ MD32_REG_T ret;            \
                        asm ("sha256sig0 %0, %1"    \
                        : "=r"(ret)                 \
                        : "r"(x)); ret;             })

メイン処理

ここは何も変える必要ないので、そのまま実装する。
構成としては

メッセージのパディング処理
データのロード処理
計算処理
を関数で作っておけばOK。

パディング処理

メイン処理のために、入力メッセージを64byte毎に区切っておく必要がある。
その際に、
区切り文字0x80(1byte) + 最後に文字列サイズ（8byte）= 9byte
を考慮する必要がある。
例）
　56byteなら56 + 9 = 65 > 64　よりメッセージサイズ128byte
　119byteなら119 + 9 = 128 <= 128 より　メッセージサイズ128byte

難しく考えずに64で割り切れなければ切り上げて64をかければ良い。
ただ今回はブロックサイズが64なのでよいが、ブロックサイズで計算は変わるので注意。

padding.cpp

        auto padding(const std::string &input)
        {
            size_t size = input.size();
            size_t padding_size = ((size + 9 + BLOCK_SIZE - 1) / BLOCK_SIZE) * BLOCK_SIZE;
            std::vector<uint8_t> ret(padding_size);
            for (int i = 0; i < size; i++)
            {
                ret[i] = static_cast<uint8_t>(input[i]);
            }
            ret[size] = 0x80;
            size *= 8;
            ret[padding_size - 4] = static_cast<unsigned int>(size >> 24) & 0xff;
            ret[padding_size - 3] = static_cast<unsigned int>(size >> 16) & 0xff;
            ret[padding_size - 2] = static_cast<unsigned int>(size >> 8) & 0xff;
            ret[padding_size - 1] = static_cast<unsigned int>(size) & 0xff;
            return ret;
        }

データのロード

書いておいてなんだが、特になし。
メッセージブロックをロードするだけ。最初からその型で保存してればよい気がする。
パディング処理の際にまとめてから保存すれば良い。面倒なのでやらない。

load.cpp

        unsigned int loadMessge(const std::vector<uint8_t> &arr, int index)
        {
            unsigned int load{};
            load |= static_cast<unsigned int>(arr[index]) << 24;
            load |= static_cast<unsigned int>(arr[index + 1]) << 16;
            load |= static_cast<unsigned int>(arr[index + 2]) << 8;
            load |= static_cast<unsigned int>(arr[index + 3]);
            return load;
        }

計算処理

以上のデータ、関数を使用して実行する。
元の論文ではここの処理を4工程に分けており分かりやすくなっていたが、opensslではそれらの処理を短縮してループ処理の回数を減らしていた。
そっくりそのままパクる。ただ変数をいちいち8つ用意するのが嫌だったのでここでもarrayを生成。
(結局opensslに合わせて構造化束縛してるし意味はないかも）

sha256.cpp

        auto operator()()
        {
            size_t size = messages.size();
            for (int num = 0; num < size; num += 64)
            {
                unsigned int T1{}, T2{}, s0{}, s1{};
                std::array<unsigned int, 16> X;
                std::array<unsigned int, 8> arr;
                for (int i = 0; i < 8; ++i)
                {
                    arr[i] = H[i];
                }
                auto &[a, b, c, d, e, f, g, h] = arr;
                int t;
                for (t = 0; t < 16; ++t)
                {
                    T1 = X[t] = loadMessge(messages, t * 4);
                    T1 += h + Sigma1(e) + Ch(e, f, g) + K[t];
                    T2 = Sigma0(a) + Maj(a, b, c);
                    h = g;
                    g = f;
                    f = e;
                    e = d + T1;
                    d = c;
                    c = b;
                    b = a;
                    a = T1 + T2;
                }
                for (; t < 64; ++t)
                {
                    s0 = X[(t + 1) & 0x0f];
                    s0 = sigma0(s0);
                    s1 = X[(t + 14) & 0x0f];
                    s1 = sigma1(s1);

                    T1 = X[t & 0xf] += s0 + s1 + X[(t + 9) & 0xf];
                    T1 += h + Sigma1(e) + Ch(e, f, g) + K[t];
                    T2 = Sigma0(a) + Maj(a, b, c);
                    h = g;
                    g = f;
                    f = e;
                    e = d + T1;
                    d = c;
                    c = b;
                    b = a;
                    a = T1 + T2;
                }

                for (int i = 0; i < 8; ++i)
                {
                    H[i] += arr[i];
                }
            }
            return std::make_pair(seed, H);
        }

0x0fはmod 16と読み替えれば良い。論文内ではマイナス表記だったがopensslではmod 16にして負の数をなくしている。

クラス構成

以上を踏まえる。

変数a,b,c,d,e,f,g,hが中心になっている
初期値の定数はコンパイル時定数でOK
内部で出ているM、H系の配列はメモリの使い回しできる
クラスはHash

上記をまとめて最終コード

速度比較

一応本家のopensslと比較してみる。
比較方法はchronoを使った単純な速度比較。
コンパイルオプションは下記

command.bash

clang++-12  -lcrypto Hash.cpp -std=c++20 -o hash -O3

追記：2022/12/20
テストコードを変更。

出力部分を計測に含めていたのを外す
計測時間をnanosecondsに変更　←別にmicroでも良かったがなんとなく

テストコードは下記のものを使用

test.cpp

    std::string message = "helloworld";
    {
        auto start = std::chrono::system_clock::now();

        unsigned char digest[SHA256_DIGEST_LENGTH];

        SHA256_CTX sha_ctx;
        SHA256_Init(&sha_ctx);                                    // コンテキストを初期化
        SHA256_Update(&sha_ctx, message.c_str(), message.size()); // message を入力にする
        SHA256_Final(digest, &sha_ctx);                           // digest に出力

        auto end = std::chrono::system_clock::now();
        double elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        std::cout << elapsed << " nano seconds " << std::endl;
        for (int i = 0; i < sizeof(digest); ++i)
        {
            std::cout << std::setfill('0') << std::setw(2) << std::hex << static_cast<unsigned int>(digest[i]);
            // printf("%x", digest[i]);
        }
        std::cout << std::endl;
        // 処理
    }
    {

        auto start = std::chrono::system_clock::now();
        using namespace sha;
        auto hash = Hash<sha256>::createHash(message);
        auto [seed, hashArray] = hash();
        // std::cout << "seed is " << seed << std::endl;

        auto end = std::chrono::system_clock::now();
        double elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        std::cout << elapsed << " nano seconds " << std::endl;
        for (int i = 0; i < hashArray.size(); ++i)
        {
            std::cout << std::hex << hashArray[i];
        }
        std::cout << std::endl;
    }

結果は以下の通り

3115 nano seconds 
beffc66aa4f9c61496f6a660ae5c203d8de37de5fbd2b0ca2b7068c382e296b6
6769 nano seconds 
fef929cf1ed20d98b3d1b40898206d0459d86e9ebec5932af900dc47fff5c24a

SHAライブラリ	平均速度(ns)
openssl	4595 ns
自作	8721 ns

平均して4000nsほどopensslが速い。（時々逆転していることがあるが平均するとopensslのほうが速い）

遅いのかと思ったが、順番を入れ替えたら同じような結果になったので、速度差はほぼ無いと見てよさそう。
厳密に測れば違うのかもしれないがこれだけ見やすくなってこの程度なら、とりあえず良しとする。

以下注意

opensha.cpp

	char *message = {"Sample Message"};
	unsigned char digest[SHA256_DIGEST_LENGTH];
	
	SHA256_CTX sha_ctx;
	SHA256_Init(&sha_ctx); // コンテキストを初期化
	// SHA256_Update(&sha_ctx, message, sizeof(message)); // message を入力にする
    SHA256_Update(&sha256, string, strlen(string)); //注意！！　こちらに変更する必要がある
	SHA256_Final(digest, &sha_ctx); // digest に出力

	printf("%s\n", message);
	
	for (int i = 0; i < sizeof(digest); ++i) {
		printf("%x", digest[i]);
	}
	printf("\n");

上記のコードでは問題が発生。出力されるハッシュ値が全然違くなってしまう。
とりあえずサンプルのmessageをstringで置き換えたところ他のサイト等での結果とも一致した。
messageの部分で警告が出ていたし、上記の初期化方法にはものすごい違和感があるので、ここが原因だとは思う。
C++　SHA256 opensslで検索したサイトからコピペしたが、sizeofの部分で正常に読み込めていないので修正が必要、
コピペ実行する時は、ハッシュ結果が他の同ハッシュ関数と同じか気を付けたほうが良い

実験結果

コンパイラの進歩のおかげか知らないが速度差はほぼなかった。
速度測定時間が細かくなりすぎているので、もっと大きなバイトでハッシュ値を作成をすれば違いが出るかもしれない。
あとvalarrayとか使えばもう少し早くなるかも？

最後に

ソースコード全体

時間がなかったのでかなり適当な記事になってしまったが、結構面白かったのでやってみて良かった。
実装は別にC++である必要はないので、他の言語版も追加してもよかったかも、Rustとか。
SHA3系も興味深かったので気が乗ったらそちらも記事にまとめる。