[閒聊] 2017.W19 - 橢圓曲線加密 ECC

看板NetSecurity (資安資訊安全)作者CMJ0121 (請多指教!!)時間7年前 (2017/05/09 20:58)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串1/1

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://www.ptt.cc/bbs/NetSecurity/M.1494334702.A.07A.html