拓冰网站定制 
文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载本篇技術指南以 ctf-wiki 的 ecc.md 為主體系統梳理橢圓曲線加密Elliptic Curve Cryptography, ECC的數學基礎、基於 ECC 的 ElGamal 加解密流程並以 2013 年 SECCON CTF quals 的 Cryptanalysis 題目完整演示「曲線階過小 → 暴力求解私鑰 → 還原明文」的完整攻擊鏈路。讀完後你將掌握橢圓曲線群結構、ECC 密鑰生成與加解密的每一步運算並能在 SageMath 中獨立復現此類 CTF 題目。概述為什麼是橢圓曲線ECC 全稱「橢圓曲線加密」Ellipse Curve Cryptography原文如此通常寫作 Elliptic Curve Cryptography是一種基於橢圓曲線數學的公鑰密碼體制。與傳統的基於大質數因子分解困難性的 RSA 不同ECC 的安全性依賴於解決橢圓曲線離散對數問題ECDLP的困難性——在一個大階橢圓曲線群上給定生成元 (G) 與點 (Q)求解滿足 (Q mG) 的整數 (m) 在計算上是不可行的。它的核心優勢在於相對於其它方法它可以在使用較短密鑰長度的同時保持相同的密碼強度。例如同等安全強度下ECC 的密鑰長度遠小於 RSA 的模長這在資源受限的嵌入式設備與移動終端上尤為重要。目前橢圓曲線主要採用的有限域有兩類以素數為模的整數域 (GF(p))通常在通用處理器上更為有效也是目前應用最廣的選擇如 NIST P-256、Curve25519 等。特徵為 2 的伽羅華域 (GF(2^m))其加法可退化為異或運算適合設計專門的硬件實現。基本知識有限域上的橢圓曲線曲線方程與非奇異條件有限域上的橢圓曲線是指在橢圓曲線的定義式[ y^2axybyx^3cx^2dxe ]中所有的係數都是某個有限域 (GF(p)) 中的元素其中 (p) 為一個大素數。當然並不是所有的橢圓曲線都適合於加密最為常用的方程是如下形式的 Weierstrass 方程[ y^2x^3axb ]其中必須滿足非奇異條件判別式不為零[ 4a^327b^2 \bmod p \neq 0 ]該條件保證曲線上沒有重根即曲線是「光滑」的非奇異曲線從而確保點的加法運算具有良好的群結構若判別式為 0曲線上會出現奇異點離散對數問題將退化成易解的代數問題。點集與無窮遠點我們稱該方程的所有解 ((x,y))其中 (x \in F_p, y \in F_p)以及一個稱為**「無窮遠點」(O)** 的點所組成的集合為定義在 (F_p) 上的一條橢圓曲線記為 (E(F_p))。無窮遠點在射影幾何中對應鉛直方向的交點同時充當群的單位元。群的結構與週期一般定義橢圓曲線密碼需要以下條件假設 (E(F_p)) 對點的運算 (\oplus)點的加法幾何上即「過兩點作直線交曲線於第三點再關於 x 軸取對稱點」形成一個Abel 群交換群滿足逆元存在、封閉性等性質。設 (p \in E(F_q))且存在很大的正整數 (t) 滿足[ \underbrace{p \oplus p \oplus \cdots \oplus p}_{t\ \text{個}} O ]這裡我們稱 (t) 為點 (p) 的週期階。此外對於 (Q \in E(F_q))一定存在某個正整數 (m) 使得[ Q m\cdot p \underbrace{p \oplus p \oplus \cdots \oplus p}_{m\ \text{個}} ]由此定義離散對數 (m \log_p Q)——注意這裡的「對數」是橢圓曲線點群意義下的標量倍乘指數而不是傳統的實數對數。假設 (G) 是該曲線群 (E_q(a,b)) 的生成元即可以生成其中的所有元素其階為滿足 (nG O) 的最小正整數 (n)。群中所有點的個數被稱為曲線的階cardinality它直接決定了 ECDLP 的困難程度也決定了該曲線參數能否安全使用。與離散對數章的關係上述「已知 (G) 與 (QmG)求解 (m)」的困難性正是 離散對數 一章所討論的一般離散對數問題DLP在橢圓曲線群上的推廣。當曲線階 (n) 是光滑數即僅含小素因子時ECDLP 可用 Pohlig-Hellman 等算法在低複雜度內求解——這正是後文 CTF 題目可被暴力破解的根本原因。ECC 中的 ElGamal將 ElGamal 公鑰加密體制移植到橢圓曲線群上就得到基於 ECC 的 ElGamal 方案。這裡我們假設用戶 B 要把消息加密後傳給用戶 A。與標準的整數域上的ElGamal 對照標準 ElGamal 在乘法群 (Z_p^*) 上運算使用模冪 (g^r \bmod p)ECC 版本的 ElGamal 則在橢圓曲線點群上運算使用點的標量倍乘 (kG)。兩者結構完全同構安全性都歸約到對應群上的離散對數困難性。密鑰生成用戶 A 先選擇一條橢圓曲線 (E_q(a,b))然後選擇其上的一個生成元 (G)假設其階為 (n)。再選擇一個正整數 (n_a) 作為私鑰計算公鑰 (P_a n_a G)。其中曲線參數 (E_q(a,b))、(q)、生成元 (G) 都會被公開即公鑰為 (P_a)私鑰為 (n_a)。攻擊者即便拿到 (G) 與 (P_a)也難以由 ECDLP 恢復 (n_a)。加密用戶 B 要向用戶 A 發送消息 (m)這裡假設消息 (m) 已經被編碼為橢圓曲線上的一個點這是 ECC 加密的必備前置步驟明文先通過某種可逆映射轉換為曲線上的點。加密步驟如下查詢用戶 A 的公鑰 (E_q(a,b), q, P_a, G)。在區間 ((1, q-1)) 內選擇隨機數 (k)。根據 A 的公鑰計算點 ((x_1, y_1) kG)。計算點 ((x_2, y_2) kP_a)如果為無窮遠點 (O)則從第二步重新開始防止密文退化。計算 (C m (x_2, y_2))用共享密鑰點對明文點做一次點加法完成「掩碼」。將 (((x_1, y_1), C)) 發送給 A。可見最終密文由兩部分構成隨機點 ((x_1,y_1))承載隨機數 (k) 的信息與掩碼後的明文點 (C)。解密接收方 A 拿到密文後解密步驟如下利用私鑰計算點 (n_a(x_1, y_1) n_a k G k P_a (x_2, y_2))——這是整個方案的核心只有持有私鑰 (n_a) 的人才能從 ((x_1, y_1)) 重新導出共享點 ((x_2, y_2))。計算消息 (m C - (x_2, y_2))即從掩碼後的點中減去共享點恢復明文點。關鍵點這裡的關鍵點在於我們即使知道了 ((x_1, y_1)) 也難以知道 (k)這是由橢圓曲線離散對數問題的難度決定的。同理公開的 (P_a n_a G) 也無法反推出 (n_a)。只要曲線參數選取得當階為大素數或含大素因子整個體制就是安全的。實戰2013 SECCON CTF quals Cryptanalysis理論之後看實戰。這裡以 2013 年 SECCON CTF quals 中的Cryptanalysis題目為例題目描述如下從題面可知我們已知橢圓曲線方程、對應的生成元base、相應的模數、公鑰以及加密後的結果。本題本質上就是一個ECC 版本的 ElGamal解密題。攻擊思路模數太小暴力枚舉關鍵觀察在於模數曲線階(n 7654319) 太小。橢圓曲線群的階只有約 (7.6 \times 10^6)意味著最多暴力枚舉 (7.6\times 10^6) 次點加法就能窮盡所有可能的私鑰這在現代計算機上僅需數秒。因此我們可以直接暴力枚舉出 secret key之後便可以解密。原題解參考了公開的 SageMath 程序暴力跑出私鑰後再還原明文。完整的 Sage 程序如下a 1234577 b 3213242 n 7654319 E EllipticCurve(GF(n), [0, 0, 0, a, b]) base E([5234568, 2287747]) pub E([2366653, 1424308]) c1 E([5081741, 6744615]) c2 E([610619, 6218]) X base for i in range(1, n): if X pub: secret i print [] secret:, i break else: X X base print i m c2 - (c1 * secret) print [] x:, m[0] print [] y:, m[1] print [] xy:, m[0] m[1]對這段腳本逐步解讀a 1234577, b 3213242即曲線 (y^2 x^3 ax b) 的係數n 7654319既是模數也是曲線所在的有限域大小。EllipticCurve(GF(n), [0, 0, 0, a, b])以 Weierstrass 係數[a1, a2, a3, a4, a6]的形式在 (GF(7654319)) 上構造曲線前三個 0 對應一般式 (y^2 a_1xy a_3y x^3 a_2x^2 a_4x a_6) 中缺失的項a4 a、a6 b。base為生成元 (G)pub為公鑰 (P_a)c1、c2即密文 (((x_1,y_1), C))。暴力循環從i 1開始逐次累加X X base一旦X pub即求得私鑰secret。解密直接套用 ECC-ElGamal 的解密式m c2 - (c1 * secret)其中c1 * secret即共享點 (kP_a)。暴力跑出的結果如下[] secret: 1584718 [] x: 2171002 [] y: 3549912 [] xy: 5720914即私鑰為1584718明文點為 ((2171002, 3549912))最終答案明文點的x y為5720914。用純 Python 獨立驗證腳本結果SageMath 的輸出可以進一步用一段不依賴 Sage、僅用純 Python 的橢圓曲線點運算實現來交叉驗證。點加法與標量倍乘的標準公式如下本倉庫文檔寫作過程中也實際運行驗證過p 7654319 a 1234577 b 3213242 def on_curve(P): x, y P return (y*y - (x*x*x a*x b)) % p 0 def add(P, Q): if P is None: return Q if Q is None: return P x1, y1 P; x2, y2 Q if x1 x2 and (y1 y2) % p 0: return None # 無窮遠點 if P Q: lam (3*x1*x1 a) * pow(2*y1, -1, p) % p else: lam (y2 - y1) * pow(x2 - x1, -1, p) % p x3 (lam*lam - x1 - x2) % p y3 (lam*(x1 - x3) - y1) % p return (x3, y3) def mul(k, P): # 二進制快速倍乘 R None while k: if k 1: R add(R, P) P add(P, P) k 1 return R base (5234568, 2287747) pub (2366653, 1424308) c1 (5081741, 6744615) c2 (610619, 6218) print(base on curve:, on_curve(base)) print(pub on curve:, on_curve(pub)) print(c1 on curve:, on_curve(c1)) print(c2 on curve:, on_curve(c2)) secret 1584718 print(base*secret pub:, mul(secret, base) pub) # m c2 - secret*c1 shared mul(secret, c1) neg (shared[0], (-shared[1]) % p) m add(c2, neg) print(m , m) print(m[0]m[1] , m[0]m[1])運行輸出base on curve: True pub on curve: True c1 on curve: True c2 on curve: True base*secret pub: True m (2171002, 3549912) m[0]m[1] 5720914這份獨立實現驗證了三個關鍵事實所有給定點生成元、公鑰、兩段密文都確實位於曲線上base × 1584718 pub私鑰正確解密結果與 SageMath 輸出完全一致。這說明題目的攻擊流程與解密公式可以被任何語言的實現復現不依賴特定工具。延伸當曲線階更大時暴力不再可行本題能暴力破解根本原因是曲線階 (n 7654319) 過小。若階增大到 (2^{160}) 以上暴力枚舉將完全不可行此時需要借助更高效的離散對數算法例如 離散對數 一章中介紹的Baby-step giant-step小步大步法利用中間相遇思想以 (O(\sqrt{n})) 時間與空間折中求解。Pollards ρ 算法以 (O(\sqrt{n})) 時間、(O(1)) 空間的隨機化算法。Pollards kangaroo 算法已知解的取值範圍時更高效。Pohlig-Hellman 算法當群的階是光滑數可分解為多個小素數冪之積時將 DLP 分解到每個小因子子群上求解再以中國剩餘定理組合複雜度為 (O(\sum_i e_i(\log n \sqrt{p_i})))。因此安全橢圓曲線的階必須是大素數或含大素因子正如標準 ElGamal 要求 (p-1) 有大素因子一樣。CTF 中此類「參數過小」題目正是為了訓練選手識別這一安全前提。實戰要點小結識別出題模式題面給出曲線方程、生成元、公鑰與密文要求恢復明文即 ECC-ElGamal 解密先判斷曲線階的大小階很小就直接暴力枚舉私鑰。計算工具SageMath 的EllipticCurve(GF(n), [a1,a2,a3,a4,a6])與點運算、*是最順手的工具不依賴 Sage 時用點加法與二進制快速倍乘的公式即可在任何語言中復現。核心公式解密即 (m C - n_a(x_1,y_1))而 (n_a(x_1,y_1) n_a kG kP_a)安全性完全建立在 ECDLP 之上。參數檢查無論是自建曲線還是解題都要檢查曲線階的因子分解階光滑含小素因子是 ECDLP 被攻破的最常見原因。參考資料本篇主體文檔ecc.md簡體中文版見 docs/zh/docs/crypto/asymmetric/discrete-log/ecc.md離散對數基礎與攻擊算法discrete-log.md標準 ElGamal 加密與其 CTF 實例elgamal.md本題目原題解的公開 writeup 可依題目名「SECCON CTF quals 2013 Cryptanalysis」檢索獲取此處不再列出外部鏈接。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐A2UI Express 格式优化实录run_020 数据路径斜杠预处理如何让评测通过率稳定在 100%A2UI Express 格式优化实录run_020 数据路径斜杠预处理如何让评测通过率稳定在 100% 本篇以 A2UI 仓库中一次完整的迭代优化报告 ev文档网络安全教程Dagger v0.8.5 版本解析listen 会话令牌、DAGGER_CLOUD_TOKEN 与 Secret 挂载模式等变更详解Dagger v0.8.5 版本解析listen 会话令牌、DAGGER_CLOUD_TOKEN 与 Secret 挂载模式等变更详解 本篇基于仓库中的版本变文档网络安全教程PAR Technology 开发者门户迁移实战Scalar 如何支撑一个基于 OpenAPI 与 docs-as-code 的企业级 API 平台PAR Technology 开发者门户迁移实战Scalar 如何支撑一个基于 OpenAPI 与 docs as code 的企业级 API 平台 本文以文档网络安全教程上一篇WeChatMsg3步把Mac微信聊天记录导出成网页、Word和CSV下一篇终极解决方案MacType安装失败日志深度分析与修复指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 ctf-wiki 橢圓曲線加密（ECC）從入門到實戰：離散對數基礎、ElGamal 方案與 SECCON CTF 破解
文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载本篇技術指南以 ctf-wiki 的 ecc.md 為主體系統梳理橢圓曲線加密Elliptic Curve Cryptography, ECC的數學基礎、基於 ECC 的 ElGamal 加解密流程並以 2013 年 SECCON CTF quals 的 Cryptanalysis 題目完整演示「曲線階過小 → 暴力求解私鑰 → 還原明文」的完整攻擊鏈路。讀完後你將掌握橢圓曲線群結構、ECC 密鑰生成與加解密的每一步運算並能在 SageMath 中獨立復現此類 CTF 題目。概述為什麼是橢圓曲線ECC 全稱「橢圓曲線加密」Ellipse Curve Cryptography原文如此通常寫作 Elliptic Curve Cryptography是一種基於橢圓曲線數學的公鑰密碼體制。與傳統的基於大質數因子分解困難性的 RSA 不同ECC 的安全性依賴於解決橢圓曲線離散對數問題ECDLP的困難性——在一個大階橢圓曲線群上給定生成元 (G) 與點 (Q)求解滿足 (Q mG) 的整數 (m) 在計算上是不可行的。它的核心優勢在於相對於其它方法它可以在使用較短密鑰長度的同時保持相同的密碼強度。例如同等安全強度下ECC 的密鑰長度遠小於 RSA 的模長這在資源受限的嵌入式設備與移動終端上尤為重要。目前橢圓曲線主要採用的有限域有兩類以素數為模的整數域 (GF(p))通常在通用處理器上更為有效也是目前應用最廣的選擇如 NIST P-256、Curve25519 等。特徵為 2 的伽羅華域 (GF(2^m))其加法可退化為異或運算適合設計專門的硬件實現。基本知識有限域上的橢圓曲線曲線方程與非奇異條件有限域上的橢圓曲線是指在橢圓曲線的定義式[ y^2axybyx^3cx^2dxe ]中所有的係數都是某個有限域 (GF(p)) 中的元素其中 (p) 為一個大素數。當然並不是所有的橢圓曲線都適合於加密最為常用的方程是如下形式的 Weierstrass 方程[ y^2x^3axb ]其中必須滿足非奇異條件判別式不為零[ 4a^327b^2 \bmod p \neq 0 ]該條件保證曲線上沒有重根即曲線是「光滑」的非奇異曲線從而確保點的加法運算具有良好的群結構若判別式為 0曲線上會出現奇異點離散對數問題將退化成易解的代數問題。點集與無窮遠點我們稱該方程的所有解 ((x,y))其中 (x \in F_p, y \in F_p)以及一個稱為**「無窮遠點」(O)** 的點所組成的集合為定義在 (F_p) 上的一條橢圓曲線記為 (E(F_p))。無窮遠點在射影幾何中對應鉛直方向的交點同時充當群的單位元。群的結構與週期一般定義橢圓曲線密碼需要以下條件假設 (E(F_p)) 對點的運算 (\oplus)點的加法幾何上即「過兩點作直線交曲線於第三點再關於 x 軸取對稱點」形成一個Abel 群交換群滿足逆元存在、封閉性等性質。設 (p \in E(F_q))且存在很大的正整數 (t) 滿足[ \underbrace{p \oplus p \oplus \cdots \oplus p}_{t\ \text{個}} O ]這裡我們稱 (t) 為點 (p) 的週期階。此外對於 (Q \in E(F_q))一定存在某個正整數 (m) 使得[ Q m\cdot p \underbrace{p \oplus p \oplus \cdots \oplus p}_{m\ \text{個}} ]由此定義離散對數 (m \log_p Q)——注意這裡的「對數」是橢圓曲線點群意義下的標量倍乘指數而不是傳統的實數對數。假設 (G) 是該曲線群 (E_q(a,b)) 的生成元即可以生成其中的所有元素其階為滿足 (nG O) 的最小正整數 (n)。群中所有點的個數被稱為曲線的階cardinality它直接決定了 ECDLP 的困難程度也決定了該曲線參數能否安全使用。與離散對數章的關係上述「已知 (G) 與 (QmG)求解 (m)」的困難性正是 離散對數 一章所討論的一般離散對數問題DLP在橢圓曲線群上的推廣。當曲線階 (n) 是光滑數即僅含小素因子時ECDLP 可用 Pohlig-Hellman 等算法在低複雜度內求解——這正是後文 CTF 題目可被暴力破解的根本原因。ECC 中的 ElGamal將 ElGamal 公鑰加密體制移植到橢圓曲線群上就得到基於 ECC 的 ElGamal 方案。這裡我們假設用戶 B 要把消息加密後傳給用戶 A。與標準的整數域上的ElGamal 對照標準 ElGamal 在乘法群 (Z_p^*) 上運算使用模冪 (g^r \bmod p)ECC 版本的 ElGamal 則在橢圓曲線點群上運算使用點的標量倍乘 (kG)。兩者結構完全同構安全性都歸約到對應群上的離散對數困難性。密鑰生成用戶 A 先選擇一條橢圓曲線 (E_q(a,b))然後選擇其上的一個生成元 (G)假設其階為 (n)。再選擇一個正整數 (n_a) 作為私鑰計算公鑰 (P_a n_a G)。其中曲線參數 (E_q(a,b))、(q)、生成元 (G) 都會被公開即公鑰為 (P_a)私鑰為 (n_a)。攻擊者即便拿到 (G) 與 (P_a)也難以由 ECDLP 恢復 (n_a)。加密用戶 B 要向用戶 A 發送消息 (m)這裡假設消息 (m) 已經被編碼為橢圓曲線上的一個點這是 ECC 加密的必備前置步驟明文先通過某種可逆映射轉換為曲線上的點。加密步驟如下查詢用戶 A 的公鑰 (E_q(a,b), q, P_a, G)。在區間 ((1, q-1)) 內選擇隨機數 (k)。根據 A 的公鑰計算點 ((x_1, y_1) kG)。計算點 ((x_2, y_2) kP_a)如果為無窮遠點 (O)則從第二步重新開始防止密文退化。計算 (C m (x_2, y_2))用共享密鑰點對明文點做一次點加法完成「掩碼」。將 (((x_1, y_1), C)) 發送給 A。可見最終密文由兩部分構成隨機點 ((x_1,y_1))承載隨機數 (k) 的信息與掩碼後的明文點 (C)。解密接收方 A 拿到密文後解密步驟如下利用私鑰計算點 (n_a(x_1, y_1) n_a k G k P_a (x_2, y_2))——這是整個方案的核心只有持有私鑰 (n_a) 的人才能從 ((x_1, y_1)) 重新導出共享點 ((x_2, y_2))。計算消息 (m C - (x_2, y_2))即從掩碼後的點中減去共享點恢復明文點。關鍵點這裡的關鍵點在於我們即使知道了 ((x_1, y_1)) 也難以知道 (k)這是由橢圓曲線離散對數問題的難度決定的。同理公開的 (P_a n_a G) 也無法反推出 (n_a)。只要曲線參數選取得當階為大素數或含大素因子整個體制就是安全的。實戰2013 SECCON CTF quals Cryptanalysis理論之後看實戰。這裡以 2013 年 SECCON CTF quals 中的Cryptanalysis題目為例題目描述如下從題面可知我們已知橢圓曲線方程、對應的生成元base、相應的模數、公鑰以及加密後的結果。本題本質上就是一個ECC 版本的 ElGamal解密題。攻擊思路模數太小暴力枚舉關鍵觀察在於模數曲線階(n 7654319) 太小。橢圓曲線群的階只有約 (7.6 \times 10^6)意味著最多暴力枚舉 (7.6\times 10^6) 次點加法就能窮盡所有可能的私鑰這在現代計算機上僅需數秒。因此我們可以直接暴力枚舉出 secret key之後便可以解密。原題解參考了公開的 SageMath 程序暴力跑出私鑰後再還原明文。完整的 Sage 程序如下a 1234577 b 3213242 n 7654319 E EllipticCurve(GF(n), [0, 0, 0, a, b]) base E([5234568, 2287747]) pub E([2366653, 1424308]) c1 E([5081741, 6744615]) c2 E([610619, 6218]) X base for i in range(1, n): if X pub: secret i print [] secret:, i break else: X X base print i m c2 - (c1 * secret) print [] x:, m[0] print [] y:, m[1] print [] xy:, m[0] m[1]對這段腳本逐步解讀a 1234577, b 3213242即曲線 (y^2 x^3 ax b) 的係數n 7654319既是模數也是曲線所在的有限域大小。EllipticCurve(GF(n), [0, 0, 0, a, b])以 Weierstrass 係數[a1, a2, a3, a4, a6]的形式在 (GF(7654319)) 上構造曲線前三個 0 對應一般式 (y^2 a_1xy a_3y x^3 a_2x^2 a_4x a_6) 中缺失的項a4 a、a6 b。base為生成元 (G)pub為公鑰 (P_a)c1、c2即密文 (((x_1,y_1), C))。暴力循環從i 1開始逐次累加X X base一旦X pub即求得私鑰secret。解密直接套用 ECC-ElGamal 的解密式m c2 - (c1 * secret)其中c1 * secret即共享點 (kP_a)。暴力跑出的結果如下[] secret: 1584718 [] x: 2171002 [] y: 3549912 [] xy: 5720914即私鑰為1584718明文點為 ((2171002, 3549912))最終答案明文點的x y為5720914。用純 Python 獨立驗證腳本結果SageMath 的輸出可以進一步用一段不依賴 Sage、僅用純 Python 的橢圓曲線點運算實現來交叉驗證。點加法與標量倍乘的標準公式如下本倉庫文檔寫作過程中也實際運行驗證過p 7654319 a 1234577 b 3213242 def on_curve(P): x, y P return (y*y - (x*x*x a*x b)) % p 0 def add(P, Q): if P is None: return Q if Q is None: return P x1, y1 P; x2, y2 Q if x1 x2 and (y1 y2) % p 0: return None # 無窮遠點 if P Q: lam (3*x1*x1 a) * pow(2*y1, -1, p) % p else: lam (y2 - y1) * pow(x2 - x1, -1, p) % p x3 (lam*lam - x1 - x2) % p y3 (lam*(x1 - x3) - y1) % p return (x3, y3) def mul(k, P): # 二進制快速倍乘 R None while k: if k 1: R add(R, P) P add(P, P) k 1 return R base (5234568, 2287747) pub (2366653, 1424308) c1 (5081741, 6744615) c2 (610619, 6218) print(base on curve:, on_curve(base)) print(pub on curve:, on_curve(pub)) print(c1 on curve:, on_curve(c1)) print(c2 on curve:, on_curve(c2)) secret 1584718 print(base*secret pub:, mul(secret, base) pub) # m c2 - secret*c1 shared mul(secret, c1) neg (shared[0], (-shared[1]) % p) m add(c2, neg) print(m , m) print(m[0]m[1] , m[0]m[1])運行輸出base on curve: True pub on curve: True c1 on curve: True c2 on curve: True base*secret pub: True m (2171002, 3549912) m[0]m[1] 5720914這份獨立實現驗證了三個關鍵事實所有給定點生成元、公鑰、兩段密文都確實位於曲線上base × 1584718 pub私鑰正確解密結果與 SageMath 輸出完全一致。這說明題目的攻擊流程與解密公式可以被任何語言的實現復現不依賴特定工具。延伸當曲線階更大時暴力不再可行本題能暴力破解根本原因是曲線階 (n 7654319) 過小。若階增大到 (2^{160}) 以上暴力枚舉將完全不可行此時需要借助更高效的離散對數算法例如 離散對數 一章中介紹的Baby-step giant-step小步大步法利用中間相遇思想以 (O(\sqrt{n})) 時間與空間折中求解。Pollards ρ 算法以 (O(\sqrt{n})) 時間、(O(1)) 空間的隨機化算法。Pollards kangaroo 算法已知解的取值範圍時更高效。Pohlig-Hellman 算法當群的階是光滑數可分解為多個小素數冪之積時將 DLP 分解到每個小因子子群上求解再以中國剩餘定理組合複雜度為 (O(\sum_i e_i(\log n \sqrt{p_i})))。因此安全橢圓曲線的階必須是大素數或含大素因子正如標準 ElGamal 要求 (p-1) 有大素因子一樣。CTF 中此類「參數過小」題目正是為了訓練選手識別這一安全前提。實戰要點小結識別出題模式題面給出曲線方程、生成元、公鑰與密文要求恢復明文即 ECC-ElGamal 解密先判斷曲線階的大小階很小就直接暴力枚舉私鑰。計算工具SageMath 的EllipticCurve(GF(n), [a1,a2,a3,a4,a6])與點運算、*是最順手的工具不依賴 Sage 時用點加法與二進制快速倍乘的公式即可在任何語言中復現。核心公式解密即 (m C - n_a(x_1,y_1))而 (n_a(x_1,y_1) n_a kG kP_a)安全性完全建立在 ECDLP 之上。參數檢查無論是自建曲線還是解題都要檢查曲線階的因子分解階光滑含小素因子是 ECDLP 被攻破的最常見原因。參考資料本篇主體文檔ecc.md簡體中文版見 docs/zh/docs/crypto/asymmetric/discrete-log/ecc.md離散對數基礎與攻擊算法discrete-log.md標準 ElGamal 加密與其 CTF 實例elgamal.md本題目原題解的公開 writeup 可依題目名「SECCON CTF quals 2013 Cryptanalysis」檢索獲取此處不再列出外部鏈接。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐A2UI Express 格式优化实录run_020 数据路径斜杠预处理如何让评测通过率稳定在 100%A2UI Express 格式优化实录run_020 数据路径斜杠预处理如何让评测通过率稳定在 100% 本篇以 A2UI 仓库中一次完整的迭代优化报告 ev文档网络安全教程Dagger v0.8.5 版本解析listen 会话令牌、DAGGER_CLOUD_TOKEN 与 Secret 挂载模式等变更详解Dagger v0.8.5 版本解析listen 会话令牌、DAGGER_CLOUD_TOKEN 与 Secret 挂载模式等变更详解 本篇基于仓库中的版本变文档网络安全教程PAR Technology 开发者门户迁移实战Scalar 如何支撑一个基于 OpenAPI 与 docs-as-code 的企业级 API 平台PAR Technology 开发者门户迁移实战Scalar 如何支撑一个基于 OpenAPI 与 docs as code 的企业级 API 平台 本文以文档网络安全教程上一篇WeChatMsg3步把Mac微信聊天记录导出成网页、Word和CSV下一篇终极解决方案MacType安装失败日志深度分析与修复指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考