密码编码学原理之随机数和流加密

随机数是密码学中重要的概念，它用途广泛，在密钥分发和认证、会话密钥以及流加密中都有应用。随机数分为真随机数和伪随机数。真随机数是通过将外界物理环境的不可预测的熵源转换成对应的二进制位流得到的，真随机数生成器(TRNG)负责这个转换的过程。伪随机数是将一个固定的值(或者叫种子)应用于一个确定的随机数生成算法而得到的二进制位流。有两种不同的伪随机数生成工具，一种是伪随机数生成器(PRNG)，它生成不限长度的位序列，另一种叫为随机函数(PRF)，它生成固定长度的位序列。TRNG和PRNG的主要区别在于PRNG效率更高，它可以完全是软件算法实现，也可以使用硬件实现，而TRNG需要对真实的不可预测的物理过程进行采用，所以它需要硬件的支持。

伪随机数生成器可以使用专门的算法生成伪随机数，下面我们介绍两种专门的伪随机数生成算法：线性同余和BBS。

线性同余算法可以使用下列表达式表示，其中伪随机数表示为 的序列：

其中 就是种子，当 选择的足够大的时候，生成的 就会有足够的强度。这个算法容易被破解，当知道使用线性同余算法并且获得其中的几个随机数之后就可以通过解方程的方式破解 、 和 ：

BBS是生成安全伪随机数的常用算法，它可以描述为： 和 是大素数， ，种子 是与 互素的随机数，那么伪随机位序列 表示为：

除了使用专有算法外，随机数生成器还可以使用分组加密算法作为产生伪随机数的算法。如TDEA和AES都可以作为随机数生成器的生成算法，并且推荐使用CTR或OFB模式。这两种工作模式下，种子都是由两部分组成的：加密密钥，和一个初始值V。在CTR模式下V作为计数初始值，每次加密后V增加1。在OFB模式下，V更新成前一次的密文。

使用CTR模式的伪随机数生成器叫做CTR_DRBG(计数器模式的确定性随机位生成器)，它使用TDEA或者AES作为加密算法，不同加密算法生成的随机分组也不同。CTR_DRBG的种子的初始化过程是一个随机选择的V值经过随机选择的密钥K加密后，与相应的熵源生成的TRNG异或，得到初始的种子。种子的前半部分是加密密钥，后半部分是初始的V值。密钥和V值的长度由选择的分组加密算法确定。生成伪随机数的过程是使用种子的密钥将V值加密，生成随机分组，然后V值加1，再生成下一组随机分组。经过一定轮数之后，需要更新种子，采用前面讲述的种子初始化算法再生成一个新的种子，然后才能再次生成伪随机分组。

流加密适用于加密大量快速的数据流，数据流是持续流动的，并且不确定每次的数量，所以流加密需要持续不断的更新密钥。流加密最关键是持续不断的生成密钥序列，这个密钥应该是随机的，但应该是伪随机数，而不能是真随机数，因为加密和解密需要相同的密钥序列，对于相同的输入，PRNG可以生成相同的随机数序列，而TRNG生成的随机数序列就是不同的，所以现在的PRNG都可以作为流密码的生成器。除了PRNG可以作位流密码生成器外，还有一些专用的算法生成密钥流，如RC4和Grain-128a。