CTF实战：LCG算法破解与逆向分析

1. LCG算法基础从伪随机到CTF实战线性同余生成器LCG是密码学中最基础的伪随机数生成算法之一它的核心原理可以用一个简单的公式表示Xₙ₊₁ (aXₙ b) mod m。我第一次接触这个算法时被它的简洁性震惊了——仅用一次乘法和一次加法就能产生看似随机的数列。但正是这种简单性让它成为CTF竞赛中常见的考点。举个生活中的例子假设你家的门牌号是1234初始种子物业规定每次更新门牌号要遵循先乘2再加3最后取后三位的规则a2, b3, m1000。那么下一个门牌号就是(2×12343)%1000471。这种可预测的随机正是破解的关键。在CTF比赛中LCG题目通常会给出部分输出序列或参数要求我们反推出初始种子或flag。常见的有六种题型已知全部参数求后续状态LCG-1通过最终状态反推初始种子LCG-2根据中间状态求增量bLCG-3通过输出序列恢复模数mLCG-4完全未知参数时的全恢复LCG-5高位泄露的特殊情况LCG-62. 核心破解公式与数学原理2.1 逆向推导基本公式破解LCG的核心在于这四个黄金公式我通过多次实战总结出了它们的典型应用场景状态回推公式Xn (a⁻¹(Xn1 - b)) mod m这个公式就像时间倒流已知当前状态可以推算前一个状态。在Python中实现模逆运算需要用到扩展欧几里得算法def modinv(a, m): g, x, y extended_gcd(a, m) return x % m if g 1 else None乘数求解公式a ((Xn2 - Xn1)(Xn1 - Xn)⁻¹) mod m这个公式我在2023年某次比赛中用过只需要连续三个输出值就能破解乘数。增量求解公式b (Xn1 - aXn) mod m知道a之后用这个公式求b就像做小学数学题一样简单。模数求解公式m gcd(tn1tn-1 - tn², tn tn-2 - tn-1²)其中tn Xn1 - Xn。这个公式最神奇通过数列差值就能找到模数。2.2 数学原理深度解析这些公式背后的数学原理其实很优美。以模数求解为例由于tn ≡ a tn-1 (mod m)所以tn1tn-1 ≡ a²tn-1² ≡ tn² (mod m)。这意味着(tn1tn-1 - tn²)必定是m的倍数。通过计算多个这样的差值求最大公约数就能准确找到m。我在实际解题中发现当数据量较大时可以先计算多个可能的m值然后取它们的最大公约数来提高准确性。例如在LCG-5题型中我通常会计算7-8组数据再确定最终的m。3. CTF实战题型详解3.1 已知全部参数的简单破解LCG-1题型这是最简单的题型给出初始种子和所有参数要求恢复flag。就像原始文章中的第一个例子seed 33477128523140105764301644224721378964069 a 216636540518719887613942270143367229109002078444183475587474655399326769391 b 186914533399403414430047931765983818420963789311681346652500920904075344361 n 155908129777160236018105193822448288416284495517789603884888599242193844951 c 209481865531297761516458182436122824479565806914713408748457524641378381493解题思路就像搭积木用给定参数运行LCG算法10次得到最终seed利用异或性质plaintext seed ^ ciphertext转换长整型为字节即可得flagfor i in range(10): seed (a*seed b) % n plaintext seed ^ c print(long_to_bytes(plaintext))3.2 状态逆向推导LCG-2题型这种题型给出最终状态而非初始状态就像把LCG算法倒着播放。原始文章中的第二个例子a 59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969 b 32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137 n 43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467 c 8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276破解步骤计算a的模逆元ani逆向迭代公式seed (ani * (seed - b)) % n初始seed就是flagMMI lambda A, n,s1,t0,N0: (n 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n1] ani MMI(a, n) seed c for i in range(10): seed (ani * (seed - b)) % n print(long_to_bytes(seed))4. 高级破解技巧与实战经验4.1 从输出序列恢复参数LCG-4题型这是比较复杂的题型只给出输出序列和模数n。我在某次比赛中遇到过类似题目当时的解决过程是这样的output [683884150..., 285126221..., ...] # 10个输出值 n 714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819解题步骤用前三个输出计算a (output[2]-output[1])*MMI(output[1]-output[0], n) % n用a和第一个输出求b (output[1] - a*output[0]) % n逆向推导初始seed (a⁻¹(output[0] - b)) % ndef modinv(a, m): return pow(a, -1, m) a (output[2]-output[1]) * modinv(output[1]-output[0], n) % n b (output[1] - a*output[0]) % n seed (modinv(a,n) * (output[0] - b)) % n4.2 完全未知参数的全恢复LCG-5题型最复杂的情况是只有输出序列所有参数都未知。这时候就需要用到前面提到的模数求解公式s [999729798627..., 494309297248..., ...] # 10个输出值 t [s[i]-s[i-1] for i in range(1, len(s))] all_n [] for i in range(1, len(t)-2): all_n.append(gcd(t[i1]*t[i-1] - t[i]*t[i], t[i2]*t[i] - t[i1]*t[i1])) n max(set(all_n), keyall_n.count) # 取出现次数最多的n这个解法非常巧妙通过数列差值的数学性质找出模数m。我在实际使用中发现有时候会有干扰项所以取出现频率最高的那个值更可靠。5. 特殊题型与优化技巧5.1 高位泄露问题LCG-6题型有些题目会只输出随机数的高位部分就像原始文章中的第六个例子output [16985619148410545083429542035273917746612, ...] # seed64的结果这类题目的解法比较复杂需要用到格基规约算法LLL算法。基本思路是建立包含高位信息的方程组构建合适的格使用LLL算法找到最短向量从最短向量中恢复低位信息由于涉及较深的数学知识建议初学者先掌握前五种基础题型再尝试这类题目。5.2 性能优化与实战技巧在实战中我总结了几条宝贵经验模逆运算缓存频繁计算模逆时可以预先计算并缓存结果多线程爆破当参数可能范围较小时可以用多线程加速爆破输入验证注意检查参数是否互质避免模逆计算失败错误处理对可能的无解情况要有处理逻辑比如当gcd≠1时from multiprocessing import Pool def brute_force(args): # 多线程爆破示例 pass with Pool(4) as p: results p.map(brute_force, params_list)6. 防御措施与替代方案虽然LCG算法容易破解但在CTF比赛中仍然常见。对于开发者来说如果需要使用伪随机数生成器建议使用更安全的算法如MT19937虽然也有弱点结合哈希函数增加复杂度使用系统提供的加密安全随机数生成器如/dev/urandom避免直接暴露连续随机数输出在CTF比赛中遇到LCG题目时首先要判断属于哪种题型然后选择合适的破解公式。我通常的解题流程是分析题目给出的信息确定缺失的参数选择对应的破解公式编写脚本实现破解验证结果的合理性记住LCG算法的安全性完全依赖于参数的保密性。一旦输出序列部分泄露整个系统就可能被攻破。这让我想起去年参加的一场CTF比赛当时花了3个小时才意识到题目是LCG-4变种但一旦找到正确思路解决问题只用了10分钟。这种从困惑到顿悟的过程正是CTF比赛的魅力所在。