65.9K
CodeProject 正在变化。 阅读更多。
Home

应用 Crypto++：伪随机数生成器

Jeffrey Walton
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.77/5 (32投票s)

2007年1月2日

CPOL

17分钟阅读

viewsIcon

206950

downloadIcon

6052

如何选择 Crypto++ 伪随机数生成器。

不应该随机生成数字
而是选择一种方法
- Donald Knuth
计算机程序设计艺术
卷II：半数值算法

引言

随机数不仅是密码学家、计算机科学家和程序员的原始要素。我们想要的是一种能够快速生成加密安全的伪随机数流的方法。然而，这些目标是截然相反的——伪随机序列可以快速生成，或者可以强健地生成；但通常不能快速生成具有抵抗密码分析特性的序列。

本文将探讨伪随机数生成器的应用。涵盖的主题包括

  • 随机数的有用性
  • 随机数生成器类
  • 生成器类型
  • 随机数源
  • 序列测试
  • 种子
  • 密钥派生函数
  • 标准C++ rand()
  • 线性同余生成器
  • 最小标准生成器
  • 非线性同余生成器
  • Win32 API CryptGenRandom()
  • 编译和集成Crypto++
  • Crypto++ 随机数生成器
    • LC_RNG
    • RandomPool
    • AutoSeededRandomPool
    • AutoSeeded917RNG
  • 应用表
  • 其他CSPRNG
  • 劣质生成器
    • 中方格法
    • IBM大型机RANDU

下载次数

本文有七个可下载的资源。下载项列于文章末尾。

随机数的有用性

在他著述丰富的《计算机程序设计艺术》卷II：半数值算法中，Donald Knuth列举了需要随机数的以下常见情况

  • 模拟
  • 采样
  • 数值分析
  • 计算机编程
  • 决策
  • 美学
  • 娱乐

模拟和抽样不言而喻。数值分析使用随机数解决复杂问题，例如，使用微分方程的捕食者/猎物模型。第四项同样显而易见。引用Knuth关于第五项的观点，决策

有报道称，许多行政人员通过抛硬币或飞镖等方式做决策。还有传言说一些大学教授也以此为基础准备成绩。有时做出完全“无偏”的决策很重要。随机性也是矩阵博弈理论中最佳策略的重要组成部分。

人耳可以区分合成音乐（由计算机生成）与艺术家创作的音乐。艺术家会有细微的节奏偏差，使音乐更悦耳。此外，少量随机性也能使计算机生成的图形显得更柔和。请注意下方左侧图像的僵硬结构与右侧图像的柔和。右侧图像下方是通过添加少量随机噪声的滤波器生成的。在信号处理中，这被称为抗锯齿。

无随机噪声

随机噪声

为了进一步向读者展示美学，Adobe Photoshop在其许多滤镜中都使用了随机数，包括模糊、扭曲和噪声。

Adobe Photoshop 滤镜

最后，娱乐包括洗牌或掷骰子。

随机数生成器类

引用 NIST, FIPS 140-2

随机数生成器分为两种：确定性和非确定性。确定性RNG由一个算法组成，该算法从一个称为种子的初始值生成一系列比特。非确定性RNG生成的输出依赖于某种人类无法控制的不可预测的物理源。

请注意，普通大众通常将非确定性生成器称为“真随机数生成器”。

随机数生成器类型

程序员可以选择两种确定性随机数生成器

  • 伪随机数生成器
  • 加密安全伪随机数生成器

伪随机数生成器包括线性同余生成器和梅森旋转算法等生成器。它们通常能快速提供[0, 1)区间内的均匀分布流。它们几乎不提供任何密码学安全。

加密安全伪随机数生成器具有额外的特性，使其适用于密码学。加密用途包括

  • 密钥生成
  • Nonce（一次性随机数）
  • Salt（盐）
  • 一次性密钥

Nonce是一个只使用一次的数字或比特串。它是在身份验证协议中生成的一个伪随机数，用于确保旧通信不能被重放攻击重新使用。为确保Nonce仅使用一次，它应该是随时间变化的（在其值中包含足够精细的时间戳），或以足够的随机比特生成，以确保重复先前生成值的概率微不足道。

一次性密钥（约1917年发明）是一种加密算法，其中明文与一个与明文一样长且只使用一次的随机密钥或“密钥”结合。使用模加法将明文与密钥结合。对于二进制数据，XOR操作就是等价的。如果密钥是真正随机的、从不重用且保密的，则一次性密钥提供完美保密。

随机数源

虽然NIST目前不认可任何非确定性RNG，但可以使用确定性RNG来播种加密安全伪随机数生成器。引用FIPS 140-2

在存在批准的非确定性RNG标准之前，批准用于机密应用的非确定性RNG可用于密钥生成或播种用于密钥生成的批准的确定性RNG。

NIST提供测试，允许我们开发启发式方法来确定目标生成器的序列质量。可下载的包括NIST验证套件、FIPS 140-2和FIPS 186。此外，读者可能还想参考ANSI 9.17，附录C（FIPS 140-2批准的随机数生成器，密码模块安全要求）。

另外，NIST SP800-90也值得关注，确定性随机比特生成器的随机数生成建议。一些保守的密码学家不建议使用Dual_EC-DRBG（椭圆曲线变体），但推荐使用CTR_DRBG或Hash_DRBG。Schneier的文章可以在NSA是否在新加密标准中放置了秘密后门？找到。

测试背景

在一个随机序列中，期望每个十进制数字都出现大约1/10次。如果基数为2（数字0或1），每个数字应占序列的约50%。

测试涉及区分好的来源与差的选择。例如，二进制流...1111111110000000000...对于简单的频率测试来说表现完美，但对于运行测试、块中运行最长、累积和等高级测试则会失败。对于所呈现的二进制流，一个反直觉的点是它是一个有效的随机数序列。在无偏生成器中，每个流出现的可能性与其他流的出现可能性相同。

序列测试

下方读者将找到各种应在评估生成器有效性时使用的测试。读者应参考NIST的统计测试指南和Knuth的《计算机程序设计艺术》以获取完整描述。

此外，还应参考NIST的SP800-22，用于密码学应用的随机数和伪随机数生成器的统计测试套件。NIST的网站包含用于测试生成器的软件。

NIST要求PRNG通过16项统计测试。测试列表如下，附有简要说明。

  • 频率 - 整个序列中零和一的比例。
  • 块内频率 - 确定M比特块中1的频率是否接近M/2。
  • 运行 - 整个序列中零和一的总运行次数，其中运行是相同比特的不间断序列。
  • 块内连续1的最长运行 - 确定测试序列中连续1的最长运行长度是否与随机序列中预期的连续1的最长运行长度一致。
  • 随机二进制矩阵秩 - 检查原始序列的固定长度子字符串之间的线性相关性。
  • 离散傅里叶变换（频谱） - 检测周期性特征。
  • 非重叠（非周期）模板匹配 - 预定义目标子字符串的出现次数。
  • 重叠（周期）模板匹配 - 预定义目标子字符串的出现次数。
  • Maurer通用统计测试 - 匹配模式之间的比特数。测试的目的是检测序列是否可以在不丢失信息的情况下被显著压缩。
  • Lempel-Ziv复杂度 - 测试序列可以压缩多远。如果序列可以被显著压缩，则认为它不是随机的。
  • 线性复杂度 - 生成反馈寄存器的长度。
  • 序列 - 整个序列中每个重叠m比特模式的频率。
  • 近似熵 - 每个重叠m比特模式的频率。
  • 累积和 - 确定测试序列中出现的局部序列的累积和是否相对于随机序列的累积和的预期行为过大或过小。
  • 随机游走 - 确定随机游走中状态访问次数是否超过随机序列的预期。
  • 随机游走变体 - 检测随机游走中各种状态的出现次数是否偏离预期。

Knuth指出，随机序列应通过13项统计测试。未包含在NIST要求中的测试如下所示。

  • 卡方 - 经典定义
  • Kolmogorov-Smirnov - 将卡方检验扩展到实数集
  • 间隔 - 检测序列中一定范围内的数字之间的间隔
  • 扑克（分区） - 将流分成n组，每组五个连续整数，观察产生的模式。一对是aabcd，三条是aaabb，依此类推。
  • 优惠券收集者 - 检查观察完0到d-1集合中的所有数字所需的序列长度。
  • 排列 - 将序列分组为分区的顺序数量
  • 碰撞 - 当卡方检验的碰撞次数超过一定数量时使用
  • 生日间隔 - 类似于生日悖论，当在序列中选择两个整数时。

种子

加密安全RNG与其他伪随机数生成器一样，也有一个致命弱点——都需要一个初始种子作为输入。如果秘密种子泄露，攻击者就可以通过使用相同的算法立即生成整个输出序列。

1995年，当时在伯克利的在读研究生David Wagner和他的同学Ian Goldberg破解了Netscape网络浏览器用于保护在线交易的随机数生成器。两人发现Netscape使用易于预测的数字（如当前时间）来构建其种子。

密钥派生函数

密钥派生函数（除其他外）用于从秘密密码或密码短语派生密钥。作为参考，可以使用RFC 2898，密码学规范。此外，.NET平台提供了Rfc2898DeriveBytes，它是System.Security.Cryptography的一部分。

密钥派生函数通常与非秘密参数结合使用，从一个通用的秘密值派生密钥。KDF还可以用于确保派生密钥具有其他期望的属性，例如在某些特定加密系统中避免弱密钥。

密钥派生函数也用于应用程序中，从通常不具有直接用作加密密钥的所需属性的秘密密码或密码短语派生密钥。在此类应用中，通常建议使密钥派生函数有意地变慢，以挫败对密码或密码短语输入值的暴力破解攻击或字典攻击。

这种用法可以表示为 Dk = KDF(Key, Salt, Iterations)，其中 Dk 是派生密钥，KDF 是密钥派生函数，Key 是原始密钥或密码，Salt 是作为密码学盐的随机数，Iterations 指的是子函数的迭代次数。派生密钥用于替代原始密钥或密码作为系统的密钥。Salt 的值和迭代次数（如果未固定）与散列密码一起存储，或与加密消息一起以明文形式发送。

标准C++ rand() 函数

标准C++ rand() 函数使用线性同余生成器。如果参数 *m*、*a*、*c* 和 *X0* 选择得当，它可以快速提供均匀分布的比特流。LCG 不提供密码学安全性。

X0 通常被称为种子，经常使用系统时间。生成器通过使用以下递推关系获得数字

Xn+1 = (*aXn* + *c*) mod *m*

Microsoft Visual C++ 环境中使用的生成器值如下所示。请注意，& 0x7FFF 正在执行模约减。

return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);

Joan Boyar的博士论文《推断由低位比特缺失的线性同余生成器产生的序列》是一篇有趣的读物。敏锐的读者应该意识到，可能存在一个在线博彩网站在使用不安全的系统。请注意，这与*Wonging*（以斯坦福大学前IBM研究员兼职业赌徒Stanford Wong命名）是不同的攻击，后者基本上是一种算牌系统。

最小标准生成器

该生成器由Miller、Lewis和Goldman于1969年首次提出，是一个线性同余生成器，其中c=0。去除常数的改进产生了乘法生成器

Xn+1 = *aXn* mod *m*

Park和Miller建议使用 *a* = 75 = 16807，*m* = 231-1 = 2147483647。231-1 产生一个周期为231-2。使用231-1时存在其他 *a* 值：48271和69627。不应使用其他值。

非线性同余生成器

有许多快速随机数生成器可用，作为标准C/C++库的rand()和srand()函数的替代品。读者应该熟悉《随机数生成器：好用的很难找到》。Steve Park在他的《随机数生成器》网页上提供了Lehmer生成器的源代码。Park的代码提供了基于以下分布的额外PRNG（这些生成器被称为非线性同余生成器）

  • 伯努利
  • 二项式
  • 等可能
  • 几何
  • Pascal
  • 泊松

由Makoto Matsumoto和Takuji Nishimura于1997年开发的梅森旋转算法也属于此类。在计算机病毒领域有一个有趣的事实是，30个病毒使用了该生成器。据推测，其中一个作者负责这些病毒。

Win32 API CryptGenRandom()

CryptGenRandom()为用户生成所需数量的字节。GenCryptRandom()是Windows上熵的一个极好来源，因为它适用于除NT 3.51及更早版本，以及Windows 95（SR1）及更早版本之外的所有操作系统。

CryptGenRandom的最新种子值存储在Windows注册表中，位于HKEY_LOCAL_MACHINE根目录下的\SOFTWARE\Microsoft\Cryptography\RNG\Seed键下。种子由操作系统使用各种系统参数生成。例如，在Windows CE设备上，将使用以下参数

  • 线程和内核切换（CeGetRandomSeed）
  • 当前进程标识符（GetCurrentProcessId）
  • 当前线程标识符（GetCurrentThreadId）
  • 自启动以来的滴答数（GetTickCount）
  • 当前时间（GetLocalTime）
  • 内存信息（GlobalMemoryStatus）
  • 对象存储统计信息（GetStoreInformation）

种子生成后，它会经过两个加密变换：MD4散列和RC4加密，以进行额外的混合和截断。

示例1演示了如何使用Windows API获取伪随机值。为了减轻SDK的负担，程序使用了LoadLibrary()和GetProcAddress()。

编译和集成Crypto++

Crypto++请参阅相关文章将Crypto++编译并集成到Microsoft Visual C++环境。本文基于前述文章中呈现的基本假设。它还解决了从命令行到MFC的项目中遇到的大多数问题（错误C1083、C1189、LNK1104、LNK2001和LNK2005）。此外，它还提供了一些使用Crypto++库的技巧和其他便利。

LC_RNG

LC_RNG是一个线性同余RNG。虽然该生成器没有密码学价值，但它允许在调试程序时重现结果。此外，它通常在生成字节块（或流）时速度更快。如果使用0x00作为LCG的种子，会得到一个稳定的0x80流。此种子值产生周期为1。其他种子按预期工作。可以使用示例1来比较线性同余生成器各种种子值的输出。

RandomPool

RandomPool的行为类似于LCG，因为相同的种子会产生相同的结果。然而，与LC_RNG不同的是，RandomPool背后的密码是当前的MD5<SHA>。randpool.cpp提供了typedef MDC<SHA> RandomPoolCipher。然后，可以按如下方式初始化和使用RandomPool（如示例3所示）

// Must be at least 16 for RandomPool
const unsigned int SEEDSIZE = 16;
byte pcbSeed[ SEEDSIZE ];

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];

...

// Random Pool Initialization
CryptoPP::RandomPool rng( SEEDSIZE );
rng.Put( pcbSeed, SEEDSIZE );

// Use
rng.GenerateBlock( pcbScratch, BLOCKSIZE );

AutoSeededRandomPool

Leonard Janke建议了一种自动播种的随机池，后来Wei Dai将其集成到Crypto++中。AutoSeededRandomPool使用PGP的RandPool设计。它适用于所有密码学目的，包括生成密钥和IV。根据操作系统，生成器将使用以下方法进行播种

  • 通过密码服务提供商使用CryptGenRandom()
  • /dev/urand
  • /dev/rand

示例4简单地演示了如何使用AutoSeededRandomPool。

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];

// Construction
AutoSeededRandomPool rng;

// Random Block
rng.GenerateBlock( pcbScratch, BLOCKSIZE );

AutoSeededX917RNG

与LG_RNG和RandomPool不同，AutoSeededX917RNG不需要播种。但是，必须指定一个批准的块密码作为模板参数。两个ANSI 9.17批准的密码是3键三重DES和SHA1。示例5演示了与SHA1的用法。

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];

// Construction
AutoSeededX917RNG< DES_EDE3 > rng;

// Random Block
rng.GenerateBlock( pcbScratch, BLOCKSIZE );

应用表

在实际选择随机数生成器时，应应用以下表格。

其他CSPRNG

除上述之外，各种FIPS标准还认可其他加密安全生成器。如读者现在应已认识到的，加密安全伪随机数生成器将确定性生成器封装在一个难题中。FIPS 186-3批准数字签名算法（DSA）和椭圆曲线DSA（ECDSA）作为CSPRNG。

劣质生成器

本节包含出于泛知论的考虑。我希望读者能够欣赏（有时是享受）这些缺点。

中方格法

约翰·冯·诺依曼提出的中方格法生成方法。该生成器从1946年使用到20世纪50年代中期。请记住，在1946年，计算机才刚刚问世一年。该生成器的问题在于它收敛到0序列的速度太快；一旦达到0，它就会被锁定在0。

IBM大型机RANDU

RANDU是IBM为其大型机提供的同余生成器。选择a=65539和m=231被证明是一个糟糕的选择。当《数值分析C语言实现》的作者生成样本并绘制平面图时，只有11个平面（理论上应为m1/k的阶数，其中k是在三维空间中绘制的随机数数量）。该生成器存在k维空间中的相关性问题。IBM代表表示

我们保证每个数字单独是随机的，但我们不保证它们中有一个以上是随机的。

减法与借位

1992年，物理学家发现，即使是“高质量”的随机数生成器，在某些情况下也会产生不正确的结果。在模拟三维Ising模型之前，研究人员测试了该软件包在二维版本上的性能，该版本有已知答案。结果是错误的。[1]

摘要

本文根据问题领域为读者提供了各种伪随机数生成器的选择。如果读者需要模拟或抽样源，请选择LCG。如果读者需要强度，请选择Win32 API、AutoSeededRandomPool或AutoSeededX917RNG。如果读者需要密码学安全性，请选择AutoSeededX917。最后，如果读者需要熵，请使用Win32 API或AutoSeededRandomPool。

此外，还存在其他生成器（其中一些在Crypto++中公开）。例如，Blum Blum Shub CSPRNG基于二次剩余生成比特序列。只要整数分解仍然困难，该生成器将保持加密安全。整数分解在复杂性理论中的位置尚未确定。

致谢

  • Wei Dai for Crypto++ 及其在 Crypto++ 邮件列表上的宝贵帮助
  • A. Brooke Stephens 博士，他为我打下了密码学基础

修订

  • 2008.10.04 添加了对Schneier的Wired.com文章的引用
  • 2007.11.28 添加了“劣质生成器”部分
  • 2007.11.07 添加了对NIST测试套件的引用
  • 2007.09.13 添加了Nonce的说明
  • 2007.09.05 添加了对NIST 800-90的引用
  • 2007.09.05 添加了对NIST 800-22的引用
  • 2007.08.28 添加了对梅森旋转算法的引用
  • 2007.08.27 添加了对RFC 2898的引用
  • 2007.01.12 添加了非线性同余生成器
  • 2007.01.09 扩展了随机数的有用性
  • 2007.01.07 添加了对Leonard Janke的引用
  • 2007.01.05 添加了应用表
  • 2007.01.04 添加了密钥派生函数
  • 2007.01.03 初始发布

下载次数

校验和

  • ASRP.zip
    MD5: 773B2C409A7140CBA16EFF7903AA2C11
    SHA-1: 9CD4BC2C3E156157AA10ADF62994D4065980EC80
  • AutoSeededX917.zip
    MD5: B855380703A24DF9671AE8C7146113A9
    SHA-1: 1B724CD0C28CC4909F7A14F374EE1874CFB49E42
  • FIPS140-2.zip
    MD5: 7E106DBF757F281C764AD6F09DFEF4DA
    SHA-1: 0ACD845C20B4F8FA5EA58C3C04270A8DFB6DCAC7
  • GenRandom.zip
    MD5: B99A0CCC8BA862350235EBEBDFC3A0D2
    SHA-1: 33EA241D0E86E8AB6D86F64FB62C7C67678163CC
  • LCG.zip
    MD5: 0F4A91276B2CE558DB8C8F65218AA32D
    SHA-1: BB598A1A9FC13B519BD5D5CDB37FA52B39E1230C
  • RNGVS.zip
    MD5: 6E608C5AFFFE4D906E435C39BC2CC687
    SHA-1: ED5E73E39E3ADBEDA008A175E4243D8A59ABD254
  • RandomPool.zip
    MD5: 345CF4D59BED53B501ED1D58EF0FD892
    SHA-1: E699F73A53A57178E150A1A020DE4B173F4FF1E9

参考文献

[1] 随机数生成器的偏差，http://www.sciencenews.org/articles/20030927/mathtrek.as，访问时间2007年11月。

© . All rights reserved.