Mersenne Twister

文章复盘了 KalmarCTF 2026 两道高难密码学题。第一题利用 SageMath 在扩域上生成随机矩阵时对 Mersenne Twister 的调用方式，结合拒绝采样与 MT 内部递推关系，构造仅依赖偶数偏移输出的三元关系，逐步恢复 PRNG 状态。第二题基于短位数 RSA 模数与 LCG 更新指数，先因式分解模数，再按分支将高次稀疏指数方程转化为低度代数系统，借助 LLL 寻找指数模 p-1 的短关系，并用结果式消元得到关于明文的单变量多项式，从而恢复消息。