强网杯2025 • Misay's blog

写在前面#

第一次参加学校认可度比较高的的比赛解决了Crypto的两道赛题以及Misc的一道赛题明年继续加油~

check-little#

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os

flag, key = open('secret').read().split('\n')

e = 3

while 1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    if phi % e != 0:
        break
N = p * q
c = pow(key, e, N)

iv = os.urandom(16)
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()

f = open('output.txt', 'w')
f.write(f'N = {N}\n')
f.write(f'c = {c}\n')
f.write(f'iv = {iv}\n')
f.write(f'ciphertext = {ciphertext}\n')

加密指数 $e$ 很小但是由于明文key非常大导致无法对穷举 $k$ 对 $c+kn$ 开三次方

经过数据检查发现 $c$ 与 $N$ 不互素且公因数为1024位故得到 p = gcd(N,c)

分解 $N$ 进行RSA解密

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
print(p.bit_length())


p = gcd(N,c)
assert N % p == 0
q = N // p

phi = (p-1)*(q-1)
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = bytes.fromhex("bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2")
e = 3
d = inverse_mod(e,phi)
key = pow(c,d,N)
cipher = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC)

print(ciphertext)
flag = cipher.decrypt(ciphertext)
print(flag)

'''
1024
b'\xbf\x87\x02{\xc6>i\xd3\tcep:mG\xb5Y\xe06K\x16\x05\t+ds\xec\xdek\xab\xef\xf2'
b'flag{m_m4y_6e_divIS1b1e_by_p?!}\x01'
'''

ezran#

from Crypto.Util.number import *
from random import *

f = open('flag.txt', 'r')
flag = f.read().encode()

gift=b''
for i in range(3108):
    r1 = getrandbits(8)
    r2 = getrandbits(16)
    x=(pow(r1, 2*i, 257) & 0xff) ^ r2
    c=long_to_bytes(x, 2)
    gift+=c

m = list(flag)
for i in range(2025):
    shuffle(m)

c = "".join(list(map(chr,m)))

f = open('output.txt', 'w')
f.write(f"gift = {bytes_to_long(gift)}\n")
f.write(f"c = {c}\n")

考察python random库中getrandbits相关mt算法的攻击

源题2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz) ↗

对于mt算法其存在一个state初态，其为624个32bits数字每轮调用getrandbits都会生成32位比特同时更新state 而后续的shuffle也会调用环境下的state生成伪随机的位序下标，故而本题的思路为

从gift获取足够的关于state的位数信息接着调用shuffle预测下标从密文c中恢复flag

首先分析如何从3108轮中拿到getrandbits的部分位数

对于624 * 32的state 我们把它展开为长19968的向量 $s$ 对于我们由 $s$ 生成的任意一位 $b$ （0或1）都存在一个向量 $t$ 满足

t\cdot s=b

我们需要收集至少19968组方程凑成满秩的空间即可解出 $s$

$r_1$ 是8位的随机数进行(pow(r1, 2i, 257) & 0xff)计算后得到的还是8位与16位的随机数 $r_2$ 进行异或我们能直接取到 $r_2$ 高8位

特别的因为 $257=2^8 + 1$ 所以说当我们的指数幂 $2i$ 为 $2^8$ 的倍数的时候由欧拉定理能够得到（pow(r1, 2i, 257) & 0xff）=1

此时能得到 $r_2$ 的高15位

综上我们能获得的总位数是

3108 \times 8 + 15 \times(3108 - \frac{3108}{8})\times 15 = 30684 >> 19968

信息完全够我们恢复

参考源题的exp

但获取比特更分散同时获取的noise更多对脚本进行修改同时在s的解空间中进行一个穷举，能找到我们的解

from Crypto.Util.number import long_to_bytes, bytes_to_long
from random import Random
from tqdm import trange
from sage.all import Matrix, GF, vector

gift = 
c = ')9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u'

NUM_ITERATIONS = 3108
MT_STATE_BITS = 19968
MT_N_WORDS = 624
MAX_TRY_SOLUTIONS = 1024 

def construct_row_r2_highbytes(rng: Random):
    row_bits = []
    for _ in range(NUM_ITERATIONS):
        rng.getrandbits(8)           
        r2 = rng.getrandbits(16)    
        r2_high = r2 >> 8
        row_bits.extend(int(b) for b in bin(r2_high)[2:].zfill(8))
    return row_bits

def build_L_matrix():
    rows = []
    rng = Random()
    for bit_index in trange(MT_STATE_BITS, desc="构造 L 矩阵行"):
        bitstring = "0" * bit_index + "1" + "0" * (MT_STATE_BITS - 1 - bit_index)
        state_words = [int(bitstring[32*w:32*w+32], 2) for w in range(MT_N_WORDS)]
        rng.setstate((3, tuple(state_words + [MT_N_WORDS]), None))
        rows.append(construct_row_r2_highbytes(rng))
    return Matrix(GF(2), rows)

def build_R_vector_from_gift_long(gift_long: int):
    gift_bytes = long_to_bytes(gift_long)
    if len(gift_bytes) != 2 * NUM_ITERATIONS:
        gift_bytes = (b'\x00' * (2*NUM_ITERATIONS - len(gift_bytes))) + gift_bytes
    bits = []
    for i in range(NUM_ITERATIONS):
        high_byte = gift_bytes[2*i]  
        bits.extend(int(b) for b in bin(high_byte)[2:].zfill(8))
    return vector(GF(2), bits)

def try_recover_flag_from_s(s_vector, c_str):
    bit_str = "".join(map(str, list(s_vector)))
    state_words = [int(bit_str[32*i:32*i+32], 2) for i in range(MT_N_WORDS)]
    recovered_state = (3, tuple(state_words + [MT_N_WORDS]), None)
    rng = Random()
    rng.setstate(recovered_state)


    for _ in range(NUM_ITERATIONS):
        rng.getrandbits(8)   
        rng.getrandbits(16)  

    x = [i for i in range(len(c_str))]
    for _ in range(2025):
        rng.shuffle(x)

    flag_chars = []
    for i in range(len(c_str)):
        flag_chars.append(c_str[x.index(i)])
    flag = "".join(flag_chars)
    if "flag" in flag:
        return flag
    return None

def main():
    print("[*] 正在构造 L 矩阵（这一步可能比较慢）...")
    L = build_L_matrix()

    print("[*] 正在从 gift 构造观测向量 R ...")
    R = build_R_vector_from_gift_long(gift)

    print("[*] 求解 s（线性方程）...")
    s_particular = L.solve_left(R)

    kernel_basis = L.left_kernel().basis()
    k_dim = len(kernel_basis)
    total = 2 ** k_dim
    print(f"[*] kernel 维度 = {k_dim}, 解空间大小 = {total}")

    to_try = total
    if to_try > MAX_TRY_SOLUTIONS:
        print(f"[!] 解空间太大 ({total})，只尝试前 {MAX_TRY_SOLUTIONS} 个组合")
        to_try = MAX_TRY_SOLUTIONS

    for j in trange(to_try, desc="枚举 kernel 组合并尝试恢复"):
        s_kernel = vector(GF(2), [0] * MT_STATE_BITS)
        bin_j = bin(j)[2:].zfill(k_dim)
        for idx in range(k_dim):
            if bin_j[idx] == '1':
                s_kernel += kernel_basis[idx]
        s_current = s_particular + s_kernel

        recovered_flag = try_recover_flag_from_s(s_current, c)
        if recovered_flag:
            print(recovered_flag)
            return

    print("[!] 在尝试的解中未发现包含 'flag' 的字符串。")

if __name__ == "__main__":
    main()

    
'''
[*] 正在构造 L 矩阵
构造 L 矩阵行: 100%|██████████| 19968/19968 [01:11<00:00, 279.58it/s]
[*] 求解 s ...
[*] kernel 维度 = 38, 解空间大小 = 274877906944
枚举 kernel 组合并尝试恢复:
flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}(some_noise_to_make_sure_you_get_it)
'''

*sk#

task.py

from random import randint
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from math import gcd
import signal
from secret import flag

def gen_coprime_num(pbits):
    lbits = 2 * pbits + 8
    lb = 2**lbits
    ub = 2**(lbits + 1)
    while True:
        r = randint(lb, ub)
        s = randint(lb, ub)
        if gcd(r, s) == 1:
            return r, s

def mult_mod(A, B, p):
    result = [0] * (len(A) + len(B) - 1)
    for i in range(len(A)):
        for j in range(len(B)):
            result[i + j] = (result[i + j] + A[i] * B[j]) % p
    
    return result

def gen_key(p):
    f = [randint(1, 2**128) for i in ":)"]
    h = [randint(1, 2**128) for i in ":("]
    
    R1, S1 = gen_coprime_num(p.bit_length())
    R2, S2 = gen_coprime_num(p.bit_length())

    B = [[randint(1, p - 1) for i in ":("] for j in ":)"]

    P = []
    for b in B:
        P.append(mult_mod(f, b, p))
    
    Q = []
    for b in B:
        Q.append(mult_mod(h, b, p))

    for i in range(len(P)):
        for j in range(len(P[i])):
            P[i][j] = P[i][j] * R1 % S1
            Q[i][j] = Q[i][j] * R2 % S2

    sk = [(R1, S1), (R2, S2), f, h, p]
    pk = [P, Q, p]

    return sk, pk

def encrypt(pk, pt):
    P, Q, p = pk
    pt = bytes_to_long(pt)

    PP = 0
    QQ = 0

    for i in range(len(P)):
        u = randint(1, p)
        for j in range(len(P[0])):
            PP = PP + P[i][j] * (u * pt**j % p)
            QQ = QQ + Q[i][j] * (u * pt**j % p)

    return PP, QQ

def decrypt(sk, ct):
    RS1, RS2, f, h, p = sk
    R1, S1 = RS1
    R2, S2 = RS2

    P, Q = ct
    invR1 = inverse(R1, S1)
    invR2 = inverse(R2, S2)
    P = (P * invR1 % S1) % p
    Q = (Q * invR2 % S2) % p

    f0q = f[0] * Q % p
    f1q = f[1] * Q % p
    h0p = h[0] * P % p
    h1p = h[1] * P % p

    a = f1q + p - h1p % p
    b = f0q + p - h0p % p

    pt = -b * inverse(a, p) % p
    pt = long_to_bytes(pt)

    return pt

signal.alarm(30)
p = getPrime(256)
sk, pk = gen_key(p)
ticket = long_to_bytes(randint(1, p))
enc_ticket = encrypt(pk, ticket)
print(pk)
print(enc_ticket)
    
for i in range(2):
    op = int(input("op>").strip())
    if op == 1:
        msg = input("pt:").strip().encode()
        ct = encrypt(pk, msg)
        print(f"ct: {ct}")
    elif op == 2:
        user_input = input("ct:").strip().split(" ")
        if len(user_input) == 2:
            ct = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid ct.")
            break
        
        user_input = input("your f:").strip().split(" ")
        if len(user_input) == 2:
            user_f = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid f.")
            break

        user_input = input("your h:").strip().split(" ")
        if len(user_input) == 2:
            user_h = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid h.")
            break

        user_input = input("your R1 S1:").strip().split(" ")
        if len(user_input) == 2:
            user_r1s1 = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid R1 S1.")
            break

        user_input = input("your R2 S2:").strip().split(" ")
        if len(user_input) == 2:
            user_r2s2 = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid R2 S2.")
            break

        pt = decrypt((user_r1s1, user_r2s2, user_f, user_h, p), ct)
        if pt == ticket:
            print(flag)
        else:
            print(pt.hex())
    else:
        print("invalid op.")
        break

print("bye!")

基于线性系统的非对称加密

简而言之就是基于两组私钥矩阵 $P$$Q$ 进行多项式卷积加密同时对公钥的矩阵进行

P_{pub}=R_1\cdot P\mod S_1

Q_{pub}=R_2\cdot P\mod S_2

的掩码混淆加密用公钥解密用私钥这些都不是很重要

交互有两次一次能进行一次选择明文Oracle 另一次需要你构造特殊的密文和私钥来调用decrypt解出ticket 如果解出来就给你flag

我们每次加密的时候会进行一个带噪声u混淆随机生成4个解不了一点

而且encrypt接口也没有泄露任何有关原始密钥的任何信息我们想解出 $(R,S)$ 也是不可能的

赛中就卡死在这了

赛后看到了NowayBack ↗战队师傅的复盘发现利用我们这里enc pk p ticket的数量级差异可以尝试直接打格子尝试把ticket格出来我们看看

token = "icqc83544d7b9625155bf207b782d382"
r = remote("47.104.146.31", 7777)
r.sendlineafter(b"token:", token.encode())
pk = eval(r.recvline().strip().decode())
enc = eval(r.recvline().strip().decode())

print(pk)
print(enc)

P, Q, p = pk
PP, QQ = enc
print(QQ.bit_length())
print(p.bit_length())
print((P[0][0]).bit_length())
'''
776
256
521
'''

数量级几乎是倍数的差距我们可以尝试去看看有没有线性关系

我们把ticket记为 $t$ 对 $t$ 的加密过程可以看成以下操作

先给你已知的公钥矩阵

P^{'}_{2\times3}\;\;Q^{'}_{2\times3}

随后进行一个计算

PP=\sum^{1}_{i=0}(\sum^{2}_{j=0}P_{i,j}(u_it^{j}\;\;mod\;\;p))

QQ=\sum^{1}_{i=0}(\sum^{2}_{j=0}Q_{i,j}(u_it^{j}\;\;mod\;\;p))

外圈决定 $u$ 内圈决定这个指数幂随后我们也注意到 $P\;\;Q$ 里面都是比较大的量

未知量都是很小的

t\;\;u_0\;\;u_1\;\;k_1\;\;k_2\;\;\cdots

我们把它放在向量里面

我们以上面的计算式为例子展开可以得到,因为当 $j=0$ 时候我们的 $u<p$ 此时我们能刚好让一个 $u\;mod\;p=u$ 暴露出来

PP=P_{0,0}u_0+\cdots+P_{1,0}u_1+\cdots

所以我们左短向量处这里就可以对应上 $u_0\;\;u_1$

我们很直白的展开

PP=P_{0,0}u_0+P_{0,1}(u_0t\;\;mod\;\;p)+P_{0,2}(u_0t^2\;\;mod\;\;p)+P_{1,0}u_1+P_{1,1}(u_1t\;\;mod\;\;p)+P_{1,2}(u_1t^2\;\;mod\;\;p)

另一边同理

QQ=Q_{0,0}u_0+Q_{0,1}(u_0t\;\;mod\;\;p)+Q_{0,2}(u_0t^2\;\;mod\;\;p)+Q_{1,0}u_1+Q_{1,1}(u_1t\;\;mod\;\;p)+Q_{1,2}(u_1t^2\;\;mod\;\;p)

就很直接.. 构造

v=(u_0,u_0t\;\;mod\;\;p,u_0t^2\;\;mod\;\;p,u_1,u_1t\;\;mod\;\;p,u_1t^2\;\;mod\;\;p,-1)

对应矩阵也是很直白的

L=\begin{pmatrix}1&0&0&0&0&0&P_{0,0}&Q_{0,0}&0\\0&1&0&0&0&0&P_{0,1}&Q_{0,1}&0\\0&0&1&0&0&0&P_{0,2}&Q_{0,2}&0\\0&0&0&1&0&0&P_{1,0}&Q_{1,0}&0\\0&0&0&0&1&0&P_{1,1}&Q_{1,1}&0\\0&0&0&0&0&1&P_{1,2}&Q_{1,2}&0\\0&0&0&0&0&0&PP&QQ&1\\\end{pmatrix}

有

vL=(u_0,u_0t\;\;mod\;\;p,u_0t^2\;\;mod\;\;p,u_1,u_1t\;\;mod\;\;p,u_1t^2\;\;mod\;\;p\;,0,0,-1)

我们取有-1的那一行 $y$ 把 $y_0$ 也就是 $u$ 提出来就可以和第二个一起来解 $t$ 了可以给后两行多一些权重让这边更容易规约到0

对 $L$ 格基规约然后取末尾为-1的行取 $u$ 解 $t$

多打几次就出了

exp

from sage.all import *
from pwn import *

io = remote("47.104.146.31", 7777)
io.sendlineafter(b"team token:", b"icqc83544d7b9625155bf207b782d382")
pk = eval(io.recvline().strip().decode())
enc = eval(io.recvline().strip().decode())

P, Q, p = pk
PP, QQ = enc
L = block_matrix(ZZ, [
    [1, 2**512*matrix(P[0]+P[1]).T, 2**512*matrix(Q[0]+Q[1]).T, 0],
    [0, 2**512*PP, 2**512*QQ, 1]
]).LLL()
for v in L:
    if abs(v[-1]) == 1:
        print([_.nbits() for _ in v])
        m = v[1]*inverse_mod(v[0], p) % p
        print(m)
        m = v[2]*inverse_mod(v[1], p) % p
        print(m)
        break
pt = m
b = -pt % p
a = 1
R1, S1 = 1, p
R2, S2 = 1, p
f = [b, a]
h = [0, 0]
P = 1
Q = 1
io.sendlineafter(b"op>", b"2")
io.sendlineafter(b"ct:", " ".join(map(str, (PP, QQ))).encode())
io.sendlineafter(b"your f:", " ".join(map(str, f)).encode())
io.sendlineafter(b"your h:", " ".join(map(str, h)).encode())
io.sendlineafter(b"your R1 S1:", " ".join(map(str, (R1, S1))).encode())
io.sendlineafter(b"your R2 S2:", " ".join(map(str, (R2, S2))).encode())
respond = io.recvline()
print(respond)
# b'flag{b9850465bc588b3e0cf0fbbf258681a4}\n'

*blurred#

task.py

      
from sage.all import *
from sage.misc import prandom
import random
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad

q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
flag = b"flag{*****************************}"

def sample(rand):
    return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))


def GenNTRU():
    f = [sample(prandom) for _ in range(n)]
    g1 = [sample(prandom)for _ in range(n)]
    g2 = [sample(prandom) for _ in range(n)]
    g1x = Q(g1)
    g2x = Q(g2)

    while True:
        fx = Q(f)
        try:
            h1 = g1x / fx
            h2 = g2x / fx
            return (h1.lift(), h2.lift(), fx)
        except:
            prandom.shuffle(f)
            continue

for _ in range(20259):
    c = int(input("c :"))
    if c == 1:
        coin = random.getrandbits(1)
        if coin == 0:
            pk1, pk2, fx = GenNTRU()
        else:
            pk1, pk2, fx = Q.random_element().lift(), Q.random_element().lift(), Q([sample(prandom) for _ in range(n)])

        print("Hints:", pk1.list(), pk2.list())
        
    elif c == 2:
        SHA = SHA256.new()
        SHA.update(str(random.getrandbits(256)).encode())
        KEY = SHA.digest()
        cipher = AES.new(KEY, AES.MODE_ECB)
        flag = pad(flag, AES.block_size)
        print("Flag:", cipher.encrypt(flag))
    else:
        break

一个oracle游戏当你输入c = 1的时候会抛硬币,即抽取随机1个比特的变量coin 如果coin是0 就给你返回一组NTRU类下的数据否则给你一组随机的变量

我们分析一下这里的GenNTRU类

先随机构造三个多项式 $f\;\;g_1\;\;g_2$ 再计算

h_1\equiv g_1\cdot f^{-1}\mod (x^n+1) \tag{1}

h_2\equiv g_2\cdot f^{-1}\mod (x^n+1) \tag{2}

由多项式带余除法可得

f(x)=Q(x)(x+1)+R

即

f(-1)=R\equiv f(x)\mod (x+1)

也就是说对1 2两个式子我们对其转化到模 $x+1$ 上进行那么此时转移到更小的模域下就会体现

h_1(-1)\equiv g_1(-1)\cdot f^{-1}(-1)\mod (x+1)

h_2(-1)\equiv g_2(-1)\cdot f^{-1}(-1)\mod (x+1)

那么在这个时候我们关注到此时的 $h_1$ $h_2$ 在模 $x+1$ 下都涉及到一个共通的 $f^{-1}(-1)$ 元素相较于我们随机变量更能被格基规约找到一个小的量，那么我们思路就比较明确了

多次输入c=1，获取大量 $h_1\;h_2$ 的信息
造格子利用LLL判断哪些 $h_1\;\;h_2$ 来自NTRU，猜出coin
猜出足够的coin 恢复我们的mt19937状态库state
预测AES密钥求出flag

NowayBack的师傅们给出的格子如下

L=\begin{pmatrix}1&h_1(-1)&h_2(-1)\\0&p&0\\0&0&p\end{pmatrix}

一般来说我们求解的短向量的范数如果比较小我们就可以认为数据来自NTRU 否则是随机的

后续根据区分出的coin还原MT求解flag即可

from Crypto.Util.number import *

q = 1342261
n = 1031
PR = PolynomialRing(GF(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)

from pwn import *
from ast import literal_eval
from tqdm import *

sh = remote("8.147.130.84", 36918)
BITS = []
for _ in trange(20000):
    sh.recvuntil(b"c :")
    sh.sendline(b"1")
    sh.recvuntil(b"Hints:")
    res = sh.recvline().strip().decode().split("] [")
    h1 = PR(literal_eval(res[0]+"]"))
    h2 = PR(literal_eval("[" + res[1]))

    h1_ = GF(q)(h1 % (x+1))
    h2_ = GF(q)(h2 % (x+1))
    L = Matrix(ZZ, [
        [1, h1_, h2_],
        [0, q, 0],
        [0, 0, q]
    ])
    L = L.LLL()
    res = L[0]
    if(res.norm() < 100):
        BITS.append(0)
    else:
        BITS.append(1)

print(BITS)

sh.recvuntil(b"c :")
sh.sendline(b"2")
print(sh.recvline())

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *

defmt19937(out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = [rng.getrandbits(1) ^ int(o) for o in out] + [mt[0] ^ int(0x00000000)]
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand

################################################################################## test
out = BITS
RNG1 = mt19937(out)
STATE = RNG1.getstate()[1][:-1]

print(STATE)
RNG2 = RNG1
temp = [RNG2.getrandbits(1) for i inrange(20000)]

from Crypto.Cipher import AES
from Crypto.Hash import SHA256
enc = b'\xb9\xd5\x91\xea\x0c\x00\xd7\x90\xc4\x12\xe3_\xf0g\xaf\xacn]S\x84\xb6_0\xf9\xaf\x01Yv\x86\xedr\x97\n\xdf\x86=\t61Q\xb0\xda\x91J\xc7\x16\xe2\x7f'
SHA = SHA256.new()
SHA.update(str(RNG2.getrandbits(256)).encode())
KEY = SHA.digest()
cipher = AES.new(KEY, AES.MODE_ECB)
print(cipher.decrypt(enc))