搁置了好久了
MT19937，伪随机数生成算法，可快速的产生高质量的伪随机数，python中的random类使用的就是这个算法。
python实现代码：
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
代码就不分析了，有大佬分析的很好，乘前人之荫。
主要记录几种题型。
恢复经extract_number后的数
o = 2080737669
# 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(o)
print(recover(y) == o)
一道来自buu的题MT，之前就没做：
from Crypto.Random import random
from Crypto.Util import number
from flag import flag
def convert(m):
m = m ^ m >> 13
m = m ^ m << 9 & 2029229568
m = m ^ m << 17 & 2245263360
m = m ^ m >> 19
return m
def transform(message):
assert len(message) % 4 == 0
new_message = ''
for i in range(len(message) / 4):
block = message[i * 4 : i * 4 +4]
block = number.bytes_to_long(block)
block = convert(block)
block = number.long_to_bytes(block, 4)
new_message += block
return new_message
transformed_flag = transform(flag[5:-1].decode('hex')).encode('hex')
print 'transformed_flag:', transformed_flag
# transformed_flag: 641460a9e3953b1aaa21f3a2
逆向即可，修改下recover的参数：
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,19)
y = inverse_left_mask(y,17,2245263360)
y = inverse_left_mask(y,9,2029229568)
y = inverse_right(y,13)
return y&0xffffffff
def transform(message):
assert len(message) % 4 == 0
new_message = b''
for i in range(int(len(message) / 4)):
block = message[i * 4 : i * 4 +4]
block = bytes_to_long(block)
block = recover(block)
block = long_to_bytes(block, 4)
new_message += block
return new_message
transformed_flag = b'd\x14`\xa9\xe3\x95;\x1a\xaa!\xf3\xa2'
flag = transform(transformed_flag)
print("flag{" + hex(bytes_to_long(flag))[2:] + "}")
#flag{84b45f89af22ce7e67275bdc}
预测后随机数
在已知624个从开始连续输出的随机数，就可预测之后生成的每一个随机数。做法就是通过给的624个随机数逆向extract_number，从而得到对应的624个state，得到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
prng = []
g = clone_mt(prng[:624])
for i in range(700):
g.getrandbits(32)
key = g.getrandbits(32)
print(key)
预测前随机数
类似预测前随机数，逆向twist
例题+实现代码：
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)
已知1000个从第5个开始的随机数，需要恢复前4个随机数，分成两段，(4+620)+(380)，：
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)
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)
一道结合两种情况的例题：
import random, libnum
from secret import flag
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
D = []
key = random.getrandbits(64)
for i in range(666):
D.append(random.getrandbits(32))
iv = random.getrandbits(128)
key = libnum.n2s(key)*2
iv = libnum.n2s(iv)
my_aes = AES.new(key, AES.MODE_CBC, iv)
c = my_aes.encrypt(pad(flag, 16))
print(c)
print(D)
- 求key：预测前随机数
- 求iv：预测后随机数
key是64bits，相当于2个随机数，修改下参数就好：
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
D = []
partS = recover_state(D)
state = backtrace([0]*2+partS)[:624]
# print(state)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
key = prng.getrandbits(64)
print(key)
#2780465883630350376
iv，给了666个随机数，iv128bits，同样改下参数即可：
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(666):
g.getrandbits(32)
iv = g.getrandbits(128)
print(iv)
#146646280676207134538940202991544021070
还有一种是根据第一次的 state，逆向 seed，遇到再说吧。
收获挺多的，总算把搁置了很久的东西解决了。
参考：
浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)
梅森旋转算法(MT19937)及其逆向详解 - 知乎 (zhihu.com)
流密码 | Lazzaro (lazzzaro.github.io)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com