本来想投在奇安信攻防社区赚点小钱，结果审核没过，可能写的太基础了，算了

前言

在ctf中会遇到一些伪随机数的问题，在这里记录总结一下

php

在php中，产生伪随机数的函数为mt_rand()

mt_rand()是根据种子和调用次数来生成随机数，比如第一次运行种子为12345，调用三次依次生成1705348431，1355611734，507358263，第二次运行种子为45678，调用三次依次生成1531982830，487967345，256758859
因此，如果我们知道种子的话就能预测随机数了，这里用到工具php_mt_seed来爆破种子
以最后一次运行生成的随机数为例，依次为759475017，1177445368，1052089167

./php_mt_seed 第一次生成的随机数

可以看到找到了4个种子，测试后发现种子为4099053638

这工具还有一种用法
当产生的随机数设置了区间时，php_mt_seed传入的数据以4个数为一组，前2个数是随机数的结果区间，后2个数是随机数的范围

python

python 生成伪随机数为random.random()

random.random()同样是有种子的，不过python可以用random.getstate()直接获取到

手动设置种子的话用random.seed()

java

java中常用的伪随机数为java.util.Random，这也是可预测的，只需知道前两个随机数，就能预测出第三个随机数

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        Random random = new Random();
        System.out.println(random.nextInt());
        System.out.println(random.nextInt());
        System.out.println(random.nextInt());
    }
}

去源码中查看一下是如何生成的

可以看到nextseed右移16位后强转成int的值就是随机数，而nextseed则是在oldseed上生成nextseed = (oldseed * multiplier + addend) & mask;（种子初始值为根据当前系统时间运行生成）
而multiplier,addend,mask则是系统定义的常量，该算法其实就是线性同余生成器

因此知道前两个随机数即可预测第三个数
具体实现方法为先将第一个随机数左移16位，得到一个空出了16个位置的第一个随机数种子seed1，也就是说此时seed1有2的16次方个可能
接着爆破这个seed1，如果((seed1 * multiplier + addend) & mask) >> 16 == 第二个随机数，那么就得到了正确的seed1，有了seed1就能直接计算seed2,seed3，自然就能算出第三个随机数
如果是负数的话需求补码，也就是取反加一
实现代码已经有师傅写了，我就不重复造轮子了

# 代码来自r1ngs师傅
a = 0x5DEECE66D
b = 0xB
mask = (1 << 48) - 1

def n2p(x):
    y = -x
    y ^= 2 ** 32 - 1 #取反
    y += 1
    return y

def findseed(x1, x2):
    if x1 < 0:
        x1 = n2p(x1)

    if x2 < 0:
        x2 = n2p(x2)

    seed = x1 << 16
    for i in range(2 ** 16):
        if ((a * seed + b) & mask) >> 16 == x2:
            return seed
        seed += 1

def cal_x(seed):
    x = seed>>16
    if '{:032b}'.format(x).startswith('1'):
        x ^= 2 ** 32 - 1
        x += 1
        return -x
    return x

if __name__ == '__main__':
    x1 = 1564370740
    x2 = 2121441037

    seed1 = findseed(x1, x2)
    seed2 = (a * seed1 + b) & mask
    seed3 = (a * seed2 + b) & mask
    x3 = cal_x(seed3)
    print(x3)

总结

总结了一下php,python和java中的伪随机数漏洞，在ctf中的伪随机数题目主要以php居多