ECC

Elliptic curves over the real numbers

這邊這教老師要怎麼考

給p跟function：p = 23 曲線: y² = x³ + x + 1 <----後面我簡稱F(x)

首先先找a，b(原式為X³+ax+b)

所以a=1，b=1

首先先檢查點存不存在

將a、b、p帶入 (4*a³+27*b²)mod p

若等於0則無點，若不等於有點才能做下去!!

則測試即為(4*1+27*1)mod 23= 8 <> 0 所以ok

再來找點，

努力記好兩個方程式

y² mod p 以及 F(x)mod p

裡用這兩個找點

將相同的找出來，例如下圖

例如：左邊為將1帶入y² mod 23(那個y就是帶入1)

右邊為將1帶入x³ + x + 1 mod 23(那個x就是帶入1)

那左邊的就是y² mod p

右邊的就是 x³ + x + 1 mod p

然後得到答案，找點

找點方法為，相同答案為一組，例如說

右邊3的答案左邊也有兩個，就是看3然後對到最左邊找座標點為1

然後左邊相同的3對到最左邊為7所以第一個點為(1,7)，然後左邊第二的

相同的3最左邊對過去是16所以第二個點是(1,16)依此類推

部分如下(共有 27個點, 左表0也要計入,少7個點請看倌找找看...)

(1,7)、(1,16)、(3,10)、(3,13)、(5,4)、(5,19)、(6,4)、(6,19)

(7,11)、(7,12)、(9,7)、(9,16)、(11,3)、(12,4)、(12,19)、(13,7)

(13,16)、(17,3)、(18,3)、(19,5)

得到這堆點之後，老師會隨便挑一組點，要你算2P啦或3P啦

方法如下

算2P

給點P(1,7)找3P

Step1：先找2P(就是找(1,7)跟(1,7))

分成(1,7)+(1,7)之後，首先一為P一為Q

P=(Xp,Yp)以及Q=(Xq,Yq)

Xp=1,Yp=7

Xq=1,Yq=7

函數：x³ + x + 1

斜率：因為等於是(1,7)跟(1,7)所以斜率必須用公式二

y'=( 3*(Xp)²+a ) / ( 2*Yp ) mod p 即為 2/7 mod 23

分數mod p 的方式為 先把7x=1 mod p也就是 7x=1 mod 23，x= 10

2再乘上10=20，最後20 mod 23=20就是

然後要求Xr與Yr

Xr公式為Xr=(²-Xp-Xq)mod p

Yr公式為Yr=((Xp-Xr)-Yp)mod p

所以Xr=7，Yr=11

所以2P=(7,11)(為安全起見，可以去檢查這個點有沒有在剛剛找到的點有的話才有可能是對的)