【原】密码学的骰子——随机数

做开发的工程师们应该或多或少都接触过随机数，可能认为它就是一个随机生成的数字嘛，使用时也很简单，只要调用开发语言提供的函数即可。但实际上随机数后面还是有着比较复杂但也有趣的知识点的。

根据一般定义，随机数应该具有以下三个性质：随机性，不存在统计学偏差，是完全杂乱的数列，即分布均匀性和独立性；不可预测性，不能从过去的随机数数列推测出下一个出现的数；不可重现性，不能重现相同的数列。

我们在平时编程开发里用到的随机数，一般都只满足第一个条件，这种只满足随机性分布的随机数，就叫做伪随机数或弱伪随机数。这是因为编程语言提供的随机数生成方法（学名叫伪随机数生成器）是靠软件算法实现的，既然是算法，那就必定遵循了一定的规律，也就有被预测的可能。像常用到的C语言的rand库和Java的java.util.Random类，就是采用了线性同余算法生成随机数。虽然名字好像不好听，但伪随机数已经满足大多数应用场景的需求了。

但对于密码学来讲，伪随机数就远远不够了。除了随机性，密码学要求的随机数还要具备不可预测性。我们把具有这两个性质的随机数叫做密码学安全的伪随机数或强伪随机数。在密码学中随机数的用途很广，主要有以下几个方面：

l 生成密钥：无论是对称密钥还是公私钥对，生成过程中都有随机因子参与其中，以增加密钥被破解的难度；

l 生成Nonce：Nonce是Number used once或Number once的缩写，意思是只用一次的数字。通过在数据里加入Nonce，哪怕是对同样的明文加密或签名，都可以保证每一次的加密或签名结果都不相同，以防止重放攻击，这一点对于身份验证系统尤其有意义。所谓重放攻击就是指攻击者截获了你提交的验证信息，然后将信息原封不动的提交给验证系统，冒充你进行身份验证。

l 加盐：加盐都是Nonce的拓展应用，基本原理也是在加密时向明文掺入随机数因子，以增加加密结果的不可预测性。在密码学里，有这样一个基本原则：加密结果尽量不要保留原数据的规律。举个例子：对称加密都是采用分组加密模式，也就是将原文数据分成组，对每一组进行加密，最后将得到的多组密文合并起来。下图中最左边是原图，中间就是用对称分组加密的方式生成的密文。可以看出，虽然作为分组的原图中每一块区域的都加密了，但颜色一致的区域加密后的数据也是一样的，组合成的密文图像还是带有原图的规律，我们依然可以看出原图的大体内容。针对这个问题，可以在分组数据中加入随机数，使得即使是同样的数据，加密后的结果也不一样。最右边就是经过上述处理后加密的结果，可以看出加密后图像已完全没有任何规律可循了。对称加解密的初始化向量或非对称加解密中的Padding都属于这种加盐应用。

l Blinding：与加盐的原理类似，只不过是针对密文。话说有一种RSA攻击方式叫做时序攻击，基本方法就是攻击者根据解密所花费的时间确定私钥，比如这一位私钥为0时，解密花1ms，私钥为1时，解密要花10ms，攻击者通过构造不同密文，统计解密花费的时间，理论上可以推算出私钥。针对这种攻击，可以先将密文与随机数进行合并，再送给私钥解密，这样就无法通过时间推算出私钥了。这种方法叫Blinding。

综上所述，密码学就是利用了随机数的随机性和不可预测性，提高密钥和加解密过程的复杂性和不可预测性，以增加被攻破的难度。

那么，密码学安全的伪随机数或强伪随机数如何生成呢？前面分析过了，靠软件算法生成是不靠谱的。科学已经证明，如果要实现不可与预测性的随机数，需要借助物理规律、人品或者老天爷，比如掷钱币、骰子、滑动鼠标的轨迹、电子元件噪声、核裂变、量子理论、大气辐射等等。以它们为随机源生成的随机数，是满足密码学安全要求的。实际中基本都是利用电子元件的噪声原理，制作出专门的随机数发生器芯片。而一般计算机使用的CPU或主板是没有这种随机数发生器功能的，因此，在密码学的应用中，随机数发生器成了USBKey的标配，安全的运算，不能没有它的参与。你看，又一次回归到了“私钥永远不出KEY”的金科玉律。

所谓“有一利必有一弊”，强随机数虽然安全，但缺点就是运算速度太慢。我们做过一个实测，在同一台PC主机和生成程序的情况下，采用USBKey生成1000组，每组128KB的随机数，共计耗时约12个小时；采用软件函数库生成同样数量的随机数，只用了不到一分钟。

最后聊聊真随机数，真随机数就是除了随机性和不可预测性外，还需具有不可重复性，也就是产生的随机数列，不可能再次出现。但是在给定边界条件下，是不存在真随机数的，因为随机数范围有边界，那计算出的随机数列必然有重复。不过如果边界条件十分复杂且难以捕捉，我们也可以认为它是真随机数。很多伪随机数列从局部看，都展现了完美的随机性，但如果你把这个随机数列拉长，就会发现它的分布也是有规律的。而真随机数，就是把数列拉的无限长，也是没有任何规律所循。这也就是测试一个随机数发生器质量时，样本数据量要足够大的原因。

其实说到这，不可避免的出现了一个根本问题：世界上到底有没有真正的随机数？前面说过，随机数的产生有赖于物理现象的随机性，但我们现在认为随机的物理现象，是不是只是因为人类认识不够，还没有发现其真正规律？也就是说，这个世界真的是充满了不可预知的各种混沌，还是有一只我们看不见的手在操纵着（爱因斯坦老先生说过：上帝不掷骰子）？幸亏我们讨论的是密码学，不是哲学，这个问题顶多想想就好了。虽然真正的随机数可能不存在，但是有密码学能够用的随机数就已经很好了。