0x1 前言

最近比赛比较频繁，各种比赛各种糊脸。好家伙！我直接发现自己是一个成事不足败事有余的家伙。简单题能秒，难题不会，就连复现都十分的废劲。仔细的回看了一下自己写的东西，发现真的有点太浅了，很多知识只停留在表面，没有深知原理，有种向“题棍”发展的趋势（当然说的只是方向，不是数量）。这样并不好，最近沉下心来好好想了想，我虽然一直在努力的冲击线下赛，但是这好像并不是目的，首先我并不是很缺钱，其次不是因为要功利的混奖来到社团的，只是想学点知识和师傅们快乐的打比赛而已。周末的比赛虽然我们打的不好，但是整整一天真的非常的快乐。我发现我想要的并不是线下赛，而是一群志同道合的人一起努力的时光罢了。所以之后的博客应该会以最近的知识点为主，题目的复现为辅，静下心来好好学习学习我喜欢的计算机！

最近题目遇见了很多关于随机数的操作，包括re，Crypto，web，pwn。并且wp中涉及到了很多对伪随机数的爆破，从正面突破随机数的方法，这引起了我强烈的兴趣，于是就有了这篇文章，好好的研究一下何为（伪）随机数。

0x2 随机数的基本分类

首先我们先给随机数分个类，但是分类标准是什么呢？我们一般的随机数会有如下三个标准：

1. 统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中，1的数量大致等于0的数量，同理，“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。
2. 密码学安全伪随机性。其定义为，给定随机样本的一部分和随机算法，不能有效的演算出随机样本的剩余部分。
3. 真随机性。其定义为随机样本不可重现。实际上只要给定边界条件，真随机数并不存在，可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉（比如当地的背景辐射波动值），可以认为用这个方法演算出来了真随机数。但实际上，这也只是非常接近真随机数的伪随机数，一般认为，无论是背景辐射、物理噪音、抛硬币等等都是可被观察了解的，任何基于经典力学产生的随机数，都只是伪随机数。

简单讲就是：1.单位比特大致相等 2.无法被有效的完全预测 3.不可重现
按照这三个标准我们可以讲随机数分为

-伪随机数：满足第一个条件的随机数。

• 密码学安全的伪随机数：同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。
• 真随机数：同时满足三个条件的随机数。
  我们这里主要研究的是密码学安全的伪随机数。

0x3 伪随机数的产生原理与方法

本文主要介绍三种方法：

• 平方取中方法
• 线性同余方法
• 梅森旋转随机生成法

平方取中方法

平方取中法(midsquare method)是产生[0，1]均匀分布随机数的方法之一，亦称冯·诺伊曼取中法，最早由冯·诺伊曼(John von Neumann，1903-1957)提出的一种产生均匀伪随机数的方法。此法将一个2s位十进制随机数平方后得到的一个4s位数，去头截尾取中间2s位数作为一个新的随机数，重复上述过程可得到一个伪随机数列。这里我们简单的概括一下这种方法：
首先来讲一下算法使用的常量:

• seed:种子，整套算法的最初值。
• s：每次选取低位舍弃位数
• mod：每次取得位数（尽可能的取满）

算法过程：

1. 取初值（上一个生成随机数），进行平方
2. 从低位数s位，后取mod位数，生成新一轮随机数
3. 重复第一步

举个例子：

python代码模拟：

#平方取中 -xlxw
from time import time

def rander(seed,n):
    if n ==1:
        return 0
    seed = int(seed)
    #print(seed)
    s = 3   #舍弃位数
    mood=10000000  #每次取得长度
    seed = int(seed**2/pow(10,(s/2))) % mood
    print(str(101-n)+":"+str(s)+"   "+str(seed))
    rander(seed,n-1)
def main():
    seed = time()
    rander(seed,100)

main()

这种方法生成的伪随机数有很明显的缺点，就是周期太短而且分布并不均匀 ，有兴趣的小伙伴可以试试稍微的将mod值改小，你就会发现，整个随机数列收敛的特别得快，不出50组，随机数已经变成了一个固定的数值了。
所以这种方法适用于数量不多的伪随机数的快速生成。

线性同余方法

lei了lei了，信息安全数学基础带着他的同余方程走过来了。顺带一提，我再不复习信息安全数学基础我可能就要去世了。
简单来讲就是通过一个线性同余方程不断地进行迭代生成的一串序列。哈？这样不就是可以被预测的了嘛，确实这就是伪随机数，整个参数只有输入的种子不同，其余的参数都完全相同。我们来看一下迭代方程：

其中除了seed以外，其余常数都是随机数生成器所规定好的，因为这几个常数会直接决定整个随机数列的质量与周期。
用线性同余法产生随机数的特点是非常容易实现，生成速度快，但是弊端也很明显，32位的数周期最长只能到2的23次方 ，达不到需要高质量随机数的应用如加密应用的要求。所以我们平常使用的rand也不是这种方式。
python代码实现：

from time import time,clock

#define
m = 2**32
a = 1103515245
c = 12345
rdls = []

def LCG(seed,mi,ma,n):
    if n == 1:
        return 0
    else:
        seed = (a * seed + c) % m
        rdls.append(int((ma-mi)*seed/float(m-1)) + mi)
        LCG(seed,mi,ma,n-1)
          
def main():
    co = 100
    mi = 0
    ma = 100
    seed = time()
    LCG(seed,mi,ma,co)
    print("随机生成的数字",rdls)
    
main()

其中co为所取随机数数量，mi，ma则为随机数区间。

梅森旋转随机生成法

这个算法相比较前两种随机数算法就靠谱了很多很多。梅森旋转随机生成法也是现在主流包括python在内的大多数随机数生成器使用的算法。与其说我们需要和众多随机数进行较量，还不如说我们需要与这种方法进行正面对抗。这种算法可以产生“优质“”随机数，特点就是它的循环节特别长。而且产生的数分布是比较平均的。在理想的情况下，这种算法的周期长度大概在2^19937-1。在我们了解它之前我们要首先明确几个相关的前置知识：（这里我会讲出我的理解，可能会有一点偏差，有兴趣的师傅们可以稍微的搜索一下）

前置知识

• 线性反馈移位寄存器（LFSR）：一个寄存器，用来存储输入与中间数据的。最明显的特点就是他会进行移位操作，导致最低为丢失（在本算法中）。
• 本原多项式：高深吧！其实就是一种不可化简的多项式，这个多项式的选取很重要，会直接影响我们伪随机数的质量，最好的选取方式就是选取本原多项式。
• 级：一级，一级的分布。指的就是计算机的一个二进制单位（0或1）。每一位就是一级。
• 反馈函数：个人理解一种方法，用于进行数据处理。相当一个函数，寄存器会用这个规则处理数据。

算法过程

• 程序读入随机种子，将其存入线性反馈移位寄存器中。
• 选取特定的位数进行异或，得到结果a。
• 进行右移1位，将a存取寄存器最高位
• 将得到的结果输出，并1作为新的seed重复第二步
  是不是有一点抽象，不要慌我们来模拟一个。

手动模拟

由于我们选择了原多项式，所以他最后的循环节是2^4-1=15（包括种子输入）。
我们每次计算出来的结果会放在开头，序列后移一位，看起来就像数组在向后旋转。
实现代码：（代码是嫖的）

class MersenneTwister:
    __n = 624
    __m = 397
    __a = 0x9908b0df
    __b = 0x9d2c5680
    __c = 0xefc60000
    __kInitOperand = 0x6c078965
    __kMaxBits = 0xffffffff
    __kUpperBits = 0x80000000
    __kLowerBits = 0x7fffffff

    def __init__(self, seed = 0):
        self.__register = [0] * self.__n
        self.__state = 0

        self.__register[0] = seed
        for i in range(1, self.__n):
            prev = self.__register[i - 1]
            temp = self.__kInitOperand * (prev ^ (prev >> 30)) + i
            self.__register[i] = temp & self.__kMaxBits

    def __twister(self):
        for i in range(self.__n):
            y = (self.__register[i] & self.__kUpperBits) + \
                    (self.__register[(i + 1) % self.__n] & self.__kLowerBits)
            self.__register[i] = self.__register[(i + self.__m) % self.__n] ^ (y >> 1)
            if y % 2:
                self.__register[i] ^= self.__a
        return None

    def __temper(self):
        if self.__state == 0:
            self.__twister()

        y = self.__register[self.__state]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & self.__b
        y = y ^ (y << 15) & self.__c
        y = y ^ (y >> 18)

        self.__state = (self.__state + 1) % self.__n

        return y

    def __call__(self):
        return self.__temper()

    def load_register(self, register):
        self.__state = 0
        self.__register = register

if __name__ == "__main__":
    mt = MersenneTwister(0)
    tank = set()
    kLen = 100
    for i in range(kLen):
        t = mt()
        tank.add(t)
        print(t)
    print(len(tank) == kLen)

0x4 常见随机数爆破方法

爆破原理

看到这里大家应该也差不多明白了，计算机中的伪随机数并不是坚不可摧的。最常用的梅森旋转随机生成法也只不过用来异或与移位来实现的。做RE的应该都明白，异或是一个可逆的加密算法，所以只要样本足够多，我们就可以完成整个函数的逆推。梅森旋转算法的设计目的是优秀的伪随机数发生算法，而不是产生密码学上安全的随机数。
那我们来稍微的试一试爆破,我们就以我们刚才生成的4级随机数进行实验（以下可能会出现问题，纯自己推导，师傅们轻骂）。
做题之前我们要明确一下已知条件：我们知道若干组随机数的输出。
未知量（我们要推导的东西）：seed种子，反馈函数。
首先我们对比14与13次输出，很容易观察到移位是1，所以我们可以假设反馈函数（如下图）。之和列出所有的反馈函数的可能（为了方便，我只验证了两级）

我们通过逐级验证的方法，可以基本确定原反馈函数。
这里是上方代码的爆破代码：

class TemperInverser:
    __b = 0x9d2c5680
    __c = 0xefc60000
    __kMaxBits = 0xffffffff

    def __inverse_right_shift_xor(self, value, shift):
        i, result = 0, 0
        while i * shift < 32:
            part_mask = ((self.__kMaxBits << (32 - shift)) & self.__kMaxBits) >> (i * shift)
            part = value & part_mask
            value ^= part >> shift
            result |= part
            i += 1
        return result

    def __inverse_left_shift_xor(self, value, shift, mask):
        i, result = 0, 0
        while i * shift < 32:
            part_mask = (self.__kMaxBits >> (32 - shift)) << (i * shift)
            part = value & part_mask
            value ^= (part << shift) & mask
            result |= part
            i += 1
        return result

    def __inverse_temper(self, tempered):
        value = tempered
        value = self.__inverse_right_shift_xor(value, 18)
        value = self.__inverse_left_shift_xor(value, 15, self.__c)
        value = self.__inverse_left_shift_xor(value, 7, self.__b)
        value = self.__inverse_right_shift_xor(value, 11)
        return value

    def __call__(self, tempered):
        return self.__inverse_temper(tempered)

相关例题

空指针密码学VSS

通过强行爆破获取时间种子

留空，忘带书了回去补上吧

0x5 后记

这是现在我已知的两种正面突破伪随机数的方法，后续如有新的方法我会补上。昨天和师父们出去聚餐的时候，真的很喜欢子洋师傅的一句话，在这里我要把他送给你们也是送个我自己：“flag是可以爆破的，但生活不可以！”

0x6 参考资料

wiki随机数
谈谈梅森旋转：算法及其爆破
Python下探究随机数的产生原理和算法