はじめに

こんにちは！Saku0512です。
今回は暗号論的観点から見る安全な乱数生成について話そうと思います。

疑似乱数生成器と暗号論的疑似乱数生成器

疑似乱数生成器にも、2種類あります。
ただの疑似乱数生成器 (Pseudo Random Number Generator, PRNG) と、暗号論的疑似乱数生成器 (Cryptographically Secure Pseudo Random Number Generator, CSPRNG) の２つです。

普段の乱数生成であればPRNGで問題ないですが、セキュリティが重要な場合はCSPRNGを使うほうがいいと思います。

疑似乱数生成器

決定論的アルゴリズムを用いて疑似乱数を生成するもの。
※ 決定論的とは同じ初期値(シード値)を与えると、同じ乱数を生成するという意味である。
C言語ではstdlib.hのrand()関数が用意されています。

rand()を用いた場合

rand.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main () {
    printf("実行時間(UNIX時間):%ld\n", time(NULL));

    for (int i = 0; i < 5; i++) {
        printf("%d\n", rand());
    }

    return 0;
}

出力１回目

$ ./rand
実行時間(UNIX時間):1740526464  # 乱数生成には無関係
1804289383
846930886
1681692777
1714636915
1957747793

出力２回目

$ ./rand
実行時間(UNIX時間):1740526473  # 乱数生成には無関係
1804289383
846930886
1681692777
1714636915
1957747793

ランダムなはずの出力が被っていることが分かる。

srand(time(NULL))を用いた場合

srand(time(NULL))でUNIX時間をシード値に設定することで、実行毎に異なる乱数を生成することが可能になります。
(シード値は毎回変わるので、実行毎に異なる乱数を生成することが可能になる)
しかし、これにも以下のような問題点がある。

time(NUll)の値は予測可能
rand()関数のアルゴリズムが脆弱でシード値が分かると次の値が計算できる。
time(NUll)は１秒単位でしか扱えない

`time(NUll)`の値は予測可能

time(NULL)は1970年1月1日からの経過秒数（UNIX時間）を取得するものである。
UNIX時間は誰でも取得できるため、攻撃者が実行時の時刻をある程度知っていればシード値を予測することが可能になる。
特定の時間(たとえば、毎日0時0分)に実行されるプログラムがある場合は、攻撃者は容易にシード値を推測することができる。

`rand()`関数のアルゴリズムが脆弱

rand()関数のアルゴリズムは、srand()関数に与えたシード値を用いて生成される。
※ 上記のrand.cではsrand()関数を用いていないがC言語の特性上、srand()関数でシード値が設定されていない場合は、実装依存のデフォルトのシード値を用いるため、出力が同じになっている。

rand() 関数は、線形合同法（Linear Congruential Generator, LCG）という手法で疑似乱数を生成する。

LCGは、次の式で表される。

$$
X_{n+1} = (a X_n + c) \mod m
$$

$X_{n}$ : n番目の乱数
$a$ : 乗数
$c$ : 加算数
$m$ : 剰余数
$X_{0}$ : シード値 (srand() 関数で決定される)

つまり、シード値が分かればそのシード値に対する全ての乱数を計算できる。

linuxのglibcでは次のようにパラメータが決定されています。

$$
a = 1103515245 \qquad c = 12345 \qquad m = 2^{31}
$$

よって上記の式は下記のようになります。

$$
X_{n+1} = (1103515245 X_n + 12345) \mod 2^{31}
$$

では実際に確かめていきましょう。

srand.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define A 1103515245  // 乗数 (multiplier)
#define C 12345        // 加算数 (increment)
#define M 2147483648   // 2^31 (modulus, RAND_MAX + 1)

// LCGを使った擬似乱数生成関数
unsigned int lcg_rand(unsigned int *seed) {
    *seed = (A * (*seed) + C) % M;
    return *seed;
}

int main() {
    // シード値を time(NULL) に設定
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);  // 標準の rand() にも同じシードを設定

    printf("シード値: %u\n\n", seed);
    
    printf("LCGによる乱数:\n");
    for (int i = 0; i < 5; i++) {
        printf("%u\n", lcg_rand(&seed));
    }

    printf("\nrand() による乱数:\n");
    for (int i = 0; i < 5; i++) {
        printf("%u\n", rand());
    }

    return 0;
}

出力

シード値: 1740529793

LCGによる乱数:
305960230
983647591
1853497108
1559200701
1833754034

rand() による乱数:
1427280996
1758078112
1940178374
322899173
619782472

出力結果が違ってしまいました...
おそらくrand()関数のアルゴリズムが環境によってずれている事が原因だと思われます。
しかし、一定の周期によって乱数がパターン化してしまうという問題は依然存在します。

`time(NUll)`は1秒単位でしか扱えない

time(NULL)は１秒単位でしか値が変動しない。
つまりsrand(time(NULL))で初期値を設定していたとしても、1秒以内に複数回実行すると、同じ乱数が出力される。

以下の様なshでrand.cを1秒間に複数回実行してみましょう。

rand.sh

echo "1回目"
./rand

echo -e "\n2回目"
./rand

echo -e "\n3回目"
./rand

出力

1回目
実行時間(UNIX時間):1740531376
1804289383
846930886
1681692777
1714636915
1957747793

2回目
実行時間(UNIX時間):1740531376
1804289383
846930886
1681692777
1714636915
1957747793

3回目
実行時間(UNIX時間):1740531376
1804289383
846930886
1681692777
1714636915
1957747793

1,2,3回目の出力結果が全て同じになっていることが分かる。

暗号論的疑似乱数生成器

暗号やセキュリティに関わる用途で安全な疑似乱数を生成するもの。
今回はOpenSSL の RAND_bytes()関数を紹介する。
RAND_bytes()関数は、プラットフォームに依存せず安全な乱数生成でができる。
※ 他にもLinux/macOSでの /dev/urandom や Windowsでの CryptGenRandom()関数を使う方法もある。

`RAND_bytes()`関数を使った場合

rand_bytes.c

#include <stdio.h>
#include <openssl/rand.h>

int main() {
    unsigned char buffer[16];

    for (int j = 0; j < 5; j++) { // 5回ループ
        // 乱数を buffer に格納（成功すると 1 を返す）
        if (RAND_bytes(buffer, sizeof(buffer)) != 1) {
            printf("RAND_bytes() failed.\n");
            return 1;
        }

        // 生成された乱数を表示
        for (int i = 0; i < sizeof(buffer); i++) {
            printf("%02x ", buffer[i]);
        }
        printf("\n");
    }

    return 0;
}

出力１回目

$ ./rand_bytes
9e 12 35 c7 98 7d a8 3f 20 59 73 2d 12 14 cb f2 
25 9e 6b 1e 05 b7 09 9c 6d 19 af a8 56 af 04 24 
40 89 b5 39 60 0f dc 59 ae 95 9f bb 22 36 b7 f1 
94 5b 49 f9 79 bd 15 a3 e2 49 ab 4b 1c 8b bd 91 
7b 21 48 6a 58 45 53 6b bb 52 39 9a 00 d0 ef 53

出力２回目

$ ./rand_bytes
9e 2a f4 76 1f 04 c0 11 e8 77 c7 35 08 64 fc f5 
91 68 0b 15 c5 19 03 db 99 f9 ac ba 61 ca d5 ae 
2b 8d 64 1d c8 7a 90 91 7e d5 2b c9 1f ba e2 1a 
ac 2a 74 02 1b 94 ff 28 12 04 9e 59 1b 03 27 a3 
46 87 71 d8 c8 f1 a6 4c ac fd e7 28 ed e4 d9 43

出力結果が違うので、少なくともランダムっぽい値が生成されていることが分かる。

`RAND_bytes()`関数の簡単な仕組み

RAND_bytes()関数は、シード値にシステムのエントロピーを利用している。

エントロピーとは、乱数生成における「不確実性」や「予測不能性」の度合いを指す言葉。
システムのエントロピーとは、予測不能なデータやランダム性を提供するシステムのリソースやイベントのこと。

エントロピーとは、以下のようなところから集められる。

/dev/random と /dev/urandom
- Linux や他の Unix 系のシステムでは、/dev/random と /dev/urandom がエントロピー源として使用されます。
- /dev/random は、システム内のエントロピーが十分に集まるまでブロックするので、他の処理が一時停止することがある。
- /dev/urandom は、/dev/random よりも高速で一定の質は保証されているが、dev/random より低品質なエントロピーを提供する。
システムイベント
- システムの動作やユーザーの入力から得られるランダム性もエントロピー源として利用される。例えば、 :
  - マウスの動き : ユーザーのマウスの位置や移動の速度、加速度。
  - キーボードの入力 : キーが押されたタイミングやパターン。
ハードウェアランダムジェネレーター
- 一部のハードウェアには、物理的な現象（例えば、電子ノイズ）を使ってランダムなデータを生成するための専用回路が組み込まれている。これらは、非常に高品質なエントロピー源を提供し、システムのソフトウェア乱数生成に加えて使用されることがある。
  - IntelのRDRAND命令 : 一部のIntel CPUには、ハードウェアでランダム数を生成する命令が実装されている。
  - TPM（Trusted Platform Module）: 一部のPCには、エンタープライズ向けのセキュリティ機能として TPM が内蔵されており、これを利用することで強力なエントロピーが得られる。

RAND_bytes()関数の、処理の流れ

システムのエントロピーソースからエントロピーを収集する。
収集したエントロピーを元にシード値を生成する。
疑似乱数生成器を用いて乱数生成する。

`RAND_bytes()`関数の検証

次のようなshで検証してみる。

rand_bytes.sh

echo "1回目"
./rand_bytes

echo -e "\n2回目"
./rand_bytes

echo -e "\n3回目"
./rand_bytes

出力

1回目
c1 10 b5 b0 02 9f 62 d1 91 c5 b4 99 25 f7 94 7a 
51 51 a6 97 62 59 4b e5 08 59 70 ef a6 14 fb 83 
d0 af ff cc 67 23 e5 cd 63 74 80 65 63 1e 88 73 
03 3e 40 a1 f6 57 65 cd 4b c1 6d b5 92 c3 f1 0b 
8d d4 3e 8d cf 9b 8e 5f 80 a4 a9 86 50 ad 8c fa 

2回目
a8 27 7e dd 51 5d 93 8f 71 fa e8 94 49 07 8d 16 
f6 99 6d c8 15 0a 5b 7c 97 dc 8b e3 4b eb 6a d2 
e1 ba 92 76 a4 e2 f9 8b 18 64 4c 8b 0a f5 29 8a 
8b c3 83 e2 9c af 8c 86 bc cc 91 41 0f 59 ca 8d 
1d d1 85 f1 26 62 d5 8c 8c 0f 63 30 be 2a d4 73 

3回目
48 8b c0 65 31 70 92 64 8d 90 42 0f 10 da 9d cf 
64 1a f6 91 3f 4d 0b ab 7e 32 58 0c d7 2e ad 66 
19 ee 9c 9c 03 f2 ca da 9f 26 92 7e 5b ae f7 04 
0f a1 e8 e0 94 18 ad 07 07 65 83 a5 af 4f e5 fe 
da 64 62 3a 6b bb f1 52 68 91 7a 23 2e 07 90 a1

同じ時間に実行しても出力が違うことが分かる。
また、生成に使うシード値が毎回違うため、安全に乱数生成することができる。