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簽名漏洞題目的鑰匙。 從ECDSA隨機數重用漏洞到私鑰破解：CTF實戰與數學推導
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簽名漏洞題目的鑰匙。