文章总结： 本文分析了2025年RCTF比赛中yetanotherMTgame密码学题目的解题思路，详细剖析了SageMath中MersenneTwister随机数生成器的实现机制。作者通过构造特定参数矩阵最大化随机数最低有效位泄露，建立GF(2)线性模型，并最终使用Coppersmith小根攻击恢复原始种子。文章提供了完整的攻击流程和数学推导，展示了如何利用随机数生成器的实现漏洞进行攻击。
综合评分： 85
文章分类： CTF,漏洞分析,密码学,安全工具,技术标准
2025 RCTF writeup by Arr3stY0u
原创
CTF组
山海之关
📢 战队招新
🎯 基础条件
- 良好的人品与学习态度
- 赛龄一年以上
⚡ 简历格式
- 放置个人博客或github地址（如果有）
- 需包含个人信息、教育经历、比赛经历、个人技能
- 比赛经验需标明个人产出占比不要只写奖项
- 个人技能需标明掌握的具体技术，trick
📮 简历投递
（如未回复可加qq2944508194）
Crypto
yet another MT game
> I think SageMath copies everything from Python, right? 🤔
FROM sagemath/sagemath:10.7
nc 1.14.196.78 42101
题目附件：
题目概览与目标
服务端核心逻辑简化后如下：
secret = os.urandom(64)
set_random_seed(int.from_bytes(secret, 'big'))
mod, nrow, ncol = map(int, input().split())
nbits = (mod - 1).bit_length()
if nbits * nrow * ncol > 19937: exit()
outs = random_matrix(Zmod(mod), nrow, ncol).list()
print("🤖 Machine output:", outs)
guess = bytes.fromhex(input("🤔 secret (hex): ").strip())
if guess == secret:
print(f"🎉 Correct! Here is your flag: {FLAG}")
首先从 Sage 10.7 源码确认随机数流。
set_random_seed 的实现（sage/misc/randstate.pyx）：
cpdef set_random_seed(seed=None):
global _current_randstate
_current_randstate = randstate(seed)
randstate.__init__ 中调用 gmp_randseed：
if seed:
mpz_init(mpz_seed)
mpz_set_pylong(mpz_seed, seed)
gmp_randseed(self.gmp_state, mpz_seed)
mpz_clear(mpz_seed)
而 gmp_randseed 在 GMP 中最终走到 randseed_mt（gmp-src/rand/randmts.c），核心数学过程如下：
-
设
-
将用户 seed（此处为
int.from_bytes(secret,'big')）缩放到 ：注意本题中 ，所以其实就是 。
-
再做一次幂模映射：
-
将 的 位填入 MT 状态：
-
第 位（bit ）作为
mt[0]的最高位 bit31，其余 31 位为 0； -
剩余 位按 32 位小端拆成
mt[1..623]。 -
预热（warm-up）：
-
常量
WARM_UP = 2000； -
调用
__gmp_mt_recalc_buffer（相当于 twist） 次； -
设
mti = WARM_UP % 624 = 128。
之后所有 c_random() 都通过 __gmp_randget_mt 从这颗 GMP Mersenne Twister 中输出随机数：
- 先按 MT19937 标准方式 twist + temper（32 位）；
- 然后
gmp_urandomb_ui(self.gmp_state, 31)取其低 31 位，作为 31 比特随机整数返回。
random_matrix(Zmod(mod), ...) 最终会走到 matrix_modn_dense_template.pxi 中的 randomize：
cdef randstate rstate = current_randstate()
cdef int p = <int>self.p # p = mod
if not nonzero:
if density == 1:
for i from 0 <= i < self._nrows*self._ncols:
self._entries[i] = rstate.c_random() % p
因此，每个矩阵元素都是
其中 c_random() 是上述 GMP MT19937 的 temper 后输出的低 31 位。
关键观察：
-
选取 时，有
也就是 temper 后 32 位输出的最低有效位（LSB）。
-
如果我们让矩阵的元素个数为 ，则可以在一次交互中，完整观察到 warm-up 后 MT 的连续 个 LSB。
这就是后续攻击的核心信息源。
构造最大化 LSB 泄露
根据题目限制：
令：
- ；
- 。
则：
刚好卡在上限，泄露了尽可能多的随机性。
GF(2) 线性建模
MT 的内部状态与输出之间是 线性 的（在 上）：
- twist 本质上是线性递推；
- temper 由移位与按位与/异或构成；
- 取 LSB 是取最低一位。
同时，randseed_mt 中 seed2 -> mt[0..623] 的映射也是线性的：
- 记 ，；
- 则
因此，可以直接把 个比特的 当作 上的变量，写出：
- 为 的 bit 变量；
- 为观测到的 LSB 序列；
- 是由 “
seed2 -> mt[] -> twist/temper -> LSB” 组成的线性变换矩阵。
非线性部分
已知 seed2 后则是非线性部分，回顾播种部分
- ，视作整数 ；
- ，但 ，所以 ，且 ；
- 。
我们已知 和 ，希望恢复 和 。
设 ，计算
在 Sage 中实际计算得到：
MOD2 = (ZZ(1) << 19937) - 20023
E = ZZ(0x40118124)
phi = MOD2 - 1
g = gcd(E, phi) # 12
E1 = E // g
phi1 = phi // g
D1 = E1.inverse_mod(phi1)
可以推得：
因此我们要解的方程是：
这完全符合 Coppersmith 小根攻击的条件：
- 模数 ；
- 多项式次数 ；
- 种子上界 ，远小于
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：山海之关 CTF组《2025 RCTF writeup by Arr3stY0u》