WKCTF Crypto wp

fl@g

from Crypto.Util.number import *
from sympy import *
from tqdm import *
from secret import flag
from itertools import *
from math import factorial
import string

table = string.ascii_letters + string.digits + "@?!*"
#26+26+10+4=66

def myprime():
    num = 0
    for i in tqdm(permutations(table) , total=factorial(len(table))):
        temp = "".join(list(i))
        if("flag" in temp or "FLAG" in temp or "f14G" in temp or "7!@9" in temp or "🚩" in temp):#排列组合；4种单独的排列62！*63*4  重复的：60!*4 还要补上一小块：57！
            num += 1
    return nextprime(num)

m = bytes_to_long(flag)
n = myprime()*getPrime(300)
c = pow(m,65537,n)

print("n =",n)
print("c =",c)


'''
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
'''

一个RSA加密，突破点在myprime()上，我们可以通过计算出num的值得到p，然后得到q，即可解出答案

要求出num,考察的是数学的排列组合(画个图就很清晰了，也是容斥原理)

对于单个flag/FLAG/f14G/7!@9可以进行排列的总数有：63！*4

（把flag看为一个整体，那么总的字符数就可以变为60，这60个字符再进行全排列即60！,下面的同理）

需要删掉重复的：60！*4

还要补上一小块被删掉的：57！

即num=63!*4-60*4+57!

解密代码：

from math import factorial
from Crypto.Util.number import *
from sympy import nextprime

n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596

num=factorial(63)*4 -factorial(60)*4+factorial(57)

p1=nextprime(num)
q1=n//p1
phi1=(p1-1)*(q1-1)
d1=inverse(65537,phi1)
m1=pow(c,d1,n)
print(long_to_bytes(m1))
#b'WKCTF{How_long_does_it_take_to_run_directly?}'

easy_random

import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'WKCTF{}'
pad_flag = pad(flag,16)#填充
key = random.randbytes(16)
cipher = AES.new(key,AES.MODE_ECB)#AES加密
print(cipher.encrypt(pad_flag))
# b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
with open('random.txt','w') as f:
    for i in range(2496):
        f.write(str(random.getrandbits(8))+'\n')

MT19937+AES

关键在于怎么求到key,我们要知道一点：python中的random类使用的是MT19937算法

题目给了2496个key之后的随机数数据，那么就需要根据这2496个随机数据得到当前状态state，然后向前预测state得到key的数据（大致的思路）

先插入一个小知识：

import random

random.seed(1)
print(hex(random.getrandbits(32))[2:])#getrandbits(a)是生成a位二进制的随机数
print(hex(random.getrandbits(32))[2:])
#2265b1f5
#91b7584a

random.seed(1)
print(hex(random.getrandbits(64))[2:])#64位的是两个32位的拼接，但是是倒序拼接
#91b7584a2265b1f5

random.seed(1)
# print(random.randbytes(8))#ranbytes(a)是生成a个字节的数据
print(hex(bytes_to_long(random.randbytes(8)))[2:])#正好是getrandbits生成的数据的倒序
#f5b165224a58b791

random.seed(1)
print(hex(bytes_to_long(random.randbytes(2)))[2:])
print(hex(bytes_to_long(random.randbytes(2)))[2:])
#6522
#b791

print()
random.seed(1)
print(long_to_bytes(random.getrandbits(32)))
print(long_to_bytes(random.getrandbits(32)))
#b'"e\xb1\xf5'
#b'\x91\xb7XJ'

random.seed(1)
print(long_to_bytes(random.getrandbits(64)))
#b'\x91\xb7XJ"e\xb1\xf5'

random.seed(1)
print(random.randbytes(8))
#b'\xf5\xb1e"JX\xb7\x91'

print()
random.seed(1)
print(hex(random.getrandbits(8))[2:])
print(hex(random.getrandbits(8))[2:])
#22
#91

getrandbits( a )生成指定a位数的数据

以32位为分界线

小于32位的取前a位，接下来再次生成的随机数又是从下一个32位数据中取

大于32位的就取多个32位数据进行拼接，倒序拼接

randbytes()生成指定字节数的数据

同getrandbits类似的，但是这个拼接是顺序拼接的，其实就是一个大端一个小端

ok,知识解释结束

回到题目，我们要根据数据回推到状态，一般来说可以通过逆向extract_number函数进行，但是注意：这里我们得到的数据只有每个32位数据的前8位，我们逆向extract_number函数是需要32位完整的数据的

所以采用构造矩阵的办法求解，解释一下原理：

$$\begin{gathered} 假设state[i]的二进制表示形式为： \\ {x}_0{x}_1{x}_2...x_{31} \\ 输出的随机数形式为： \\ {z}_0{z}_1{z}_2...z_{31} \\ 根据extract\_number函数可以知道z和x是存在线性关系的（可以推出来的） \\ 即X\ast T=Z \\ X=Z\ast T^{-1} \\ 这就把问题转换成了矩阵的问题了 \\ 我们要求X,已知Z,如何求T呢？ \\ 可以令X=(1,0,0,....,0),这样X\ast T得到的Z就是T的第一行了 \\ 实际计算中，就是设置特定的状态，然后向后预测得到Z,这个Z就是我们T的某一行 \\ (因为XT=Z实际体现的是随机数预测的线性关系） \end{gathered}$$

回到这题，构建矩阵T:

X是状态state的矩阵，一个state包含624个数，一个数32位即X是1*19968

Z是输出数据的矩阵，总共输出数据为2496个，一个数8位，即Z是1*19968

那么T是19968*19968
$$\begin{gathered} 所以设置特定的状态 \\ 令X=(1<<31,0,0,...,0{)}_{1\ast 624},即将其作为初始状态，往后预测得到Z_1,即得到T的第一行 \\ 令X=(1<<30,0,0,...,0{)}_{1\ast 624},即将其作为初始状态，往后预测得到Z_2,即得到T的第二行 \\ ... \\ 令X=(0,1<<31,0,...,0{)}_{1\ast 624},即将其作为初始状态，往后预测得到Z_{3}3,即得到T的第三十三行 \\ 依次类推，总共19968行 \\ 我们就可以得到完整的T矩阵 \end{gathered}$$

#求解X矩阵
from sage.all import *
from random import Random
length = 19968

def myState():
    state = [0]*624
    i = 0
    while i<length:
        ind = i//32
        expont = i%32
        state[ind] = 1<<(31-expont)
        
        for j in range(len(state)):#这里要做个类型转化，不做代码跑不了（奇怪）
            state[j]=int(state[j])
        
        s = (3,tuple(state+[0]),None)
        yield s
        state[ind] = 0
        i += 1

def getRow():
    rng = Random()
    gs = myState()#设置特定的状态state
    for i in range(length):
        s = next(gs)
        rng.setstate(s)
#         print(s[1][0])
        data=[]
        for i in range(length // 8):
            #根据特定的状态state往后预测2496个数据，放入data中，以二进制一个一个放入
            data.extend(list(bin(rng.getrandbits(8))[2:].zfill(8)))
        data=[int(i) for i in data] # 只有1行，还是length长度
        row = vector(GF(2),data)
        yield row

def buildBox():
    b = matrix(GF(2),length,length)
    rg = getRow()#得到每一行，再把每一行放入b矩阵中
    for i in range(length):
        b[i] = next(rg)
    return b # length * length

# X = Z*(T^-1)
def recoverState(T,leak):
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])#得到X,但是X是二进制的，还需要转化一下
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)#32位为一个数
        state.append(tmp)
    return state

# 根据题型2,还原state,有两种可能,这时候可以直接用暴破进行测试
def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^ state[396]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return (1 << 32 - 1) | tmp & low, tmp & low

def main():
    T = buildBox()#构建矩阵T
    prng = Random()
    originState = prng.getstate()
    leak = [183, 224, 115, 52, 238, 65, 223, 53, 177, 94, 13, 188, 101, 5, 78, 21, 255, 176, 193, 117, 4, 110, 71, 99, 183, 44, 165, 106, 79, 245, 13, 234, 125, 12, 197, 181, 45, 4, 122, 24, 158, 190, 233, 16, 51, 139, 68, 244, 139, 202, 113, 69, 100, 181, 159, 154, 28, 34, 251, 196, 234, 188, 228, 22, 243, 145, 160, 179, 152, 44, 173, 163, 98, 4, 76, 49, 15, 74, 128, 89, 65, 147, 241, 243, 167, 12, 22, 237, 128, 9, 176, 128, 206, 9, 67, 178, 6, 214, 8, 198, 197, 10, 227, 57, 195, 75, 106, 157, 239, 167, 157, 155, 130, 169, 116, 7, 190, 200, 154, 26, 98, 126, 255, 32, 140, 108, 198, 123, 229, 40, 125, 208, 4, 68, 33, 58, 209, 20, 131, 101, 255, 65, 142, 25, 104, 98, 155, 174, 229, 165, 7, 38, 101, 71, 204, 69, 116, 171, 61, 34, 240, 156, 199, 226, 11, 121, 140, 86, 180, 26, 47, 120, 150, 218, 178, 65, 131, 171, 247, 22, 19, 42, 102, 249, 193, 188, 236, 41, 152, 37, 200, 180, 105, 138, 1, 97, 75, 40, 2, 112, 111, 8, 179, 50, 28, 18, 72, 170, 96, 180, 224, 58, 167, 179, 99, 52, 191, 211, 251, 235, 221, 201, 93, 214, 246, 148, 62, 208, 128, 242, 135, 186, 222, 213, 30, 42, 135, 2, 45, 139, 216, 134, 214, 54, 84, 225, 142, 162, 96, 247, 152, 34, 95, 77, 241, 204, 46, 186, 88, 28, 40, 164, 195, 81, 94, 33, 184, 132, 126, 122, 235, 193, 139, 168, 2, 116, 86, 62, 237, 108, 149, 211, 42, 58, 203, 96, 245, 216, 198, 158, 93, 12, 169, 222, 38, 50, 134, 62, 105, 40, 13, 154, 187, 254, 253, 236, 167, 173, 138, 0, 248, 81, 101, 224, 229, 48, 123, 14, 94, 133, 137, 202, 172, 63, 145, 158, 25, 140, 238, 25, 144, 186, 19, 30, 164, 134, 214, 152, 19, 227, 56, 244, 60, 33, 177, 107, 138, 87, 149, 35, 240, 247, 182, 29, 170, 113, 106, 56, 137, 210, 169, 189, 207, 5, 44, 47, 22, 225, 237, 0, 110, 57, 202, 196, 208, 92, 152, 220, 86, 45, 132, 221, 163, 240, 70, 206, 177, 125, 36, 170, 168, 29, 102, 227, 249, 73, 46, 74, 145, 84, 26, 6, 195, 114, 40, 113, 250, 154, 119, 106, 20, 99, 26, 129, 117, 243, 33, 77, 67, 255, 141, 188, 119, 173, 120, 88, 183, 163, 195, 98, 211, 114, 63, 113, 198, 205, 18, 232, 50, 27, 191, 214, 88, 20, 64, 144, 14, 174, 118, 227, 125, 95, 76, 108, 32, 160, 97, 10, 65, 36, 240, 161, 134, 129, 98, 43, 165, 23, 29, 30, 114, 118, 173, 192, 196, 51, 8, 190, 166, 6, 158, 207, 1, 10, 201, 234, 88, 160, 248, 118, 212, 142, 132, 226, 254, 216, 235, 190, 94, 247, 237, 78, 147, 166, 218, 18, 2, 162, 186, 46, 28, 105, 113, 145, 202, 76, 213, 255, 136, 92, 12, 239, 61, 2, 84, 112, 127, 58, 52, 175, 181, 56, 116, 36, 88, 120, 213, 101, 88, 187, 143, 71, 245, 93, 216, 223, 3, 211, 129, 86, 54, 121, 108, 156, 138, 183, 249, 252, 13, 58, 1, 94, 199, 13, 93, 239, 27, 248, 202, 93, 77, 27, 14, 64, 223, 198, 168, 78, 225, 95, 86, 69, 24, 213, 159, 166, 243, 163, 27, 20, 211, 91, 71, 217, 93, 214, 165, 105, 78, 202, 243, 201, 200, 194, 145, 50, 230, 243, 109, 213, 157, 239, 34, 211, 166, 24, 207, 246, 19, 218, 4, 20, 70, 92, 233, 158, 193, 237, 138, 194, 49, 247, 245, 163, 204, 210, 243, 144, 45, 150, 144, 217, 206, 140, 239, 13, 13, 76, 46, 28, 234, 199, 93, 234, 167, 16, 129, 144, 138, 136, 26, 112, 251, 131, 123, 223, 12, 88, 59, 233, 29, 5, 254, 91, 121, 157, 231, 17, 145, 70, 241, 141, 166, 140, 199, 124, 188, 216, 0, 254, 246, 60, 187, 17, 207, 245, 29, 161, 5, 49, 177, 148, 246, 41, 245, 13, 156, 226, 240, 237, 111, 190, 235, 245, 25, 228, 8, 190, 219, 82, 229, 69, 195, 166, 218, 63, 54, 186, 158, 208, 33, 223, 173, 165, 107, 185, 226, 156, 217, 210, 255, 241, 60, 136, 157, 161, 167, 220, 64, 169, 24, 48, 243, 210, 121, 220, 99, 194, 233, 220, 150, 144, 63, 76, 244, 136, 231, 135, 72, 127, 243, 205, 1, 21, 156, 224, 183, 131, 187, 231, 205, 33, 184, 254, 29, 120, 140, 102, 138, 35, 132, 229, 180, 200, 130, 196, 48, 45, 193, 80, 128, 231, 241, 73, 117, 130, 254, 186, 22, 86, 31, 200, 7, 17, 128, 198, 104, 192, 241, 91, 31, 163, 125, 124, 174, 171, 31, 253, 61, 85, 38, 101, 226, 97, 231, 45, 36, 176, 66, 7, 200, 181, 207, 72, 181, 191, 41, 43, 164, 61, 255, 177, 235, 30, 91, 195, 19, 227, 57, 136, 72, 29, 9, 95, 214, 180, 88, 174, 185, 185, 20, 219, 150, 40, 146, 218, 120, 172, 126, 169, 242, 103, 64, 20, 158, 41, 63, 113, 110, 138, 238, 202, 78, 170, 188, 90, 20, 159, 169, 43, 96, 64, 208, 138, 43, 229, 251, 121, 148, 206, 249, 97, 55, 50, 94, 139, 152, 226, 111, 14, 55, 10, 207, 55, 28, 191, 163, 229, 189, 24, 73, 89, 43, 115, 52, 2, 159, 7, 8, 199, 215, 132, 124, 253, 111, 110, 117, 191, 0, 173, 119, 0, 37, 139, 198, 119, 37, 181, 85, 59, 0, 172, 99, 30, 91, 219, 65, 1, 241, 138, 43, 171, 55, 208, 224, 156, 224, 194, 50, 131, 116, 59, 148, 92, 173, 181, 137, 84, 82, 8, 34, 177, 1, 174, 226, 97, 51, 198, 2, 57, 220, 87, 56, 214, 78, 227, 13, 155, 94, 102, 220, 79, 6, 193, 42, 158, 69, 91, 28, 44, 142, 216, 41, 105, 135, 165, 160, 121, 54, 228, 226, 253, 68, 150, 204, 77, 214, 113, 9, 228, 47, 66, 243, 168, 210, 208, 74, 240, 91, 242, 223, 168, 128, 128, 127, 126, 140, 184, 73, 71, 245, 162, 207, 163, 19, 22, 132, 154, 251, 205, 3, 183, 198, 219, 75, 135, 5, 198, 232, 185, 17, 8, 44, 26, 152, 76, 9, 148, 40, 239, 139, 76, 176, 216, 73, 135, 16, 231, 8, 134, 44, 152, 236, 38, 190, 93, 238, 178, 73, 142, 190, 243, 106, 85, 147, 129, 48, 25, 30, 175, 180, 91, 242, 135, 124, 86, 125, 227, 2, 152, 251, 2, 48, 159, 246, 135, 68, 250, 238, 206, 180, 144, 209, 54, 211, 121, 249, 13, 1, 156, 192, 247, 46, 129, 108, 239, 23, 246, 200, 243, 1, 228, 230, 15, 124, 200, 14, 177, 80, 132, 17, 107, 80, 252, 81, 224, 55, 246, 128, 119, 208, 56, 147, 244, 21, 224, 42, 157, 64, 78, 150, 1, 29, 245, 80, 65, 248, 106, 48, 83, 178, 159, 204, 38, 207, 27, 15, 129, 238, 206, 12, 159, 216, 43, 147, 247, 59, 17, 53, 236, 3, 108, 188, 16, 70, 164, 146, 8, 4, 13, 223, 88, 228, 137, 206, 72, 114, 226, 25, 157, 2, 223, 122, 128, 112, 57, 154, 252, 107, 189, 157, 51, 92, 18, 17, 98, 13, 180, 227, 133, 112, 70, 149, 130, 199, 160, 39, 225, 23, 240, 115, 193, 84, 126, 38, 34, 45, 180, 224, 89, 7, 115, 65, 86, 238, 219, 176, 182, 197, 92, 158, 12, 143, 122, 17, 148, 228, 215, 100, 70, 204, 230, 149, 1, 127, 202, 10, 9, 166, 79, 68, 128, 6, 185, 215, 197, 192, 99, 117, 69, 62, 43, 59, 3, 56, 59, 74, 211, 66, 46, 162, 158, 91, 112, 64, 195, 129, 142, 161, 153, 27, 181, 111, 117, 53, 198, 143, 45, 242, 162, 99, 79, 125, 61, 179, 110, 67, 125, 126, 105, 118, 73, 197, 22, 141, 223, 252, 1, 49, 172, 99, 77, 193, 187, 76, 138, 76, 106, 36, 218, 223, 99, 79, 119, 38, 161, 64, 121, 69, 103, 106, 141, 71, 59, 69, 151, 226, 134, 182, 8, 30, 170, 70, 170, 151, 237, 4, 43, 179, 17, 141, 80, 207, 104, 155, 0, 188, 221, 17, 100, 47, 137, 121, 192, 169, 130, 39, 199, 109, 33, 218, 97, 171, 137, 173, 81, 237, 99, 5, 98, 191, 239, 39, 205, 172, 114, 252, 2, 235, 49, 6, 161, 238, 107, 141, 124, 125, 106, 243, 33, 197, 224, 112, 106, 187, 89, 63, 130, 169, 111, 202, 171, 13, 195, 92, 23, 153, 237, 60, 45, 170, 115, 110, 133, 14, 42, 15, 11, 129, 131, 49, 219, 11, 48, 235, 108, 35, 135, 50, 192, 220, 253, 83, 102, 140, 140, 149, 193, 198, 246, 218, 186, 14, 190, 202, 145, 97, 90, 144, 118, 251, 131, 72, 163, 242, 165, 142, 160, 83, 171, 84, 226, 144, 216, 8, 84, 118, 1, 218, 225, 190, 218, 194, 175, 228, 75, 45, 165, 111, 229, 100, 76, 134, 186, 15, 14, 223, 62, 254, 190, 58, 43, 161, 75, 106, 86, 70, 120, 139, 160, 124, 123, 163, 73, 102, 143, 29, 195, 104, 201, 56, 96, 181, 200, 192, 127, 145, 229, 122, 215, 215, 242, 37, 133, 179, 8, 101, 123, 228, 56, 148, 217, 112, 222, 50, 85, 17, 119, 109, 55, 61, 129, 191, 54, 109, 29, 11, 178, 195, 224, 92, 70, 90, 60, 147, 240, 43, 75, 238, 138, 160, 226, 202, 36, 46, 182, 163, 3, 66, 23, 49, 128, 163, 221, 162, 233, 94, 84, 174, 143, 187, 123, 205, 91, 22, 117, 243, 113, 50, 92, 168, 143, 196, 230, 182, 11, 2, 168, 2, 143, 98, 96, 33, 12, 88, 174, 35, 50, 87, 123, 30, 67, 13, 213, 229, 237, 212, 72, 8, 230, 24, 112, 186, 22, 207, 165, 131, 145, 138, 159, 227, 43, 224, 131, 76, 204, 91, 15, 64, 109, 211, 196, 160, 187, 119, 125, 224, 111, 146, 187, 159, 117, 245, 53, 203, 36, 69, 165, 246, 34, 249, 82, 185, 28, 99, 121, 176, 211, 135, 211, 238, 159, 105, 5, 112, 105, 41, 176, 140, 228, 111, 229, 13, 88, 27, 254, 110, 197, 22, 6, 20, 13, 160, 60, 246, 135, 217, 51, 49, 178, 232, 61, 138, 175, 66, 118, 197, 251, 25, 126, 5, 0, 69, 155, 201, 186, 245, 198, 50, 126, 124, 122, 248, 98, 174, 59, 80, 107, 99, 164, 80, 142, 224, 24, 132, 209, 167, 140, 8, 0, 119, 114, 82, 79, 198, 165, 223, 146, 104, 236, 22, 106, 173, 211, 26, 127, 12, 57, 233, 33, 200, 222, 144, 65, 85, 160, 42, 151, 113, 210, 4, 70, 29, 141, 63, 77, 213, 59, 16, 2, 194, 201, 144, 213, 20, 141, 208, 19, 13, 87, 87, 46, 91, 242, 123, 167, 153, 65, 33, 67, 11, 128, 181, 7, 72, 201, 165, 172, 219, 76, 25, 27, 128, 215, 142, 134, 64, 249, 33, 154, 238, 55, 1, 110, 2, 208, 53, 39, 83, 45, 138, 228, 33, 21, 143, 197, 232, 155, 34, 130, 106, 142, 218, 149, 100, 95, 129, 163, 5, 14, 77, 232, 148, 91, 57, 75, 1, 228, 29, 49, 179, 198, 11, 219, 82, 14, 69, 98, 148, 214, 59, 207, 148, 24, 112, 145, 162, 61, 53, 145, 245, 151, 75, 27, 115, 80, 246, 5, 219, 230, 118, 95, 237, 81, 131, 238, 57, 96, 58, 181, 70, 216, 200, 107, 174, 104, 159, 219, 110, 6, 87, 175, 190, 57, 219, 248, 198, 157, 176, 209, 182, 116, 218, 41, 125, 87, 7, 92, 153, 204, 65, 56, 194, 227, 43, 234, 32, 75, 79, 181, 208, 186, 195, 78, 186, 129, 194, 55, 253, 38, 36, 187, 197, 136, 7, 116, 98, 247, 27, 64, 41, 40, 34, 159, 133, 15, 64, 190, 65, 71, 0, 211, 43, 149, 100, 240, 5, 175, 35, 158, 77, 21, 67, 194, 79, 68, 233, 175, 144, 236, 5, 230, 92, 18, 87, 160, 33, 115, 51, 195, 129, 64, 84, 170, 80, 143, 222, 15, 136, 98, 124, 198, 34, 120, 80, 59, 115, 59, 228, 192, 121, 161, 25, 196, 170, 193, 25, 64, 217, 99, 184, 159, 209, 112, 61, 102, 118, 158, 134, 217, 132, 145, 249, 215, 3, 114, 58, 104, 14, 112, 104, 141, 150, 112, 162, 91, 120, 152, 97, 221, 73, 37, 220, 84, 183, 8, 194, 252, 108, 36, 146, 144, 180, 164, 226, 27, 214, 133, 214, 66, 15, 163, 254, 25, 145, 102, 84, 41, 155, 196, 238, 8, 19, 134, 196, 213, 105, 68, 75, 232, 95, 30, 100, 130, 24, 102, 142, 209, 37, 150, 161, 187, 12, 124, 144, 6, 112, 90, 149, 26, 148, 13, 203, 96, 236, 21, 136, 245, 200, 180, 239, 127, 63, 80, 48, 66, 78, 129, 31, 233, 249, 178, 87, 13, 163, 39, 150, 239, 239, 189, 151, 19, 139, 39, 201, 49, 42, 57, 108, 243, 153, 21, 183, 167, 58, 185, 173, 6, 41, 131, 23, 87, 88, 201, 234, 154, 82, 80, 39, 55, 200, 243, 166, 146, 35, 138, 194, 132, 203, 88, 188, 108, 101, 123, 1, 65, 69, 102, 168, 131, 71, 55, 178, 25, 199, 28, 200, 247, 205, 127, 116, 57, 17, 93, 87, 191, 194, 142, 12, 173, 253, 115, 29, 173, 233, 105, 74, 233, 215, 164, 189, 205, 19, 117, 141, 99, 222, 83, 81, 245, 67, 111, 149, 116, 187, 39, 97, 79, 193, 224, 59, 156, 177, 136, 1, 23, 145, 16, 67, 216, 98, 148, 254, 244, 221, 46, 112, 225, 55, 147, 212, 72, 225, 177, 199, 183, 245, 157, 67, 184, 71, 115, 68, 126, 68, 119, 27, 117, 92, 25, 201, 51, 196, 174, 131, 6, 106, 194, 111, 22, 61, 197, 217, 109, 110, 124, 76, 88, 5, 103, 144, 242, 53, 27, 188, 216, 7, 252, 100, 198, 66, 147, 238, 225, 142, 115, 117, 213, 162, 128, 246, 66, 215, 176, 232, 172, 90, 223, 195, 92, 52, 36, 49, 165, 205, 147, 82, 240, 206, 141, 4, 225, 108, 139, 212, 50, 212, 236, 21, 207, 116, 2, 138, 45, 3, 250, 52, 237, 112, 237, 73, 233, 165, 187, 200, 103, 186, 182, 25, 180, 134, 229, 185, 140, 6, 210, 167, 0, 55, 22, 76, 32, 32, 10, 190, 37, 23, 46, 28, 81, 17, 44, 232, 133, 89, 88, 30, 30, 213, 207, 41, 85, 11, 14, 253, 145, 128, 104, 99, 96, 229, 103, 142, 64, 71, 51]
    leak1=[int(j) for j in "".join([bin(i)[2:].zfill(8) for i in leak[:19968//8]])]
    #输出的数据转二进制，转为矩阵
    leak1 = matrix(GF(2), leak1)
    # 恢复state
    state = recoverState(T,leak1)
    print("state恢复完成")#注意这里state的第一个数是不对的，还需要重新求
    # 两种可能，对这两种可能进行测试，如果能够得到最后输出的结果说明这个guess是正确的
    guess1, guess2 = backfirst(state)
    print(guess1, guess2)
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("first")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("true")
            print(state)
            return
    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("second")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("true")
            print(state)
            return
main()

需要注意的是这里构造的T并不是满秩的，但是sage仍然可以求解，不过求解得到的X的前32位，并不正确。但是我们仍然能够得到623位的state，我们可以利用题型3中的方法还原第一位state。进而利用state预测接下来的随机数，所以有两个guess

这样就成功得到题目数据的前624个数据的状态state

state = [2922114156, 2886276701, 1168768544, 2339187170, 3551087255, 117510054, 4232565172, 1076139110, 3366831833, 1734453078, 4105913658, 1066792668, 2395352043, 785096749, 3707690263, 2430171307, 2064716469, 1119720065, 1112222395, 2136656989, 2232844740, 388978998, 1363102788, 67899517, 457789137, 3527002829, 1187847099, 1188611575, 3830294635, 3760337941, 297081839, 3230408812, 2906355860, 279725084, 3056220997, 1053068885, 3252084646, 2818726015, 3615795115, 2751222655, 74688614, 1452880497, 426221319, 1680367484, 4211465923, 908441837, 2290937869, 526329269, 3225608663, 350552485, 885538125, 3496826412, 3347875222, 2730243675, 1823616219, 1474037291, 2474670592, 1175091387, 1527449390, 2024565653, 2185945759, 902338428, 3571876882, 632524934, 1235569406, 3612682285, 2727233684, 2085380963, 1570339017, 3839696585, 1482742582, 646051896, 3804319832, 2113555238, 4150326517, 2606046640, 1454130831, 1919843931, 1018624146, 1956310311, 1162868231, 1118548906, 974692065, 3020424226, 2996838388, 1724936385, 1668410782, 3044755338, 3710133971, 1043581839, 362583150, 3880481779, 114234888, 1724135673, 1280834309, 2958310395, 3502226151, 620064160, 3244210820, 3839287479, 2283659292, 405764632, 29535149, 2759062778, 1662916252, 2374319319, 3359789079, 1896011543, 1991740933, 2041947596, 3393060496, 996086198, 193135800, 1184463268, 819767446, 410330102, 569788256, 3880255000, 340523190, 885031563, 2752345656, 4116368372, 1738848623, 1895472503, 85502529, 334873925, 3543996685, 3082948803, 3195880838, 1458851187, 2843458392, 20236078, 3136689072, 2121777470, 3543587943, 3590933177, 4057799526, 1241162800, 1014541188, 1031410742, 267989518, 92604561, 2190353015, 87786611, 435741463, 3800398555, 1860727248, 2608606593, 287619193, 768990059, 1686137462, 3255556540, 3234299857, 2087562050, 1575350832, 1982640551, 1476745138, 2757668599, 108958643, 337813164, 273001595, 3515727084, 2976758889, 2674818924, 2133197017, 3709052669, 1992118633, 2421927781, 174599786, 3608298365, 1708985493, 3925831183, 3063611093, 3852984733, 540242111, 1623482619, 1874921843, 1317809124, 2774735715, 3828180102, 1997343223, 1516869708, 941992323, 307089973, 368181535, 163007409, 596938343, 1686397275, 52708329, 230996593, 3597201983, 378926364, 3618422671, 2062721049, 3659976071, 546629459, 3976307656, 1509609055, 3677736141, 1613243397, 1378877471, 531534610, 2602178644, 4099876535, 1394187732, 1706260244, 1842911215, 3381571710, 456693813, 1667668257, 792813840, 4044011316, 1391972141, 1677638507, 1467741933, 2542725716, 3261642613, 1122181516, 1726857655, 2765884383, 2563231823, 1890137479, 3462591813, 290505918, 3480784421, 4146013364, 906268950, 1460571462, 625398701, 1868955581, 2562420879, 3524561573, 2480663847, 424010572, 3760440358, 506451740, 2616205788, 3835513223, 2698078113, 933669512, 2259175222, 1766445936, 3062774434, 3383207496, 165724374, 717679250, 872303977, 1054921507, 1640987195, 2398705310, 744526846, 2142916476, 3769314780, 3643489144, 906983325, 1001096018, 1522376663, 3516789445, 425379249, 1807654888, 1584889396, 996500676, 2138028000, 1877118731, 2780715755, 56317932, 994780643, 231703463, 1590924826, 449553992, 1970334362, 3631415563, 2378887069, 2645995105, 604040985, 766274135, 2897107084, 3122401328, 604584226, 3514594183, 3159592392, 539086862, 1966827756, 1548312674, 2223920152, 4193868755, 2604831097, 2301554299, 2919432501, 3445772747, 221908018, 1919849944, 1707243688, 1311680342, 1132835813, 824121832, 2623654824, 4245764621, 1669541543, 793028119, 1400611299, 2330555992, 1295319061, 2376883177, 3054784982, 1534527889, 3381065612, 431181624, 2520679460, 1612115175, 3417053178, 3202101207, 4112825474, 209873225, 3982289256, 3175605361, 1007754107, 1533969733, 3657972615, 1233249703, 1775877579, 2812100730, 3215107528, 1781386145, 3025989255, 3066346118, 3283795978, 1197222174, 2936543382, 3503535134, 2892598771, 2621962168, 931511531, 2231087188, 4146539078, 4002087507, 2491835423, 4060649251, 4048333160, 2444738719, 2691519303, 1556526141, 3615497232, 4050826531, 500299044, 717467546, 2206683369, 861398548, 3151369905, 4029791836, 3416545629, 4120104600, 1465267912, 483234533, 3035820989, 3832933168, 3568690105, 96174302, 2545526712, 1102861924, 1074783639, 4182941480, 1533353222, 1488829617, 1503690984, 185887778, 4211993208, 2290188486, 1146083769, 2041769341, 2684027677, 3176900642, 1387338494, 946259368, 1066487432, 795876682, 3861793354, 1668825820, 216618949, 2896083408, 3851619025, 442276681, 206355214, 270139248, 347366931, 1910792165, 3953458832, 2734158556, 2811136264, 1920172269, 1837836373, 3778467275, 3779230355, 3897121172, 2344011383, 1146522764, 2190434845, 609244986, 2013714652, 560173192, 2402932255, 1072869170, 1770725561, 952360909, 1412825165, 3696544236, 2306376326, 2830983153, 207976619, 4155556879, 3728896627, 2654370117, 3334033001, 1365410137, 1493856098, 1253593280, 1631830970, 5803336, 3918597809, 86127041, 333464839, 3604499396, 149662371, 2129288705, 1461710188, 3760680120, 3729872359, 2100765881, 3535556758, 444301423, 2716178967, 1126522126, 4087265377, 129975151, 3676574817, 946781552, 1144144314, 4160587561, 3992786314, 45372372, 2839307265, 3121990915, 2417091275, 2394722122, 2336989436, 3126674182, 3231554964, 3785353831, 3066121066, 4059908701, 3257600631, 3304564137, 976977941, 2994176851, 3509885563, 436168092, 2194926470, 572263581, 2964578564, 2577729800, 4257414592, 1074783671, 2629434251, 42822614, 1475322010, 3068645543, 3694724738, 3480058324, 4204711804, 3168448984, 2767935672, 3016152818, 4134435775, 2141315517, 2182008981, 2871864678, 2294299758, 1409773258, 3418660825, 3090287076, 3241139267, 2315623533, 2157788904, 334169841, 2062298350, 4075844652, 1672438569, 2994084656, 2204498767, 2430183901, 4179388667, 317027997, 2894184457, 3635887387, 1307832846, 3358657065, 734371454, 610520453, 3421706671, 3240587498, 3690351924, 935152653, 2737123774, 203357945, 1027962332, 3777141639, 743025036, 4046422672, 1085389282, 110265143, 320421926, 1931570193, 936595461, 2927488848, 2265674314, 3444945553, 786566925, 4133145648, 2879270131, 4165751769, 3985446237, 1971125873, 3724681025, 2661325531, 2441664181, 3290805620, 2459158763, 2102811157, 2881160687, 1153639082, 827213914, 3028527431, 2205345684, 3556675715, 1279123065, 4253124398, 3483559979, 4068430995, 4141206587, 2571521727, 2944439402, 443124686, 2268164570, 2235451426, 3679071975, 3129207272, 2516367556, 1468462786, 1881517367, 3491042253, 2913831047, 3164481275, 202602034, 3150723817, 1533130707, 1912730441, 2090267514, 3558123575, 1133228007, 3421482977, 2553693497, 3421969717, 2520271965, 2067324870, 1223636150, 2714495378, 3773685424, 2961634881, 88882886, 408668635, 904339271, 3187997208, 2883270961, 1911371885, 1111177434, 3677904221, 1424566197, 456428662, 3160502725, 2571618126, 1931038165, 1229862345, 885692642, 928907436, 281108918, 2025639202, 4098934983, 245166619, 3978368942, 2335134348, 2663736265, 3483476476, 1019177183, 1076843627, 2150626843, 3549898506, 497411044, 2948681730, 1293862520, 3364439483, 200913955, 876046583, 2810673955, 2828391839, 1905062360, 3783182365, 2472665728, 1439731349, 2736703148, 3316496080, 2996051367, 448455111, 3808598160, 2313472828, 1619655346, 1198200314, 3744504057, 1680713197, 2474661491, 3214410863, 1662774943, 3537885099, 3365412658, 3583677483]

然后只需要向前预测得到key，这里有两种方法

1.通过逆转twist

from random import Random
from Crypto.Cipher import AES

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

state = [2922114156, 2886276701, 1168768544, 2339187170, 3551087255, 117510054, 4232565172, 1076139110, 3366831833,
         1734453078, 4105913658, 1066792668, 2395352043, 785096749, 3707690263, 2430171307, 2064716469, 1119720065,
         1112222395, 2136656989, 2232844740, 388978998, 1363102788, 67899517, 457789137, 3527002829, 1187847099,
         1188611575, 3830294635, 3760337941, 297081839, 3230408812, 2906355860, 279725084, 3056220997, 1053068885,
         3252084646, 2818726015, 3615795115, 2751222655, 74688614, 1452880497, 426221319, 1680367484, 4211465923,
         908441837, 2290937869, 526329269, 3225608663, 350552485, 885538125, 3496826412, 3347875222, 2730243675,
         1823616219, 1474037291, 2474670592, 1175091387, 1527449390, 2024565653, 2185945759, 902338428, 3571876882,
         632524934, 1235569406, 3612682285, 2727233684, 2085380963, 1570339017, 3839696585, 1482742582, 646051896,
         3804319832, 2113555238, 4150326517, 2606046640, 1454130831, 1919843931, 1018624146, 1956310311, 1162868231,
         1118548906, 974692065, 3020424226, 2996838388, 1724936385, 1668410782, 3044755338, 3710133971, 1043581839,
         362583150, 3880481779, 114234888, 1724135673, 1280834309, 2958310395, 3502226151, 620064160, 3244210820,
         3839287479, 2283659292, 405764632, 29535149, 2759062778, 1662916252, 2374319319, 3359789079, 1896011543,
         1991740933, 2041947596, 3393060496, 996086198, 193135800, 1184463268, 819767446, 410330102, 569788256,
         3880255000, 340523190, 885031563, 2752345656, 4116368372, 1738848623, 1895472503, 85502529, 334873925,
         3543996685, 3082948803, 3195880838, 1458851187, 2843458392, 20236078, 3136689072, 2121777470, 3543587943,
         3590933177, 4057799526, 1241162800, 1014541188, 1031410742, 267989518, 92604561, 2190353015, 87786611,
         435741463, 3800398555, 1860727248, 2608606593, 287619193, 768990059, 1686137462, 3255556540, 3234299857,
         2087562050, 1575350832, 1982640551, 1476745138, 2757668599, 108958643, 337813164, 273001595, 3515727084,
         2976758889, 2674818924, 2133197017, 3709052669, 1992118633, 2421927781, 174599786, 3608298365, 1708985493,
         3925831183, 3063611093, 3852984733, 540242111, 1623482619, 1874921843, 1317809124, 2774735715, 3828180102,
         1997343223, 1516869708, 941992323, 307089973, 368181535, 163007409, 596938343, 1686397275, 52708329, 230996593,
         3597201983, 378926364, 3618422671, 2062721049, 3659976071, 546629459, 3976307656, 1509609055, 3677736141,
         1613243397, 1378877471, 531534610, 2602178644, 4099876535, 1394187732, 1706260244, 1842911215, 3381571710,
         456693813, 1667668257, 792813840, 4044011316, 1391972141, 1677638507, 1467741933, 2542725716, 3261642613,
         1122181516, 1726857655, 2765884383, 2563231823, 1890137479, 3462591813, 290505918, 3480784421, 4146013364,
         906268950, 1460571462, 625398701, 1868955581, 2562420879, 3524561573, 2480663847, 424010572, 3760440358,
         506451740, 2616205788, 3835513223, 2698078113, 933669512, 2259175222, 1766445936, 3062774434, 3383207496,
         165724374, 717679250, 872303977, 1054921507, 1640987195, 2398705310, 744526846, 2142916476, 3769314780,
         3643489144, 906983325, 1001096018, 1522376663, 3516789445, 425379249, 1807654888, 1584889396, 996500676,
         2138028000, 1877118731, 2780715755, 56317932, 994780643, 231703463, 1590924826, 449553992, 1970334362,
         3631415563, 2378887069, 2645995105, 604040985, 766274135, 2897107084, 3122401328, 604584226, 3514594183,
         3159592392, 539086862, 1966827756, 1548312674, 2223920152, 4193868755, 2604831097, 2301554299, 2919432501,
         3445772747, 221908018, 1919849944, 1707243688, 1311680342, 1132835813, 824121832, 2623654824, 4245764621,
         1669541543, 793028119, 1400611299, 2330555992, 1295319061, 2376883177, 3054784982, 1534527889, 3381065612,
         431181624, 2520679460, 1612115175, 3417053178, 3202101207, 4112825474, 209873225, 3982289256, 3175605361,
         1007754107, 1533969733, 3657972615, 1233249703, 1775877579, 2812100730, 3215107528, 1781386145, 3025989255,
         3066346118, 3283795978, 1197222174, 2936543382, 3503535134, 2892598771, 2621962168, 931511531, 2231087188,
         4146539078, 4002087507, 2491835423, 4060649251, 4048333160, 2444738719, 2691519303, 1556526141, 3615497232,
         4050826531, 500299044, 717467546, 2206683369, 861398548, 3151369905, 4029791836, 3416545629, 4120104600,
         1465267912, 483234533, 3035820989, 3832933168, 3568690105, 96174302, 2545526712, 1102861924, 1074783639,
         4182941480, 1533353222, 1488829617, 1503690984, 185887778, 4211993208, 2290188486, 1146083769, 2041769341,
         2684027677, 3176900642, 1387338494, 946259368, 1066487432, 795876682, 3861793354, 1668825820, 216618949,
         2896083408, 3851619025, 442276681, 206355214, 270139248, 347366931, 1910792165, 3953458832, 2734158556,
         2811136264, 1920172269, 1837836373, 3778467275, 3779230355, 3897121172, 2344011383, 1146522764, 2190434845,
         609244986, 2013714652, 560173192, 2402932255, 1072869170, 1770725561, 952360909, 1412825165, 3696544236,
         2306376326, 2830983153, 207976619, 4155556879, 3728896627, 2654370117, 3334033001, 1365410137, 1493856098,
         1253593280, 1631830970, 5803336, 3918597809, 86127041, 333464839, 3604499396, 149662371, 2129288705,
         1461710188, 3760680120, 3729872359, 2100765881, 3535556758, 444301423, 2716178967, 1126522126, 4087265377,
         129975151, 3676574817, 946781552, 1144144314, 4160587561, 3992786314, 45372372, 2839307265, 3121990915,
         2417091275, 2394722122, 2336989436, 3126674182, 3231554964, 3785353831, 3066121066, 4059908701, 3257600631,
         3304564137, 976977941, 2994176851, 3509885563, 436168092, 2194926470, 572263581, 2964578564, 2577729800,
         4257414592, 1074783671, 2629434251, 42822614, 1475322010, 3068645543, 3694724738, 3480058324, 4204711804,
         3168448984, 2767935672, 3016152818, 4134435775, 2141315517, 2182008981, 2871864678, 2294299758, 1409773258,
         3418660825, 3090287076, 3241139267, 2315623533, 2157788904, 334169841, 2062298350, 4075844652, 1672438569,
         2994084656, 2204498767, 2430183901, 4179388667, 317027997, 2894184457, 3635887387, 1307832846, 3358657065,
         734371454, 610520453, 3421706671, 3240587498, 3690351924, 935152653, 2737123774, 203357945, 1027962332,
         3777141639, 743025036, 4046422672, 1085389282, 110265143, 320421926, 1931570193, 936595461, 2927488848,
         2265674314, 3444945553, 786566925, 4133145648, 2879270131, 4165751769, 3985446237, 1971125873, 3724681025,
         2661325531, 2441664181, 3290805620, 2459158763, 2102811157, 2881160687, 1153639082, 827213914, 3028527431,
         2205345684, 3556675715, 1279123065, 4253124398, 3483559979, 4068430995, 4141206587, 2571521727, 2944439402,
         443124686, 2268164570, 2235451426, 3679071975, 3129207272, 2516367556, 1468462786, 1881517367, 3491042253,
         2913831047, 3164481275, 202602034, 3150723817, 1533130707, 1912730441, 2090267514, 3558123575, 1133228007,
         3421482977, 2553693497, 3421969717, 2520271965, 2067324870, 1223636150, 2714495378, 3773685424, 2961634881,
         88882886, 408668635, 904339271, 3187997208, 2883270961, 1911371885, 1111177434, 3677904221, 1424566197,
         456428662, 3160502725, 2571618126, 1931038165, 1229862345, 885692642, 928907436, 281108918, 2025639202,
         4098934983, 245166619, 3978368942, 2335134348, 2663736265, 3483476476, 1019177183, 1076843627, 2150626843,
         3549898506, 497411044, 2948681730, 1293862520, 3364439483, 200913955, 876046583, 2810673955, 2828391839,
         1905062360, 3783182365, 2472665728, 1439731349, 2736703148, 3316496080, 2996051367, 448455111, 3808598160,
         2313472828, 1619655346, 1198200314, 3744504057, 1680713197, 2474661491, 3214410863, 1662774943, 3537885099,
         3365412658, 3583677483]

# partS = recover_state(c)
state = backtrace([0]*4+state)[:624]
# print(state)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
key = prng.getrandbits(16 * 8).to_bytes(16, 'little')
c = b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
aes = AES.new(key, AES.MODE_ECB)
print(aes.decrypt(c))
#b'WKCTF{3f2af637b773613c18d27694f20d98fd}\t\t\t\t\t\t\t\t\t'

2.直接用现成的模块extend_mt19937_predictor进行回溯( 需要python版本最新才能下载，记得更新一下 )

GitHub - NonupleBroken/ExtendMT19937Predictor：通过放置 32 * 624 位生成的数字MT19937来预测和回溯 PRNG。Python“随机”标准库使用mt19937，因此我们可以轻松破解它。

from random import Random
from Crypto.Cipher import AES
from extend_mt19937_predictor import ExtendMT19937Predictor

s = [3086615663, 3771906507, 1933791567, 874400704, 4000928288, 1101512046, 3757205682, 895930285, 2975657910,
     1590250704, 227397937, 3163700038, 1702493296, 86408336, 1317214060, 355017934, 4281601498, 2958424486, 3248821687,
     1977038961, 75767861, 1848107476, 1201089736, 1669521311, 3079560731, 753259725, 2783047520, 1792692953,
     1335325755, 4118154638, 221587457, 3931660158, 2105971738, 205787269, 3306213190, 3047766446, 757659831, 70863674,
     2054184739, 418281550, 2654142751, 3195128907, 3920550815, 273337573, 856860348, 2332777112, 1144893468,
     4097373151, 2348453877, 3391728911, 1909111864, 1167657184, 1690201897, 3037596190, 2683689827, 2591985588,
     483396539, 583852871, 4213595783, 3297463098, 3940471284, 3167491933, 3836764654, 385184073, 4089593895,
     2435556034, 2689611721, 3009515703, 2557788155, 742759035, 2911234764, 2747466359, 1658388676, 77325257,
     1282826102, 833518584, 258773596, 1252680510, 2161330425, 1505524757, 1106189058, 2479195181, 4059279758,
     4087261637, 2802856115, 215936888, 385734300, 3976823712, 2155716808, 166878602, 2958581226, 2153643018,
     3459229793, 166654981, 1135752470, 2999716815, 102870168, 3592405002, 143561712, 3332529987, 3320611547, 176304087,
     3809410875, 956905158, 3283895217, 1267764884, 1781613649, 2648889013, 4023857409, 2805378741, 2649655508,
     2608225929, 2196639843, 2844902511, 1947381383, 133311662, 3189375534, 3360781939, 2598704112, 449730728,
     1660136746, 2120362421, 4282918442, 553031705, 2359175283, 1820194402, 3326941501, 2079373053, 3848840564,
     674418166, 2099289575, 3503720323, 71654499, 1153326313, 560391397, 987219237, 3519108661, 343772283, 2206155982,
     1710469128, 4284016382, 1099544658, 2385903806, 435889661, 1754514095, 1654595795, 2611465271, 2924309399,
     3849122741, 2771388572, 132443906, 639488960, 1702455392, 1197499823, 3431742381, 1162507747, 1956793904,
     2882150352, 1024607141, 573195509, 4026654414, 2622992078, 3350586931, 3799382718, 189653578, 2030853706,
     2360599919, 1447670146, 3029293260, 449492231, 794537698, 2013929440, 2521582617, 3662902133, 2988382934,
     1101429406, 2204422539, 2884223003, 4160719615, 378925199, 321253023, 713869660, 1722066591, 4190495614,
     3241838993, 3156104799, 3976107465, 690141471, 2565083608, 629627271, 3367902606, 3025623735, 1771459709,
     2325207656, 29331249, 1631496960, 1272596234, 677116176, 36223230, 1894006200, 1868323656, 147662067, 3018282350,
     847618418, 473803624, 303813116, 1222076488, 2857631548, 1620440323, 3028453586, 3771115277, 974948581, 2805463577,
     3012869721, 1677541868, 873746956, 3206333732, 3540196648, 4222297189, 3955666095, 3723668809, 3383181896,
     1572023031, 3593767211, 4139994756, 2493637240, 1055398974, 3491895839, 2158774748, 4074778554, 2265454243,
     3123246270, 3737495019, 3584208536, 505004504, 711346815, 2265659930, 44813444, 762261590, 2345302575, 3635851795,
     2255282129, 3598634106, 921749760, 1418440684, 3784150188, 2393915660, 2720478000, 1612782044, 4147046015,
     2561634247, 586916363, 1606384598, 1299844033, 4047608483, 3431257347, 781242816, 3127114595, 1484369015,
     483654543, 678493767, 2757899632, 3276695749, 1363370762, 1578035875, 555054787, 3093962781, 2222987767,
     2130200534, 2053306276, 3948690640, 3249023873, 2343777324, 2833997966, 44199340, 1950451402, 1448991312,
     1055067146, 3980624341, 1812874122, 2512418377, 3541037815, 714180005, 987816438, 3414079245, 1619142872,
     4122595525, 3638144912, 3337941608, 2664929972, 1577036940, 206102296, 2850863132, 3729200403, 644729416,
     844182047, 2261919397, 1040614315, 1776485562, 677708826, 223842114, 2591956969, 3141458682, 4271489476,
     4253854271, 3973860423, 2805984925, 2908508806, 2328769351, 3865140, 4170270812, 1373888554, 1702101960,
     3761095439, 3848481069, 812779025, 2073985983, 239315333, 1585392927, 2233774162, 2308108952, 3393306946,
     2891660426, 1059096016, 2448311649, 2662483261, 422228248, 2356192519, 4004741305, 432651290, 2419877069,
     3136967672, 329338548, 510605497, 2753410852, 2256462380, 3602678268, 2558451886, 324326056, 3822050324, 944965241,
     4107093336, 1023337388, 564298141, 2977064774, 1802025909, 2329346614, 1460784428, 2510641562, 593994802,
     4034614216, 4154528137, 3061249939, 487067285, 2856327155, 1909407614, 1782934804, 947220403, 2311402749,
     3528590202, 2841893555, 3179384475, 3485733076, 87074890, 753396673, 790057962, 378850528, 3789224576, 3983502105,
     1166116, 1854075229, 965611444, 3399039227, 3301304385, 3499808775, 1553588463, 2562124078, 3702675704, 1456114141,
     768418804, 2227423616, 3711148950, 2738970313, 4033988307, 1184409529, 3461105405, 2986057969, 2112332635,
     615658869, 2858394250, 2819269426, 499315937, 1714425168, 3816439521, 4188657733, 1226314395, 773286132,
     1257824142, 2439511774, 1412431345, 451028253, 102711904, 3272107935, 1915128127, 674941443, 1907183006,
     4205826365, 2592631544, 2001660887, 1793337902, 336832953, 1676534641, 439197643, 2175306211, 1969440247,
     4084563735, 564896680, 1293717918, 1136684128, 4289259757, 2368216261, 3167549822, 1998645278, 2908859410,
     2014400533, 1482521794, 3082876093, 2742987778, 3273667028, 1654313273, 3551772744, 1923315597, 1063687791,
     1907747434, 3323400678, 3445870975, 316314436, 3905619499, 853586576, 456263058, 3213830894, 3603099146,
     1478599807, 344267130, 1085971878, 2416474796, 247701271, 2926294528, 1981779524, 3809025846, 2106937971,
     1596271124, 1289668306, 1824884242, 543613169, 2698011204, 1632632104, 179981234, 1091171130, 608067622,
     4034608897, 2707671187, 2261524231, 2177175178, 1649366013, 733151281, 2783115482, 389580085, 495962438, 512715565,
     1917819840, 1993385884, 2910358830, 3223741704, 3302008571, 857474180, 143995596, 3194737469, 2792999636,
     111369357, 2665449999, 3481184513, 21965724, 172308864, 3373225896, 3941204120, 1487487599, 2697473345, 4173199839,
     1988623177, 3567610975, 2393053467, 2231132558, 3798877543, 4275987399, 3626515970, 3957758644, 3196139612,
     1577858639, 4145376193, 3982712357, 1316354617, 2476570111, 2796635786, 3673095113, 317782376, 38302891,
     2729549772, 3124741082, 779634809, 480059945, 1764557943, 1905762442, 2439926326, 3398546304, 1275206055,
     3578388510, 4286589961, 2284154687, 1547652572, 211218778, 4019993609, 1035325551, 47385212, 1413260320,
     1895132671, 2144191841, 976730195, 880818479, 2944522030, 3051883625, 941172532, 1956827360, 604038865, 1490554868,
     2014326554, 3585424155, 1705580179, 1484996770, 3145161387, 2410763156, 1196196268, 4125882510, 1569631240,
     3635487118, 3743075539, 53348120, 3549050110, 2179975673, 1455493727, 909517499, 2034744814, 1815931219,
     2625466993, 2328144852, 3083176966, 4185591290, 4232725936, 233807337, 987553443, 25498384, 1577858645, 3349985471,
     222166290, 1566719496, 4025597331, 454410574, 4172717618, 3397690720, 1563985388, 1294197484, 454917824, 250364909,
     1076318659, 3751354075, 3324840413, 2834288682, 1309780963, 3789459740, 1605544538, 1448439145, 1158482892,
     407656226, 3589982226, 2670402128, 2795218845, 4079499284, 2736737218, 468906864, 347349067, 3541605667,
     1532233501, 1192558327, 3650037602, 1570092544, 3596826230, 2768927258, 1775543901, 1324819997, 3401066173,
     4078892370, 3373389918, 3360817112, 3261261117, 2443241006, 847292772, 3862028592, 4086319712, 1837673494,
     3577160747, 2636413549, 4021668342, 573747407, 3546255858, 2787607684, 403421850, 3477281082, 4133820736,
     332805644, 3663845239, 80993494, 344033777, 1187319040, 1547969768]

predictor = ExtendMT19937Predictor()
a = []
for i in range(624):
    a.append(predictor.setrandbits(s[i], 32))#setrandbits方法让输入32*624位数字后，其内部状态确定，即输入数据可以获取当前的状态
    #注意这里输入数据得到状态之后状态会变
print(a)
aa = []
#这个时候的数据已经是下一个624数据的第一个状态了，所以需要先回溯624个数据才行
for i in range(624):
    aa.append(predictor.backtrack_getrandbits(32))#向前回溯数据
print(aa)

key = predictor.backtrack_getrandbits(16 * 8).to_bytes(16, 'little')
c = b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
aes = AES.new(key, AES.MODE_ECB)
print(aes.decrypt(c))
# WKCTF{3f2af637b773613c18d27694f20d98fd}

参考文章：浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

[WKCTF 2024] Crypto (random)_wkctf2024-CSDN博客

原文地址：https://blog.csdn.net/m0_73725283/article/details/140596668

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！