橢圓曲線

橢圓曲線是一種存在有限數域的平面曲線,而非存在一般實數域中的平面曲線,
通常為:
y^2 = x^3 + ax +b
而其中
4a3 + 27 b2 ≠ 0
來避免存在奇異點

橢圓曲線的運算

加法:

曲線上的兩點 A,B 相加,就把A和B連成一條線,然後將該線延伸,和曲線相交於點R
再將點R(r1,r2)對x軸做對稱成為-R(r1,-r2)
而該-R點就是A+B的結果

乘法

橢圓曲線的乘法就是做數次加法,今天給定一個係數c和點A
令點B=c⋅A換句話說就是點A和自己做c次的加法

無窮遠點

橢圓曲線會定義無窮遠點O
當點A,B相加但再也不會和曲線相交
則定義A+B=O
而這個無窮遠點就像實數加法的0
所以曲線上A+O=A

曲線基本運算統整

令A,B為橢圓曲線EC上的兩點

• A+B+R=O,所以A+B=-R
• A+(-A)=O,其中-A為A對x軸作對稱
• A+(B+C)=(A+B)+C
• A+B=B+A

在密碼學中的運用

密碼學中的橢圓曲線密碼系列,是將曲線拿去 mod p,而p是一個安全的質數(p:對,又我)
這樣讓曲線上的每一個點的x,y值都會侷限在有限體Fp內部也就是最大不會超過p-1
接著用橢圓曲線中的特性計算
在曲線EG上
B=c⋅A mod p
點B就是點A做c次的加法,再對其mod p
當今天給定B,A,p和曲線EG但沒有c的情況下
很難去算出c為多少
除了暴力硬踹c的值
又是不可逆的運算式
所以又能用來進行非對稱式加密

好處

相較於RSA和DF在同樣等級的安全質數和金鑰下,橢圓曲線能提供更安全的防護

壞處

橢圓曲線密碼是最被量子演算法給威脅的非對稱式加密
而且由於計算複雜,通常不會運用太長的質數和金鑰
(RSA通常為2048bits以上,而橢圓曲線系列通常為256位元而已)