茶年 · 中文维基百科

伪随机数生成器

Wikipedia · 2026-05-16 维基百科 👁 0 阅读

伪随机数生成器（，），又被称为确定性随机位元生成器（，），是一个生成数字序列的算法，其特性近似于随机数序列。伪随机数生成器生成的序列并不是完全随机，生成的每一个数完全由一个初始值决定，这个初始值被称为随机种子（种子有时使用接近于完全随机的硬件随机数生成器生成）。尽管硬件随机数生成器可以生成接近于完全随机的序列，但伪随机数生成器因为其生成速度和可再现的优势，在实践中显得尤为重要。

**'多用於仿真（例如蒙地卡羅方法）、电子游戏（例如程序化生成）以及密码学等領域。此加密程序不能从以前的输出中预测输出，而要采用更复杂的、不具有简单PRNGs线性特性的算法。

**'的核心是具有良好的统计特性，通常需要严格的数学分析来证明其生成結果准确性足够接近完全随机，以满足预期用途。

周期性
PRNG可以使用随机种子从任意的初始状态启动，使用同一状态进行初始化时，它将始终生成相同的序列。PRNG的周期定义为：序列的无重复前缀长度在所有起始状态中的最大值。周期受状态数的限制，通常用位元数表示。然而，每增加一个位元，周期长度就可能增加一倍，所以构建周期足够长的PRNG对于许多实际应用程序来说是很容易的。

如果PRNG的内部状态包含n位，那么它的周期不会超过2^n，甚至可能非常短。对于大多数PRNG，周期长度的计算并不需要遍历整个周期。线性反馈移位寄存器（）的周期通常正好是2^n-1。線性同餘方法的周期可以通过因式分解进行计算。 尽管PRNG在达到周期之后会出现重复的结果，但重复序列的出现并不意味着到达了一个周期，因为它的内部状态可能比输出要大很多。对于输出为1位的PRNG，这一点尤其明显。

潜在问题
在实践中，许多常见的PRNG会显示出特定跡象，導致它們無法通過統計學的模式檢測。约翰·冯诺依曼警告，不要把PRNG错误地解释为真随机数生成器，还开玩笑说：“任何使用算术方法生成随机数的人，都是有罪的”。這些缺陷包括:

  • 某些种子状态的周期短於預期:在这种情况下，这种种子被称为“弱種子”；
  • 生成的大量数字分布不均匀；
  • 连续值之間存在关联性；
  • 输出序列的空間維度分布不佳；
  • 特定值出现的的間距与随机序列分布的分布特徵不同。

在許多领域，21世纪之前依赖PRNG的研究工作，由于使用了低品质的PRNG，其可靠性遠低於理想。 即使在今天，有时也需要谨慎，如下面的来自的警告所示:The list of widely used generators that should be discarded is [long] ... Check the default [PRNG] of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.

举例来说，考虑一下广泛使用的编程语言Java。Java仍然使用線性同餘方法 ()来实现PRNG。 然而其的品質很差。直到 Java 17 版本，Java 的隨機數支援才得到了顯著的升級與改進。

一個避免了主要问题而且运行速度快的著名PRNG是1998年发布的梅森旋轉演算法。學界也開發了許多在運算效能與統計表現上更高品質的 PRNG。

基于线性递归的生成器
在20世纪下半叶，PRNG的标准算法由線性同餘方法（）构成。众所周知，LCG的质量不优，但也没有更好的方法。Press et al. (2007) 描述了这种情况：“如果所有因为LCG而受质疑的科学论文从书架上消失，那么每一个架子上都会有一个拳头大小的空隙”。

伪随机生成器构造的重大进展，是在二元域中引入的线性递归技术，这种生成器和线性反馈移位寄存器有关。

1997年发明的梅森旋转算法，避免了很多问题。梅森旋转算法的周期长达2^{19937}-1，被证明在623个维度上是均匀分布的（对于32位数值），同时它的运行速度比其他统计方法快。

在2003年，George Marsaglia提出了xorshift生成器家族，它也基于线性递归。这种生成器的运行速度非常快，再结合非线性操作，通过了强有力的统计测试。

在2006年，WELL家族的生成器被提出。 WELl生成器在某些方面提高了梅森旋转算法的质量，梅森旋转算法具有非常大的状态空间，而且从含有大量0值的状态空间中的恢复非常缓慢。

密码安全的伪随机数生成器
适合于加密应用程序的PRNG称为加密安全的PRNG（）。CSPRNG的一个必要条件是不知道初始种子的敌人在分辨生成器的输出序列和真随机序列时只有可忽略的优势。换句话说，若PRNG只需要通过特定统计测试时，则CSPRNG必须通过种子规模的多项式复杂度内的所有统计测试。尽管这一性质的证明超出了计算复杂性理论目前的技术水平，大量的证据如下，把CSPRNG规约到计算困难的数学问题，例如整数分解。 通常，在一个算法被认证为CSPRNG之前需要多年的检验。

CSPRNG的类别包括：

  • stream ciphers
  • 技术模式或输出反馈模式的块加密
  • 保证密码安全的PRNG，例如微软的密码学应用编程接口函数CryptGenRandom，Yarrow algorithm（集成进Mac OS X和FreeBSD）以及Fortuna
  • 组合PRNG把多个PRNG算法组合在一起以移除可检测的非随机性
  • 基于数学难题假设的设计，例如Micali–Schnorr generator、Naor-Reingold伪随机函数、Blum Blum Shub算法，这些算法具有较强的安全性。相比于传统方法，这些算法的速度非常缓慢，对于许多应用是不实际的。

通用PRNG。已经证明，密码安全的PRNG可以通过单向函数构造。然而，这些构造在实际应用中非常缓慢，主要用于理论研究。
有证据表示，NSA向NIST认证的伪随机生成器 Dual_EC_DRBG注入了非对称后门。

大多数使用PRNG的密码算法的安全性是基于下面的假设：PRNG和真随机序列的分辨是不可行的。

BSI评估标准
德国联邦信息安全办公室(, )制订了四条评估确定性随机生成器的标准。 如下：

  • K1 - 产生的随机数序列彼此不同的概率应该是很高的
  • K2 - 根据某些统计测试，无法分辨产生的序列和真随机序列。这些测试包括： monobit测试（序列中的0和1的数量相等）、poker测试（chi-squared测试的特殊情况）、runs测试（不同长度运行的频率）、来自于BSI的longruns测试、autocorrelation测试。
  • K3 - 给定任何子序列，任何攻击者都无法计算后续序列或者生成器的内部状态
  • K4 - 给定生成器的内部状态，任何攻击者都无法计算之前的序列或者生成器之前的状态

对于密码学应用，只有满足K3和K4标准的生成器是可以接受的。

数学定义
给定

  • P - \left(\mathbb{R},\mathfrak{B}\right)上的概率分布，其中\mathfrak{B}是实数集上的Borel set
  • \mathfrak{F} - 非空子集\mathfrak{F}\subseteq\mathfrak{B}，例如 \mathfrak{F}=\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}
  • A\subseteq\mathbb{R} - 非空集合

称一个函数f:\mathbb{N}_1\rightarrow\mathbb{R}（\mathbb{N}_1=\left\{1,2,3,\dots\right\}是正整数的一个子集）为一个伪随机生成器，当且仅当：

  • f\left(\mathbb{N}_1\right)\subseteq A
  • \forall E\in\mathfrak{F} \quad \forall 0

相關條目

  • 随机数生成
  • 随机性
  • 偽亂數二進位數列
  • 硬件随机数生成器
  • Random.org

參考資料
參考書目

  • Barker E., Kelsey J., [http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf Recommendation for Random Number Generation Using Deterministic Random Bit Generators] , NIST SP800-90A, January 2012
  • Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
  • Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
  • Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
  • Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. . Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
  • Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996.
  • von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.

*

  • Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
  • Viega J., "[http://www.acsac.org/2003/papers/79.pdf Practical Random Number Generation in Software] ", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

外部連結

#算法信息论 #密码学 #伪随机性 #伪随机数生成器

评论 (0)

  • 还没有评论，来抢沙发吧。