打各种比赛学习到了很多知识点还有脚本，在这里粗略记录一下
通过随机数求state
由于MT19937是线性的，就可以直接通过
T是由MT19937本身算法得到的确定的线性关系，b是泄露的足够多的比特，这两个都是已知的
以此来求出s
详细学习参考：2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto
两种方法：
矩阵方程
from sage.all import *
from Crypto.Util.number import *
from tqdm import *
import random
rng = random.Random(1)
Original_state = rng.getstate()
output = [rng.getrandbits(32)for i in range(624)]
RNG = random.Random()
def construct_a_row(RNG):
row = []
for i in range(len(output)):
row += list(map(int, (bin(RNG.getrandbits(32))[2:].zfill(32))))
return row
L = []
for i in trange(19968):
state = [0]*624
temp = "0"*i + "1"*1 + "0"*(19968-1-i)
for j in range(624):
state[j] = int(temp[32*j:32*j+32],2)
RNG.setstate((3,tuple(state+[624]),None))
L.append(construct_a_row(RNG))
L = Matrix(GF(2),L)
R = []
for i in range(len(output)):
R += list(map(int, (bin(output[i])[2:].zfill(32))))
R = vector(GF(2),R)
s = L.solve_left(R)
init = "".join(list(map(str,s)))
state = []
for i in range(624):
state.append(int(init[32*i:32*i+32],2))
assert (3,tuple(state+[624]),None) == Original_state
gf2bv
from sage.all import *
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random
rng = random.Random(1)
Original_state = rng.getstate()
output = [rng.getrandbits(32)for i in range(624)]
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = []
for o in output:
zeros.append(rng.getrandbits(32) ^ int(o))
zeros.append(mt[0] ^ int(0x80000000))
sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
assert pyrand.getstate() == Original_state
state推seed(Python 的 random 库)
因为有很多师傅写了详细的逆向代码，我就在这里写一下我比较喜欢用的这个函数，可能比较方便点
详细的参考：
MT19937 | DexterJie'Blog
MT19937 - SeanDictionary | 折腾日记
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
#https://github.com/Aeren1564/CTF_Library/blob/master/CTF_Library/Cryptography/MersenneTwister/python_random_breaker.py
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
seed = random.randint(0, 2**32 - 1)
RNG = random.Random(seed)
# Original_state = RNG.getstate()
outs = []
for i in range(19968//2):
outs.append(RNG.getrandbits(2))
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = [mt[0] ^ int(0x80000000)]
for i in tqdm(range(len(outs))):
zeros.append((rng.getrandbits(2)) ^ outs[i])
sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
mt_state = pyrand.getstate()
breaker = python_random_breaker()
recovered_seeds = breaker.recover_all_integer_seeds_from_state(mt_state, 32)
assert recovered_seeds[0] == seed
这里得到的state都是MT19937最初的state，所以可以直接恢复出seed，如果不是初始state需要untwist
举例：
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
seed = random.getrandbits(128)
rng = random.Random(1)
rounds = 629
untwist_rounds = 1 + rounds//624
for i in range(rounds):
rng.getrandbits(2)
dirty_state = rng.getstate()
breaker = python_random_breaker()
dirty_mt = list(dirty_state[1][:-1])
# clean_mt = [breaker.untemper(rng.getrandbits(32)) for _ in range(624)]
# print(clean_mt)
for i in range(untwist_rounds):
dirty_mt = breaker.untwist(dirty_mt)
clean_state_tuple = (3, tuple(dirty_mt + [624]), None)
recovered_seeds = breaker.recover_all_integer_seeds_from_state(clean_state_tuple, 128)
print(f"破解结果: {recovered_seeds}")
few_outputs恢复seed
因为位数之间存在线性关系，所以并不一定要有19968bit
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
def crackme(outputs):
breaker = python_random_breaker()
bit_len = 128
is_exact = 1
indices = [i for i in
breaker.get_required_output_indices_for_integer_seed_recovery(bit_len,
is_exact)]
cur_outputs = [outputs[i] for i in indices]
# print(cur_outputs)
return (breaker.recover_all_integer_seeds_from_few_outputs(bit_len,cur_outputs, True))
if __name__ == "__main__":
seed = random.getrandbits(128)
rng = random.Random(seed)
outputs = [rng.getrandbits(32) for i in range(240)]
print(outputs)
print(seed)
print(crackme(outputs))
MT19937线性关系
MT19937中距离(1，397，624)的生成数存在线性关系，例如：mt[1]， mt[397]，mt[624]
求mask
from sage.all import *
from random import getrandbits
# 初始化有限域 GF(2)
F = GF(2)
m = []
print("[+] Collecting data to find linear dependencies...")
# 1. 采集数据
for _ in range(256):
# 模拟生成随机数流
x = [getrandbits(21) for _ in range(1337)]
# 提取 MT19937 关键位置的数：idx 1, 397, 624
# 将它们拼接成二进制字符串
a = "".join(map("{:021b}".format, [x[1], x[397], x[624]]))
# 转换为 GF(2) 向量并存入列表
m.append(list(map(F, a)))
# 2. 构建矩阵并计算右核 (Right Kernel)
m = matrix(F, m)
ker = m.right_kernel_matrix()
print(f"[+] Kernel dimensions: {ker.dimensions()}")
# 验证计算出的核是否正确
for row in ker:
assert all(row * k == 0 for k in m)
# 3. 提取并转换 Masks
# 将 GF(2) 向量转回整数形式
masks = sorted([int("".join(map(str, row)), 2) for row in ker])
print("\n[+] FOUND MASKS (Copy these to your Python script):")
print(f"masks = {masks}")
# 4. 再次验证 (Optional)
print("\n[+] Verifying masks on new data...")
for _ in range(100):
x = [getrandbits(21) for _ in range(1337)]
# 拼接校验位
u = (x[1] << 42) | (x[397] << 21) | x[624]
for mk in masks:
# 验证点积是否为 0 (偶数个1)
assert bin(u & mk).count('1') & 1 == 0
print("[+] Verification successful.")
我们可以通过这个性质来做Decision，判断是不是MT19937生成的数
例题：
for tests in range(1024):
is_mt_source = (tests % 2 == 0)
if is_mt_source:
a = [randrange(q) for i in range(2062)]
else:
a = [randbelow(q) for i in range(2062)]
注意：MT的randrange(q)，会遇到拒绝采样
例如：
，而 ，接受率
所以只需要在这两处一定范围内爆破，就能找到真正的mt[1]， mt[397]，mt[624]
from random import randrange
from secrets import randbelow
from math import ceil, floor
# 题目给定的模数
q = 1342261
# Mask 指纹 (来自 SageMath)
masks = [673178275939392, 4646537255715348, 9084442103645188,
36451018107523088, 144115772462219393, 576461989258788866,
1153168072270545936, 2305913927730724872, 4902405758213194009]
# --- 【新增配置】 设定分界线 ---
THRESHOLD = 450000
# 用于存储得分
c = [[] for _ in range(2)]
# 用于统计正确率
correct_predictions = 0
total_rounds = 1024
print(f"[+] Starting {total_rounds} rounds of distinguishing tests...")
print(f" Target Modulus: {q}")
print(f" Decision Threshold: {THRESHOLD}")
for tests in range(total_rounds):
# --- 1. 黑盒数据生成 ---
# 偶数轮 (tests % 2 == 0): MT19937 (Target)
# 奇数轮 (tests % 2 == 1): Secure Random (Reference)
is_mt_source = (tests % 2 == 0)
if is_mt_source:
a = [randrange(q) for i in range(2062)]
else:
a = [randbelow(q) for i in range(2062)]
# --- 2. 核心评分逻辑 ---
count = 0
for i in range(1600):
# 1. 计算 m1
m1 = sum([(((a[i] << 42) & m).bit_count() & 1) << idx for idx, m in enumerate(masks)])
t = dict()
# 2. 搜索 m2
for j in range(-18, 19):
m2 = sum([(((a[i + 254 + j] << 21) & m).bit_count() & 1) << idx for idx, m in enumerate(masks)])
t[m1 ^ m2] = j
# 3. 搜索 m3 并打分
for k in range(-24, 25):
m3 = sum([((a[i + 400 + k] & m).bit_count() & 1) << idx for idx, m in enumerate(masks)])
if m3 in t:
# 命中特征！
count += 100 - abs(t[m3]) - abs(k)
# --- 3. 判定与统计 ---
# 判定逻辑：分数高判定为 MT，分数低判定为 Secure
predicted_is_mt = (count > THRESHOLD)
# 检查预测是否正确
if predicted_is_mt == is_mt_source:
correct_predictions += 1
# 记录分数用于分布展示
c[tests & 1].append(count)
c[0] = sorted(c[0])
c[1] = sorted(c[1])
# --- 4. 实时输出 ---
if (tests + 1) % 100 == 0:
current_acc = (correct_predictions / (tests + 1)) * 100
print(f"\n--- Round {tests + 1} / {total_rounds} ---")
print(f"Current Accuracy: {current_acc:.2f}% (Threshold: {THRESHOLD})")
# 打印分数分布，方便你微调 Threshold
if len(c[1]) > 0:
print("Secure Scores (Max 5):", c[1][-5:]) # 看看真随机最高得几分
if len(c[0]) > 0:
print("MT Scores (Min 5): ", c[0][:5]) # 看看MT最低得几分
# --- 最终结果 ---
final_acc = (correct_predictions / total_rounds) * 100
print(f"\n[+] Test Finished.")
print(f"[+] Final Accuracy: {final_acc:.2f}%")
print(f" Correctly Classified: {correct_predictions}/{total_rounds}")
# 最终验证分界线是否合理
max_secure = c[1][-1] if c[1] else 0
min_mt = c[0][0] if c[0] else 0
print(f"\n[Analysis]")
print(f"Max Secure Score: {max_secure}")
print(f"Min MT Score: {min_mt}")
if max_secure < THRESHOLD < min_mt:
print(f"Result: The threshold {THRESHOLD} is PERFECT (Separates classes completely).")
else:
print(f"Result: The threshold {THRESHOLD} might have errors. Suggestion: Set it between {max_secure} and {min_mt}.")
不能保证每次正确率都是百分之百，但是大体没错，做题的时候应该不会卡太死，count和THRESHOLD很接近的可以舍去