密码学中的随机数_加密随机数

#各人学习经验和知识总结，欢迎大家传阅，禁止商业用途 #

1.背景

 随机数的生成对密码学来说是极其重要的，比如网络安全算法中 秘钥分发和互相认证，短时间内对话使用的 会话秘钥生成，RSA公钥加密算法的密钥生成，所以完全有必要弄懂随机数发生器。

随机数又分为真随机发生器（TRNG）和伪随机数发生器（PRNG），TRNG使用一个随机源作为输入，然后输出随机位流，这个输入通常被叫做 “熵源”，一切不可预测的东西都可以被作为熵源，比如此时电脑上cpu的温度，鼠标的位置，cpu的电压值，电流，空气湿度等，由于熵源输入是不可复现的，所以输出位序列也是不可复现；而PRNG取一个确定性输入（种子），再通过确定性算法生成输出位序列；这些输出序列是随性的，但是如果知道了算法和种子是可以复现出序列的。如下图所示，图1位为TRNG，图2为PRNG。

2 伪随机序列生成方法

2.1 简单算法函数生成：

伪随机生成器主要有两类算法，分别是线性同余生成器和BBS生成器。

2.1.1 线性同余生成器

                                                            公式1

其中 m为模，a为乘，c为增量，X0为种子

如果对方知道使用的是线性同于函数，那就可以通过一小部序列推算出m、a、c参数，就可以知道所有的序列

2.1.2BBS生成器

        先选择两个大素数p和q，满足 p = 3mod4, q =3mod4 ，然后按照下面方法迭代：

                                        

                                        

                                               

                                                

BBS被称为密码安全伪随机位生成器（CSPRBG），因为不能通过输出序列的前K位输入，能以大于1/2的概率预测第K+1位。

2.2 使用分组密码生成伪随机数字

2.2.1常用的两种分组密码的PRNG机制如下图所示：

   图3为CTR模式，也就是计数器模式，每轮输出密文作为伪随机位，图4为OFB，负反馈模式，初始值V的更新为密文。其中key必须是来源于熵源，也就是我们基于一个真实的随机数，然后通过加密算法生成随机序列，这里的V值可以设定为任意值，没有特俗要求。

2.2.2 CTR_DRBG（计数器模式确定性随机位发生器）

        单独介绍这个生成器的原因是因为其已经被多个厂家广泛应用

   图5是用来生成种子（key 和 V），然后把种子给到图6生成函数用来生成伪随机位，由于为保证安全性，生成函数里面的 +1 操作，有个上限，超过上上限后，就需要使用图5生成新的key和V。

2.3 反馈移位寄存器

        移位寄存器（FSR）结构如上图所示，A1,A2,...An分别是多项式的系数，用公式表示为：

                              

若系数Ai为0，那图上对应的异或可以省略。

上述的反馈为线性的，还可以使用非线性，即Bi之间直接进行运算

非线性与线性反馈组合可以作为伪随机生成器的一个方法，大家根据自己兴趣取研究。

3 伪随机数的应用：

有了伪随机序列生成方法，我们就可以用来生成和明文一样长的序列，也被称为流密码，将流密码和明文异或后就可以得到密文。相反，将密文与流密码异或后可得到明文；这种伪流密码的一个例子就是RC4，RC4的算法比较简单，有兴趣可以看看维基百科，但RC4的安全性最近被发现有漏洞，已经被NIST禁止政府用途使用。

4 真随机数发生器（TRNG）

通过采集自然界中的无序的模拟信号来作为熵源，比如电磁信号，辐射值等，这种方法虽然有效，但生成的序列速度极其慢；为此一般采用的方法是熵源+反馈算法生成伪随机数。

其中英特尔采用了个数字随机数发生器：                

图中两个pmos的栅极连接到时钟上，当时钟信号为0时，两个管子都打开，两个反相器的输入和输出均为1，在热噪声的作用下，节点A和节点B的信号分别偏移到反向值，于是形成稳定态；随着时钟的不断置位，反相器的输出值也在随机化生成bit流，也就是熵源，熵源作为 2.2.2中算法 CTR_DRBG的输入。为了调节熵源的输出可能出现偏差，一般对熵源做一个hash计算，英特尔使用的调节器为 AES_CBC_MAC，即基于AES的CMAC加密方法，经过调节器调节后，输出值再给到CTR_DRBG函数，然后得到伪随机序列 。