1. 项目概述当ECDSA签名不再“安全”在CTF的密码学赛道上ECDSA椭圆曲线数字签名算法相关的题目一直是区分选手水平的一道分水岭。它不像基础的RSA那样有大量现成的攻击脚本也不像AES对称加密那样直观。ECDSA以其数学上的优雅和公认的安全性著称广泛应用于比特币、TLS等关键领域。然而正是这种“公认的安全”让许多CTFer在遇到相关题目时感到无从下手觉得它是个黑盒。实际上ECDSA的安全性严重依赖于其实现过程中的每一个细节一旦这些细节出现纰漏——比如随机数k被重复使用、泄露或者签名过程中存在侧信道泄露——整个签名体系就会土崩瓦解。这个项目就是带你亲手拆解这个“黑盒”从零开始理解ECDSA的工作原理并实战演练如何利用其常见的实现漏洞来破解签名最终拿到Flag。我会用最直白的Python代码一步步还原攻击过程让你不仅会“用”脚本更明白脚本每一行背后的数学逻辑和攻击原理。2. ECDSA核心原理与安全基石拆解在动手破解之前我们必须先搞清楚我们要攻击的对象到底是什么它的弱点可能藏在哪里。ECDSA可以看作是在椭圆曲线这个数学结构上实现的“数字签名版DSA”。它的安全性根基在于椭圆曲线离散对数问题ECDLP的困难性简单说就是从公钥Q反推出私钥d是计算上不可行的。但算法是完美的实现是人写的人就会犯错。2.1 签名与验证的数学流程假设我们有一条选定的椭圆曲线比如经典的secp256k1一个基点G其阶为n一个非常大的素数。用户持有一个私钥d一个在[1, n-1]区间内的随机整数公钥Q d * G椭圆曲线上的点乘运算。签名过程Sign对消息m计算哈希值e Hash(m)。例如使用SHA-256生成一个临时随机数k同样在[1, n-1]区间内。这个k至关重要也是绝大多数漏洞的源头。计算椭圆曲线点 (x1, y1) k * G。令 r x1 mod n。如果r0则返回第2步重选k。计算 s k^{-1} * (e d * r) mod n。如果s0也返回第2步。得到的(r, s)就是消息m的数字签名。验证过程Verify检查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。验证 r x1 mod n。若相等则签名有效。从流程看验证方只需要公钥Q、消息m和签名(r, s)完全不需要私钥d或随机数k。整个系统的安全假设是k必须是一次一密且绝对保密。2.2 常见漏洞模式分析CTF中ECDSA的题目几乎都是围绕破坏这个安全假设展开的随机数k重复使用这是最经典、最著名的漏洞。如果对两个不同的消息m1和m2签名时使用了同一个k那么攻击者可以直接解出私钥d。随机数k部分泄露或可预测如果k的某些比特位泄露例如通过侧信道攻击或者k是由一个脆弱的伪随机数生成器PRNG产生的攻击者可能利用格基规约LLL算法等数学工具恢复出私钥。签名过程中存在故障注入在计算s k^{-1} * (e d * r) mod n时如果通过某种物理手段如电压毛刺导致计算错误可能会产生无效签名分析这些错误签名有时也能泄露信息。签名参数如r, s的某些性质被利用例如s值过小、存在某种数学关系等在特定场景下可能被攻击。我们本次实战将聚焦于第一种情况——随机数k重复使用。因为它的原理最直观攻击代码最简洁非常适合作为入门ECDSA攻击的第一课。理解了它你就掌握了破解一半以上相关CTF题目的钥匙。3. 攻击场景构建与Python环境准备为了模拟一个真实的CTF漏洞场景我们假设遇到这样一个题目服务器使用了一个有缺陷的ECDSA签名库在对多条不同的消息进行签名时意外地重复使用了同一个随机数k。我们的任务是通过收集到足够多的消息签名对推导出私钥d然后伪造签名通过验证从而获取Flag。3.1 核心工具与库选择我们将使用Python进行攻击演示主要依赖ecdsa和hashlib库。ecdsa库本身是安全的我们将用它来“正确”地生成密钥、签名和验证以模拟目标系统。而我们的攻击代码则会基于数学原理从头编写不依赖任何现成的攻击函数以此加深理解。# 安装必要的库 pip install ecdsahashlib是Python标准库无需安装。我们选择secp256k1曲线进行演示因为它应用广泛比特币就用它且原理通用。3.2 模拟漏洞签名生成首先我们写一段模拟有漏洞的签名服务器代码。关键点在于我们固定一个k值并用它对多条不同的消息进行签名。import ecdsa import hashlib import random # 选择曲线 curve ecdsa.SECP256k1 n curve.order # 曲线的阶一个非常大的素数 # 生成一对正常的密钥 private_key ecdsa.SigningKey.generate(curvecurve) public_key private_key.get_verifying_key() print(f[*] 生成的公钥坐标: ({public_key.pubkey.point.x()}, {public_key.pubkey.point.y()})) # 模拟漏洞固定一个随机数k在实际漏洞中这是无意发生的 k_fixed random.randrange(1, n) # 随机选一个k但之后固定不变 print(f[*] 被重复使用的致命随机数 k {k_fixed}) # 准备两条不同的消息 messages [bHello, CTF!, bECDSA is broken if k is reused.] signatures [] for msg in messages: # 计算消息哈希 e int(hashlib.sha256(msg).hexdigest(), 16) % n # 使用固定的k进行签名模拟漏洞 # 计算 r (k * G).x mod n kG k_fixed * curve.generator r kG.x() % n # 计算 s k^{-1} * (e d * r) mod n d private_key.privkey.secret_multiplier k_inv pow(k_fixed, -1, n) # Python 3.8 支持模逆计算 s (k_inv * (e d * r)) % n signatures.append((r, s)) print(f[*] 消息: {msg.decode()}) print(f 签名 (r, s): ({r}, {s})) # 用标准库验证签名是否正确确认我们的模拟是有效的 for msg, (r, s) in zip(messages, signatures): sig ecdsa.ecdsa.Signature(r, s) if public_key.pubkey.verifies(e, sig): print(f[] 签名验证通过: {msg.decode()}) else: print(f[-] 签名验证失败!)运行这段代码我们就得到了一个关键的“战场环境”两条不同消息m1,m2它们对应的哈希e1,e2以及使用同一个k生成的两组签名(r1, s1)和(r2, s2)。注意因为k相同所以第一步计算的椭圆曲线点k*G相同因此r1 r2 r。这是我们攻击的起点。注意在实际CTF题目中你通常拿不到k的值也拿不到私钥d。你拿到的是公开的公钥Q、若干条消息及其签名(r, s)。我们的目标是从这些公开信息中推出d。4. 破解实战从重复的k到私钥d现在我们进入最核心的环节如何利用k重复使用这一漏洞从公开信息中解出私钥d。这个过程是一道漂亮的数学推导。4.1 数学推导过程我们有两条签名方程因为k相同所以r也相同s1 k^{-1} * (e1 d * r) mod ns2 k^{-1} * (e2 d * r) mod n注意这里的k^{-1}是k在模n下的乘法逆元。我们将两个方程相减在模n运算下s1 - s2 k^{-1} * (e1 d*r) - k^{-1} * (e2 d*r) mod ns1 - s2 k^{-1} * (e1 - e2) mod n看方程中的d被消掉了现在我们得到了一个只包含s1, s2, e1, e2和未知数k^{-1}的方程。我们可以解出k^{-1}进而解出kk^{-1} (s1 - s2) * (e1 - e2)^{-1} mod n因此k (e1 - e2) * (s1 - s2)^{-1} mod n一旦我们知道了k就可以将它代入任何一个原始的签名方程来解出私钥d。例如从第一个方程s1 k^{-1} * (e1 d * r) mod n两边乘以kk * s1 e1 d * r mod n所以d * r (k * s1 - e1) mod n最终d (k * s1 - e1) * r^{-1} mod n大功告成私钥d被我们推导出来了。整个攻击过程我们只需要两条使用相同k签名的消息及其哈希值。4.2 Python攻击代码实现现在我们把上面的数学公式翻译成Python代码。假设我们处于攻击者视角我们只知道公钥Q、两条消息m1, m2、以及它们的签名(r, s1)和(r, s2)注意r相同。import hashlib # 攻击者已知的信息从题目或网络流量中获取 # 公钥 Q (这里我们从模拟代码中获取公钥点实际题目可能以字节或坐标形式给出) Q public_key.pubkey.point # 两条消息 m1, m2 messages # 两个签名 (r, s1), (r, s2) (r1, s1), (r2, s2) signatures # 由于k重复使用r1 等于 r2 r r1 assert r1 r2, k未重复使用无法进行此攻击 # 1. 计算消息哈希 e1, e2 def hash_message(msg): return int(hashlib.sha256(msg).hexdigest(), 16) % n e1 hash_message(m1) e2 hash_message(m2) # 2. 计算 k (e1 - e2) / (s1 - s2) mod n # 注意模运算下的除法是乘以模逆元 s_diff_inv pow((s1 - s2) % n, -1, n) k_recovered ((e1 - e2) * s_diff_inv) % n print(f[] 恢复出的随机数 k: {k_recovered}) print(f 与真实的k是否一致 {k_recovered k_fixed}) # 3. 计算私钥 d (k * s1 - e1) / r mod n r_inv pow(r, -1, n) d_recovered ((k_recovered * s1 - e1) * r_inv) % n print(f[] 恢复出的私钥 d: {d_recovered}) print(f 与真实的私钥是否一致 {d_recovered private_key.privkey.secret_multiplier}) # 4. 验证使用恢复的私钥对一条新消息签名并用公钥验证 print(f\n[*] 攻击验证阶段使用恢复的私钥进行签名) recovered_priv_key ecdsa.SigningKey.from_secret_exponent(d_recovered, curvecurve) test_msg bFlag: I_Stole_Your_Private_Key! sig recovered_priv_key.sign(test_msg, kk_recovered) # 注意这里我们“知道”了k实际攻击中无法指定 if public_key.verify(sig, test_msg): print(f[] 攻击成功恢复的私钥有效可以伪造签名。) else: print(f[-] 攻击失败。)运行这段攻击代码你会看到控制台输出成功恢复了k和私钥d。这完美演示了“随机数k重复使用”漏洞的致命性。4.3 关键细节与边界处理在编写攻击脚本时有几个细节必须注意否则很容易在CTF比赛中卡住模运算处理Python的%运算符对于负数取模的结果可能不是我们想要的数学上同余的正数。例如(s1 - s2) % n确保了结果在[0, n-1]之间。在计算模逆pow(a, -1, n)时必须保证a与n互质在ECDSA中由于n是素数只要a不是n的倍数就成立。哈希与截断ECDSA签名时对消息哈希值e的处理是e Hash(m) mod n。如果哈希输出长度如SHA-256是256位大于n的位长度需要取模。我们的hash_message函数已经做了这个处理。r0或s0的检查在真正的ECDSA签名规范中如果计算出的r或s为0必须重新选择k。我们的模拟代码省略了这一步以简化流程但攻击代码需要能处理题目给出的任何有效签名。公钥格式转换实际CTF题目中公钥可能以PEM格式、十六进制字符串或坐标对(x, y)给出。你需要根据题目提示将其正确加载为椭圆曲线点对象。ecdsa库提供了VerifyingKey.from_pem(),from_string()等方法。实操心得在真实解题时拿到题目第一步不是急着写代码而是先人工推导。拿出纸笔根据题目描述写出签名方程。确认是否存在k重用看r值是否相同或者是否存在其他关系比如多个签名共享了k的某些比特。把数学模型理清代码只是翻译工具。5. 漏洞拓展与高级攻击场景掌握了基础攻击后我们来看看CTF中可能出现的其他变种和更复杂的情况。这能帮助你在赛场上快速识别题目类型。5.1 随机数k部分泄露LSB泄露这是比完全重用更隐蔽、也更常见于现实世界和CTF赛题的漏洞。假设由于侧信道攻击我们知道了随机数k的最低有效位LSB或者知道了k满足某个线性关系例如k a * k b其中k很小。攻击通常使用格基规约LLL算法。其核心思想是将签名方程转化为一个格上的最近向量问题。对于k的部分泄露我们可以构造一个格使得包含私钥d的短向量就在这个格中。使用SageMath内置LLL可以很方便地求解。# 以下是一个概念性示例实际需要SageMath环境 # 假设已知多个签名 (r_i, s_i)对应消息哈希 e_i且已知每个 k_i 的低位 bits_leaked # 我们可以写出k_i bits_leaked_i 2^l * x_i其中 x_i 是未知的高位。 # 代入签名方程s_i k_i^{-1}(e_i d * r_i) mod n # 可以转化为关于 d 和 x_i 的线性方程并构建格。 # 具体构造较为复杂此处不展开代码但思路是将问题转化为寻找格中的短向量。遇到这类题目通常的线索是题目描述中提到了“侧信道”、“故障注入”、“随机数生成器有缺陷”或直接给出了k的部分信息。工具上优先考虑使用SageMath。5.2 签名值s过小或存在线性关系有时题目并非直接攻击k而是利用签名结果(r, s)本身。例如如果要求签名中的s值非常小比如小于某个阈值或者多个签名之间存在s_i a * s_j b mod n这样的关系也可能结合其他条件构造出攻击。这类题目更偏向于数学技巧和观察。解题时需要将收集到的所有签名方程并列出来尝试通过线性组合消去未知数或者利用中国剩余定理CRT等工具。5.3 实战CTF题目模式解析根据经验CTF中的ECDSA题目通常呈现以下模式“经典重现”型直接给出多组消息和签名其中r值相同。这就是我们刚才练习的直接套用公式即可。“网络流量”型提供一个pcap文件你需要从中提取出多次签名通信的记录。使用Wireshark过滤TLS握手或特定应用层协议找到证书、签名等字段解析出r,s,e。挑战在于数据提取和格式解析。“服务器交互”型给你一个网络地址和端口你可以提交消息让服务器签名但无法获取私钥或者服务器会用自己的私钥签名某些信息给你。你需要设计交互获取到足够多利用漏洞的签名对。这可能涉及到构造特定消息、触发错误状态等。“混合密码”型ECDSA与其他密码算法结合。比如用ECDSA签名一个AES密钥或者签名一个RSA参数。你需要先破解ECDSA部分拿到关键参数再继续下一步。6. 防御措施与安全编程启示作为攻击者我们乐见漏洞但作为开发者我们必须避免它们。通过这次破解实战我们应该深刻理解到绝对不可重复使用随机数k这是铁律。每次签名都必须生成密码学安全的、不可预测的新随机数。使用安全的随机数源在生成k时必须使用操作系统提供的密码学安全随机数生成器CSPRNG如/dev/urandomLinux、CryptGenRandomWindows或secrets.randbits()Python 3.6。绝对禁止使用random.randint()或基于时间的种子。考虑确定性ECDSARFC 6979为了解决随机数生成的问题RFC 6979定义了一种确定性ECDSA。它通过私钥d和消息m的哈希值使用HMAC-DRBG算法确定性地生成k。这样对于相同的消息和私钥总会生成相同的签名完全消除了随机数风险。许多现代库如ecdsa库默认或提供选项使用RFC 6979。代码审计与测试在安全关键代码中对签名函数进行模糊测试和静态分析检查是否存在随机数状态重置或共享的情况。# 安全签名示例使用RFC 6979 from ecdsa import SigningKey, SECP256k1 import hashlib sk SigningKey.generate(curveSECP256k1) message bcritical transaction # 默认情况下sign方法可能已采用RFC 6979但最好显式确认或使用支持它的库。 # 使用ecdsa库并确保使用deterministicTrue参数如果支持。 sig sk.sign(message, hashfunchashlib.sha256) # 检查库文档以确认其随机数生成方式7. 常见问题与调试技巧实录在真正解题或复现攻击时你肯定会遇到各种报错和意外。这里记录几个我踩过的坑和解决方法“Invalid signature” 验证失败检查哈希算法确保你计算消息哈希时使用的算法与签名方一致SHA-1? SHA-256?。有时题目会使用非标准哈希。检查数据格式r和s是大整数但题目可能以十六进制字符串、Base64或字节形式给出。公钥也可能有多种编码格式压缩、未压缩。仔细阅读题目说明进行正确的解码和类型转换。检查模数n确认你使用的曲线和阶n是否正确。不同曲线的n不同。恢复出的私钥d验证不通过检查符号在计算s1 - s2或e1 - e2时确保模运算处理了负数。使用(a - b) % n来保证结果为正。检查方程代入最稳妥的方法是用恢复的d和k重新按照签名方程计算一遍s‘看是否等于题目给出的s。如果不等于逐步回溯计算每一步的中间值与你的攻击代码输出对比。消息编码对同一条消息不同的编码如是否包含换行符、是否进行URL编码会产生不同的哈希值。确保你签名的消息字节与验证方完全一致。使用SageMath进行格攻击时无解检查格构造是否正确这是最复杂的一步。仔细阅读相关论文如HNP: Hidden Number Problem或成熟的CTF题解对照检查你的格矩阵构造是否一致。一个系数的符号错误都可能导致失败。调整格维度与界限LLL算法找到的向量不一定就是目标向量。可能需要尝试调整格的维度使用的签名数量和权重参数。题目看似是ECDSA但无从下手寻找非标准参数检查题目是否使用了自定义的椭圆曲线弱曲线、特殊的基点G、或者修改了签名验证公式。有时漏洞就藏在非标准实现里。寻找旁路信息题目描述、注释、甚至变量名有时会给出提示如leak、hint、fault等。最后分享一个我最常用的调试技巧单元测试式攻击。在写出完整的攻击脚本前先用模拟代码生成一个带有已知漏洞如固定k的密钥和签名对。然后用你正在编写的攻击脚本去攻击这个你自己生成的、结果已知的“靶子”。这样能快速定位是数学公式错了还是代码实现错了。当你的脚本能稳定攻破自己的模拟靶场后再去挑战真正的题目成功率会高很多。密码学攻击就像解谜每一步都需要严密的逻辑。从理解原理到推导公式再到代码实现最后调试成功这个过程带来的成就感正是CTF竞赛和密码学研究的魅力所在。希望这篇从零开始的实战指南能成为你解开下一个ECDSA签名漏洞题目的钥匙。
1. 项目概述当ECDSA签名不再“安全”在CTF的密码学赛道上ECDSA椭圆曲线数字签名算法相关的题目一直是区分选手水平的一道分水岭。它不像基础的RSA那样有大量现成的攻击脚本也不像AES对称加密那样直观。ECDSA以其数学上的优雅和公认的安全性著称广泛应用于比特币、TLS等关键领域。然而正是这种“公认的安全”让许多CTFer在遇到相关题目时感到无从下手觉得它是个黑盒。实际上ECDSA的安全性严重依赖于其实现过程中的每一个细节一旦这些细节出现纰漏——比如随机数k被重复使用、泄露或者签名过程中存在侧信道泄露——整个签名体系就会土崩瓦解。这个项目就是带你亲手拆解这个“黑盒”从零开始理解ECDSA的工作原理并实战演练如何利用其常见的实现漏洞来破解签名最终拿到Flag。我会用最直白的Python代码一步步还原攻击过程让你不仅会“用”脚本更明白脚本每一行背后的数学逻辑和攻击原理。2. ECDSA核心原理与安全基石拆解在动手破解之前我们必须先搞清楚我们要攻击的对象到底是什么它的弱点可能藏在哪里。ECDSA可以看作是在椭圆曲线这个数学结构上实现的“数字签名版DSA”。它的安全性根基在于椭圆曲线离散对数问题ECDLP的困难性简单说就是从公钥Q反推出私钥d是计算上不可行的。但算法是完美的实现是人写的人就会犯错。2.1 签名与验证的数学流程假设我们有一条选定的椭圆曲线比如经典的secp256k1一个基点G其阶为n一个非常大的素数。用户持有一个私钥d一个在[1, n-1]区间内的随机整数公钥Q d * G椭圆曲线上的点乘运算。签名过程Sign对消息m计算哈希值e Hash(m)。例如使用SHA-256生成一个临时随机数k同样在[1, n-1]区间内。这个k至关重要也是绝大多数漏洞的源头。计算椭圆曲线点 (x1, y1) k * G。令 r x1 mod n。如果r0则返回第2步重选k。计算 s k^{-1} * (e d * r) mod n。如果s0也返回第2步。得到的(r, s)就是消息m的数字签名。验证过程Verify检查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。验证 r x1 mod n。若相等则签名有效。从流程看验证方只需要公钥Q、消息m和签名(r, s)完全不需要私钥d或随机数k。整个系统的安全假设是k必须是一次一密且绝对保密。2.2 常见漏洞模式分析CTF中ECDSA的题目几乎都是围绕破坏这个安全假设展开的随机数k重复使用这是最经典、最著名的漏洞。如果对两个不同的消息m1和m2签名时使用了同一个k那么攻击者可以直接解出私钥d。随机数k部分泄露或可预测如果k的某些比特位泄露例如通过侧信道攻击或者k是由一个脆弱的伪随机数生成器PRNG产生的攻击者可能利用格基规约LLL算法等数学工具恢复出私钥。签名过程中存在故障注入在计算s k^{-1} * (e d * r) mod n时如果通过某种物理手段如电压毛刺导致计算错误可能会产生无效签名分析这些错误签名有时也能泄露信息。签名参数如r, s的某些性质被利用例如s值过小、存在某种数学关系等在特定场景下可能被攻击。我们本次实战将聚焦于第一种情况——随机数k重复使用。因为它的原理最直观攻击代码最简洁非常适合作为入门ECDSA攻击的第一课。理解了它你就掌握了破解一半以上相关CTF题目的钥匙。3. 攻击场景构建与Python环境准备为了模拟一个真实的CTF漏洞场景我们假设遇到这样一个题目服务器使用了一个有缺陷的ECDSA签名库在对多条不同的消息进行签名时意外地重复使用了同一个随机数k。我们的任务是通过收集到足够多的消息签名对推导出私钥d然后伪造签名通过验证从而获取Flag。3.1 核心工具与库选择我们将使用Python进行攻击演示主要依赖ecdsa和hashlib库。ecdsa库本身是安全的我们将用它来“正确”地生成密钥、签名和验证以模拟目标系统。而我们的攻击代码则会基于数学原理从头编写不依赖任何现成的攻击函数以此加深理解。# 安装必要的库 pip install ecdsahashlib是Python标准库无需安装。我们选择secp256k1曲线进行演示因为它应用广泛比特币就用它且原理通用。3.2 模拟漏洞签名生成首先我们写一段模拟有漏洞的签名服务器代码。关键点在于我们固定一个k值并用它对多条不同的消息进行签名。import ecdsa import hashlib import random # 选择曲线 curve ecdsa.SECP256k1 n curve.order # 曲线的阶一个非常大的素数 # 生成一对正常的密钥 private_key ecdsa.SigningKey.generate(curvecurve) public_key private_key.get_verifying_key() print(f[*] 生成的公钥坐标: ({public_key.pubkey.point.x()}, {public_key.pubkey.point.y()})) # 模拟漏洞固定一个随机数k在实际漏洞中这是无意发生的 k_fixed random.randrange(1, n) # 随机选一个k但之后固定不变 print(f[*] 被重复使用的致命随机数 k {k_fixed}) # 准备两条不同的消息 messages [bHello, CTF!, bECDSA is broken if k is reused.] signatures [] for msg in messages: # 计算消息哈希 e int(hashlib.sha256(msg).hexdigest(), 16) % n # 使用固定的k进行签名模拟漏洞 # 计算 r (k * G).x mod n kG k_fixed * curve.generator r kG.x() % n # 计算 s k^{-1} * (e d * r) mod n d private_key.privkey.secret_multiplier k_inv pow(k_fixed, -1, n) # Python 3.8 支持模逆计算 s (k_inv * (e d * r)) % n signatures.append((r, s)) print(f[*] 消息: {msg.decode()}) print(f 签名 (r, s): ({r}, {s})) # 用标准库验证签名是否正确确认我们的模拟是有效的 for msg, (r, s) in zip(messages, signatures): sig ecdsa.ecdsa.Signature(r, s) if public_key.pubkey.verifies(e, sig): print(f[] 签名验证通过: {msg.decode()}) else: print(f[-] 签名验证失败!)运行这段代码我们就得到了一个关键的“战场环境”两条不同消息m1,m2它们对应的哈希e1,e2以及使用同一个k生成的两组签名(r1, s1)和(r2, s2)。注意因为k相同所以第一步计算的椭圆曲线点k*G相同因此r1 r2 r。这是我们攻击的起点。注意在实际CTF题目中你通常拿不到k的值也拿不到私钥d。你拿到的是公开的公钥Q、若干条消息及其签名(r, s)。我们的目标是从这些公开信息中推出d。4. 破解实战从重复的k到私钥d现在我们进入最核心的环节如何利用k重复使用这一漏洞从公开信息中解出私钥d。这个过程是一道漂亮的数学推导。4.1 数学推导过程我们有两条签名方程因为k相同所以r也相同s1 k^{-1} * (e1 d * r) mod ns2 k^{-1} * (e2 d * r) mod n注意这里的k^{-1}是k在模n下的乘法逆元。我们将两个方程相减在模n运算下s1 - s2 k^{-1} * (e1 d*r) - k^{-1} * (e2 d*r) mod ns1 - s2 k^{-1} * (e1 - e2) mod n看方程中的d被消掉了现在我们得到了一个只包含s1, s2, e1, e2和未知数k^{-1}的方程。我们可以解出k^{-1}进而解出kk^{-1} (s1 - s2) * (e1 - e2)^{-1} mod n因此k (e1 - e2) * (s1 - s2)^{-1} mod n一旦我们知道了k就可以将它代入任何一个原始的签名方程来解出私钥d。例如从第一个方程s1 k^{-1} * (e1 d * r) mod n两边乘以kk * s1 e1 d * r mod n所以d * r (k * s1 - e1) mod n最终d (k * s1 - e1) * r^{-1} mod n大功告成私钥d被我们推导出来了。整个攻击过程我们只需要两条使用相同k签名的消息及其哈希值。4.2 Python攻击代码实现现在我们把上面的数学公式翻译成Python代码。假设我们处于攻击者视角我们只知道公钥Q、两条消息m1, m2、以及它们的签名(r, s1)和(r, s2)注意r相同。import hashlib # 攻击者已知的信息从题目或网络流量中获取 # 公钥 Q (这里我们从模拟代码中获取公钥点实际题目可能以字节或坐标形式给出) Q public_key.pubkey.point # 两条消息 m1, m2 messages # 两个签名 (r, s1), (r, s2) (r1, s1), (r2, s2) signatures # 由于k重复使用r1 等于 r2 r r1 assert r1 r2, k未重复使用无法进行此攻击 # 1. 计算消息哈希 e1, e2 def hash_message(msg): return int(hashlib.sha256(msg).hexdigest(), 16) % n e1 hash_message(m1) e2 hash_message(m2) # 2. 计算 k (e1 - e2) / (s1 - s2) mod n # 注意模运算下的除法是乘以模逆元 s_diff_inv pow((s1 - s2) % n, -1, n) k_recovered ((e1 - e2) * s_diff_inv) % n print(f[] 恢复出的随机数 k: {k_recovered}) print(f 与真实的k是否一致 {k_recovered k_fixed}) # 3. 计算私钥 d (k * s1 - e1) / r mod n r_inv pow(r, -1, n) d_recovered ((k_recovered * s1 - e1) * r_inv) % n print(f[] 恢复出的私钥 d: {d_recovered}) print(f 与真实的私钥是否一致 {d_recovered private_key.privkey.secret_multiplier}) # 4. 验证使用恢复的私钥对一条新消息签名并用公钥验证 print(f\n[*] 攻击验证阶段使用恢复的私钥进行签名) recovered_priv_key ecdsa.SigningKey.from_secret_exponent(d_recovered, curvecurve) test_msg bFlag: I_Stole_Your_Private_Key! sig recovered_priv_key.sign(test_msg, kk_recovered) # 注意这里我们“知道”了k实际攻击中无法指定 if public_key.verify(sig, test_msg): print(f[] 攻击成功恢复的私钥有效可以伪造签名。) else: print(f[-] 攻击失败。)运行这段攻击代码你会看到控制台输出成功恢复了k和私钥d。这完美演示了“随机数k重复使用”漏洞的致命性。4.3 关键细节与边界处理在编写攻击脚本时有几个细节必须注意否则很容易在CTF比赛中卡住模运算处理Python的%运算符对于负数取模的结果可能不是我们想要的数学上同余的正数。例如(s1 - s2) % n确保了结果在[0, n-1]之间。在计算模逆pow(a, -1, n)时必须保证a与n互质在ECDSA中由于n是素数只要a不是n的倍数就成立。哈希与截断ECDSA签名时对消息哈希值e的处理是e Hash(m) mod n。如果哈希输出长度如SHA-256是256位大于n的位长度需要取模。我们的hash_message函数已经做了这个处理。r0或s0的检查在真正的ECDSA签名规范中如果计算出的r或s为0必须重新选择k。我们的模拟代码省略了这一步以简化流程但攻击代码需要能处理题目给出的任何有效签名。公钥格式转换实际CTF题目中公钥可能以PEM格式、十六进制字符串或坐标对(x, y)给出。你需要根据题目提示将其正确加载为椭圆曲线点对象。ecdsa库提供了VerifyingKey.from_pem(),from_string()等方法。实操心得在真实解题时拿到题目第一步不是急着写代码而是先人工推导。拿出纸笔根据题目描述写出签名方程。确认是否存在k重用看r值是否相同或者是否存在其他关系比如多个签名共享了k的某些比特。把数学模型理清代码只是翻译工具。5. 漏洞拓展与高级攻击场景掌握了基础攻击后我们来看看CTF中可能出现的其他变种和更复杂的情况。这能帮助你在赛场上快速识别题目类型。5.1 随机数k部分泄露LSB泄露这是比完全重用更隐蔽、也更常见于现实世界和CTF赛题的漏洞。假设由于侧信道攻击我们知道了随机数k的最低有效位LSB或者知道了k满足某个线性关系例如k a * k b其中k很小。攻击通常使用格基规约LLL算法。其核心思想是将签名方程转化为一个格上的最近向量问题。对于k的部分泄露我们可以构造一个格使得包含私钥d的短向量就在这个格中。使用SageMath内置LLL可以很方便地求解。# 以下是一个概念性示例实际需要SageMath环境 # 假设已知多个签名 (r_i, s_i)对应消息哈希 e_i且已知每个 k_i 的低位 bits_leaked # 我们可以写出k_i bits_leaked_i 2^l * x_i其中 x_i 是未知的高位。 # 代入签名方程s_i k_i^{-1}(e_i d * r_i) mod n # 可以转化为关于 d 和 x_i 的线性方程并构建格。 # 具体构造较为复杂此处不展开代码但思路是将问题转化为寻找格中的短向量。遇到这类题目通常的线索是题目描述中提到了“侧信道”、“故障注入”、“随机数生成器有缺陷”或直接给出了k的部分信息。工具上优先考虑使用SageMath。5.2 签名值s过小或存在线性关系有时题目并非直接攻击k而是利用签名结果(r, s)本身。例如如果要求签名中的s值非常小比如小于某个阈值或者多个签名之间存在s_i a * s_j b mod n这样的关系也可能结合其他条件构造出攻击。这类题目更偏向于数学技巧和观察。解题时需要将收集到的所有签名方程并列出来尝试通过线性组合消去未知数或者利用中国剩余定理CRT等工具。5.3 实战CTF题目模式解析根据经验CTF中的ECDSA题目通常呈现以下模式“经典重现”型直接给出多组消息和签名其中r值相同。这就是我们刚才练习的直接套用公式即可。“网络流量”型提供一个pcap文件你需要从中提取出多次签名通信的记录。使用Wireshark过滤TLS握手或特定应用层协议找到证书、签名等字段解析出r,s,e。挑战在于数据提取和格式解析。“服务器交互”型给你一个网络地址和端口你可以提交消息让服务器签名但无法获取私钥或者服务器会用自己的私钥签名某些信息给你。你需要设计交互获取到足够多利用漏洞的签名对。这可能涉及到构造特定消息、触发错误状态等。“混合密码”型ECDSA与其他密码算法结合。比如用ECDSA签名一个AES密钥或者签名一个RSA参数。你需要先破解ECDSA部分拿到关键参数再继续下一步。6. 防御措施与安全编程启示作为攻击者我们乐见漏洞但作为开发者我们必须避免它们。通过这次破解实战我们应该深刻理解到绝对不可重复使用随机数k这是铁律。每次签名都必须生成密码学安全的、不可预测的新随机数。使用安全的随机数源在生成k时必须使用操作系统提供的密码学安全随机数生成器CSPRNG如/dev/urandomLinux、CryptGenRandomWindows或secrets.randbits()Python 3.6。绝对禁止使用random.randint()或基于时间的种子。考虑确定性ECDSARFC 6979为了解决随机数生成的问题RFC 6979定义了一种确定性ECDSA。它通过私钥d和消息m的哈希值使用HMAC-DRBG算法确定性地生成k。这样对于相同的消息和私钥总会生成相同的签名完全消除了随机数风险。许多现代库如ecdsa库默认或提供选项使用RFC 6979。代码审计与测试在安全关键代码中对签名函数进行模糊测试和静态分析检查是否存在随机数状态重置或共享的情况。# 安全签名示例使用RFC 6979 from ecdsa import SigningKey, SECP256k1 import hashlib sk SigningKey.generate(curveSECP256k1) message bcritical transaction # 默认情况下sign方法可能已采用RFC 6979但最好显式确认或使用支持它的库。 # 使用ecdsa库并确保使用deterministicTrue参数如果支持。 sig sk.sign(message, hashfunchashlib.sha256) # 检查库文档以确认其随机数生成方式7. 常见问题与调试技巧实录在真正解题或复现攻击时你肯定会遇到各种报错和意外。这里记录几个我踩过的坑和解决方法“Invalid signature” 验证失败检查哈希算法确保你计算消息哈希时使用的算法与签名方一致SHA-1? SHA-256?。有时题目会使用非标准哈希。检查数据格式r和s是大整数但题目可能以十六进制字符串、Base64或字节形式给出。公钥也可能有多种编码格式压缩、未压缩。仔细阅读题目说明进行正确的解码和类型转换。检查模数n确认你使用的曲线和阶n是否正确。不同曲线的n不同。恢复出的私钥d验证不通过检查符号在计算s1 - s2或e1 - e2时确保模运算处理了负数。使用(a - b) % n来保证结果为正。检查方程代入最稳妥的方法是用恢复的d和k重新按照签名方程计算一遍s‘看是否等于题目给出的s。如果不等于逐步回溯计算每一步的中间值与你的攻击代码输出对比。消息编码对同一条消息不同的编码如是否包含换行符、是否进行URL编码会产生不同的哈希值。确保你签名的消息字节与验证方完全一致。使用SageMath进行格攻击时无解检查格构造是否正确这是最复杂的一步。仔细阅读相关论文如HNP: Hidden Number Problem或成熟的CTF题解对照检查你的格矩阵构造是否一致。一个系数的符号错误都可能导致失败。调整格维度与界限LLL算法找到的向量不一定就是目标向量。可能需要尝试调整格的维度使用的签名数量和权重参数。题目看似是ECDSA但无从下手寻找非标准参数检查题目是否使用了自定义的椭圆曲线弱曲线、特殊的基点G、或者修改了签名验证公式。有时漏洞就藏在非标准实现里。寻找旁路信息题目描述、注释、甚至变量名有时会给出提示如leak、hint、fault等。最后分享一个我最常用的调试技巧单元测试式攻击。在写出完整的攻击脚本前先用模拟代码生成一个带有已知漏洞如固定k的密钥和签名对。然后用你正在编写的攻击脚本去攻击这个你自己生成的、结果已知的“靶子”。这样能快速定位是数学公式错了还是代码实现错了。当你的脚本能稳定攻破自己的模拟靶场后再去挑战真正的题目成功率会高很多。密码学攻击就像解谜每一步都需要严密的逻辑。从理解原理到推导公式再到代码实现最后调试成功这个过程带来的成就感正是CTF竞赛和密码学研究的魅力所在。希望这篇从零开始的实战指南能成为你解开下一个ECDSA签名漏洞题目的钥匙。
