今天要介紹的是 ECC ， ECC 一樣是用基於數學難題，製作出來的安全機制
由於 ECC 本來就是一種艱澀的演算法，因此在內文 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語
像是幾何加法（geometric addition），代數加法（Algebraic addition）、純量乘法 (Scalar multiplication)，阿爾貝群（Abelian group）...等，這些都不是三言兩語可以簡易理解的，都需要一定基礎觀念。
整體用我認為比較簡單扼要的方式進行闡述
之前讀書會分享過ECC 議題，大家也都是聽的一知半解，想把ECC簡潔說明真的很困難 Orz
希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好（？）
ECC 簡介
橢圓曲線密碼學（英語：Elliptic Curve Cryptography，縮寫：ECC）是一種基於橢圓曲線數學的公開密鑰加密演算法。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。
ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性映射，基於Weil對或是Tate對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。
RSA vs ECC 比較
| PKI Algorithm | RSA | ECC |
|---|---|---|
| Key Size | Security: 280 @ 1024-bits | Security: 280 @160-bits |
| Security: 2112 @ 2048-bits | Security: 2112 @224-bits | |
| Security: 2128 @ 3072-bits | Security: 2128 @ 256-bits | |
| Security: 2:92 @ 7680-bits | Security: 2192 @386-bits | |
| Security: 2256 @ 15360-bits | Security: 2256 @512-bits | |
| 安全基礎 | 大數因數分解 | EC橢圖曲線上離散對數 |
| 優點 | 演算法容易說明,且同時可用做加解密 | 運算速度快,簽章長度較小 |
| 缺點 | 運算速度慢,簽章長度較大 | 理論較難理解,且實作技術較為複雜 |
從上表可以總結優點
安全性能更高
160位ECC 和 1024位RSA、DSA有相同的安全强度
處理速度更快
在計算速度上，ECC比RSA、DSA快得多
頻寬要求更低
儲存空間更小
ECC的密鑰大小參數，與RSA、DSA相比要小得多
非對稱加密算法中，之前最廣泛的 RSA 加密方法，逐漸開始被 ECC 取代
區塊鏈是基於 ECC 設計的，例如：使用ECC 製作出公鑰，經過Hash 得到地址，且此過程無法逆推還原
觀念/名詞定義
橢圓曲線
橢圓曲線是由以下形式的方程式定義 的平面曲線
其中a和b是實數。這類稱為 Weierstrass方程式
橢圓曲線運算規則(群組規則)
加法
過曲線上的兩點P、Q畫一條直線，找到直線與橢圓曲線的交點 -R
交點關於x軸對稱位置的點，定義為P Q，即為加法。如下圖所示：PQ = R
乘法定義(兩倍運算)
上述方法無法解釋P P，即兩點重合的情況。因此在這種情況下，將橢圓曲線在 P 點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為P P，即2P，即為二倍運算
無窮遠點
如果將A與-A相加，過A與-A的直線平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點。
橢圓曲線定義
依照上面特性定義後可整理出
橢圓曲線方程式為y2=x3+ax+b
此曲線剛好對稱於**x軸(y=0)**這條直線
參數a及b必需滿足4a3+27b2≠0,才能確保沒有重根, 具有唯一解!
加法單位元素O為一無窮遠的點, 並滿足O=-O
此加法單位元素亦需滿足: 橢圓曲線上某三點共線其合為O
橢圓曲線特性
- 曲線上的任何點都以X軸反射(y=0),並且仍是同樣的曲線 (奇特的對稱性)
- 任何不垂直的線穿過曲線最多只會有三個交點
奇怪的對稱
繪製的橢圓曲線。具有幾個有趣的屬性。
其中之一是水平對稱。曲線上的任何點都可以在x軸上反射並保持相同的曲線。一個更有趣的特性是，任何非垂直線最多將在三個地方與曲線相交。
將橢圓曲線比喻成擊球遊戲, 把球從A點擊向B點,
當再碰撞到曲線上的點後會反彈到(x軸以上或以下)另一邊的C點
先想像成把球在兩個點移動稱為"打點(dot)"
A dot B = C
A dot A = B
A dot C = D
... ... ...
這裡只有兩個點(稱為: 最初點&最終點)
將最初的點P自行打點 n次(as Private Key) 會得到一個最終點Q(as Public Key)
即使你知道"最初點"和"最終點"
要找出n是非常非常之困難!
有限域 (伽羅瓦域)和離散對數
橢圓曲線是連續的，容易被推算，因此，並不適合用於加密；
所以，我們必須把橢圓曲線變成離散的點
把橢圓曲線定義在有限域上，這時就會用到以質數為模的整數域
有限域GF(p)指給定某個質數p，由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算。
假設橢圓曲線為y² = x³ x 1，其在有限域GF(23)上時，寫作：
y² ≡ x³ x 1 (mod 23)
此時，橢圓曲線不再是一條光滑曲線，而是一些不連續的點，如下圖所示。以點(1,7)為例，7² ≡ 1³ 1 1 ≡ 3 (mod 23)。如此還有如下點：
(0,1) (0,22)
(1,7) (1,16)
(3,10) (3,13)
(4,0)
....
就可以使原本看起來是連續的曲線
轉換到有限域上
接著就可以進行貪食蛇遊戲(？)
從A點到B點為不垂直的線穿過曲EC線最多只會有三個交點!
當在碰撞到第三個交點時, 第三個交點一定可以在EC曲線x軸(以上或以下)找到一個對稱點C點
補充：在域空間曲線，大概是這樣的一個感覺
ECC 應用
RSA 同演算法可以直接實現簽章及加密，ECC 需要分別實作
ECDSA (Elliptic Curve Digital Signature Algorithm)
ECIES (Elliptic Curve Integrated Encryption Scheme)
ECDH (Elliptic Curve Diffie–Hellman key Exchange)
ECC 簡易定義及運作流程
計算實例
設定出一個有限域Fp
略過選取曲線，和給定參數過程計算後
曲線已知E23(1,1)上兩點P(3,10)，Q(9,7)，求(1)-P，(2)P+Q，(3) 2P
圖片來源 https://www.zhihu.com/question/26662683
如果橢圓曲線上一點P，存在最小的正整數n使得數乘nP=O∞ ,則將n稱為P的階
若n不存在，則P是無限階的
圖片來源 https://www.zhihu.com/question/26662683
因此選定 n 後即可 計算出可得27P=-P
所以28P=O ∞ P的階為28
這些點做成了一個循環阿貝爾群，其中生成元為P，階數為29
並從裡面選取基點，並開始計算
考慮K=kG ，其中K、G為橢圓曲線Ep(a,b)上的點，n為G的階（nG=O∞），k為小於n的整數。
則給定k和G，根據加法法則，計算K很容易
但反過來，給定K和G，求k就非常困難
其中k、K分別為私鑰、公鑰。
這就是橢圓曲線計算流程
一條橢圓曲線 {p,a,b,G,n,h}
- p : 一個質數 決定域
- a , b : 曲線參數
- G : 基點
- n : G的階
- h : 商除整數
橢圓曲線加解密演算法原理 ECIES
設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。
公鑰加密：
選擇隨機數r，將訊息M生成密文C，該密文是一個點對，即：
C = {rG, M rK}，其中K為公鑰
私鑰解密：
M rK – k(rG) = M r(kG) – k(rG) = M
其中k、K分別為私鑰、公鑰。
橢圓曲線上的已知G和xG求x，是非常困難的，此即為橢圓曲線上的的離散對數問題。此處x即為私鑰，xG即為公鑰。
橢圓曲線簽名演算法原理 ECDSA
設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。
私鑰簽名：
1、選擇隨機數r，計算點rG(x, y)。
2、根據隨機數r、訊息M的雜湊h、私鑰k，計算s = (h kx)/r。
3、將訊息M、和簽名{rG, s}發給接收方
公鑰驗證簽名：
1、接收方收到訊息M、以及簽名{rG=(x,y), s}。
2、根據訊息求雜湊h。
3、使用傳送方公鑰K計算：hG/s xK/s，並與rG比較，如相等即驗籤成功
原理如下：
hG/s xK/s = hG/s x(kG)/s = (h xk)G/s
= r(h xk)G / (h kx) = rG
ECC 安全性
ECC 一樣採用數學難題，進行設計，但難度比REA 質因數分寫還要難，而且運算比RSA 還要快
使用 ECDH (Elliptic Curve Diffie–Hellman key Exchange)舉例
定義了一條橢圓曲線 
因此 n = 19 , h = 1
圖片來源 :https://www.youtube.com/watch?v=F3zzNa42-tQ
詳細計算可以觀看影片
現實上，計算實會選用大的數字和質數，使其幾乎無法反推計算
ECC 應用
- TLS/SSL 數位憑證
- 基於身份加密
- 區塊鏈數位簽名
- 序號產生驗證
小結
ECC 一樣是用基於數學難題，製作出來的安全機制
我在 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語
像是幾何加法（geometric addition），代數加法（Algebraic addition）、純量乘法 (Scalar multiplication)，阿爾貝群（Abelian group）...等，這些都不是三言兩語可以簡易理解的，都需要一定基礎觀念。
整體用我認為比較簡單扼要的方式進行闡述
之前讀書會分享過ECC 議題，大家也都是聽的一知半解，想把ECC簡潔說明真的很困難 Orz
希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好（？）
參考資料
https://en.wikipedia.org/wiki/Elliptic_curve
https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
Elliptic Curve Cryptography: a gentle introduction
Elliptic Curve Cryptography: finite fields and discrete logarithms
Elliptic Curve Cryptography: ECDH and ECDSA
Elliptic Curve Cryptography: breaking security and a comparison with RSA
https://combohuang.pixnet.net/blog/post/212457468-ecc-(elliptic-curve-cryptosystem)
https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/43964/
