伪随机数的生成和流密码
本质上只有两种产生随机位或随机数的策略：伪随机数发生器PRNG或确定随机位发生器DRBG、真随机数发生器TRNG或非确定随机位发生器NRBG
用途：认证方案、会话密钥的产生、RSA公开密钥加密算法中的密钥的产生；
要求：随机性、不可预测性；
随机性评价标准：分布均匀性、独立性；
不可预测性：前向不可预测、后向不可预测
真随机数TRNG
真随机数源难以获得：随机性和精确度问题。例如：电离辐射脉冲检测、抛硬币、热噪声（相应的硬件）
真随机数发生器TRNG把一个很随机的源作为输入（熵源），源或者源的组合作为算法输入，产生随机的二元输出。
真随机数发生器，可能的随机源：声音/图像输入、磁盘驱动。
TRNG通常只适用于密钥扩展和其他只需要少量随机位的应用。这是因为TRNG通常是低效的且只能产生低位率的随机位。
英特尔数字随机数发生器（DRNG）第一次实现了和PRNG相当的位生成率，它提供新的多核芯片。两个显著特征：完全用硬件实现，更安全更快；整个DRNG和处理器再同一个多核芯片上，这减少了硬件随机数发生器之间的I/O时延。
DRNG硬件架构，从电路的热噪声生成随机数。电路的核心由两个反相器（非门）组成。
硬件熵源的核心是一对互相反馈的反相器。
PRNG_34">伪随机数PRNG
伪随机数（Pseudorandom Number）使用确定算法生成的，但能够经受随机性检测的算法。由伪随机数产生器(PRNG)产生。
伪随机数发生器PRNG，使用算法来生成随机数，算法是确定的，产生的序列并非统计随机的，但可以经受住随机性检测。取一个固定值称为种子作为输入，用一个确定的算法产生位输出序列，通过有反馈路径，由算法的部分结果反馈作为输入，而其他部分作为输出位。需要注意输出位仅仅由输入值决定，所以知道算法的种子的敌手可以重现整个位流。
两种基于应用的不同形式的PRNG：伪随机数发生器，用于生产不限长位流的算法成为PRNG；伪随机函数（PRF）用于产生固定长度的伪随机数位串。除了产生位的数量外，PRNG和PRF之间没有差别。
PRNGPRF_46">对PRNG和PRF输出保密性的这个通用要求导致对随机性、不可预测性以及种子的特性的特定要求：
对随机性：均匀性、可伸缩性、一致性；
（随机性测试：频率测试、游程测试、Maurer通用统计测试；）
不可预测性：前向不可预测性和后向不可预测性；
前向不可预测性：不知道种子，无法依据已有bit预测下一bit；
后向不可预测性：从序列无法推出种子值；
种子的要求：种子必须不可预测，实际上种子本身必须是随机数或伪随机数。
PRNG_62">可以用TRNG为何还需要用PRNG？
如果应用是流密码，那么TRNG是不实际的。发送者需要产生和明文一样长的位密钥流，并把密钥流和密文安全传送给接受者。如果使用PRNG，发送者仅需给接收方安全传送流密码的密钥，通常是54位或128位。即使是PRF应用，即只需要产生有限数量的位，也希望用TRNG为PRF提供种子，并使用PRF的输出而不是直接使用TRNG。TRNG可能会产生不平衡的二元序列。PRF具有使TRNG的输出更随机化的效果，从而消除不平衡性。最后，用于产生真随机数的机制在速率方面也许不能跟得上需要随机位的应用。
PRNG_68">用于生成PRNG的算法：
特意构造的算法（例RC4）
基于现有密码算法的算法（对称分组密码、非对称密码、Hash函数和消息认证码）
线性同余发生器
X n + 1 = ( a X n + c ) m o d m X_{n+1}=(aX_n+c) \mod m Xn+1=(aXn+c)modm
其中：模m满足m>0；乘数a满足 0 ≤ a < m 0 ≤ a<m 0≤a<m；增量c满足 0 ≤ c < m 0≤c<m 0≤c<m；初始值/种子 X 0 X_0 X0满足 0 < = X 0 < m 0<=X_0<m 0<=X0<m
要设计一个好的随机数发生器，对a,c,m的选择很重要；m一般很大，一般m接近给定的计算机所能表示的最多非负整数，例：32位机，m选择接近or等于 2 31 2^{31} 231的值
攻击方法
若知道a,c,m，则由一个随机数可以知道后继随机数；即使只知道使用该算法，且知道了四个连续随机数，形成三个线性同余式，就可恢复a,c,m
结论：一旦知道序列的一小部分，不可预测程度就变得很差
评价伪随机数发生器的三个标准：
T1：生产函数应是全周期的，即函数在重复之前应该产生0–m-1之间的所有数；
T2：产生的序列应显得随机；
T3：生产函数可以用32位运算器方便地实现。
使用内部系统始终来修正随机数流：每隔N个数就以时钟值对m取模作为新的种子来产生新的序列；直接将随机数加上时钟值再对m取模；
BBS发生器
基于公钥算法，是现在广泛使用的安全随机数产生方法
选取两个大素数p,q，满足 p ≡ q ≡ 3 m o d 4 p \equiv q \equiv 3 \mod 4 p≡q≡3mod4，令 n = p ∗ q n=p*q n=p∗q.
选取一个随机数s，且要求s与n互素，即p或q都不是s的因子。
算法：
X 0 = s 2 m o d n f o r i = 1 t o ∞ : X 1 = X i − 1 2 m o d n B i = X i m o d 2 X_0=s^2 \mod n\\ \quad for\quad i=1\quad to\quad \infty:\\ \quad \quad \quad \quad X_1=X_{i-1}^2 \mod n\\ \quad \quad \quad B_i=X_i \mod 2 X0=s2modnfori=1to∞:X1=Xi−12modnBi=Ximod2
BBS被称为密码安全伪随机位发生器（CSPRBG）
安全性是基于对n的因子分解困难性上
优点：在续位测试下，满足不可预测性，即：不存在多项式时间算法，在给定序列的前k位输入时，以不可忽略的概率预测出第k＋1位。安全性基于分解大整数N的困难性；给定任意已知bit仍满足不可预测性
缺点：很慢，因为n必须很大；对密码学应用而言太慢了，仅适用于密钥生成
使用分组密码的伪随机数产生
密码学应用中，可以使用分组加密来生成随机数
常用于由主密钥生成会话密钥
两种已被广泛接受的构建PRNG方法：CTR，OFB
CTR计数器模式（用于NIST、ANSI、RFC） X i = E K m [ i ] X_i= E_{Km}[i] Xi=EKm[i]
OFB输出反馈模式（用于ANSI、RFC） i = E K m [ X i − 1 ] i= E_{Km}[X_{i-1}] i=EKm[Xi−1]
种子由两部分组成：加密密钥值以及每产生一个随机数分组后都要由更新的V值
ANSI X9.17伪随机数发生器
是密码学意义上最强的伪随机数发生器之一，使用了3DES来加密。
输入：用2个伪随机数来输入；
密钥：使用3个3DES加密模块；
输出：64位伪随机数和64位的种子。
算法：
其中，
EDE：3DES； K 1 , K 2 K_1,K_2 K1,K2：3DES的密钥，56x2bit； D T i DT_i DTi：第i轮开始时的日期/时间，64 bit； V i V_i Vi：第i轮的种子值，64bit； R i R_i Ri：第i轮产生的随机数；
R i = E D E K 1 , K 2 [ V i ⊕ E D E K 1 , K 2 [ D T i ] ] R_i = EDE_{K_1, K_2}[V_i ⊕ EDE_{K_1, K_2}[DT_i]] Ri=EDEK1,K2[Vi⊕EDEK1,K2[DTi]]
V i + 1 = E D E K 1 , K 2 , [ R i ⊕ E D E K 1 , K 2 [ D T i ] ] V_{i+1} = EDE_{K_1, K_2},[R_i ⊕ EDE_{K_1, K_2}[DT_i]] Vi+1=EDEK1,K2,[Ri⊕EDEK1,K2[DTi]]
此方法在金融安全及PGP中被使用
流密码：
发生器的输出成为密钥流，密钥流和明文流的每一个字节进行按位异或运算，得到一个密文字节。
（不同于一次一密使用的真随机数流，流密码使用的是伪随机数流）
流密码一个潜在的优点是没有使用分组密码作为构建模块的流密码通常都比分组密码更快、使用的代码更少。
RC4：
用1-256个字节（8-2048位）的可变长度密钥初始化一个256个字节的状态向量S，从始至终S包含从0-255所有的8位数，每产生一个k值，S中的元素个体就被重新置换一次。
