橢圓曲線加法

之前介紹過在幾何上面橢圓曲線加法的方式,但在算術上要怎麼運算?
有一個演算法適用於橢圓曲線的加法,大概如下:
1.今有P、Q兩點在曲線EC上並在有限體Fp中
2.如果P=O(無窮遠點),那P+Q=Q,反之亦然
3.如果兩點都不是O,那令P(x1,y1),Q(x2,y2)
4.如果x1=x2,y1=-y2那麼P+Q=O
5.否則檢查是否P==Q
- 不相等則令tmp=(y2-y1)/(x2-x1)
- 相等則令tmp=(3x1^2+a)/2y1,其中a為曲線EC的係數之一
6.計算x3=tmp^2-x1-x2, y3=tmp(x1-x3)-y1
7.P+Q=(x3,y3)
8.所有的運算都在mod p的條件下

直接用sage.math來算

#python
from sage.all import *
E=EllipticCurve(GF(prime),[a1,a2,a3,a4,a6])
# prime為選定的質數,y^2+a1xy+a3y=x3+a2x2+a4x+a6係數參考
P=E(x1,y1)
Q=E(x2,y2)
#宣告曲線上的兩點P、Q
Sum=P+Q
#直接計算P+Q的結果

只能說,別人寫好的code真香~~

橢圓曲線乘法

1.曲線EC(Fp)和曲線上的一點P和係數n
2.令Q=P和R=O
3.當n>0時重複以下:

• 如果n = 1 mod 2,則令R=R+Q
• 否則令Q=Q+Q,然後n=⌊n/2⌋
  4.最終R=nP
  5.一樣都是在mod p下進行

直接用sage.math來算

#python
from sage.all import *
E=EllipticCurve(GF(prime),[a1,a2,a3,a4,a6])
# prime為選定的質數,y^2+a1xy+a3y=x3+a2x2+a4x+a6係數參考
P=E(x1,y1)
R=n*P
#直接計算R=n*P,其中n為係數

蒙哥馬利階梯法

另一種常見的橢圓曲線乘法演算法,每步所花的時間相同,能避免功率攻擊或是計時攻擊
1.曲線EC(Fp)和曲線上的一點P和係數n,n為一個l-bit的數
2.令R0,R1=P,2P
3.令i從l-2到0
- 如果n(2進位)的第i位是0:
- R0=R0+R0
- R1=R0+R1
- 否則:
- R0=R0+R1
- R1=R1+R1
4.最終R0=nP
5.一樣都是在mod p下進行

用sage就直接一樣給他乘下去