橢圓曲線密碼學 - Elliptic Curve Cryptograph （一）

恩……我不知道大家有沒有學過或知道橢圓曲線。

但如果是我這樣的學渣來說，肯定是不知道這東西的。

當初是因為在學習Diffie–Hellman的時候得知了這東西。

然後也知道了X25519。

橢圓曲線

我們先來說說橢圓曲線的一些特性跟公式：

1. 橢圓曲線方程式：y^2=x^3+ax+b
2. 對稱x軸。
3. a跟b必需要符合：4*a^3 + 27*b^2 != 0，才不會重根。
4. 橢圓曲線會符合圖片上的條件：
   
   圖片來自橢圓曲線 WiKi。
5. 這邊要注意的是當曲線在A的切點上時，為2A。

大概知道橢圓曲線的特性之後，我們來整理一下一些結論。

1. 非垂直的線，穿過曲線後最多只會有3個點。
2. 任意一個點都可以用x來反射出相反的點。
3. 挑選曲線上的A點跟B點可以得到C點反射出-C點。
4. 可以不斷的畫出新的點，並反射出新的點，並連接後得到新的交點。
   
   圖片來自ECC (Elliptic Curve Cryptosystem)

有限域

這個名詞我知道看到的人都很慌張，但其實就是將數學的結果規定在一個定義域裡，因為一般不會直接使用整個實數域。

在我們使用橢圓曲線時，使用『質數』來做有限域。

這樣做之後，會使曲線變成一堆離散的點，而不會有連續的圖。

其公式就會變成：y^2=x^3+ax+b (mod r)

我知道這很抽象，但實際上就是這樣，看一下圖。

圖片由Elliptic Curves over Finite Fields程式生成。

整個離散且隨機分佈化。

橢圓曲線的計算

這邊要進入到數學的部分了，也就是接下來DH會用到的部分。

在橢圓曲線 WiKi裡面其實有寫。

但我還是拿出來講：

1. 先記得曲線公式：y^2=x^3+ax+b (mod K)。
   • 設定了一個有限域K。
2. 設點P(Xp,Yp)和Q(Xq,Yq)。
3. 假設Xp != Xq，設S為(Yp-Yq)/(Xp-Xq) (mod K)。
4. 假設Xp == Xq，設S為(3*Xp^2 - a)/(2*Yp) (mod K)。
   聰明的大家應該知道，3跟4其實就是取斜率。
5. 設R=P+Q。
6. 接下來是一堆數學證明後，我們取得一個結果（證明去Wiki看）。
7. Xr = S^2 - Xp - Xq (mod K)
8. Yr = -Yp + S*(Xp - Xr) (mod K)

好的，我們有了上面的公式之後，我們設定一個起始點為G。
直時我們就能從這個起始點得到R設定為2G。
再從G跟2G得到下一個R稱為3G。
不斷的這樣堆疊稱為xG。

一樣我們先手算一下

我設定a=1,b=-1,K=23
選定G(9,1)
Xp == Xq因此：
S ＝ (3*Xp^2 - a)/(2*Yp) (mod K) ＝ 1
Xr = 1^2 - 1 - 1 = -1
Yr = -11 + 1*(1 - (-1)) = -9
R = (18,14)

橢圓曲線的困難

大家可能會問，那這有什麼困難的地方使得整個加密比質因數分解還難。

那就是G這個東西了，大家應該知道xG就是指：x次的G。

有了G跟xG之後，要反推回x次是十分困難的問題。

並且因為具有阿貝爾群因此可以符合交換率。

所以我有個A次跟B次，生成出來的AG跟BG這兩個。

當我把G跟AG、BG當成公鑰，兩方交換後再也去做BAG跟BAG結果會是相同的。

但中間攻擊的人沒辦法把『AG拆解成G跟A』或是『BG拆解G跟B』。

同時無法把AG跟BG做組合，這也就類似於質因數分解。

橢圓曲線的優勢

這就很有意思了～

我列舉一些優點：

1. 抗攻擊強。
2. 資源佔用少。
3. 加解密速度快。
4. 金鑰很短，卻能提供RSA與之相對的安全性。

而且ECC金鑰長度以線性方式增加，但安全度卻以指數增加，這是多麼優秀的一種方式。

例如：

• 加密128位的安全加密需要：256位的ECC金鑰 同等於 3072位的RSA金鑰。
• 加密128位的安全加密需要：512位的ECC金鑰 同等於 15360位的RSA金鑰。

雖然Wiki上面寫的是，目前的估算認為：

破解256位素數域上的橢圓曲線，需要2330個量子比特與1260億個托佛利門。
使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。

上述一段為Wiki橢圓曲線迪菲-赫爾曼金鑰交換所描述。

但不管怎麼樣，ECC在目前也是主流中的主流了，後量子密碼學也有橢圓曲線的蹤跡，但那就事後話了。

橢圓曲線結論

這一章看起來短短的，但其實很難。

不只不好理解之外，同時這樣的特性跟曲線也是第一次遇到。

我光把這篇文章搞懂就花了不少的時間。

我在寫程式的時候也有發現到一些問題。

接下來我會花時間來探討如何實做這部份，同時把我找到的資料分享出來。

參考資料

橢圓曲線 WiKi

橢圓曲線加密演算法

橢圓曲線密碼學

橢圓曲線迪菲-赫爾曼金鑰交換

Elliptic Curves over Finite Fields

ECC (Elliptic Curve Cryptosystem)

公钥加密算法那些事 | RSA 与 ECC 系统对比

椭圆曲线加密算法（ECC）

補充資料

Elliptic Curve Cryptography Overview Youtube