CTF实战：ECDSA随机数重用漏洞分析与私钥破解

1. 项目概述一次典型的CTF密码学实战复盘最近在复盘一场线上CTF比赛的题目其中一道涉及ECDSA椭圆曲线数字签名算法的密码学题目让我印象挺深。这道题目的典型之处在于它没有直接给你一个复杂的加密系统让你去黑盒破解而是巧妙地利用了一个在实际密码学实现中非常经典、但在CTF中又高频出现的漏洞ECDSA签名过程中的随机数重用。最终这个漏洞成为了我们拿到服务器上那个宝贵flag文件的关键跳板。很多刚接触CTF密码学的朋友一看到椭圆曲线、模运算、签名验证这些词可能就有点发怵觉得门槛太高。其实不然这类题目的核心往往不是让你从头推导数学公式而是考验你对算法流程的理解以及能否敏锐地发现实现上的“瑕疵”。今天我就以这道题为蓝本把从分析到利用的完整过程拆解一遍你会看到整个过程更像是在解一个逻辑严密的数学谜题而不是在搞高深莫测的密码学研究。简单来说这道题给了我们一个在线的签名服务。我们可以提交任意消息服务器会用它的私钥我们不知道进行ECDSA签名然后把签名的两个组成部分(r, s)返回给我们。同时服务器还提供了一个“验证并执行”的功能如果我们能提供一个消息及其有效的ECDSA签名服务器就会验证签名如果验证通过就会执行该消息在我们的场景里消息就是一条系统命令并将执行结果返回。我们的目标很明确就是构造一条能读取flag文件的命令比如cat /flag或/readflag并为其生成一个合法的签名从而欺骗服务器执行它。而突破口就藏在那看似随机、实则可能被预测或重用的签名参数里。2. ECDSA算法原理与漏洞根源深度拆解在动手之前我们必须先搞清楚ECDSA到底是怎么工作的以及漏洞究竟出在哪。如果你对算法细节已经熟悉可以快速浏览如果想彻底理解漏洞利用的原理这部分是基石。2.1 ECDSA签名与验证的标准流程ECDSA基于椭圆曲线密码学。我们不需要深入椭圆曲线的数学细节只需要关注签名生成和验证的算法流程这更像一个“配方”。首先系统会公开一些参数一条椭圆曲线及其上的一个生成点G基点。曲线的阶n这是一个很大的素数。私钥和签名过程中的随机数都在模n的整数域里操作。公钥Q。这是由私钥d一个随机选择的介于1和n-1之间的整数通过椭圆曲线点乘计算得出的Q d * G。Q是公开的d是严格保密的私钥。签名生成过程Sign 假设要对消息m签名计算消息的哈希值e hash(m)。通常使用SHA-1或SHA-256结果转换为一个大整数。生成一个临时随机数k其取值范围是[1, n-1]。这个k必须每次签名都不同且不可预测这是安全性的核心计算椭圆曲线点(x1, y1) k * G。计算r x1 mod n。如果r为0则返回第2步重选k。计算s k^(-1) * (e d * r) mod n。其中k^(-1)是k在模n下的乘法逆元。如果s为0也返回第2步。得到的签名就是一对值(r, s)。签名验证过程Verify 收到消息m和签名(r, s)后验证r和s是否都在[1, n-1]范围内。计算e hash(m)。计算w s^(-1) mod n。计算u1 e * w mod n和u2 r * w mod n。计算椭圆曲线点(x1, y1) u1 * G u2 * Q。验证x1 mod n r。如果相等则签名有效。验证过程的正确性源于椭圆曲线点乘的运算律本质上是通过公钥Q和签名值(r,s)反向推导出签名时使用的那个临时点(x1, y1)的x坐标看是否与签名中的r一致。2.2 致命漏洞随机数k的重用算法的安全性严重依赖于第2步中的随机数k。如果k被重复使用了两次用来签署两个不同的消息m1和m2那么灾难就发生了。假设两次签名使用了相同的k那么第一次签名s1 k^(-1) * (e1 d * r) mod n第二次签名s2 k^(-1) * (e2 d * r) mod n注意因为k相同第一步计算出的点(x1, y1)相同所以产生的r值也完全相同。现在我们有了两个方程s1 k^(-1) * (e1 d * r) mod ns2 k^(-1) * (e2 d * r) mod n其中e1,e2,r,s1,s2都是我们已知的从服务器获取未知数是k和私钥d。我们可以用这两个方程来消去d直接解出k将两个方程相减在模n下s1 - s2 k^(-1) * (e1 - e2) mod n因此k (e1 - e2) * (s1 - s2)^(-1) mod n一旦我们算出了k私钥d就唾手可得。从第一个方程变形d (s1 * k - e1) * r^(-1) mod n这就是整个攻击的数学核心。服务器在为我们签名不同消息时如果错误地重用了同一个随机数k我们就能通过收集两组签名数据完全破解出它的私钥。有了私钥我们就能为任何我们想要的消息比如cat /flag生成合法的签名从而通过服务器的验证。注意在实际CTF题目中k的重用可能以更隐蔽的形式出现。例如k可能由一个伪随机数生成器PRNG生成且种子可预测或者k是由一个秘密值如私钥d和消息哈希e通过某种确定性函数如k hash(d || e)派生而来这同样会导致对同一消息签名时k恒定对不同消息签名时k虽不同但存在确定关系也可能被利用。这道题属于最经典的“完全重用”情况。3. 实战环境搭建与信息收集理论清晰了我们开始实战。首先需要一个模拟环境来练习。这道题通常以“交互式解题”形式出现你需要连接到一个远程的ncNetcat服务。3.1 本地模拟环境搭建用于练习在真正攻击远程服务器前强烈建议在本地用Python模拟一个存在漏洞的签名服务。这能让你反复测试攻击脚本加深理解。#!/usr/bin/env python3 # vulnerable_ecdsa_server.py from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse import hashlib import random # 使用一个简单的椭圆曲线参数secp256k1的简化版仅用于演示 # 实际题目会给出具体参数 P 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F N 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 Gx 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 A 0 B 7 # 椭圆曲线点运算函数简化版实际需完整实现 def point_add(p1, p2): # 实现椭圆曲线点加 pass def point_mul(k, point): # 实现椭圆曲线标量乘法 pass # 服务器持有的私钥 (d) secret_d random.randint(1, N-1) # 漏洞所在固定的k在实际安全实现中k必须是随机的。 vulnerable_k 123456789 # 这是一个故意设置的漏洞 def sign_message(message): e bytes_to_long(hashlib.sha256(message).digest()) # 错误的重用k k vulnerable_k # 计算 k*G (x1, y1) x1, y1 point_mul(k, (Gx, Gy)) r x1 % N if r 0: return None kinv inverse(k, N) s (kinv * (e secret_d * r)) % N if s 0: return None return (r, s) def verify_signature(message, r, s): # 验证签名此处省略具体实现与标准流程一致 pass # 模拟服务器交互 print([模拟服务器] 私钥d已生成保密) print([模拟服务器] 你可以发送消息让我签名输入‘quit’退出) while True: msg_input input( ).strip() if msg_input.lower() quit: break sig sign_message(msg_input.encode()) if sig: print(f签名 (r, s): {sig[0]}, {sig[1]}) else: print(签名失败)运行这个脚本你就有了一个本地靶场。它每次签名都使用同一个k完美复现了漏洞条件。3.2 针对远程服务的初步侦察连接上真正的CTF服务器后通常用nc ip port第一件事不是盲目攻击而是进行信息收集理解交互接口服务通常会有一个菜单比如1. 获取签名 2. 验证并执行命令 3. 退出你需要搞清楚每个选项的输入输出格式。例如选择“获取签名”后是让你输入一个字符串然后它返回r和s吗返回的格式是十进制、十六进制还是Base64获取公开参数ECDSA需要公开曲线参数。有时题目会直接给出比如在源码注释或描述里有时需要你通过某种方式获取。关键参数包括曲线方程通常给出a,b,p、基点G的坐标(Gx, Gy)、曲线的阶n。没有这些你无法进行任何计算。如果没直接给出可以尝试在“获取签名”时发送特定消息如空消息或已知消息观察签名输出是否有规律或者服务端是否有信息泄露接口。确认哈希算法ECDSA使用什么哈希函数通常是SHA-1或SHA-256。这需要从题目描述或尝试中得知。你可以发送一个已知字符串获取签名然后本地用不同哈希算法计算e结合你猜测的曲线参数看是否能通过验证流程但这通常需要公钥而公钥可能未知。更直接的方法是查看题目附件源码如果有。测试漏洞是否存在这是关键一步。连续两次选择“获取签名”对两个不同的消息比如hello和world获取签名。记录下返回的(r1, s1)和(r2, s2)。然后检查r1和r2是否相等。如果相等那么有极大概率k被重用了因为根据算法只要k相同计算出的r就必然相同r是椭圆曲线点k*G的x坐标模n。如果r不同则可能k是随机的或者你需要寻找其他类型的漏洞如k的部分泄露、基于格攻击的侧信道等。在我的实战中服务器对前两次不同消息的请求返回了相同的r值。这基本坐实了“随机数重用”漏洞我们可以进入下一步的攻击计算。4. 攻击实施从数据收集到私钥推导确认漏洞存在后攻击流程就变得非常标准化但每一步的计算都需要小心。4.1 收集必要的签名数据我们需要两组签名数据对应两个不同的消息。消息内容可以任意选择但为了计算方便最好选择简单的ASCII字符串比如get_flag1和get_flag2。确保你准确记录了消息原文m1,m2对应的签名(r1, s1),(r2, s2)在收集时务必注意服务器返回的数据格式并将其正确转换为Python中的大整数int类型。例如如果服务器返回十六进制字符串0xabc...就用int(r_str, 16)转换。4.2 执行关键计算破解k和d有了数据我们就可以套用第2.2节推导出的公式进行计算。这里我用Python演示整个过程假设我们已经从服务器拿到了以下数据使用虚构的但符合逻辑的数值import hashlib from Crypto.Util.number import bytes_to_long, inverse # 假设的公开参数 (题目会给出真实值) n 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # secp256k1的阶 # 从服务器收集的数据 m1 bget_flag1 m2 bget_flag2 # 假设服务器返回的签名 (r相同证实k重用) r 0x4c7e7c5d6c5a4d3b2a1f0e1d2c3b4a5968778695a4b3c2d1e0f1a2b3c4d5e6f7 s1 0x8a1b2c3d4e5f6a7b8c9d0e1f2a3b4c5d6e7f8a9b0c1d2e3f4a5b6c7d8e9f0a1 s2 0x1f2e3d4c5b6a7988a9b0c1d2e3f4a5b6c7d8e9f0a1b2c3d4e5f6a7b8c9d0e1f # 步骤1计算消息的哈希值e (假设使用SHA-256) hash_func hashlib.sha256 e1 bytes_to_long(hash_func(m1).digest()) e2 bytes_to_long(hash_func(m2).digest()) # 步骤2计算k (e1 - e2) / (s1 - s2) mod n # 注意在模运算中“除法”是乘以模逆元 delta_s (s1 - s2) % n # 必须检查delta_s是否有模逆元即与n互质在这么大的n下随机值几乎总是互质的。 try: delta_s_inv inverse(delta_s, n) except ValueError: print(s1 - s2 与 n 不互质攻击失败。可能需要收集更多签名。) exit() delta_e (e1 - e2) % n k (delta_e * delta_s_inv) % n print(f[] 计算出的临时随机数 k {hex(k)}) # 步骤3计算私钥 d (s1 * k - e1) / r mod n # 同样计算 r 在模 n 下的逆元 try: r_inv inverse(r, n) except ValueError: print(r 与 n 不互质极其罕见可能需要重新获取签名。) exit() d ((s1 * k - e1) % n * r_inv) % n print(f[!!!] 破解出的私钥 d {hex(d)})运行这段代码如果一切顺利你就会得到服务器的私钥d。这是整个攻击中最激动人心的时刻。实操心得在实际计算中务必使用大整数运算库如Python的int类型天然支持并处理好模运算。inverse(a, n)函数用于计算a在模n下的乘法逆元即找到x使得(a * x) % n 1。如果a和n不互质即最大公约数不为1则逆元不存在函数会报错。在如此大的素数n面前s1-s2或r与n不互质的概率微乎其微但如果真的遇到只需换用另一组签名数据即可。5. 伪造签名与Flag夺取拿到私钥d我们就拥有了和服务器完全相同的签名能力。现在我们的目标是伪造一条能读取flag的命令的签名。5.1 构造目标消息并生成签名假设服务器验证通过后会执行我们签名的消息内容作为命令。我们需要构造这样的消息。通常flag文件可能位于/flag、./flag、/home/ctf/flag等位置命令可能是cat、more、head等。有时需要调用一个特定的二进制文件如/readflag。这需要一些猜测或信息搜集比如通过报错信息。假设目标命令是cat /flag。target_msg bcat /flag # 计算目标消息的哈希 e_target bytes_to_long(hash_func(target_msg).digest()) # 现在我们作为“合法”的签名者使用私钥d和一个新生成的随机数k_new来签名 # 注意这次我们生成的k_new必须是真正随机且安全的否则我们自己的签名也会有风险。 import random k_new random.randint(1, n-1) # 使用安全的随机源 # 计算签名 (r_new, s_new) # 重复标准签名流程 # 假设我们有椭圆曲线点乘函数 point_mul 和点的x坐标提取函数 get_x # (x1_new, y1_new) point_mul(k_new, G) # r_new x1_new % n # 这里为了示例我们假设已经计算出了 r_new r_new 0x9a8b7c6d5e4f3a2b1c0d9e8f7a6b5c4d3e2f1a0b9c8d7e6f5a4b3c2d1e0f9a8b kinv_new inverse(k_new, n) s_new (kinv_new * (e_target d * r_new)) % n print(f[] 为目标消息生成的伪造签名:) print(f r {hex(r_new)}) print(f s {hex(s_new)})现在我们得到了针对消息cat /flag的合法签名(r_new, s_new)。5.2 与服务器最终交互获取Flag最后一步将我们构造的消息target_msg和伪造的签名(r_new, s_new)提交给服务器的“验证并执行”功能。提交时需要注意服务器期望的输入格式。可能是直接拼接cat /flag|{r}|{s}JSON格式{cmd: cat /flag, r: 0x..., s: 0x...}或者需要先选择功能菜单再依次输入。如果我们的计算完全正确签名将通过验证服务器将执行cat /flag命令并将flag的内容输出给我们。屏幕上出现的那一串以flag{开头、包含特殊字符的字符串就是这场智力角逐的最终奖励。6. 常见问题、调试技巧与进阶思考在实际操作中很少能一击即中。下面是一些我踩过的坑和总结的技巧。6.1 问题排查清单问题现象可能原因解决方案计算出的k或d看起来不合理如非常小或为01.r,s,e的数值转换错误如进制错误。2. 使用的曲线参数n不正确。3. 哈希函数用错。1. 打印并核对所有输入的整数确保其值巨大接近n。2. 反复检查题目给出的曲线参数特别是n。3. 确认哈希算法尝试SHA-1和SHA-256。inverse函数报错提示无逆元s1-s2或r与n不互质。这是小概率事件换用另外两组不同的消息和签名重新尝试。成功计算出d但伪造的签名验证失败1. 伪造签名时自己生成的k_new对应的r_new计算错误。2. 椭圆曲线点运算代码有bug如果是自己实现。3. 服务器对消息的预处理与你不同如添加前缀、后缀、换行符。1. 使用成熟的密码学库如ecdsaPython包来生成签名避免自己实现点运算。2. 用已知正确的(d, k)对一条测试消息签名再用公钥验证确保你的签名/验证代码正确。3. 仔细分析服务器源码如果提供或通过多次测试推断消息的完整格式。服务器返回的r值每次都不一样k可能不是简单重用而是存在其他规律或使用了确定性ECDSA。收集更多签名如3-4组观察r和s之间是否存在线性关系可能需要进行更复杂的分析或考虑是否存在k的部分比特泄露这可能需要使用格基规约LLL算法攻击。6.2 使用成熟库简化流程在实战中尤其是比赛时间紧张时不建议自己从头实现椭圆曲线运算。使用成熟的库可以极大减少错误。import ecdsa from ecdsa import SigningKey, SECP256k1 import hashlib # 假设我们已经通过攻击得到了私钥d的整数形式 private_key_int 0x你的私钥d... # 使用ecdsa库构造签名密钥对象 # 注意库需要私钥的字节形式且要指定曲线 private_key_bytes private_key_int.to_bytes(32, big) # 假设是256位曲线 sk SigningKey.from_string(private_key_bytes, curveSECP256k1, hashfunchashlib.sha256) # 对目标消息签名 message bcat /flag signature sk.sign(message) # signature是DER编码格式需要解析出r和s # 或者直接使用库的签名验证功能 vk sk.verifying_key if vk.verify(signature, message): print(签名验证成功) # 通常需要提取r,s的原始整数 # ecdsa库的signature可以解析 r, s ecdsa.util.sigdecode_string(signature, sk.curve.order) print(fr: {hex(r)}, s: {hex(s)})6.3 进阶漏洞随机数k的偏置或部分泄露如果题目不是简单的k重用而是k在某些比特位上存在偏差或泄露攻击会变得复杂但核心思想不变利用签名方程中线性关系的不确定性减少。例如如果知道k的高位或低位可以将问题转化为一个格Lattice上的最近向量问题CVP使用LLL算法来求解私钥d。这类题目通常会在CTF中作为更难的密码学挑战出现。解决它们需要更深入的数论和格理论知识以及熟练使用SageMath等数学工具。回过头看这道题它像是一个精致的教学案例清晰地展示了密码学中“随机性”的重要性。一个看似微小的实现失误——随机数生成器的失败——导致整个签名体系崩塌。在真实的CTF竞赛和网络安全评估中这种对标准协议实现细节的审视能力至关重要。它提醒我们不是所有漏洞都藏在复杂的逻辑深处有时它们就明明白白地躺在那些最基本的、被认为理所当然的步骤里。