伪随机数总结

windows与linux下的随机数机制是不一样的，如果给的是elf文件要求随机序列，需要在linux下编译

C

一般先设置种子srand(0)，然后调用rand

前后两次调用rand生成的随机数不同

动调获取随机序列

2024geek flower

2024CISCN gdb_debug

爆破seed

https://mp.weixin.qq.com/s/3PZK2O2PftCqr2mS7vn5wA

📎upx2023_0.zip

Python

https://lazzzaro.github.io/2020/11/07/crypto-%E6%B5%81%E5%AF%86%E7%A0%81/

python中random库使用的是MT19937算法(梅森旋转算法)，利用算法可以求出后随机数，前未知随机数，种子等，详见博客

1.利用seed初始化624个状态

2.对状态进行旋转

3.根据状态提取伪随机数

def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 根据seed初始化624的state
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

有默认种子，由当前时间和操作系统提供的熵源例如urandom综合生成

import random
import time

print(int(time.time()))
print('随机数1：',random.random())
print(int(time.time()))
random.seed(int(time.time()))
print('随机数2：',random.random())
random.seed(0)
print('随机数3：',random.random())

# 1732158156
# 随机数1： 0.4747416427572331
# 1732158156
# 随机数2： 0.2260060177159785
# 随机数3： 0.8444218515250481

[GKCTF 2021]Random

如果能获取前624个32位的随机数，就能预测出后面全部32位的随机数

import random
from hashlib import md5
 
def get_mask():
    file = open("random.txt","w")
    for i in range(104):
        file.write(str(random.getrandbits(32))+"\n")
        file.write(str(random.getrandbits(64))+"\n")
        file.write(str(random.getrandbits(96))+"\n")
    file.close()
get_mask()
flag = md5(str(random.getrandbits(32)).encode()).hexdigest()
print(flag)

random的随机数以32位为一个单位，所以如果要产生一个64位的随机数，则等价于一次产生两个32位随机数

本题中已知的随机数有104*(1+2+3)=624个，刚好满足能够预测的条件，需要预测出下一个

randcrack

from hashlib import md5
from randcrack import RandCrack

with open(r'random.txt', 'r') as f:
    l = f.readlines()
l = [int(i.strip()) for i in l]
t = []
for i in range(len(l)):
    if i % 3 == 0:
        t.append(l[i])  # 32位长度直接存入
    elif i % 3 == 1:
        t.append(l[i] & (2 ** 32 - 1))  # 64位长度先存入低32位
        t.append(l[i] >> 32)  # 再存入高32位
    else:
        t.append(l[i] & (2 ** 32 - 1))
        t.append(l[i] & (2 ** 64 - 1) >> 32)
        t.append(l[i] >> 64)
rc = RandCrack()
for i in t:
    rc.submit(i)  # 把每个数据都丢进预测器里
flag = rc.predict_getrandbits(32)  # 预测的下一个32位
print(md5(str(flag).encode()).hexdigest())

列举全部state的状态

from random import Random

def invert_right(m,l,val=''):
    length = 32
    mx = 0xffffffff
    if val == '':
        val = mx
    i,res = 0,0
    while i*l<length:
        mask = (mx<<(length-l)&mx)>>i*l
        tmp = m & mask
        m = m^tmp>>l&val
        res += tmp
        i += 1
    return res

def invert_left(m,l,val):
    length = 32
    mx = 0xffffffff
    i,res = 0,0
    while i*l < length:
        mask = (mx>>(length-l)&mx)<<i*l
        tmp = m & mask
        m ^= tmp<<l&val
        res |= tmp
        i += 1
    return res

def invert_temper(m):
    m = invert_right(m,18)
    m = invert_left(m,15,4022730752)
    m = invert_left(m,7,2636928640)
    m = invert_right(m,11)
    return m

def clone_mt(record):
    state = [invert_temper(i) for i in record]
    gen = Random()
    gen.setstate((3,tuple(state+[0]),None))
    return gen


f = open("random.txt",'r').readlines()
prng = []
j=0
for i in f:
    i = i.strip('\n')
    print(int(i).bit_length())
    if(j%3==0):
        prng.append(int(i))
    elif(j%3==1):#将生成两次随机数的两个随机数分离出来
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)>> 32)
    else:#将生成三次随机数的三个随机数分离出来
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)& (2 ** 64 - 1) >> 32)
        prng.append(int(i)>>64)
    j+=1

g = clone_mt(prng[:624])
for i in range(624):
    g.getrandbits(32)#产生前624个随机数，让state状态到生成flag前

key = g.getrandbits(32)
print(key)
from hashlib import md5
flag = md5(str(key).encode()).hexdigest()
print(flag)
#14c71fec812b754b2061a35a4f6d8421

2023HITCTF邀请赛

数据：📎output.zip

import random

with open('output.bin', 'wb') as f:
    f.write(random.randbytes(2500))

print('HITCTF2023{%s}' % random.randbytes(16).hex())

题目已知产生了2500个byte，一个byte是8位，也就是说4个byte组成一个32位随机数，2500/4=625>624，满足预测条件

import random
from mt19937predictor import MT19937Predictor

#读取数据，并4个一组组成一个32位随机数(little是重点)
c = open('output.bin', 'rb').read()
c = [c[x:x+4] for x in range(0, len(c), 4)]
c = [int.from_bytes(x, 'little') for x in c]

predictor = MT19937Predictor()
for x in c[:624]:
	predictor.setrandbits(x, 32) #只需要624组数据就行
assert predictor.getrandbits(32) == c[-1]
print('HITCTF2023{%s}' % predictor.randbytes(16).hex())
# HITCTF2023{d6712c20657ce5e02118f8592b7da71f}