橢圓曲線密碼學(ECC)
橢圓曲線密碼學 Elliptic Curve Cryptography (ECC)
特色優點
- 最早開始發展於1980年中期
- 與 RSA 和離散對數相同的安全級別
- 更少的計算量
- 更短的簽名(signatures)和密鑰(keys)
- trap-door function
- 在同安全級別下，與RSA相比加密可以更快地使用短公鑰
ECC 應用
- TLS/SSL 數位憑證
- 基於身份加密
- 區塊鏈數位簽名
- 序號產生驗證
原理觀念
Ellipse in \(R^2\)
所有點都會分布滿足於 \(ax^2+b^2=c\)
Elliptic curve (non-singular)
橢圓曲線必須滿足下列方程式
\[\begin{align} y^2 = x^3+ax+b \label{eq1} \\ 4a^3+27^2 \neq 0 \label{eq2}\\ \end{align}\]
其中\(4a^3+27^2 \neq 0\)是為了確保\(x^3+ax+b = 0\) 有相異的三個根
together with an imaginary point of infinity O
而在ECC裡，必須嚴格滿足\((x,y) \in \mathbb{Z}_p\)且下列方程式 ( Weierstrass function)
\[\begin{equation} \label{eq3} \begin{aligned} y^2 = x^3+ax+b \mod p \\ 4a^3+27^2 \neq 0 \mod p \\ \end{aligned} \end{equation}\]
Abelian group over \(\epsilon\) (群組規則)
Case 1:\(x_1 \neq x_2\)
畫一條通過兩點P\((x_1,y_2)\)、Q\((x_2,y_2)\)直線L，此時會找到直線與橢圓曲線的交點R'\((x_3,y_3)\)
再透過R'以x軸為對稱軸會找一個R，這個即為所求。
公式化的話可以寫成：
\[\begin{align} P+Q=R \nonumber \\ R'(x_3,y_3) \nonumber \\ x_3= \lambda ^2-x_1-x_2 \nonumber \\ y_3= \lambda (x_1-x_3)-y_1 \nonumber \\ \lambda=\frac{y_2-y_1}{x_2-x_1} \nonumber \\ \end{align}\]
這裡的\(\lambda\)為L斜率
Case 2:\(x_1 = x_2\),\(y_1 \neq y_2\)
此時P跟Q會對稱於X軸，也就是P+Q=O
(O為無窮遠的虛點)
Case 2:\(x_1 = x_2\),\(y_1 = y_2\)
也就是兩點重和的時候，如果\(y_1=0\)就會跟case2一樣。
P+P點則是將橢圓曲線在 P 點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點。
這時L直線的斜率就會變為\(\lambda=\frac{dx}{dy}=\frac{3x^2_1+a}{2y_1}\)
講到這裡一定會覺得這樣很簡單，為何能安全性層級可以這麼高的疑問。
那是因為平常應用時會講橢圓曲線給離散化(如下圖)
在離散有限域超過範圍時，超過的的點就從下面的對稱點往上面直到相交第三點為止
橢圓曲線迪菲-赫爾曼金鑰交換Elliptic Curve Diffie–Hellman key Exchange(ECDH)
- p參數
- G生成數字
- N生成G的順序
- H餘因子
一開始G的斜率等於s這個公式帶入得到為13
\(x_2G\) 為2Gx的斜率
\(y_2G\) 為2Gy的斜率
N=19 有十九個點
此時我們可以透過19個點組成這個曲線生成出點(5, 1) 餘因子為 1
參考資料
- https://ithelp.ithome.com.tw/articles/10251031
- https://youtu.be/F3zzNa42-tQ