C++でハッシュ関数について学んでみる

趣旨

ハッシュ関数の仕組みとそれをC++でどうやって実装しているのかに興味があったのでGPT先生に僕が理解できるまで質問を繰り返し、後で振り返ってもわかりやすいように整理したので共有します。

①シンプルなハッシュ関数

まずは簡易版のハッシュ関数の所作を学びました。

SHA256を利用したハッシュ関数も試そうと思ったんですが、Windowsだとビルドを試すのに身元がよくわからないソフトをインストールしないとできないみたいだったので、安全が確認できる方法を見つけ次第追加するか、続投記事にします。

#include <iostream>
#include <string>

// Hash function definition
unsigned long hashFunction(const std::string& str) {
    unsigned long hash = 5381;
    for (char c : str) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

int main() {
    std::string input;
    std::cout << "Please enter a string: ";
    std::cin >> input;

    // Calculate and output the hash value
    unsigned long hashValue = hashFunction(input);
    std::cout << "Hash value: " << hashValue << std::endl;

    return 0;
}

関数 hashFunction は、与えられた文字列 str のハッシュ値を計算しています。この関数は、非常に一般的なハッシュ関数の一つであるdjb2アルゴリズムをベースにしています。以下にその動作の詳細を記載します。

djb2アルゴリズムについて：

djb2アルゴリズムは、Daniel J. Bernsteinが考案したシンプルで効果的な文字列ハッシュ関数です。このアルゴリズムは、そのシンプルさから広く使われており、特にハッシュテーブルのインデックス計算など、速度が重要な場面でよく使用されます。

初期値の設定：

関数は unsigned long 型の変数 hash を 5381 という数値で初期化します。この値は、djb2アルゴリズムでよく使用される初期値です。この値がハッシュ計算の基点となります。

5381がよく使われるのは、その数値がハッシュ衝突を避けるのに効果的であることが経験的にわかっているからです。別の値を使用してもハッシュ関数は機能します。

ハッシュ値の計算：

入力された文字列 str の各文字 c に対してループ処理を行います。このループでは、各文字に基づいて hash 値を更新しています。

• ハッシュ値を左に5ビットシフト（32倍に相当）
  シフトしたハッシュ値に元のハッシュ値を加える（33倍に相当）
• 現在の文字のASCII値を加える
• この計算は、文字列の全文字に対して繰り返され、最終的なハッシュ値を生成する

ビットシフトを使うことで、入力される文字の小さな変化（例えば文字が一文字変わるだけ）が、ハッシュ値に大きな変化をもたらすようにします。これは「アバランシュ効果」と呼ばれ、良いハッシュ関数の特徴の一つです。

サンプル:

djb2アルゴリズムの具体的な動作を理解するために、シンプルな文字列を例にとって、手順を一歩ずつ追ってみます。ここでは、文字列 "hello" を使用します。初期値として 5381 を持ち、各文字に対してハッシュ値の更新を行います。

Initial hash value: hash = 5381
For each character in "hello":
'h' (ASCII 104): hash = ((5381 * 32) + 5381) + 104 = 177673
'e' (ASCII 101): hash = ((177673 * 32) + 177673) + 101 = 5874861
'l' (ASCII 108): hash = ((5874861 * 32) + 5874861) + 108 = 194419045
'l' (ASCII 108): hash = ((194419045 * 32) + 194419045) + 108 = 6419028037

この時点で、unsigned long 型の最大値を超える可能性があります（プラットフォームによる）。しかしC++ではオーバーフローすると、値はモジュララップアラウンド（最大値に到達した後、0から再スタート）されます。

unsigned long 型について

unsigned long 型は、C++（および多くの他のプログラミング言語）で利用される整数型の一つです。この型は符号なし（負の数を表現できない）であり、そのサイズや範囲はプラットフォームによって異なることがありますが、一般的には少なくとも32ビット（0から約42億までの値を格納可能）です。多くの現代のシステムでは、64ビット（約18京までの値を格納可能）を持っています。

特徴:

符号なし: 負の値を保持できず、そのため格納可能な正の数の範囲が広がります。
整数型: 小数点以下の値を保持できません。
プラットフォーム依存のサイズ: 通常、32ビットまたは64ビットですが、コンパイラやプラットフォームにより異なります。

この型をハッシュ関数で使用する理由は、大きな範囲の整数値を扱いやすく、計算過程でのオーバーフローがプログラムの動作に影響を与えないことが多いためです。ハッシュ値としては、通常、値の範囲が広い方が良いため、unsigned long 型が適しています。

②SHA-256を利用したハッシュ関数

Linuxで実行した方がWindowsで環境整備してから実行するよりはるかに簡単だったので②はLinuxで動かす想定で解説します。

SHA-256ハッシュ関数は認知の文字列から固定長のハッシュ値を生成します。その長さ256ビット、つまり32バイトです。

#include <iostream>
#include <string>
#include <openssl/sha.h>

// SHA-256 hash function
std::string sha256(const std::string str) {

    //32バイト
    unsigned char hash[SHA256_DIGEST_LENGTH];
    
    // SHA-256 コンテキスト構造体の定義
    SHA256_CTX sha256;
    
    // コンテキストの初期化
    SHA256_Init(&sha256);
    
    // データをハッシュアルゴリズムに渡す
    SHA256_Update(&sha256, str.c_str(), str.size());

    // ハッシュ値を計算とハッシュ値をバイナリ形式でhash配列に格納
    SHA256_Final(hash, &sha256);

    // 最終的な16進数形式のハッシュ値を保持するための文字列
    std::string output;

    // 一時的に各バイトを16進数の文字列に変換して格納するためのバッファ
    // 3は2文字の16進数と終端のヌル文字'\0'を格納するために必要
    char buf[3];
    
    for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) {

    // %02x はフォーマット指定子で、16進数で出力し常に2文字になるように前に0を追加
        sprintf(buf, "%02x", hash[i]);
        
        output += buf;
    }
    return output;
}

int main() {
    std::string input;
    std::cout << "Please enter a string: ";
    std::cin >> input;

    // Calculate and output the SHA-256 hash value
    std::string hashValue = sha256(input);
    std::cout << "SHA-256 hash value: " << hashValue << std::endl;

    return 0;
}

SHA-256 ハッシュ関数の処理の詳細：

SHA256_CTX、SHA256_Init、SHA256_Update、SHA256_Final および SHA256_DIGEST_LENGTH は、OpenSSLライブラリが提供するSHA-256ハッシュ関数に関連する機能および定数です。ここで使われている各部分の説明は以下の通りです：

SHA-256ハッシュ値の長さ

SHA256_DIGEST_LENGTH は、SHA-256ハッシュ値の長さをバイトで定義しています（通常は32バイト、つまり256ビットです）。

コンテキストの初期化 (SHA256_Init)

SHA256_CTX は、SHA-256アルゴリズムの計算状態を保持する構造体です。SHA256_Init 関数はこの構造体を初期化して、新しいハッシュ計算のための準備を行います。

データの追加 (SHA256_Update)

SHA256_Update 関数は、ハッシュを計算するデータ（この例では文字列 str）をアルゴリズムに渡します。この関数は複数回呼び出されることがあり、例えば非常に大きなデータを小さなチャンクに分割して渡すことができます。

• data.c_str() はC++の文字列をCスタイルの文字列（null終端されたchar配列）に変換し、アルゴリズムに渡すデータの先頭アドレスを提供します

• data.size() は、供給するデータの長さ（バイト数）を指定します。この情報により、アルゴリズムは正確にデータの長さを知ることができます

std::string の size() メソッドは、文字列に含まれる文字の数を返します。C++では、標準の文字列（std::string）の各文字は1バイト（char）として格納されるため、size() によって返される値は文字列のバイト数と同等です。これは、ASCII文字に限られる場合の話です。UTF-8のようなマルチバイト文字エンコーディングを使用している場合、文字列の「文字数」と「バイト数」は一致しない場合がありますが、std::stringは基本的にバイト単位でのカウントを行うため、このメソッドはデータの正確なバイトサイズを渡すのに適しています。

Cスタイルの文字列とC++の文字列の違い

Cスタイルの文字列: C言語で一般的に使用される文字列で、char 型の配列で表されます。これらの文字列はヌル文字（'\0'）で終了する必要があります。このヌル終端により、文字列の終わりを示します。

C++の文字列: C++では、std::string クラスを用いて文字列を扱います。このクラスは動的にサイズが変わることができ、文字列操作やメモリ管理を簡単かつ安全に行う多くの機能を提供します。std::string は内部的にはchar配列を使用していますが、ユーザーがヌル終端を気にする必要はありません。

Cスタイルの文字列を扱う理由

多くのC++のライブラリやAPIがC言語の基盤に基づいているため、互換性のためにCスタイルの文字列をサポートしています。OpenSSLライブラリもその一つで、SHA256_Update などの関数はCスタイルの文字列を引数として受け取るため、std::string からCスタイルの文字列に変換する必要があります

ハッシュの最終化 (SHA256_Final)

すべてのデータがアルゴリズムに渡された後、SHA256_Final 関数を呼び出してハッシュ計算を完了します。この関数は最終的なハッシュ値を hash 配列に格納します。

ハッシュ値の16進数表現への変換

ハッシュ値はバイナリデータとして生成されますが、通常は16進数の文字列として表現されます。このため、各バイトを %02x フォーマット指定子を使って2桁の16進数に変換し、連結していきます。%02x は、バイト値を必ず2桁で表示し、足りない場合は0で埋めることを意味します。

環境整備とコンパイル

以下の通りにコマンドを実行していきます。

sudo apt update
sudo apt upgrade
sudo apt install build-essential // for c++
nano hello.cpp 

nanoで以下のテストC++プログラムを保存します。

#include <iostream>

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}

テストプログラムをコンパイルして実行してみます。

g++ hello.cpp -o hello
./hello

OPENSSLを導入してプログラムをコピーしてコンパイルして実行してみます。

sudo apt install code
sudo apt install openssl libssl-dev
openssl version
nano hash.cpp 
g++ -o hash hash.cpp -lssl -lcrypto
./hash