随机数生成技术概述

发表于 更新于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 11 分钟

在密码学中，熵（entropy，指不可预测的随机性）扮演了一个非常重要的角色，许多算法都要求使用一个不可预测的随机数，只有在生成的随机数不可预测时，这些算法才能保证其安全性，典型应用包括：

  • 密钥生成
  • 生成初始化向量，IV，用于分组密码的 CBC，CFB，OFB 模式
  • 某些签名方案中的盐，如 ECDSA， RSASSA-PSS

一、伪随机数生成器 - PRNG

PRNG（Pseudo-Random Number Generators）是一种数字序列的生成算法，它生成出的数字序列的统计学属性跟真正的随机数序列非常相似，但它生成的伪随机数序列并不是真正的随机数序列！
换句话说，如果输入的初始种子是相同的，PRNG 总是会生成出相同的伪随机数序列，因此也被称为确定性随机比特生成器（DRBG，Deterministic Random Bit Generator）。

伪随机数通常来源于某个生成算法（例如，C库中提供的rand函数），尽管存在可复现的问题，但由于 PRNG 的成本低和速度快，仍然广泛用于现代软件开发中。NIST SP 800-90A规范中描述了三种产生伪随机数的算法：

  • Hash_DRBG：使用单向散列算法作为伪随机数生成的基础算法
  • HMAC_DRBG：使用消息认证码算法作为随机数生成的基础算法
  • CTR_DRBG：使用分组密码算法的计数器模式作为随机数生成的基础算法，可选算法包括 3DES 、AES128 、 AES192 或 AES256 等

实际运用中，我们经常使用 PRNG 从一个很小的初始随机性（熵）生成出大量的伪随机性，这被称做密钥拉伸（Key Stretching）。

二、真随机数生成器 - TRNG

TRNG（True Random Number Generators）作为“真正的随机数，需要具备不可重现性（不能通过给定同样的数据而演算出同一串比特序列），由于计算机算法均具备确定的特性，所以真随机数无法由算法来生成，只能基于硬件设备通过对物理过程的测量来实现，因此也被称为硬件随机数生成器（HRNG，Hardware Random Number Generator）。

TRNG 通常基于一些能生成低等级、统计学随机的“噪声”信号的微观现象，包括：基于环形振荡器采样、直接放大热噪声、基于亚稳态电路Ell、光电效应、利用放射性元素衰变等量子力学的基本量等，这些物理过程在理论上是完全不可预测的，并且已经得到了实验的证实。
TRNG 通常由换能器、放大器和模拟数字转换器组成。其中换能器将物理过程中的某些效果转换为电信号，放大器将随机扰动的振幅放大到宏观级别，而模拟数字转换器则将输出变成数字。
TRNG 从随机过程中收获熵之后，还需要通过后处理技术（诺伊曼校正、异或链、线性反馈移位寄存器、异或周期序列等）消除随机位的概率偏差，并重复重采样过程以满足随机数的长度需求，最后输出高质量的随机数。Apple 安全隔区和恩智浦 STM32 系列安全芯片等都内置了 TRNG 组件。

  • TRNG 满足“完全随机性”，即：不可预测性、均匀性、独立性，并具备保密性要求
  • 由于 TRNG 来源于物理过程，生成速度很慢，通常每秒只能产生很有限的随机比特
  • 为了提高数据产生效率，TRNG 通常用于生成伪随机数生成器的“种子”，也就是熵源（熵池）

三、密码学安全随机数生成器 - CSPRNG

由于 PRNG 无法为随机数提供不可预测性，存在安全隐患，但是 TRNG 的生成速度又太慢，无法及时提供大量随机数，怎么解决这个矛盾呢？答案就是CSPRNG。

CSPRNG（Cryptography Secure Random Number Generators）是一种满足密码学安全要求的 PRNG，需要同时满足以下条件：

  • 不可预测性：即使有人获知了该 PRNG 的 k 位，他也无法使用合理的资源预测第 k+1 位的值
  • 不可回溯性：如果攻击者猜出了 PRNG 的内部状态或该状态因某种原因而泄漏，攻击者也无法重建出内部状态泄漏之前生成的所有随机数

美国国家标准和技术研究所(NIST)制定了随机数发生器的技术规范，称为NIST SP 800 - 22和SP 800 - 90，其推荐的技术路线是 TRNG + PRNG，即 TRNG 作为熵源提供少量且高质量的随机数，通过 PRNG 进行提供大量随机数，这就是 CSPRNG 最常用的设计方法。

大多数的 CSPRNG 结合使用来自 OS 的熵与高质量的 PRNG，并且一旦系统生成了新的熵（这可能来自用户输入、磁盘 IO、系统中断、或者硬件 RNG），CSPRNG 会立即使用新的熵来作为 PRNG 新的种子。 这种不断重置 PRNG 种子的行为，使随机数变得非常难以预测。

  • 基于计数器(CTR)模式下的安全分组密码、流密码或安全散列函数的 CSPRNG
  • 基于数论设计的 CSPRNG，它依靠整数分解问题（IFP）、离散对数问题（DLP）或椭圆曲线离散对数问题（ECDLP）的高难度来确保安全性
  • CSPRNG 基于加密安全随机性的特殊设计，例如 Yarrow algorithm 和 Fortuna，这俩分别被用于 MacOS 和 FreeBSD.

四、对比分析

TRNG CSPRNG PRNG
不可重现性
不可预测性 不可预测性
不可回溯性 不可回溯性
无偏性 无偏性 无偏性
  • 不可重现性：相同的输入必须生成不同的输出
  • 不可预测性：即使有人获知了该 PRNG 的 k 位，他也无法使用合理的资源预测第 k+1 位的值
  • 不可回溯性：如果攻击者猜出了 PRNG 的内部状态或该状态因某种原因而泄漏，攻击者也无法重建出内部状态泄漏之前生成的所有随机数
  • 无偏性：任何数均有平等出现的机会

五、Unix系统的技术实现

随机数在操作系统中非常重要，TCP/IP 序列号、密码盐和 DNS 源端口号都依赖于随机数。CSPRNG 经常被用于以下场景：

  • 随机密钥的产生。比如为对称密码算法加密提供随机密钥。
  • 一次性随机序列的产生。比如用于通信协议，可以防止回放攻击。
  • 用于口令保护的盐(salt)的产生，可以防止口令的预计算攻击（也叫字典攻击）
  • 一次一密。比如直接拿来跟明文异或生成密文，但是只能用一次

类Unix系统通过如下两个虚拟设备提供 CSPRNG:

  • /dev/random（受限阻塞随机生成器）: 从这个设备中读取到的是内核熵池中已经收集好的熵，如果熵池空了，此设备会一直阻塞，直到收集到新的环境噪声。
  • /dev/urandom（不受限非阻塞随机生成器）: 它可能会返回内核熵池中的熵，也可能返回使用之前收集的熵 + CSPRNG计算出的安全伪随机数。它不会阻塞。

random

注意！两者产生的随机数都是从同一个熵池（主熵池）中提取的，只有当各自的熵池耗尽了，它们的行为才有所不同。

一般有个规则，/dev/random 产生的随机数质量高，主要用于一些安全方面，而且，它是阻塞的，对于大部分应用来说，这是不能接受的

对于 /dev/urandom ，当熵池计数器足够的时候，产生真随机数，计数不够的时候，产生伪随机数，最重要的是 它不会阻塞，而且，对于绝大多数的应用来说，伪随机数也能很好的满足需求了

常用命令

在 Linux上，可以通过下面的命令查看当前系统主熵池大小, 单位是二进制位的数量

1
2
[root@localhost ~]# cat /proc/sys/kernel/random/poolsize
4096

提取随机数并转换为 Base64 编码
head -c 32 /dev/random | base64

随机转换为md5（20位）：
head /dev/urandom | md5sum | head -c 20

随机纯数字（20位）：
head /dev/urandom | tr -dc 0-9 | head -c 20

随机小写字母+数字（20位）：
head /dev/urandom | tr -dc a-z0-9 | head -c 20

随机大小写字母+数字（20位）：
head /dev/urandom | tr -dc A-Za-z0-9 | head -c 20

使用系统环境变量($RANDOM)生成随机数
echo $RANDOM | md5sum | cut -c 5-11

编程接口

常见编程语言的 CSPRNG 接口或库如下：

  • Java: java.security.SecureRandom
  • Python: secrets 库或者 os.urandom()
  • C#: System.Security.Cryptography.RandomNumberGenerator.Create()
  • JavaScript: 客户端可使用 window.crypto.getRandomValues(Uint8Array)，服务端可使用 crypto.randomBytes()

附录一：Apple 提供的CSPRNG

Apple 为此提供了运行在 iOS、iPadOS、macOS、Apple tvOS 和 watchOS 内核中的受信任软件 CPRNG（= CSPRNG）。它负责聚合系统中的原始熵并为内核和用户空间的使用者提供安全的随机数。

内核 CPRNG 源自启动过程中的多个熵源并存在于设备的整个生命周期。这些来源包括（取决于可用性）：

  • 安全隔区硬件 TRNG
  • 启动过程中所收集基于时序的时间误差
  • 从硬件中断收集的熵
  • 用于启动过程中保持熵的种子文件
  • Intel 随机指令，例如 RDSEED 和 RDRAND（仅限基于 Intel 的 Mac）

内核 CPRNG 的设计源自 Fortuna 算法，旨在满足 256 位安全级别。它使用以下 API 为用户空间使用者提供高质量的随机数：

  • getentropy(2) 系统调用
  • 随机设备 (/dev/random)

内核 CPRNG 通过写入随机设备接受用户提供的熵。

附录二：DUAL_EC_DRBG 的安全漏洞

2005年，NIST SP 800-90A草案公开发布，其包含四个随机数生成算法：HASH_DRBG, HMAC_DRBG, CTR_DRBG, DUAL_EC_DRBG。

2006年，NTNU（挪威科技大学）的 Kristian Gjøsteen 公开宣称“Dual_EC_DRBG is not cryptographically sound”，并构造了一个具有 0.0011 优势的 bit-predictor，证明了其不满足 CSPRNG 的随机数发生器设计原理。

在 Crypto 2007（原美密会，现为国际密码会议）会议上，Bruce Schneier 宣布该标准中存在技术后门，使得拥有某特殊资源的攻击者能够轻而易举地攻击其中的 Dual ECC DRBG 随机数产生器算法，从而得到该算法后续的所有随机数值。

2013年，Edward Snowden 泄露的内部备忘录曝光了 NSA 的 Bullrun 项目，显示该项目在 Dual_EC_DRBG 中植入了一个后门。

2013年9月19日，EMC 公司的 RSA 事业本部宣布，该公司已向 BSAFE（一个用于开发安全应用的工具套件） 及 Data Protection Manager（一个用于数据加密的工具）的客户发出呼吁，不要使用其默认的 Dual_EC_DRBG 技术标准，RSA 目前正在审查其所有的产品。

路透社报道，NSA 向 RSA 支付了一千万美元，要求其在 BSAFE 中将 Dual_EC_DRBG 设为默认的 CSPRNG。随后，RSA公司发表声明否认与 NSA 有任何的秘密接触，以便在BSAFE加密库中放置有缺陷的随机数生成器算法，但并未否认或者解释之前与 NSA 之间的大额交易。

行业普遍认为，Dual_EC_DRBG 算法可能潜伏着一个后门，如果以特定方式选择定义算法的一个参数，NSA 将可能预测出算法产生的随机数。

参考文献

技术分析

文档下载