伪随机数产生的背景

大量基于密码学的网络安全算法和协议都要使用二进制随机数

这些应用对随机数序列有两个要求

  • 随机性：随机性可以用下面两个标准评价
    分布均匀性：序列中的位分布应是均匀的，即0、1出现的频率大致相等
    独立性：即序列中任何子序列不能由其他子序列推导出
  • 不可预测性：即攻击者不能从先前的随机数推导出后面的随机数

随机数发生器可以分为真随机数发生器TRNG和伪随机数发生器PRNG

TRNG把一个或多个很随机的源（例如键盘敲击的时间模式、鼠标移动等）作为输入，称为熵源，并转换为二进制序列输出
一般而言，TRNG并不具有实用性，因为其有输出序列不可重现、效率较低等等缺点

而PRNG则选择一个固定值作为输入，称为种子，并用一个确定性的算法产生二进制序列输出

对随机性而言，要求PRNG尽管输出的位流是确定的但要“显示随机”
然而并没有单个测试可以判定一个PRNG算法产生的输出的随机性，一般做法是设计一系列测试，如果该PRNG算法在多个测试上表现良好，则认为它满足要求
对PRNG的随机性测试应该从如下几方面着手

  • 均匀性：在序列的任何点，0或1出现的次数大约相等
  • 可伸缩性：若序列是随机的，那么其中的任何子序列也应该是随机的，即任何子序列都应通过测试
  • 一致性：对所有种子，发生器的行为必须具有一致性，也即使用任何种子都应通过测试

对于不可预测性而言，PRNG应具有两种形式的不可预测性

  • 前向不可预测性：若不知道种子，则无论已知序列中前面多少位，都无法预测下一位
  • 后向不可预测性：从产生的任何值都不能推出种子

显然若已知种子和PRNG算法，则攻击者可以重现整个随机数序列，因此种子必须不可预测且必须保密
事实上，为了保证种子安全，种子必须是随机数或伪随机数，典型的，种子可由TRNG产生

常见的PRNG算法

线性同余发生器

线性同余发的随机数序列${X_n}$按如下公式迭代获得

其中$X_0$即为种子

显然参数$a,c,m$的选择对线性同余法的好坏影响很大，例如$a=c=1$显然不行

一般要求$m$很大，以便产生较长的不同随机数序列，同时可以证明若$m$为素数且$c=0$，则存在$a$使得输出序列的周期为$m-1$。$a=7^5,c=0,m=2^{31}-1$就是使用非常广泛的一组参数

然而线性同余法并不那么安全，若攻击者确定了4个连续的随机数$X_0,X_1,X_2,X_3$，则可通过如下方程组直接求出$a,c,m$，从而确定整个随机数序列

BBS发生器

BBS发生器是普遍使用的产生安全伪随机数的算法，其方法如下

首先选择两个大素数$p,q$，满足$p\equiv q\equiv (\mod 4)$
令$n=pq$，并选择随机数$s$满足$s$与$n$互素，然后BBS按如下算法产生随机位流${B_i}$

BBS的安全性是基于对n的因子分解的困难性上的

使用分组密码的PRNG

使用分组密码PRNG基于这样一个显然的现象，即对称分组密码产生的输出看起来是随机的，即密文里里没有可用于推导明文的规律
基于分组密码的CTR模式和OFB模式构建PRNG是两种广泛使用的方法

如图所示，基于分组密码的PRNG的种子为密钥$K$和初值$V$
CTR模式中，$V$每次加密后增加1作为下一次输入，OFB中下一次输入为上一次的随机数输出

SP 800-90A、ANS标准X9.82以及RFC4086都推荐了CTR模式
而X9.82和RFC 4086推荐了OFB模式

prng_blockcipher

ANSI X9.17伪随机数发生器

ANSI X9.17伪随机数发生器是密码学意义上最强的伪随机数发生器

算法有两个64位输入$DT_i$和$V_i$，其中$DT_i$代表当前的日期和时间，每产生一次随机数更新一次，$V_i$为第$i$轮产生随机数的种子，需要指定$V_0$

产生伪随机序列的公式如下，其中$EDE([K_1,K_2],X)$表示两个密钥三重DES的加密-解密-加密过程，$R_i$为该轮随机数输出

prng_ansix9.17