MT19937预测

Python中内置了一个random库,用来产生随机数

其内置的算法为梅森算法(Mersenne Twister)

梅森旋转算法可以产生高质量的伪随机数,并且效率高效,弥补了传统伪随机数生成器的不足,梅森旋转算法的最长周期取自一个梅森素数: $2^{19937}-1$

由此命名为梅森旋转算法,常见的两种为基于32位的MT19937-32和基于64位的MT19937-64

我们注意到一个梅森素数为 $2^{19937}-1$ ,也就是说只要超过梅森素数,我们即可重新回到生成体系中来

说来也简单,我们已经知道随机数的范围(随机数表)就那么大,我们只需要找到随机数从哪儿来的,只要经过一个循环,必定能找到具体的位置,然后就能预测出来了

举个简单的例子:

已知字符串”12345678956789″,如果我们能够知道”34567895678912″,那我们必定能够知道这个循环是从”2“开始的

思路清晰了,我们要解决的问题就是搞到一个梅森素数大小的随机数,然后交给程序分析,找到起始位置,然后预测即可

题目-1

! [HNCTF 2022 WEEK4]random

from randhlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

f = open('output.txt','w')

for i in range(666):
    f.write(f'{getrandbits(32)}\n')
f.close()

r = getrandbits(32)
key = bytes.fromhex(hex(r)[2:])
key = md5(key).digest()
cipher = AES.new(key,AES.MODE_CBC)
c = cipher.encrypt(pad(flag,16))
print(f'c = \'{cipher.iv.hex() + c.hex()}\'')

#c = '91fd1824ddc0a35e845e87f59e53a103334df418e6a65a7d7769699c3ca2119019361cd23a46a61d4e7f6cdff5f5200f586f90b66eabfd8ecff4ddf11ee444d37f80ada0bbe8af09e4fc32c1a51e3f29e2771b51c71d2ba4acb84fda61904b96'

数据

解题思路

@@ 找到循环点

由于Python中使用的梅森算法为MT19937

最为广泛使用Mersenne Twister的一种变体是MT19937,可以产生32位整数序列,具有以下的优点:

有的非常长的周期,在许多软件包中的短周期—232随机数产生器在一个长周期中不能保证生成随机数的质量

在1≤k≤623的维度之间都可以均等分布(参见定义)

除了在统计学意义上的不正确的随机数生成器以外,在所有伪随机数生成器法中是最快的(当时)

我们注意到,其生成的数据在624*32后会达到循环(注:623*32=19936)

由于每次随机产生了32位的随机数,且623次尚未达到2的19937次方的循环点,我们必须需要624个32位由梅森算法产生的随机数才能找到循环点,也就是如果我们能够找到624个32位随机数即可

进行预测

我们使用randcrack的Python库进行预测

解答

from hashlib import md5
from Crypto.Cipher import AES
import binascii
from randcrack import RandCrack
from Crypto.Util.Padding import unpad

with open('D:\\AAACTF题目\\random\\output.txt','r') as f:
    lines = [int(line) for line in f.readlines()]
    f.close()

rc=RandCrack()
for i in range(len(lines)-624,666):
    rc.submit(lines[i])
r=rc.predict_getrandbits(32)
key = bytes.fromhex(hex(r)[2:])
key = md5(key).digest()
c = binascii.unhexlify('91fd1824ddc0a35e845e87f59e53a103334df418e6a65a7d7769699c3ca2119019361cd23a46a61d4e7f6cdff5f5200f586f90b66eabfd8ecff4ddf11ee444d37f80ada0bbe8af09e4fc32c1a51e3f29e2771b51c71d2ba4acb84fda61904b96')
iv = c[:16]
c = c[16:]
aes = AES.new(key,AES.MODE_CBC,iv)
m = aes.decrypt(c)
print(unpad(m,16))
#NSSCTF{Every_Mersenne_prime_corresponds_2_exactly_1_perfect_number}

题目-2

! [SUCTF2019]MT

from Crypto.Util.number import bytes_to_long, long_to_bytes
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 = b''
    for i in range(len(message) // 4):
        block = message[i * 4 : i * 4 + 4]
        block = bytes_to_long(block)
        block = convert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = transform(bytes.fromhex(flag[5:-1])).hex()
print(f"transformed_flag: {transformed_flag}")
# transformed_flag: 641460a9e3953b1aaa21f3a2

解题思路

@@ 法1
利用它的循环性:明文不断的加密,最终的还是明文
@@ 法2
明文通过convert()函数获取随机数将flag加密,所以通过逆向extract_number函数求解
(这里的convert作为MT19937中extract_number的一部分,逆向convert是有固定套路的)

class MT19937:
    def __init__(self, seed):
        self.index = 624
        self.state = [0] * 624
        self.state[0] = seed
        for i in range(1, 624):
            self.state[i] = (1812433253 * (self.state[i - 1] ^ (self.state[i - 1] >> 30)) + i) & 0xFFFFFFFF

    def twist(self):
        for i in range(624):
            temp = (self.state[i] & 0x80000000) + (self.state[(i + 1) % 624] & 0x7FFFFFFF)
            temp_shift = temp >> 1
            if temp % 2:
                temp_shift = temp_shift ^ 0x9908B0DF
            self.state[i] = self.state[(i + 397) % 624] ^ temp_shift
        self.index = 0

    def extract_number(self):
        if self.index >= 624:
            self.twist()
        y = self.state[self.index]
        y = y ^ (y >> 11)
        y = y ^ ((y << 7) & 0x9D2C5680)
        y = y ^ ((y << 15) & 0xEFC60000)
        y = y ^ (y >> 18)
        self.index += 1
        return y & 0xFFFFFFFF

# 示例使用
if __name__ == "__main__":
    seed = 12345  # 初始种子
    mt = MT19937(seed)
    for _ in range(10):
        print(mt.extract_number())

@@ 法3
利用移位并与自身异或这一运算的特点,可以依次推出原数的二进制数,不过要注意的是m = m ^ m << 9 & 2029229568相当于m = m ^ ((m << 9) & 2029229568)

解答

!! 法1

from Crypto.Util.number import bytes_to_long, long_to_bytes

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 = b''
    for i in range(len(message) // 4):
        block = message[i * 4 : i * 4 + 4]
        block = bytes_to_long(block)
        block = convert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message

def circle(m):
    t = m
    while True:
        x = t
        t = transform(t)
        if t == m:
            return x

transformed_flag = bytes.fromhex('641460a9e3953b1aaa21f3a2')
flag = circle(transformed_flag).hex()
print('transformed_flag:', flag)
#transformed_flag: 84b45f89af22ce7e67275bdc

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

c1 = 0x641460a9
c2 = 0xe3953b1a
c3 = 0xaa21f3a2
def decode(c):
    x = c
    while (x := convert(x)) != c:
        xx = x
    return hex(xx)[2:]
print(decode(c1)+decode(c2)+decode(c3))
#84b45f89af22ce7e67275bdc

!! 法2

from Crypto.Util.number import bytes_to_long, long_to_bytes

# 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 convert(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(len(message) // 4):
        block = message[i * 4 : i * 4 + 4]
        block = bytes_to_long(block)
        block = convert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = '641460a9e3953b1aaa21f3a2'
c = bytes.fromhex(transformed_flag)
flag = transform(c)
print(flag.hex())
#84b45f89af22ce7e67275bdc

!! 法3

from Crypto.Util.number import *

def decrypt(c):
    #4
    c = c[:19] + bin(eval('0b' + c[19:]) ^ eval('0b' + c[:13]))[2:].zfill(13)
    #3
    f = bin(2245263360)[2:].zfill(32)
    c1 = c[-17:]
    c2 =  bin(eval('0b' + c[:-17]) ^ (eval('0b' + c1[-15:]) & eval('0b' + f[:-17])))[2:].zfill(15)
    c = c2 + c1
    #2
    f = bin(2029229568)[2:].zfill(32)
    c1 = c[-9:]
    f = f[:-9]
    c2 = bin(eval('0b' + c[-18:-9]) ^ (eval('0b' + c1) & eval('0b' + f[-9:])))[2:].zfill(9)
    f = f[:-9]
    c3 = bin(eval('0b' + c[-27:-18]) ^ (eval('0b' + c2) & eval('0b' + f[-9:])))[2:].zfill(9)
    f = f[:-9]
    c4 = bin(eval('0b' + c[:5]) ^ (eval('0b' + c3[-5:]) & eval('0b' + f[-5:])))[2:].zfill(5)
    c = c4 + c3 + c2 + c1
    #1
    c_1 = c[:13]
    c_2 = bin(eval('0b' + c_1) ^ eval('0b' + c[13:26]))[2:].zfill(13)
    c_3 = bin(eval('0b' + c_2[:6]) ^ eval('0b' + c[-6:]))[2:].zfill(6)
    c = c_1 + c_2 + c_3
    return c

message = '641460a9e3953b1aaa21f3a2'

m = ''
for i in range(0,len(message),8):
    txt = bin(eval('0x' + message[i:i+8]))[2:].zfill(32)
    m += decrypt(txt)

m = hex(eval('0b'+m))[2:]

print(m)
#84b45f89af22ce7e67275bdc

2025 年 8 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

MT19937预测

题目-1

解题思路

解答

题目-2

解题思路

解答

发送评论 编辑评论

推荐文章

发送评论编辑评论