發新話題
打印

用Maxima學密碼學-橢圓曲線

推到噗浪
推到臉書

用Maxima學密碼學-橢圓曲線

橢圓曲線加密請見連結介紹,本文僅就例2、例3以\(maxima\)示範計算過程。
https://math.pro/db/attachment.p ... 04&t=1565140250
例子2:在有限體\(F_{23}\)之下,取橢圓曲線\(E\):\(y^2=x^3+16x+10\)上的兩點\(P=(18,14)\)及\(Q=(5,10)\)。若\(P+Q=R=(x_3,y_3)\),則\(R=\)?
例子3:承例子2,若\(P+P=2P=R=(x_3,y_3)\),則\(R=\)?



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)
PointAdd(P,Q):=block
([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

發新話題