2017.W19 - 橢圓曲線加密 ECC > 學術介紹 輕鬆了解 ## 前言 ## 橢圓曲線加密 (Elliptic Curve Cryptography, ECC)[0] 是基於橢圓曲線數學的一種公開金要加密演算法 相對於 RSA 可以用較短的金鑰來獲得相等的安全防護 ## 內容 ## 橢圓曲線 (Elliptic Curve)[1] 是數學上一個代數曲線的分類 可以利用通式 : y^2 = x^3 + ax + b 來表示 原則上來說 所有 y 為二次且 x 為三次的多項式函數 都可透過伸縮與平移來獲得通式形式 橢圓曲線有若干特色與性質： 1. 沒有 cusp[2] 與 crunode[3] 2. 假設無窮遠點為 O，則 EC 跟直線必有三個根 相對於 RSA 是把質因數分解[5]當作是破解的困難點 ECC 則是把離散對數 (Discrete Logarithm) [6] 當作是破解的關鍵 給定一個質數 p 給定一個 數字 k 與 c 找到一個 m 滿足 c = m^k (mod p) 是困難的 把兩個概念整合起來 ECC 就是一個在橢圓曲線上的 Galois Field 的運算 其中的運算如下： 0. 無限遠的點為 0 1. P、Q 為 EC 上的一個點 2. P + 0 = P 3. P - P = 0 4. P + Q = -Z, 且 P, Q, Z 在同一個直線且同時為 EC 上的三個根 5. 2*p = P + P，同規則 4 且直線為切線 而 ECDLP (Elliptic Curve Discrete Logarithm Problem) 就是解決 給定一個橢圓曲線 C，並且任意給兩點 P、Q 找到一個 k 滿足 k * P = Q (on C) ## 驗證 ## 用一個 DLP 來當做例子： 假設有一個 GF(23) 也就是可用元素為 0 ~ 22，且所有運算都需要 module 23 計算 4 ^ 5 (mod 23) 是簡單的 用 Python 的語法則會是 pow(4, 5, 23) 計算方式為：4^5 = 4 * 4^4 其中我們可以快速鍵表格 4 = 4 (mod 23) 4^2 = 16 (mod 23) 4^4 = 3 (mod 23) 因此 pow(4, 5, 23) = 12 相反的... x^7 = 7 (mod 23) 要找出來 x 則是困難的 (一個有效的計算方式) 至於 ECDLP 有興趣的人 可以 Google 找相關的資料檢驗他的困難程度 [0]: https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%AF%86%E7%A0%81%E5%AD%A6 [1]: https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF [2]: https://zh.wikipedia.org/wiki/%E5%B0%96%E9%BB%9E [3]: https://en.wikipedia.org/wiki/Crunode [4]: https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F [5]: https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E8%A7%A3 [6]: https://en.wikipedia.org/wiki/Discrete_logarithm --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.122.171 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NetSecurity/M.1494334702.A.07A.html