1. 2026DesCTF密码学赛题解析从ECDSA到MT19937的实战复盘上周参加了2026DesCTF的密码学赛道遇到几道有意思的题目尤其是涉及ECDSA签名和MT19937伪随机数生成的题型。这类题目在近年CTF比赛中出现频率越来越高但网上完整的解题思路分享却不多。今天就把我的解题过程整理成笔记重点分析两个典型场景ECDSA签名伪造和基于MT19937的随机数预测。提示本文涉及密码学实战技巧需要基础数论知识和Python编程能力。所有代码示例均使用Python3实现。1.1 题目背景与核心考点比赛给出的题目包包含两个关键文件ecdsa_challenge.py实现了一个自定义的ECDSA签名服务mt19937_rng.py使用MT19937算法生成随机数的加密服务通过分析题目描述和源码可以明确两个核心考点ECDSA签名过程中随机数重用导致的私钥泄露MT19937伪随机数生成器的状态破解与预测2. ECDSA签名漏洞分析与利用2.1 ECDSA签名原理回顾标准的ECDSA签名流程如下以secp256k1曲线为例from ecdsa import SigningKey, SECP256k1 import hashlib # 密钥生成 sk SigningKey.generate(curveSECP256k1) # 私钥 vk sk.verifying_key # 公钥 # 签名过程 message bcritical transaction k random.randint(1, SECP256k1.order) # 随机数k signature sk.sign(message, kk) # 使用随机数k生成签名 # 验证过程 vk.verify(signature, message) # 验证签名其中关键参数k每次签名必须独立的随机数order椭圆曲线的阶secp256k1为2²⁵⁶ - 4324203865656596568524208663949681455992.2 题目漏洞定位分析题目源码发现致命错误def sign_message(self, msg): h int.from_bytes(sha256(msg).digest(), big) k self.get_k() # 漏洞所在 r (self.G * k).x() s (inverse(k, self.order) * (h self.d * r)) % self.order return (r, s) def get_k(self): if not hasattr(self, _k): self._k randint(1, self.order - 1) # 首次调用生成k后缓存 return self._k # 后续签名复用同一个k攻击者通过收集两个不同消息的签名(r,s1)和(r,s2)可以建立方程组解出私钥ds1 (h1 d*r) / k mod n s2 (h2 d*r) / k mod n d (h1*s2 - h2*s1) / (r*(s1 - s2)) mod n2.3 完整攻击脚本实现from hashlib import sha256 from Crypto.Util.number import inverse def recover_private_key(msg1, msg2, sig1, sig2, curve_order): h1 int.from_bytes(sha256(msg1).digest(), big) h2 int.from_bytes(sha256(msg2).digest(), big) r, s1 sig1 _, s2 sig2 numerator (h1 * s2 - h2 * s1) % curve_order denominator (r * (s1 - s2)) % curve_order k (numerator * inverse(denominator, curve_order)) % curve_order d (inverse(r, curve_order) * (k * s1 - h1)) % curve_order return d注意事项实际比赛中需要处理大整数运算的边界条件Python的pow(a,b,n)比(a**b)%n更高效可靠。3. MT19937随机数预测实战3.1 MT19937算法原理MT19937Mersenne Twister是一种广泛使用的伪随机数生成算法主要特点周期长达2¹⁹⁹³⁷-1623维均匀分布通过 tempering 变换输出随机数核心漏洞只要获取连续的624个32位输出就可以完全重建内部状态。3.2 题目逆向分析题目提供了加密服务每次连接会输出20个随机数def encrypt(self, plaintext): keystream bytes([self.rng.get_random_byte() for _ in range(len(plaintext))]) return xor(plaintext, keystream)通过收集足够多的密文可以获取前624个4字节随机数约2496字节密文逆向tempering操作重建MT19937状态预测后续所有随机数3.3 状态恢复与预测实现def untemper(x): x ^ (x 18) x ^ (x 15) 0xefc60000 x ^ ((x 7) 0x9d2c5680) ^ ((x 14) 0x94284000) ^ ((x 21) 0x14200000) ^ ((x 28) 0x10000000) x ^ (x 11) ^ (x 22) return x def clone_mt(outputs): state [untemper(x) for x in outputs] cloned MT19937(0) cloned.mt state cloned.index 624 return cloned实操技巧实际网络通信中可以通过发送重复字符如NULL字节来直接获取keystream避免已知明文攻击的复杂度。4. 典型错误与调试记录4.1 ECDSA攻击常见问题签名顺序混淆确保(r,s1)对应msg1否则会导致计算错误# 正确顺序验证 assert verify(sig1, msg1, vk), Signature verification failed大整数处理Python的int类型虽支持大数但除法需要使用模逆# 错误做法 d (h1*s2 - h2*s1) / (r*(s1 - s2)) # 浮点精度丢失 # 正确做法 d (h1*s2 - h2*s1) * inverse(r*(s1-s2), n) % n4.2 MT19937实战陷阱字节序问题网络传输可能使用little-endian# 转换示例 num int.from_bytes(ciphertext[i:i4], little)状态污染某些实现会丢弃前几个输出# 安全做法多收集100个输出再开始预测 outputs outputs[100:724]tempering逆运算精度确保使用32位无符号整数x 0xFFFFFFFF # 关键掩码操作5. 防御方案与最佳实践5.1 ECDSA安全实现要点随机数生成必须使用密码学安全随机源# 安全示例 k int.from_bytes(os.urandom(32), big) % orderRFC6979标准确定性ECDSA可消除随机数风险from ecdsa.rfc6979 import generate_k k generate_k(order, sk.privkey.secret_multiplier, hashlib.sha256, msg)5.2 MT19937使用建议避免密码学用途仅适用于模拟等非安全场景# 不安全 keystream [random.getrandbits(32) for _ in range(10)] # 安全替代 keystream [secrets.randbits(32) for _ in range(10)]外部熵混合即使使用也应定期重置状态def reseed(): new_seed os.urandom(4) random.seed(int.from_bytes(new_seed, big))这次比赛中最深的体会是密码学实现就像走钢丝看似微小的设计选择如缓存随机数会导致整个系统崩塌。建议所有安全相关项目至少进行三方审计并使用标准库而非自行实现加密算法。对于MT19937这类伪随机数生成器记住它们名字中的伪字就是最大的警告。