伪随机 数 生成 器
![]() |
伪随
PRNG
PRNG
周期 性
[编辑]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.
举例
基 于线性 递归的 生成 器
[编辑]伪随
1997
密 码安全的 伪随机 数 生成 器
[编辑]适合于加
CSPRNG
- stream ciphers
技 术模式 或 输出反 馈模式 的 块加密 保 证密码安全的 PRNG,例 如微软的密 码学应用编程接 口 函数 CryptGenRandom,Yarrow algorithm(集成 进Mac OS X和 FreeBSD)以及Fortuna- 组合PRNG
把 多 个PRNG算法 组合在 一起以移除可检测的非随机性 基 于数学 难题假 设的设计,例 如Micali–Schnorr generator、Naor-Reingold伪随机 函数 、Blum Blum Shub算法 ,这些算法 具有 较强的 安全 性 。相 比 于传统方法 ,这些算法 的 速度 非常 缓慢,对于许多应用是 不 实际的 。
BSI评估标准
[编辑]- K1 - 产生
的 随 机 数 序列 彼此 不同 的 概 率 应该是 很高的 - K2 -
根 据 某 些统计测试,无法分 辨 产生的 序列 和 真 随 机 序列 。这些测试包括 : monobit测试(序列 中 的 0和 1的 数量 相等 )、poker测试(chi-squared测试的 特殊 情 况)、runs测试(不同 长度运行的 频率)、来 自 于BSI[15]和 NIST,[16]的 longruns测试、autocorrelation测试。 - K3 - 给定
任 何 子 序列 ,任 何 攻 击者都 无法计算后 续序列 或 者 生成 器 的 内部 状 态 - K4 - 给定
生成 器 的 内部 状 态,任 何 攻 击者都 无法计算之 前 的 序列 或 者 生成 器 之 前 的 状 态
对于
数学 定 义
[编辑]给定
- -
上 的 概 率 分布 ,其中是 实数集 上 的 Borel set - -
非 空 子 集 ,例 如 - -
非 空 集合
相關 條目
[编辑]參考 資料
[编辑]- ^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles. Recommendation for Key Management (PDF). NIST Special Publication 800-57. NIST. July 2012 [19 August 2013]. (
原始 内容 存 档 (PDF)于2013-06-26). - ^ Pseudorandom number generators. Khan Academy. [2016-01-11]. (
原始 内容 存 档于2020-11-26). - ^ Von Neumann, John. Various techniques used in connection with random digits (PDF). National Bureau of Standards Applied Mathematics Series. 1951, 12: 36–38 [2019-02-25]. (
原始 内容 存 档 (PDF)于2020-11-06). - ^ Press et al. (2007), chap.7
- ^ L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor—Lovric M.) Springer.
- ^ Random (Java Platform SE 8) (页面
存 档备份,存 于互联网档案 馆), Java Platform Standard Edition 8 Documentation. - ^ Random.java (页面
存 档备份,存 于互联网档案 馆) at OpenJDK. - ^ Press et al. (2007) §7.1
- ^ Matsumoto, Makoto; Nishimura, Takuji. Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator (PDF). ACM Transactions on Modeling and Computer Simulation (ACM). 1998, 8 (1): 3–30 [2019-02-25]. doi:10.1145/272991.272995. (
原始 内容 存 档 (PDF)于2019-09-25). - ^ Marsaglia, George. Xorshift RNGs. Journal of Statistical Software. July 2003, 8 (14) [2019-02-25]. (
原始 内容 存 档于2015-09-02). - ^ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto. Improved long-period generators based on linear recurrences modulo 2 (PDF). ACM Transactions on Mathematical Software. 2006, 32 (1): 1–16 [2019-02-25]. doi:10.1145/1132973.1132974. (
原始 内容 存 档 (PDF)于2020-08-11). - ^ Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. : 73. ISBN 978-0-387-48741-0.
- ^ Pass, Rafael. Lecture 11: The Goldreich-Levin Theorem (PDF). COM S 687 Introduction to Cryptography. [20 July 2016]. (
原始 内容 存 档 (PDF)于2019-07-12). - ^ Matthew Green. The Many Flaws of Dual_EC_DRBG. [2019-02-25]. (
原始 内容 存 档于2016-08-20). - ^ 15.0 15.1 Schindler, Werner. Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik: 5–11. 2 December 1999 [19 August 2013]. (
原始 内容 存 档 (PDF)于2018-01-19). - ^ Security requirements for cryptographic modules. FIPS. NIST: 4.11.1 Power–Up Tests. 1994-01-11 [19 August 2013]. (
原始 内容 存 档于2013-05-27).
參考 書目
[编辑]- Barker E., Kelsey J., 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. ISBN 0-201-89684-2. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
- Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
- 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.
- Peterson, Ivars. The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. 1997. ISBN 0-471-16449-6.
- Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
- Viega J., "Practical Random Number Generation in Software (页面
存 档备份,存 于互联网档案 馆)", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
外部 連結
[编辑]- TestU01 (页面
存 档备份,存 于互联网档案 馆): A free, state-of-the-art (GPL) C++ Random Number Test Suite. - DieHarder (页面
存 档备份,存 于互联网档案 馆): A free (GPL) C Random Number Test Suite. - "Generating random numbers (页面
存 档备份,存 于互联网档案 馆)" (in embedded systems) by Eric Uner (2004) - "Analysis of the Linux Random Number Generator (页面
存 档备份,存 于互联网档案 馆)" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006) - "Better pseudorandom generators (页面
存 档备份,存 于互联网档案 馆)" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)