# 用Maxima學密碼學－橢圓曲線

## 用Maxima學密碼學－橢圓曲線

https://math.pro/db/attachment.p ... 04&t=1565140250

y^2=x^3+ax+b (mod p)
y^2=x^3+16x+10 (mod 23)的橢圓曲線

(%i1)　[p,a,b]:[23,16,10];
(%o1)　$$\left[ 23,16,10 \right]$$

(%i2)
([lambda,num,denom,inv_denom,x3,y3],
if P=Q then
(print("λ=(3*",x_1^2,"+a)/(2*",y_1,")=",
"(3*",P[1],"^2+",a,")/(2*",P[2],")=",
lambda: (3*P[1]^2+a)/(2*Q[2]))
)
else if P[1]=Q[1] and P[2]#Q[2] then
(print(" P,Q兩點x座標相同,相加結果為無窮遠點"),
return([inf,inf])
)
else
(print("λ=(",y_2,"-",y_1,")/(",x_2,"-",x_1,")=",
"(",Q[2],"-",P[2],")/(",Q[1],"-",P[1],")=",
lambda: (P[2]-Q[2])/(P[1]-Q[1]))
),
num:num(lambda),/*分子*/
denom:denom(lambda),/*分母*/
print(1/denom,"=",inv_denom:inv_mod(denom,p),"(mod",p,")"),
print("λ=",lambda,"=",num,"*",inv_denom,"=",lambda:mod(num*inv_denom,p),"(mod",p,")"),
print(x_3,"=",λ^2,"-",x_1,"-",x_2,"=",lambda^2,"-",P[1],"-",Q[1],"=",
x3:lambda^2-P[1]-Q[1],"=",x3:mod(x3,p),"(mod",p,")"),
print(y_3,"=",λ,"(",x_1,"-",x_3,")-",y_1,"=",lambda,"(",P[1],"-",x3,")-",P[2],"=",
y3:lambda*(P[1]-x3)-P[2],"=",y3:mod(y3,p),"(mod",p,")"),
print("[",x_3,",",y_3,"]=",[x3,y3]),
return([x3,y3])
)$P=(x1,y1)=(18,14) Q=(x2,y2)=(5,10) (%i4) P:[18,14]; Q:[5,10]; (P) $$\left[18,14\right]$$ (Q) $$\left[5,14\right]$$ 計算P+Q=R=(x3,y3) (%i5) PointAdd(P,Q); $$\displaystyle \lambda=(y_2-y_1)/(x_2-x_1)=(10-14)/(5-18)=\frac{4}{13}$$ $$\displaystyle \frac{1}{13}=16\pmod{23}$$ $$\displaystyle \lambda=\frac{4}{13}=4 \cdot 16=18\pmod{23}$$ $$x_3=\lambda^2-x_1-x_2=324-18-5=301=2\pmod{23}$$ $$y_3=\lambda(x_1-x_3)-y_1=18(18-2)-14=274=21\pmod{23}$$ $$\left[x_3,y_3\right]=\left[2,21\right]$$ (%o5) $$\left[2,21\right]$$ 計算P+P=2P=R=(x3,y3) (%i6) PointAdd(P,P); $$\displaystyle \lambda=(3*x_1^2+a)/(2*y_1)=(3*18^2+16)/(2*14)=\frac{247}{7}$$ $$\displaystyle \frac{1}{7}=10\pmod{23}$$ $$\displaystyle \lambda=\frac{247}{7}=247 \cdot 10=9\pmod{23}$$ $$x_3=\lambda^2-x_1-x_2=81-18-18=45=22\pmod{23}$$ $$y_3=\lambda(x_1-x_3)-y_1=9(18-22)-14=-50=19\pmod{23}$$ $$\left[x_3,y_3\right]=\left[22,19\right]$$ (%o6) $$\left[22,19 \right]$$ TOP 例子1：有限體$$F_{23}$$之下，點$$P=(0,1)$$是橢圓曲線$$E$$：$$y^2=x^3+12x+1$$的生成數。  P=(0, 1) 2P = (13, 13) 3P = (5, 5) 4P = (3, 15) 5P = (6, 17) 6P = (19, 2) 7P = (17, 9) 8P = (18, 0) 9P = (17, 14) 10P = (19, 21) 11P = (6, 6) 12P = (3, 8) 13P = (5, 18) 14P = (13, 10) 15P = (0, 22) y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i1) [p,a,b]:[23,12,1]; (%o1) $$\left[ 23,12,1 \right]$$ 橢圓曲線點相加 (%i2) PointAdd(P,Q):=block ([lambda,num,denom,inv_denom,x3,y3], if P=Q then (lambda: (3*P[1]^2+a)/(2*Q[2]) ) else if P[1]=Q[1] and P[2]#Q[2] then (print(" P,Q兩點x座標相同,相加結果為無窮遠點"), return([inf,inf]) ) else (lambda: (P[2]-Q[2])/(P[1]-Q[1]) ), lambda:num(lambda)*inv_mod(denom(lambda),p), x3:mod(lambda^2-P[1]-Q[1],p), y3:mod(lambda*(P[1]-x3)-P[2],p), return([x3,y3]) )$

(%i3)　P:[0,1];
(P)　$$\left[0,1 \right]$$

(%i6)
L:[P]$for k:2 thru 15 do (L:append(L,[PointAdd(last(L),P)]) )$
L;

(%o6)　$$[[0,1],[13,13],[5,5],[3,15],[6,17],[19,2],[17,9],[18,0],[17,14],[19,21],[6,6],[3,8],[5,18],[13,10],[0,22]]$$

P,2P,...,15P位置再加上標籤
(%i7)　Label:create_list(append([concat(i,"P")],(L[ i ]+[1,0])),i,1,length(L));
(Label)　$$\matrix{[[1P,1,1],[2P,14,13],[3P,6,5],[4P,4,15],[5P,7,17],[6P,20,2],[7P,18,9],[8P,19,0],\cr [9P,18,14],[10P,20,21],[11P,7,6],[12P,4,8],[13P,6,18],[14P,14,10],[15P,1,22]]}$$

(%i8)
draw2d(user_preamble="set size square; set grid; set xtics 1; set ytics 1;",
grid=true,
point_type=filled_circle,
points(L),
apply(label,Label));

(%o8)　$$[gr2d(points,label)]$$

TOP

 bugmens 發短消息 加為好友 當前離線 3# 大 中 小 發表於 2019-9-1 17:59  只看該作者 前面兩篇文章利用$$maxima$$程式示範橢圓曲線加法($$P+Q$$)和兩倍($$P+P$$)的運算過程，以及藉由$$\pmod{p}$$將橢圓曲線上的每個點全部打散，讓橢圓曲線離散對數問題($$ECDLP$$)變得難以計算。 其實$$maxima$$已有內建的橢圓曲線程式庫，本篇文章將前面兩篇重新用內建橢圓曲線指令計算。 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_point_p,ec_add (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+16x+10 (mod 23)的橢圓曲線 (%i3) [p,a,b] : [23,16,10]; ec_set_curve(p,a,b); (%o2)　$$[23,16,10]$$ (%o3)　$$true$$ P,Q兩點座標 (%i5) P:[18,14]; Q:[5,10]; (P)　$$[18,14]$$ (Q)　$$[5,10]$$ 檢查P,Q有沒有在橢圓曲線上 (%i7) ec_point_p(P); ec_point_p(Q); (%o6)　$$true$$ (%o7)　$$true$$ 計算P+Q (%i8)　ec_add(P,Q); (%o8)　$$[2,21]$$ 計算P+P (%i9)　ec_add(P,P); (%o9)　$$[22,19]$$ －－－－－－－－－－－－－－－－－－－－－－ 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_mult (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i3) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o2)　$$[23,12,1]$$ (%o3)　$$true$$ 生成數P=[0,1] (%i4)　P:[0,1]; (P)　$$[0,1]$$ 用ec_mult(k,P)計算P,2P,3P,...,15P，結果放在L (%i5)　L:makelist(ec_mult(k,P),k,1,15); (L)　$$[[0,1],[13,13],[5,5],[3,15],[6,17],[19,2],[17,9],[18,0],[17,14],[19,21],[6,6],[3,8],[5,18],[13,10],[0,22]]$$ P,2P,...,15P位置再加上標籤 (%i6)　Label:create_list(append([concat(i,"P")],(L[ i ]+[1,0])),i,1,length(L)); (Label)　$$\matrix{[[1P,1,1],[2P,14,13],[3P,6,5],[4P,4,15],[5P,7,17],[6P,20,2],[7P,18,9],[8P,19,0],\cr [9P,18,14],[10P,20,21],[11P,7,6],[12P,4,8],[13P,6,18],[14P,14,10],[15P,1,22]]}$$ 將P,2P,...,15P各點坐標畫出來 (%i7) draw2d(user_preamble="set size square; set grid; set xtics 1; set ytics 1;",               grid=true,               point_type=filled_circle,               points(L),               apply(label,Label)); (%o7)　$$[gr2d(points,label)]$$ UID210 帖子884 閱讀權限200 在線時間4809 小時 註冊時間2008-12-16 最後登錄2019-9-22  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 4# 大 中 小 發表於 2019-9-7 19:39  只看該作者 上一篇文章以$$y^2=x^3+12x+1 \pmod{23}$$，$$P=[0,1]$$為生成數計算$$1P,2P,\ldots,15P$$，再加上無窮遠點總共16個點。 想要知道有限體上橢圓曲線的點個數，直觀的方法是將$$x=0,1,\ldots,p-1$$代入橢圓曲線方程式$$y^2=x^3+ax+b \pmod{p}$$，以$$jacobi$$符號判斷同餘方程式是否有$$y$$的解，將有$$y$$的解個數加起來就是答案。 關於$$jacobi$$符號請看$$wiki$$介紹 https://zh.wikipedia.org/wiki/%E ... 4%E7%AC%A6%E5%8F%B7 但橢圓曲線點個數計算不需要將各個$$(x,y)$$點坐標算出來，是利用$$jacobi$$符號判斷是否為二次剩餘。 #$$\displaystyle E(F_{p})=p+1+\sum_{x=0}^{p-1} \left(\frac{x^3+ax+b}{p}\right)$$，其中#$$E(F_p)$$為橢圓曲線點個數，$$\displaystyle \left( \frac{}{}\right)$$為$$jacobi$$符號 但這個方法很沒效率，更有效率的方法請看$$wiki$$介紹。 https://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves 另外#$$E(F_p)=p+1-t$$，$$t$$定義為$$Frobenius$$ $$trace$$，elliptic_curves.mac套件中指令為ec_trace() 要先載入elliptic_curves.mac才能呼叫ec_set_curve和ec_trace指令 (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac 要先載入gf.mac才能呼叫msqrt指令(計算二次剩餘的根) (%i2)　load("gf.mac"); (%o2)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/gf/gf.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i4) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o3)　$$[23,12,1]$$ (%o4)　true 以x=0,1,...,p-1計算橢圓曲線點個數 (%i5) EllipticCurveOrder(p,a,b):=block ([count:0,yy,JacobiSymobl], for x:0 thru p-1 do   (print("當x=",x,"時,y"^2,"=",x,""^3,"+",a,"*",x,"+",b,"=",             yy:x^3+a*x+b,"=",yy:mod(yy,p),"(mod ",p,")"),    JacobiSymbol:jacobi(yy,p),/*判斷y^2=yy(mod p)是否有解*/    if JacobiSymbol=0 then/*yy整除p時,有一解*/      (count:count+1,       print("(x,y)=(",x,",",0,")")      )    else if JacobiSymbol=1 then/*用msqrt()計算兩解的值*/       (count:count+2,         Msqrt:msqrt(yy,p),         print("(x,y)=(",x,",",Msqrt[1],"),(",x,",",Msqrt[2],")")        )    else if JacobiSymbol=-1 then       (print("無解"))   ), return(count+1)/*無窮遠點也算進來再+1*/ )$計算橢圓曲線點個數 (%i6) EllipticCurveOrder(p,a,b); 當$$x=0$$時,$$y^2=0^3+12*0+1=1=1\pmod{23}$$ $$(x,y)=(0,1),(0,22)$$ 當$$x=1$$時,$$y^2=1^3+12*1+1=14=14\pmod{23}$$ 無解 當$$x=2$$時,$$y^2=2^3+12*2+1=33=10\pmod{23}$$ 無解 當$$x=3$$時,$$y^2=3^3+12*3+1=64=18\pmod{23}$$ $$(x,y)=(3,15),(3,8)$$ 當$$x=4$$時,$$y^2=4^3+12*4+1=113=21\pmod{23}$$ 無解 當$$x=5$$時,$$y^2=5^3+12*5+1=186=2\pmod{23}$$ $$(x,y)=(5,5),(5,18)$$ 當$$x=6$$時,$$y^2=6^3+12*6+1=289=13\pmod{23}$$ $$(x,y)=(6,17),(6,6)$$ 當$$x=7$$時,$$y^2=7^3+12*7+1=428=14\pmod{23}$$ 無解 當$$x=8$$時,$$y^2=8^3+12*8+1=609=11\pmod{23}$$ 無解 當$$x=9$$時,$$y^2=9^3+12*9+1=838=10\pmod{23}$$ 無解 當$$x=10$$時,$$y^2=10^3+12*10+1=1121=17\pmod{23}$$ 無解 當$$x=11$$時,$$y^2=11^3+12*11+1=1464=15\pmod{23}$$ 無解 當$$x=12$$時,$$y^2=12^3+12*12+1=1873=10\pmod{23}$$ 無解 當$$x=13$$時,$$y^2=13^3+12*13+1=2354=8\pmod{23}$$ $$(x,y)=(13,13),(13,10)$$ 當$$x=14$$時,$$y^2=14^3+12*14+1=2913=15\pmod{23}$$ 無解 當$$x=15$$時,$$y^2=15^3+12*15+1=3556=14\pmod{23}$$ 無解 當$$x=16$$時,$$y^2=16^3+12*16+1=4289=11\pmod{23}$$ 無解 當$$x=17$$時,$$y^2=17^3+12*17+1=5118=12\pmod{23}$$ $$(x,y)=(17,14),(17,9)$$ 當$$x=18$$時,$$y^2=18^3+12*18+1=6049=0\pmod{23}$$ $$(x,y)=(18,0)$$ 當$$x=19$$時,$$y^2=19^3+12*19+1=7088=4\pmod{23}$$ $$(x,y)=(19,2),(19,21)$$ 當$$x=20$$時,$$y^2=20^3+12*20+1=8241=7\pmod{23}$$ 無解 當$$x=21$$時,$$y^2=21^3+12*21+1=9514=15\pmod{23}$$ 無解 當$$x=22$$時,$$y^2=22^3+12*22+1=10913=11\pmod{23}$$ 無解 (%o6) $$16$$ 改用jacobi符號計算橢圓曲線點個數 (%i7) JacobiList:create_list(jacobi(x^3+a*x+b,p),x,0,p-1); (JacobiList) $$\left[1,-1,-1,1,-1,1,1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,1,0,1,-1,-1,-1 \right]$$ jacobi結果全部相加 (%i8) apply("+",JacobiList); (%o8) $$-8$$ 橢圓曲線點個數 (%i9) p+1+%; (%o9) $$16$$ 利用ec_trace()指令直接得到trace值 (%i10) t:ec_trace(); (t) $$8$$ 橢圓曲線點個數 (%i11) p+1-t; (%o11) $$16$$ UID210 帖子884 閱讀權限200 在線時間4809 小時 註冊時間2008-12-16 最後登錄2019-9-22 查看詳細資料 TOP  bugmens 發短消息 加為好友 當前離線 5# 大 中 小 發表於 2019-9-21 10:08 只看該作者 橢圓曲線加密的安全性倚賴橢圓曲線離散對數問題($$Elliptic$$ $$Curve$$ $$Discrete$$ $$Logarithm$$ $$Problem$$，$$ECDLP$$)的困難度上，橢圓曲線離散對數問題敘述如下： 令$$E$$為基於有限體$$F_p$$的橢圓曲線，$$P,Q$$為橢圓曲線上的點坐標($$P,Q \in E(F_p)$$)且$$Q=kP,k \in N$$，當$$p$$很大時，計算$$k$$值非常困難。 解決橢圓曲線離散對數問題的方法會在另一篇文章討論，這裡僅示範暴力搜尋法找出$$k$$值。 elliptic_curves.mac套件中解橢圓曲線離散對數問題的指令為k:ec_log(P,Q); 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_add,ec_point_order,ec_log (%i1) load("elliptic_curves.mac"); (%o1) C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i3) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o2) $$[23,12,1]$$ (%o3) ture 計算橢圓曲線點個數 (%i4) order:p+1-ec_trace(); (order) 16 生成數P=[0,1] (%i5) P:[0,1]; (P) $$[0,1]$$ 計算P的階數n，每個點坐標有不同的階數,但都是橢圓曲線點個數的因數 例如： P=[0,1],階數16,16P=無窮遠點 P=[13,13],階數8,8P=無窮遠點 P=[5,5],階數16,16P=無窮遠點 P=[3,15],階數4,4P=無窮遠點 (%i6) n:ec_point_order(P,order); (n) 16 (%i7) Q:[17,14]; (Q) $$[17,14]$$ 計算2P,3P,...,kP，看何時等於Q (%i9) kP: P$ for k:2 thru n do   (print(k," P=",kP:ec_add(P,kP)),    if kP=Q then       (return(k))   ); $$2P=[13,13]$$ $$3P=[5,5]$$ $$4P=[3,15]$$ $$5P=[6,17]$$ $$6P=[19,2]$$ $$7P=[17,9]$$ $$8P=[18,0]$$ $$9P=[17,14]$$ (%o9)　9 直接呼叫ec_log計算k (%i10)　k:ec_log(P,Q); (k)　9 UID210 帖子884 閱讀權限200 在線時間4809 小時 註冊時間2008-12-16 最後登錄2019-9-22  查看詳細資料 TOP
﻿