大随机数生成与测试全解析

### 大随机数生成与测试全解析 #### 1. 随机数概述 随机数值序列在众多领域有着广泛应用，如统计学、数值数学、物理学以及数论应用等。其用途包括从更大集合中选取随机样本、在密码学中生成密钥和运行安全协议、作为生成素数程序的初始值、测试计算机程序，甚至用于娱乐等。 随机数可分为真随机数和伪随机数。真随机数源于随机实验，如抛硬币、掷骰子、旋转轮盘、观察放射性衰变过程以及评估电子元件输出等。而伪随机数则通过算法生成，由伪随机数生成器产生，这些生成器具有确定性，仅依赖初始状态和初始值（种子），因此具有可预测性和可重复性。 数学上，随机性的要求通常由数字序列来满足。一个理想的随机数序列应是独立随机数序列，每个数字随机且独立于序列中的其他数字，并以一定概率在特定范围内取值。然而，使用确定性程序生成数字理论上无法达到这一理想状态，但许多算法技术的目标是尽可能接近该理想状态。 #### 2. 线性同余法生成伪随机数 线性同余法是一种常用的生成伪随机数的方法，其递推公式为： \[X_{i + 1} = (X_{i}a + b) \mod m\] 该方法由D. Lehmer在1951年提出，虽然简单，但能生成具有出色统计特性的随机序列，不过其质量取决于参数 \(a\)、\(b\) 和 \(m\) 的选择。 若选择 \(m\) 为2的幂，可通过按位与操作快速计算模运算，但生成数字的最低有效二进制位的随机性不如最高有效位，使用时需谨慎。一般来说，选择 \(m\) 为素数也是一个不错的选择，因为此时各个二进制位的随机性相当。 序列的周期性受 \(a\) 和 \(m\) 的影响，由于序列值最多有 \(m\) 个不同值，所以序列最迟在生成第 \(m + 1\) 个数时开始重复。为使线性同余序列具有最大周期长度，需满足以下条件： - \(\gcd(b, m) = 1\) - 对于所有素数 \(p\)，若 \(p \mid m\)，则 \(p \mid (a - 1)\) - 若 \(4 \mid m\)，则 \(4 \mid (a - 1)\) 例如，ISO - C标准推荐的 `rand()` 函数使用的线性同余式为： \[X_{i + 1} = (X_{i} \cdot 1103515245 + 12345) \mod m\] 其中 \(m = 2^k\)，\(2^k - 1\) 是 `unsigned int` 类型能表示的最大数。该生成器生成的序列满足上述条件，具有最大周期长度 \(2^k\)。 我们可以使用R. P. Brent算法来测试序列的周期长度，其步骤如下： 1. 设置 \(y \leftarrow X_0\)，\(r \leftarrow 1\)，\(k \leftarrow 0\)。 2. 设置 \(x \leftarrow y\)，\(j \leftarrow k\)，\(r \leftarrow r + r\)。 3. 设置 \(k \leftarrow k + 1\) 并 \(y \leftarrow F(y)\)，重复此步骤直到 \(x = y\) 或 \(k \geq r\)。 4. 若 \(x \neq y\)，转到步骤2；否则，输出 \(\lambda = k - j\)。 #### 3. 简单随机数生成器实现 以下是使用线性同余法实现的简单随机数生成器： ```c // 线性同余生成器，周期长度为2^64 clint * rand64_l (void); clint * rand64_l (void) { mul_l (SEED64, A64, SEED64); inc_l (SEED64); // 模2^64运算，通过设置长度字段实现 SETDIGITS_L (SEED64, MIN (DIGITS_L (SEED64), 4)); return ((clint *)SEED64); } // 设置rand64_l()的初始值 clint * seed64_l (CLINT seed_l); // 生成无符号长整型随机数 unsigned long ulrand64_l (void); ULONG ulrand64_l (void) { ULONG val; USHORT l; rand64_l(); l = DIGITS_L (SEED64); switch (l) { case 4: case 3: case 2: val = (ULONG)SEED64[l - 1]; val += ((ULONG)SEED64[l] << BITPERDGT); break; case 1: val = (ULONG)SEED64[l]; break; default: val = 0; } return val; } // 生成指定二进制位数的CLINT类型随机数 void rand_l (CLINT r_l, int l); void rand_l (CLINT r_l, int l) { USHORT i, j, ls, lr; // 限制二进制位数 l = MIN (l, CLINTMAXBIT); // 计算所需USHORT位数和最高有效USHORT的最高有效二进制位位置 ls = (USHORT)l >> LDBITPERDGT; lr = (USHORT)l & (BITPERDGT - 1UL); // 生成随机数的各个数位 for (i = 1; i <= ls; i++) { r_l[i] = usrand64_l (); } // 设置最高有效位 if (lr > 0) { r_l[++ls] = usrand64_l (); j = 1U << (lr - 1); r_l[ls] = (r_l[ls] | j) & ((j << 1) - 1); } else { r_l[ls] |= BASEDIV2; } SETDIGITS_L (r_l, ls); } ``` #### 4. 密码学随机数生成器 密码学随机数生成器用于敏感目的，为确保其安全性，需使用不可预测且不可影响的熵源来推导初始值。因为攻击者若知道或能猜出伪随机序列的初始值，就能知晓整个随机序列或从中派生的密钥和密码。 常见的熵源包括系统统计信息（如某些进程的时钟滴答数）、外部事件测量（如鼠标移动、键盘事件或鼠标点击的时间间隔）等。这些参数可通过哈希函数进行混合。不同操作系统也提供了获取熵的函数，如Windows的Win32 CryptoAPI中的 `CryptGenRandom()` 函数，以及Linux和FreeBSD的虚拟设备 `/dev/random` 和 `/dev/urandom`。 ##### 4.1 BBS随机数生成器 BBS位生成器基于复杂性理论的结果，具有良好的密码学特性。其实现步骤如下： 1. 选择两个与3模4同余的素数 \(p\) 和 \(q\)，计算模数 \(n = pq\)。 2. 选择一个与 \(n\) 互质的数 \(X\)，计算 \(X_0 := X^2 \mod n\) 作为序列的初始值。 3. 通过连续平方模 \(n\) 计算序列： \[X_{i + 1} = X_{i}^2 \mod n\] 4. 从每个 \(X_i\) 中提取最低有效位作为随机数。 该生成器的状态集 \(S = \{ 0, 1, \ldots, n - 1 \}\)，随机值 \(R = \{ 0, 1 \}\)，状态转移函数 \(\varphi(x) = x^2 \mod n\)，输出函数 \(\psi(x) := x \mod 2\)。其安全性基于与RSA算法相同的原理，即若不知道模数 \(n\) 的因子 \(p\) 和 \(q\)，就难以预测BBS随机序列的后续比特。 以下是BBS随机数生成器的部分实现代码： ```c // BBS随机数生成器的状态转移函数 int SwitchRandBBS_l (STATEBBS *rstate); int SwitchRandBBS_l (STATEBBS *rstate) { // 继续生成器，进行模平方运算 msqr_l (rstate->XBBS, rstate->XBBS, rstate->MODBBS); // 输出最低有效位 return (*LSDPTR_L (rstate->XBBS) & 1); } // 初始化BBS随机数生成器 int InitRandBBS_l (STATEBBS *rstate, char * UsrStr, int LenUsrStr, int AddEntropy); int InitRandBBS_l (STATEBBS *rstate, char *UsrStr, int LenUsrStr, int AddEntropy) { CLINT Seed_l; int MissingEntropy; // 生成熵并得到初始值 MissingEntropy = GetEntropy_l (Seed_l, NULL, AddEntropy, UsrStr, LenUsrStr); // 生成内部初始状态 SeedBBS_l (rstate, Seed_l); // 删除初始值 local_memset (Seed_l, 0, sizeof (CLINT)); return MissingEntropy; } // 设置BBS随机数生成器的初始值 int seedBBS_l (STATEBBS *rstate, CLINT seed_l); int seedBBS_l (STATEBBS *rstate CLINT seed_l) { CLINT g_l; str2clint_l (rstate->MODBBS, (char *)MODBBSSTR, 16); gcd_l (rstate->MODBBS, seed_l, g_l); if (!EQONE_L (g_l)) { return E_CLINT_RCP; } msqr_l (seed_l, rstate->XBBS, rstate->MODBBS); // 设置标志：PRNG已初始化 rstate->RadBBSInit = 1; return E_CLINT_OK; } // 生成UCHAR类型的随机数 UCHAR bRandBBS_l (STATEBBS *rstate); UCHAR bRandBBS_l (STATEBBS *rstate) { int i; UCHAR r = SwitchRandBBS_l (rstate); for (i = 1; i < (sizeof (UCHAR) << 3); i++) { r = (r << 1) + SwitchRandBBS_l (rstate); } return r; } ``` ##### 4.2 AES生成器 对称块加密系统可用于构建随机数生成器，以高级加密标准（AES）为例，其状态集定义为 \(S := K \times D \times C\)，状态函数为： \[\varphi(k, x, i) := (\xi(k, x, i), AES_k(x), i + 1 \mod c)\] 其中： \[\xi(k, x, i) := \begin{cases} k & \text{if } i \not\equiv 0 \pmod{c} \\ k \oplus AES_k(x) & \text{if } i \equiv 0 \pmod{c} \end{cases}\] 输出函数为： \[\psi(k, x, i) := x / 2^{8 \cdot (23 - (i \mod 16))} \mod 2^8\] 常数 \(c\) 指定了密钥更新的频率，更新频率越高，安全性越高，但初始化密钥所需的时间也越长。 以下是AES随机数生成器的部分实现代码： ```c // 初始化AES随机数生成器并生成熵 int InitRandAES_l (STATEAES *rstate, char *UsrStr, int LenUsrStr, int AddEntropy, int update); int InitRandAES_l (STATEAES *rstate, char *UsrStr, int LenUsrStr, int AddEntropy, int update) { int MissingEntropy, i; // 生成初始值 MissingEntropy = GetEntropy_l (NULL, rstate->XAES, AddEntropy, UsrStr, LenUsrStr); // 初始化AES for (i = 0; i < 32; i++) { rstate->RandAESKey[i] ^= RandAESKey[i]; } ```