随机数漫谈（下）

故事后续

上回说到，不懂随机数的锁匠，他虽然打造出了世界上最安全的锁，但是所有的锁都是统一的钥匙。只要获得了其中一把钥匙，就可以打开所有的锁了。了解了随机数的三个性质后，锁匠开始准备打造至少具备不可预测性的钥匙来和他的锁配对，这样的组合才是最牢固的。于是他开始了随机数生成器研究。

伪随机数生成器

上一节说到随机数可以用软件方式生成（我们大多数情况下都是这么做的），也可以用硬件方式生成。硬件方式生成才能具备不可重复性，软件无论如何只能生成不可预测性的随机数。我们把这里的硬件设备叫做随机数生成器，而软件则成为伪随机数生成器。因为软件生成的只能做到不可预测性，所以软件生成的随机数，也叫做伪随机数。

伪随机数生成器结构

伪随机数生成器一般由二部分组成：内部状态和外部种子

内部状态

伪随机数生成器结构的内部状态，就是指伪随机数生成器管理的内存中的数值（一般是多个）。伪随机数就是根据内存中的值进行一系列的计算，计算的结果就是伪随机数。随后，为了响应下一个伪随机数生成请求，伪随机数会改变自己的内部状态。因此，将根据内部状态计算伪随机数的方法和改变内部状态的方法组合起来，就是伪随机数生成的算法。

内部状态决定了下一个生成的伪随机数，因此内部状态不能被攻击者知道。

种子

为了生成伪随机数，伪随机数生成器需要被称为种子的信息对伪随机数生成器的内部状态进行初始化。

伪随机数的种子是一串随机序列的比特值，然后根据种子结合内部状态，我们就可以生成伪随机数列了。要特别注意：伪随机数生成算法是公开的，但是种子必须保密，这就好像是密码算法是公开的，但密钥必须保密。由于种子是需要保密的，所以不能用容易被预测到的值。例如人们最常犯的错误就是把当前时间作为种子。

打造伪随机数生成器方法

杂乱的方法

有人会说，既然是生成杂乱无章的数列，那么我就使用杂乱无章的方法不就可以了吗？答案当然是否定的，如果你无法理解一个生成方法，那么你如何保证这个复杂的算法生成的数列是具备不可预测性的呢？试验证明，往往这样算法生成的伪随机数周期都非常短。由于密码技术中使用的伪随机数要求具备不可预测性，短周期的数列肯定是不可以的。

线性同余法

线性同余法是一种广泛使用的伪随机数生成器算法。然而，它不能应用于密码技术。

线性同余法算法大概思想就是将当前的伪随机数值乘以A再加上C，然后将除以M得到的余数作为下一个伪随机数。
假设我们要生成的伪随机数列伪R₀，R₁，R₂ ......。首先我们根据种子，用下列公式计算第一个伪随机数R₀。

第一个随机数R₀ = （A x 种子 + C）mod M

公式中的A,C都是常数，且A和C需要小于M。接下来，根据R₀用相同的公式计算下一个伪随机数R₀，如此反复。概括公式如下：

R_n+1 = (A x R_n + C) mod M

在线性同余法中，最近一次生成的伪随机数的值就是内部状态。伪随机数的种子被用来对内部状态进行初始化。它的结构图如下：

程序代码示例如下：

public class LineRandom {
    public static void main(String[] args) {

        int m = 7;
        int a = 3;
        int c = 1;
        int random = 0;
        int seed = 1;

        while(true){
            random = (a * seed + c)%m;
            seed = random;
            System.out.print(random);
        }

    }
}

我们看下输出结果：

46520146520146520146520146520146520146520146520146520146520146520146520146520146 ......

可以发现该数列的循环周期是6：465201
在线性同余法中，只要谨慎选择A,C,M的值，就能够很容易地生成具备随机性的伪随机数列。然而，它不具备不可预测性，我们不能将它应用与密码学技术。很多随机数库都是采用线性同余法写的。比如C语言的rand,还有java的Random。所以这些函数不能用于密码技术。

单向散列函数法

使用单向散列函数可以编写出具备不可预测性的伪随机数列（强伪随机数）。它的结构图如下：

它的工作方式如下：
1 用伪随机数的种子初始化内部状态
2 用单向散列函数计算散列值
3 输出散列值作为强伪随机数
4 修改内部状态
5 根据需要重复2-4步骤

这个工作方式是否可预测呢？攻击者如果想要预测下一个伪随机数，需要知道内部状态的值。而伪随机数是一个散列值，就相当于攻击者要破解散列函数的单向性，这是非常困难的。其实大家都看到了，单向散列函数的单向性是支撑伪随机数生成器不可预测的基础。

程序代码示例如下：

public class MacRandom {
    public static final String SHA_ALGORITHM = "SHA-512";

    public static void main(String[] args) throws Exception {

        String counter = "hello world!";//计数器初始值
        String randomStr = "";//随机数


        while (true) {
            randomStr = SHA(counter.getBytes());
            System.out.println(randomStr);
            counter = counter + 1;
        }

    }

    /**
     * SHA Security Hash Algorithm 安全散列算法，固定长度摘要信息 SHA-1 SHA-2( SHA-224
     * SHA-256 SHA-384 SHA-512) 使用的依然是MessageDigest类，JDK不支持224
     *
     * @param plainText
     * @return
     */
    public static String SHA(byte[] plainText) {
        MessageDigest messageDigest;
        try {
            messageDigest = MessageDigest.getInstance(SHA_ALGORITHM);
            return Base64.encodeBase64String(messageDigest.digest(plainText));
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }
}

上面代码中我们对内部状态值改变使用了简单的加1操作
篇幅有限这里随机截取了一些输出结果，有兴趣的同学可以自己尝试下，验证其不可预测性

cHRLWs/WLXOLhJ273RhDuN0MBC3plbi0JwyHEUo7gD02J7g8aUK0BYp4JROtTaz88UtgHm8c/9t7
fHGTu9op1Q==

jwW2P0m88M5saQue3Y9hwwVJYVs9JN94EXTkOZfB8Dsw5O9NrciPROFgfcygZ7wvH88ETRpY8ciP
k5pLhjwrAQ==

8X9m7c+1qVctkRljYXbqqZbVTAQ+Y/frL2hmHRamKIaqMO8AMytBD4GyxMPmqbWEVZRm9TLQrRiC
lWOGUa12IQ==

FoNd2JYZlIjbipqB6eShDaE78DGYOV+gw3g++bsaDJPhG88W5VcMLHz9LFDO6ZZr3/iweYChwMNG
aW1iJ5APFw==

RQ9JN8C91v+WoJYsDnlaLPsB0PTe2snp1YLj3yYCWGKknCEcYgnnZEYjEu7TfAEEjHUytWAiyaaR
61BhOzYCjw==

okZDHefqnCLT0qsAZwxA3/R423ccSLtVmlFwlcV3LZOXNdfLULSNz4X0tOKYkO4IfZU49K1UM2it
lEg4OyHw1A==

qRmhTlaQE71wHAo0+XuCBHp2CXA9CwQHYQvb50NTLIRYyEQ/41REx32UZUVqpQVLWtOwyovkUKhC
qPJ8wx5GLg==

HdN5JxdpM+m9XFnLZWois0XsrRE+XSulTfCm0/8ixCPea/DG1HaItbxRqFUnFb2zIw6yJFgeWlV9
QiWdOZmdnQ==

0HKocNlc6Un9c8Pms9vi6ppDrFv9/mq9boY38Ek2DahS4kkpyyjz5OOZD/Hr17DHlMXZKZl1h0QH
1z0rojOOiQ==

znRatSv1+5otr4E98+CPI+MeRqyhH16dbWpsFntxMGAfbTnLK76+mtRUBZ0gge3eXz3l1OB+Qg9y
aJAd9h0o8g==

k9y1PLVypfn1LqNfTCNHvkFJ3EBLYtN4nnXPkVDh+LDBjLobiyswBuoXEexOn1yjjV0fknU9wtUj
1dWKo5RxFA==

密码法

我们可以使用密码来编写能够生成强伪随机数的伪随机数生成器。既可以使用AES对称加密，也可以使用非对称的RSA，ECC算法。
这种伪随机数生成器的结构如下：

它的工作方式如下：
1 用种子的初始值部分初始化内部状态
2 用密钥加密内部状态的值
3 输出密文作为强伪随机数
4 修改内部状态
5 根据需要重复2-4步骤

我们可以看到，密码法的伪随机数生成器中发生最大变化的就是种子，它巧妙的把密钥和初始值作为种子，再结合加密算法，将密文作为伪随机数列。
和单向散列有异曲同工之妙，利用密码法中的密钥的机密性来保证了伪随机数列的不可预测性。

由于篇幅原因，就不上示例代码了。先生成密钥后，用密码像单向函数那样进行计算就可以了。该方法的伪程序代码如下：

key 的值与内部状态初始值的结合相当于伪随机数种子

初始值的值相当于内部状态
key = 密码的密钥
counter = 初始值
while(true){
    伪随机数 = 用key加密（counter）
    输出伪随机数
    counter值加1
}

ANSI X9.17

该种方法使用了三重DES算法，它的核心思想和密码法类似。在这里简单介绍下其实现步骤：
1 用种子的初始值部分初始化内部状态
2 将当前时间加密生成掩码
3 对内部状态与掩码求XOR
4 对步骤3的结果用种子密钥部分进行加密
5 将步骤4的结果作为强伪随机数输出
6 对步骤4的结果与掩码求XOR
7 将步骤6的结果用种子密钥部分进行加密
8 将步骤7的结果作为新的内部状态
9 根据需要重复2-8步骤

篇幅原因，这里只给出该程序的伪代码

key 的值与内部状态初始值的结合相当于伪随机数种子

key = 加密密钥
内部状态 = 初始化（内部状态初始值）
while(true){
    掩码 =  用key加密当前时间
    伪随机数 = 用key加密（内部状态 XOR 掩码）
    输出伪随机数
    内部状态 = 用key加密（伪随机数 XOR 掩码）
}

伪随机数生成器常受到的攻击

对种子进行攻击

伪随机数的种子和密钥同等重要。如果攻击者知道了种子，再由于算法是公开的，他就知道这个伪随机数生成器所生成的全部伪随机数列。所以我们必须使用具备了不可重现性的真随机数作为种子。

对随机数池进行攻击

一般我们不会在需要随机数的时候才会去生成，为了生成效率考虑，我们都会事先生成一堆随机数比特序列。我们称之为随机数池，一般保存在文件中。当密码软件需要伪随机数的种子时，我们就从随机池中取出所需长度的随机比特序列来使用。
随机数池本身并不存储任何有意义的信息，但是我们却要认真的保护它们。虽然听上去有点违背常识，但这是你必须要做的。

上期答案： 具备不可重复性。注意审题哦，题目问的是反复掷骰子生成的数列，而不是问掷骰子的点数哦