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签名：

1. 计算消息的哈希值：e = hash(m)。通常使用SHA-1或SHA-256，结果转换为一个大整数。
2. 生成一个临时随机数k，其取值范围是[1, n-1]。这个k必须每次签名都不同且不可预测，这是安全性的核心！
3. 计算椭圆曲线点：(x1, y1) = k * G。
4. 计算r = x1 mod n。如果r为0，则返回第2步重选k。
5. 计算s = k^(-1) * (e + d * r) mod n。其中k^(-1)是k在模n下的乘法逆元。如果s为0，也返回第2步。
6. 得到的签名就是一对值(r, s)。

签名验证过程（Verify）： 收到消息m和签名(r, s)后：

1. 验证r和s是否都在[1, n-1]范围内。
2. 计算e = hash(m)。
3. 计算w = s^(-1) mod n。
4. 计算u1 = e * w mod n和u2 = r * w mod n。
5. 计算椭圆曲线点(x1, y1) = u1 * G + u2 * Q。
6. 验证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值也完全相同。

现在我们有了两个方程：

1. s1 = k^(-1) * (e1 + d * r) mod n
2. s2 = 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. 实战环境搭建与信息收集

理论清晰了，我们开始实战。首先需要一个模拟环境来练习。这道题通常以“交互式解题”形式出现，你需要连接到一个远程的nc（Netcat）服务。

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. 理解交互接口：服务通常会有一个菜单，比如：

   1. 获取签名 2. 验证并执行命令 3. 退出

   你需要搞清楚每个选项的输入输出格式。例如，选择“获取签名”后，是让你输入一个字符串，然后它返回r和s吗？返回的格式是十进制、十六进制还是Base64？

2. 获取公开参数：ECDSA需要公开曲线参数。有时题目会直接给出（比如在源码注释或描述里），有时需要你通过某种方式获取。关键参数包括：曲线方程（通常给出a,b,p）、基点G的坐标(Gx, Gy)、曲线的阶n。没有这些，你无法进行任何计算。如果没直接给出，可以尝试在“获取签名”时发送特定消息（如空消息或已知消息），观察签名输出是否有规律，或者服务端是否有信息泄露接口。

3. 确认哈希算法：ECDSA使用什么哈希函数？通常是SHA-1或SHA-256。这需要从题目描述或尝试中得知。你可以发送一个已知字符串，获取签名，然后本地用不同哈希算法计算e，结合你猜测的曲线参数，看是否能通过验证流程（但这通常需要公钥，而公钥可能未知）。更直接的方法是查看题目附件源码（如果有）。

4. 测试漏洞是否存在：这是关键一步。连续两次选择“获取签名”，对两个不同的消息（比如"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 = b"get_flag1" m2 = b"get_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 = b"cat /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 问题排查清单

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, curve=SECP256k1, hashfunc=hashlib.sha256) # 对目标消息签名 message = b"cat /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(f"r: {hex(r)}, s: {hex(s)}")

6.3 进阶漏洞：随机数k的偏置或部分泄露

如果题目不是简单的k重用，而是k在某些比特位上存在偏差或泄露，攻击会变得复杂，但核心思想不变：利用签名方程中线性关系的不确定性减少。例如，如果知道k的高位或低位，可以将问题转化为一个格（Lattice）上的最近向量问题（CVP），使用LLL算法来求解私钥d。这类题目通常会在CTF中作为更难的密码学挑战出现。解决它们需要更深入的数论和格理论知识，以及熟练使用SageMath等数学工具。

回过头看这道题，它像是一个精致的教学案例，清晰地展示了密码学中“随机性”的重要性。一个看似微小的实现失误——随机数生成器的失败——导致整个签名体系崩塌。在真实的CTF竞赛和网络安全评估中，这种对标准协议实现细节的审视能力至关重要。它提醒我们，不是所有漏洞都藏在复杂的逻辑深处，有时它们就明明白白地躺在那些最基本的、被认为理所当然的步骤里。