MT19937
流密码 | Lazzaro (lazzzaro.github.io)
逆extract_number（求后随机数）
extract_number是对从state中提取的伪随机数做异或处理，而逆extract_number是恢复梅森算法的内部状态（即state)
extract_number
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)逆extract_number
# right shift inverse
def inverse_right(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def extract_number(y):
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff
def recover(y):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
return y&0xffffffff
y = extract_number( )例题
2020网鼎杯白虎组random
题目
def generate():
fw = open("random", "w")
for i in range(700):
fw.write(str(random.getrandbits(32))+"n")
fw.close()
generate()
f = open("flag.txt", "w")
key = str(random.getrandbits(32))
ciphertext = encryption(flag, key)
f.write(ciphertext)
f.close()
题解
预测出下一个随机数
wp
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",'r').readlines()
prng = []
for i in f:
i = i.strip('n')
prng.append(int(i))
#克隆一个MT19937伪随机数生成器
g = clone_mt(prng[:624])
for i in range(700):
g.getrandbits(32)
#使用一个随机数生成器对象g生成700个32位的随机数，并将最后一个生成的随机数存储在变量key中
#预测下一个随机数
key = g.getrandbits(32)
print(key)
#2990136190脚本
# 脚本1
# right shift inverse
def inverse_right(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def recover(y):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
return y&0xffffffff
random_number = []
state = [recover(i) for i in random_number]
## 脚本2
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
prng = []
g = clone_mt(prng[:624])
for i in range(700):
g.getrandbits(32)
key = g.getrandbits(32)
print(key)逆twist函数（求前随机数）
twist函数
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逆twist函数
def backtrace(cur):
high = 0x80000000#0b10000000000000000000000000000000
low = 0x7fffffff#'0b1111111111111111111111111111111'
mask = 0x9908b0df#0b10011001000010001011000011011111'
state = cur
for i in range(623,-1,-1):
tmp = state[i]^state[(i+397)%624]
# recover Y,tmp = Y
#检查tmp的最高位是否为1。
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
# recover highest bit
#state[i]的最高位保留
res = tmp&high
# recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
#同理求state[i-1]
tmp = state[i-1]^state[(i+396)%624]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
#(tmp)&low保留后31位
res |= (tmp)&low
state[i] = res
return state例题
2020 V&N 招新赛 Backtrace
题目
# !/usr/bin/env/python3
import random
flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}"
with open('output.txt', 'w') as f:
for i in range(1000):
f.write(str(random.getrandbits(32)) + "n")
print(flag)题解
flag是前四个随机数，这里给出1000个随机数，根据1000个随机数恢复初始state,但恢复的state缺少四个。根据624，625，626，627逆twist恢复前四位
wp
#!/usr/bin/python3
from random import Random
# right shift inverse
def inverse_right(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp>>shift & mask
return tmp
# left shift inverse
def inverse_left(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift & mask
return tmp
def backtrace(cur):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
state = cur
for i in range(3,-1,-1):
tmp = state[i+624]^state[i+397]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
# recover highest bit
res = tmp&high
# recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
tmp = state[i-1+624]^state[i+396]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
state[i] = res
return state
def recover_state(out):
state = []
for i in out:
i = inverse_right(i,18)
i = inverse_left_values(i,15,0xefc60000)
i = inverse_left_values(i,7,0x9d2c5680)
i = inverse_right(i,11)
state.append(i)
return state
f = open("output.txt","r").readlines()
c = []
for i in range(1000):
c.append(int(f[i].strip()))
partS = recover_state(c)
#[0]*4长度为4的列表，其中元素都为0
state = backtrace([0]*4+partS)[:624]
# print(state)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
flag = "flag{" + ''.join(str(prng.getrandbits(32)) for _ in range(4)) + "}"
print(flag)脚本
# 脚本
from random import Random
# right shift inverse
def inverse_right(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp>>shift & mask
return tmp
# left shift inverse
def inverse_left(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift & mask
return tmp
def backtrace(cur):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
state = cur
for i in range(5,-1,-1):
tmp = state[i+624]^state[i+397]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
# recover highest bit
res = tmp&high
# recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
tmp = state[i-1+624]^state[i+396]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
state[i] = res
return state
def recover_state(out):
state = []
for i in out:
i = inverse_right(i,18)
i = inverse_left_values(i,15,0xefc60000)
i = inverse_left_values(i,7,0x9d2c5680)
i = inverse_right(i,11)
state.append(i)
return state
c = []
partS = recover_state(c)
state = backtrace([0]*6+partS)[:624]
# print(state)
# state[0]不准确，因state[0]==seed，单推
# inv = invert(1812433253,1<<32)
# seed = inverse_right(((state[1]-1)*inv)%(1<<32),30)
# state[0] = int(seed)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
flag = "flag{" + ''.join(str(prng.getrandbits(32)) for _ in range(4)) + "}"
print(flag)
逆向init（求seed)
根据第一次的state，逆向seed。
init函数
def _int32(x):
return int(0xFFFFFFFF & x)
def init(seed):
mt = [0] * 624
mt[0] = seed
for i in range(1, 624):
mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
return mt_ ^
int32相当于在模 ,,求出1812433253的逆元inv
^
^ 可知 的高30位，可推出 >>30的高60位，计算出 的高60位…依次恢复
脚本
from gmpy2 import invert
def _int32(x):
return int(0xFFFFFFFF & x)
def init(seed):
mt = [0] * 624
mt[0] = seed
for i in range(1, 624):
mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
return mt
seed = 2080737669
def invert_right(res,shift):
tmp = res
for i in range(32//shift):
res = tmp^res>>shift
return _int32(res)
def recover(last):
n = 1<<32
inv = invert(1812433253,n)
for i in range(623,0,-1):
last = ((last-i)*inv)%n
last = invert_right(last,30)
return last
state = init(seed)
print(recover(state[-1]) == seed)python3
逆extract_number（求后随机数）
Mersenne Twister Predictor
mt19937predictor 是一个用于对 Mersenne Twister 进行状态预测的库，它允许用户根据已观察到的输出，推测 Mersenne Twister 的内部状态，从而预测未来的随机输出。使用 setrandbits 方法来更新内部状态，使用 getrandbits 方法来进行状态预测（获取随机数）
import random
from mt19937predictor import MT19937Predictor
predictor = MT19937Predictor()
for _ in range(624):
x = random.getrandbits(32)
#更新 Mersenne Twister 预测器的内部状态，传入一个给定的 32 位随机整数 x
predictor.setrandbits(x, 32)
assert random.getrandbits(32) == predictor.getrandbits(32)randcrack
import random
from randcrack import RandCrack
#random预测的时候默认以当前时间作为随机数种子
rc = RandCrack()#实例化randcrack类
for i in range(624):#循环624次
rc.submit(random.getrandbits(32))#每次循环提交一个32位random生成的随机数
print(random.getrandbits(32))#利用random库获取一个64位的随机数（你可以修改为任意位数）
print(rc.predict_getrandbits(32))#利用randcrack获取的下一个随机数逆 twist()（求前随机数）
-
Extend MT19937 Predictor
https://github.com/NonupleBroken/ExtendMT19937Predictor
import random from extend_mt19937_predictor import ExtendMT19937Predictor #生成1024个64位的伪随机数并存储在列表numbers中： numbers = [random.getrandbits(64) for _ in range(1024)] predictor = ExtendMT19937Predictor() #使用256位的随机数值(随机种子)来初始化预测器状态 for _ in range(78): #循环78次，每次迭代都会使用256位的随机数值来初始化预测器状态 predictor.setrandbits(random.getrandbits(256), 256) #回溯78次 _ = [predictor.backtrack_getrandbits(256) for _ in range(78)] #验证回溯是否正确 for x in numbers[::-1]: assert x == predictor.backtrack_getrandbits(64)
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Miaoo~！
