11 12
發新話題
打印

用Maxima學密碼學-橢圓曲線

推到噗浪
推到臉書
上一篇文章在\(F[2]/(x^4+x+1)\)Galois體之下,點\(P=(g^3,g^9)=(x^3,x^3+x)\)是橢圓曲線\(E\):\(y^2+xy=x^3+g^8x^2+g^2\)的生成數計算\(1P,2P,\ldots,15P\),再加上無窮遠點總共16個點。

想要知道有限體上橢圓曲線的點個數,直觀的方法是將\(x=0,1,g^1,g^2,\dots,g^{14}\)代入橢圓曲線方程式\(y^2+xy=x^3+ax^2+b\),解出\(y\)的解,將有\(y\)的解個數加起來就是答案。

將方程式\(y^2+xy=x^3+ax^2+b\)同除\(x^2\)得到\(\displaystyle \left(\frac{y}{x}\right)^2+\left(\frac{y}{x}\right)=x+a+\frac{b}{x^2}\)
令\(\displaystyle z=\frac{y}{x}\),\(\displaystyle \beta=x+a+\frac{b}{x^2}\)得到\(z^2+z=\beta\),\(z^2+z-\beta=0\),\(z^2+z+\beta=0\)
利用這裡的方法(\(maxima\)指令為f2_solve_quadratic(\(\beta\),n))解出\(z\),再計算\(y=z\cdot x\)解出\(y的解\)。



要先載入elliptic_curves.mac才能呼叫ec2_set_curve,f2_solve_quadratic
(%i1) load("elliptic_curves.mac");
(%o1) C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac

numth.lisp取代原本的檔案C:\maxima-5.43.0\share\maxima\5.43.0\src\numth.lisp
讓更正的程式碼能重新載入

(%i2) load("numth.lisp");
(%o2) C:/maxima-5.43.0/share/maxima/5.43.0/src/numth.lisp

\(F[2](x^4+x+1)\)的Galois體
(%i3) gf_set_data(2,4);
(%o3) Structure [GF-DATA]

\(F[2]/(x^4+x+1)\)不可約多項式為\(x^4+x+1\),元素個數16個
(%i4) [p,ReductionPoly,g,n,m]:gf_infolist();
(%o4) \([2,x^4+x+1,x,16,15]\)

產生\(g^1,g^2,\ldots,g^{15}\)
(%i5) g:create_list(gf_exp(g,i),i,1,n-1);
(g) \([x,x^2,x^3,x+1,x^2+x,x^3+x^2,x^3+x+1,x^2+1,x^3+x,x^2+x+1,x^3+x^2+x,x^3+x^2+x+1,x^3+x^2+1,x^3+1,1]\)

\(y^2+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}\)的橢圓曲線
(%i8)
a:g[8];
b:g[2];
ec2_set_curve(ReductionPoly,gf_p2n(a),gf_p2n(b));

(a) \(x^2+1\)
(b) \(x^2\)
(%o8) true

分式的分子和分母係數超過2以\(\pmod{2}\)化簡
(%i9)
PolyMod2(poly,PrintList):=block
([numpoly:num(poly),denompoly:denom(poly),numpolymod2,denompolymod2],
numpolymod2:polymod(numpoly,2),/*分子多項式對2同餘*/
denompolymod2:polymod(denompoly,2),/*分母多項式對2同餘*/
if denompoly=1 then/*分母為1,是多項式*/
    (if numpoly#numpolymod2 then
        (PrintList:append(PrintList,["=",poly:numpolymod2]))
    )
else
    (if numpoly#numpolymod2 or denompoly#denompolymod2 then
       (PrintList:append(PrintList,["=",poly:numpolymod2/denompolymod2]))
    ),
return([poly,PrintList])
)$


分式的分子和分母超過4次方以\(\pmod{x^4+x+1}\)化簡
(%i10)
PolyModGF(poly,PrintList):=block
([numpoly:num(poly),denompoly:denom(poly),numpolymodGF,denompolymodGF],
numpolymodGF:polymod(remainder(numpoly,ReductionPoly),2),/*分子多項式對x^4+x+1同餘*/
denompolymodGF:polymod(remainder(denompoly,ReductionPoly),2),/*分母多項式對x^4+x+1同餘*/
if denompoly=1 then/*分母為1,是多項式*/
   (if numpoly#numpolymodGF then
        (PrintList:append(PrintList,["=",poly:numpolymodGF]))
   )
else/*分母不為1是分式,針對分子和分母分開對x^4+x+1同餘*/
  (if numpoly#numpolymodGF or denompoly#denompolymodGF then
     (PrintList:append(PrintList,["=",poly:numpolymodGF/denompolymodGF]))
  ),
return([poly,PrintList])
)$


針對分式的分母求反元素
(%i11)
Inverse(poly,PrintList):=block
([numpoly:num(poly),denompoly:denom(poly)],
if denompoly#1 then/*分母不為1才需要計算反元素*/
  (PrintList:append(PrintList,["=(",numpoly,")(",gf_inv(denompoly),")"]),
   PrintList:append(PrintList,["=",poly:expand(numpoly*gf_inv(denompoly))]),
   [poly,PrintList]: PolyMod2(poly,PrintList),
   [poly,PrintList]: PolyModGF(poly,PrintList)
  ),
return([poly,PrintList])
)$


用大寫\(X,Y\)代表橢圓曲線,\(Y^2+XY=X^3+aX^2+b\)
用大寫\(\displaystyle Z=\frac{Y}{X}\)的變數變換
用小寫\(x\)代表Galois體運算符號

(%i12)
EllipticCurveOrder(ReductionPoly,a,b):=block
([count:0,beta,PrintList,X,Y:[0,0],Z:[0,0]],
print("當X=0時,Y"^2,"+XY=X"^3,"+aX"^2,"+b=>Y"^2,"=b"),
print("解方程式Y"^2,"=b,得Y=b^2^",(n-1),"=(",b,")^2^",(n-1),"=(",b,")"^2^(n-1),"=",Y[1]:gf_exp(b,2^(n-1))),
print("(X,Y)=(0,",Y[1],")=(0,","g"^gf_index(Y[1]),")"),
count:count+1,/*當X=0時,Y只有一解(重根)*/
for i:1 thru m do/*m為gf_infolist()除了0之外的Galois體的元素個數*/
   (print("-----------"),
    print("當X=",X:g[ i ],"時"),
    PrintList:["β=X+a+","b"/"X"^2,"=(",X,")+(",a,")+",b/X^2,"=",beta:X+a+b/X^2],
    if b/X^2#ratsimp(b/X^2) then
      (PrintList:append(PrintList,["=",beta:X+a+expand(b/X^2)])),
    if denom(beta:ratsimp(beta))#1 then/*把帶方式換成假分式*/
      (PrintList:append(PrintList,["=",beta])),
    [beta,PrintList]: PolyMod2(beta,PrintList),/*若係數大於2,同餘2*/
    [beta,PrintList]: PolyModGF(beta,PrintList),/*若超過4次方,同餘x^4+x+1*/
    [beta,PrintList]:Inverse(beta,PrintList),/*若λ為分式,將分母取反元素後和分子相乘*/
    apply(print,PrintList),
    print("解方程式Z"^2,"+Z+β=Z"^2,"+Z+(",beta,")=0"),
    Z:f2_solve_quadratic(gf_p2n(beta),hipow(ReductionPoly,x)),
    if Z=false then
      (print("Z無解")
      )
    else
      (print("Z=",Z:[gf_n2p(Z[1]),gf_n2p(Z[2])]),
       PrintList:["Y1=Z1*X=(",Z[1],")(",X,")=",Y[1]:expand(Z[1]*X)],
       [Y[1],PrintList]: PolyMod2(Y[1],PrintList),/*若係數大於2,同餘2*/
       [Y[1],PrintList]: PolyModGF(Y[1],PrintList),/*若超過4次方,同餘x^4+x+1*/
       [Y[1],PrintList]:Inverse(Y[1],PrintList),/*若λ為分式,將分母取反元素後和分子相乘*/
       apply(print,PrintList),
       PrintList:["Y2=Z2*X=(",Z[2],")(",X,")=",Y[2]:expand(Z[2]*X)],
       [Y[2],PrintList]: PolyMod2(Y[2],PrintList),/*若係數大於2,同餘2*/
       [Y[2],PrintList]: PolyModGF(Y[2],PrintList),/*若超過4次方,同餘x^4+x+1*/
       [Y[2],PrintList]:Inverse(Y[2],PrintList),/*若λ為分式,將分母取反元素後和分子相乘*/
       apply(print,PrintList),
       print("(X,Y)=(",X,",",Y[1],")=(","g"^gf_index(X),",",if Y[1]=0 then 0 else "g"^gf_index(Y[1]),")和",
                           "(",X,",",Y[2],")=(","g"^gf_index(X),",",if Y[2]=0 then 0 else "g"^gf_index(Y[2]),")"),
       count:count+2
      )
   ),
return(count+1)/*無窮遠點也算進來再+1*/
)$


以\(x=0,1,g^1,\ldots,g^{14}\)計算橢圓曲線點個數
(%i13) EllipticCurveOrder(ReductionPoly,a,b);
當\(X=0\)時,\(Y^2+XY=X^3+aX^2+b\)=>\(Y^2=b\)
解方程式\(Y^2=b\),得\(Y={b^2}^{15}={(x^2)^2}^{15}=(x^2)^{32768}=x\)
\((X,Y)=(0,x)=(0,g)\)
-----------
當\(X= x \)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x)+(x^2+1)+1=x^2+x+2=x^2+x\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^2+x)=0\)
\(Z=[x+1,x]\)
\(Y1=Z1*X=(x+1)(x)=x^2+x\)
\(Y2=Z2*X=(x)(x)=x^2\)
\((X,Y)=(x,x^2+x)=(g,g^5)\)和\((x,x^2)=(g,g^2)\)
-----------
當\(X=x^2\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^2)+(x^2+1)+\frac{1}{x^2}=2x^2+\frac{1}{x^2}+1=\frac{2x^4+x^2+1}{x^2}=\frac{x^2+1}{x^2}=(x^2+1)(x^3+x^2+1)\)
\(=x^5+x^4+x^3+2x^2+1=x^5+x^4+x^3+1=x^3+x^2\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2)=0\)
\(Z\)無解
-----------
當\(X= x^3\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3)+(x^2+1)+\frac{1}{x^4}=x^3+x^2+\frac{1}{x^4}+1=\frac{x^7+x^6+x^4+1}{x^4}=\frac{x^2+1}{x+1}=(x^2+1)(x^3+x^2+x)\)
\(=x^5+x^4+2x^3+x^2+x=x^5+x^4+x^2+x=x+1\)
解方程式\(Z^2+Z+\beta=Z^2+Z+( x+1 )=0\)
\(Z=[x^3+x^2+1,x^3+x^2]\)
\(Y1=Z1*X=(x^3+x^2+1)(x^3)=x^6+x^5+x^3=x\)
\(Y2=Z2*X=(x^3+x^2)(x^3)=x^6+x^5=x^3+x\)
\((X,Y)=(x^3,x)=(g^3,g)\)和\((x^3,x^3+x)=(g^3,g^9)\)
-----------
當\(X=x+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x+1)+(x^2+1)+\frac{x^2}{(x+1)^2}=\frac{x^2}{(x+1)^2}+x^2+x+2=\frac{x^2}{x^2+2x+1}+x^2+x+2=\frac{x^4+3x^3+6x^2+5x+2}{x^2+2x+1}\)
\(\displaystyle =\frac{x^4+x^3+x}{x^2+1}=\frac{x^3+1}{x^2+1}=(x^3+1)(x^3+x+1)=x^6+x^4+2x^3+x+1=x^6+x^4+x+1=x^3+x^2\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2)=0\)
\(Z\)無解
-----------
當\(X=x^2+x\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^2+x)+(x^2+1)+\frac{x^2}{(x^2+x)^2}=\frac{x^2}{(x^2+x)^2}+2x^2+x+1=\frac{x^2}{x^4+2x^3+x^2}+2x^2+x+1\)
\(\displaystyle =\frac{2x^4+5x^3+5x^2+3x+2}{x^2+2x+1}=\frac{x^3+x^2+x}{x^2+1}=(x^3+x^2+x)(x^3+x+1)=x^6+x^5+2x^4+2x^3+2x^2+x=x^6+x^5+x=x^3\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3)=0\)
\(Z\)無解
-----------
當\(X=x^3+x^2\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x^2)+(x^2+1)+\frac{x^2}{(x^3+x^2)^2}=\frac{x^2}{(x^3+x^2)^2}+x^3+2x^2+1=\frac{x^2}{x^6+2x^5+x^4}+x^3+2x^2+1\)
\(\displaystyle =\frac{x^7+4x^6+5x^5+3x^4+2x^3+x^2+1}{x^4+2x^3+x^2}=\frac{x^7+x^5+x^4+x^2+1}{x^4+x^2}=\frac{x^3+x+1}{x^2+x+1}=(x^3+x+1)(x^2+x)\)
\(=x^5+x^4+x^3+2x^2+x=x^5+x^4+x^3+x=x^3+x^2+x+1\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2+x+1)=0\)
\(Z\)無解
-----------
當\(X=x^3+x+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x+1)+(x^2+1)+\frac{x^2}{(x^3+x+1)^2}=\frac{x^2}{(x^3+x+1)^2}+x^3+x^2+x+2\)
\(\displaystyle =\frac{x^2}{x^6+2x^4+2x^3+x^2+2x+1}+x^3+x^2+x+2=\frac{x^9+x^8+3x^7+6x^6+5x^5+9x^4+8x^3+6x^2+5x+2}{x^6+2x^4+2x^3+x^2+2x+1}\)
\(\displaystyle =\frac{x^9+x^8+x^7+x^5+x^4+x}{x^6+x^2+1}=\frac{x+1}{x^3+1}=(x+1)(x)=x^2+x\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^2+x)=0\)
\(Z=[x+1,x]\)
\(Y1=Z1*X=(x+1)(x^3+x+1)=x^4+x^3+x^2+2x+1=x^4+x^3+x^2+1=x^3+x^2+x\)
\(Y2=Z2*X=(x)(x^3+x+1)=x^4+x^2+x=x^2+1\)
\((X,Y)=(x^3+x+1,x^3+x^2+x)=(g^7,g^{11})\)和\((x^3+x+1,x^2+1)=(g^7,g^8)\)
-----------
當\(X=x^2+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^2+1)+(x^2+1)+\frac{x^2}{(x^2+1)^2}=\frac{x^2}{(x^2+1)^2}+2x^2+2=\frac{x^2}{x^4+2x^2+1}+2x^2+2=\frac{2x^6+6x^4+7x^2+2}{x^4+2x^2+1}=\frac{x^2}{x^4+1}=x\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x)=0\)
\(Z=[x^3+x,x^3+x+1]\)
\(Y1=Z1*X=(x^3+x)(x^2+1)=x^5+2x^3+x=x^5+x=x^2\)
\(Y2=Z2*X=(x^3+x+1)(x^2+1)=x^5+2x^3+x^2+x+1=x^5+x^2+x+1=1\)
\((X,Y)=(x^2+1,x^2)=(g^8,g^2)\)和\((x^2+1,1)=(g^8,1)\)
-----------
當\(X=x^3+x\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x)+(x^2+1)+\frac{x^2}{(x^3+x)^2}=\frac{x^2}{(x^3+x)^2}+x^3+x^2+x+1=\frac{x^2}{x^6+2x^4+x^2}+x^3+x^2+x+1\)
\(\displaystyle =\frac{x^7+x^6+3x^5+3x^4+3x^3+3x^2+x+2}{x^4+2x^2+1}=\frac{x^7+x^6+x^5+x^4+x^3+x^2+x}{x^4+1}=\frac{x^3+x^2}{x}=(x^3+x^2)(x^3+1)=x^6+x^5+x^3+x^2=x^2+x\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^2+x)=0\)
\(Z=[x+1,x]\)
\(Y1=Z1*X=(x+1)(x^3+x)=x^4+x^3+x^2+x=x^3+x^2+1\)
\(Y2=Z2*X=(x)(x^3+x)=x^4+x^2=x^2+x+1\)
\((X,Y)=(x^3+x,x^3+x^2+1)=(g^9,g^{13})\)和\((x^3+x,x^2+x+1)=(g^9,g^{10})\)
-----------
當\(X=x^2+x+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^2+x+1)+(x^2+1)+\frac{x^2}{(x^2+x+1)^2}=\frac{x^2}{(x^2+x+1)^2}+2x^2+x+2=\frac{x^2}{x^4+2x^3+3x^2+2x+1}+2x^2+x+2\)
\(\displaystyle =\frac{2x^6+5x^5+10x^4+11x^3+11x^2+5x+2}{x^4+2x^3+3x^2+2x+1}=\frac{x^5+x^3+x^2+x}{x^4+x^2+1}=\frac{x^3}{x^2+x}=(x^3)(x^2+x+1)=x^5+x^4+x^3=x^3+x^2+1\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2+1)=0\)
\(Z\)無解
-----------
當\(X=x^3+x^2+x\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x^2+x)+(x^2+1)+\frac{x^2}{(x^3+x^2+x)^2}=\frac{x^2}{(x^3+x^2+x)^2}+x^3+2x^2+x+1\)
\(\displaystyle =\frac{x^2}{x^6+2x^5+3x^4+2x^3+x^2}+x^3+2x^2+x+1=\frac{x^7+4x^6+8x^5+11x^4+10x^3+7x^2+3x+2}{x^4+2x^3+3x^2+2x+1}\)
\(\displaystyle =\frac{x^7+x^4+x^2+x}{x^4+x^2+1}=\frac{x^3+x^2+x}{x^2+x}=(x^3+x^2+x)(x^2+x+1)= x^5+2x^4+3x^3+2x^2+x=x^5+x^3+x=x^3+x^2\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2)=0\)
\(Z\)無解
-----------
當\(X=x^3+x^2+x+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x^2+x+1)+(x^2+1)+\frac{x^2}{(x^3+x^2+x+1)^2}=\frac{x^2}{(x^3+x^2+x+1)^2}+x^3+2x^2+x+2\)
\(\displaystyle =\frac{x^2}{x^6+2x^5+3x^4+4x^3+3x^2+2x+1}+x^3+2x^2+x+2=\frac{x^9+4x^8+8x^7+14x^6+18x^5+18x^4+16x^3+11x^2+5x+2}{x^6+2x^5+3x^4+4x^3+3x^2+2x+1}\)
\(\displaystyle =\frac{x^9+x^2+x}{x^6+x^4+x^2+1}=\frac{x^3+x^2}{x^3+x}=(x^3+x^2)(x^3+x^2)=x^6+2x^5+x^4=x^6+x^4=x^3+x^2+x+1\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2+x+1)=0\)
\(Z\)無解
-----------
當\(X=x^3+x^2+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+x^2+1)+(x^2+1)+\frac{x^2}{(x^3+x^2+1)^2}=\frac{x^2}{(x^3+x^2+1)^2}+x^3+2x^2+2\)
\(\displaystyle =\frac{x^2}{x^6+2x^5+x^4+2x^3+2x^2+1}+x^3+2x^2+2=\frac{x^9+4x^8+5x^7+6x^6+10x^5+6x^4+5x^3+7x^2+2}{x^6+2x^5+x^4+2x^3+2x^2+1}\)
\(\displaystyle =\frac{x^9+x^7+x^3+x^2}{x^6+x^4+1}=\frac{x^3+x^2+1}{x^3+x^2+x}=(x^3+x^2+1)(x+1)=x^4+2x^3+x^2+x+1=x^4+x^2+x+1=x^2\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^2)=0\)
\(Z=[x^3+1,x^3]\)
\(Y1=Z1*X=(x^3+1)(x^3+x^2+1)=x^6+x^5+2x^3+x^2+1=x^6+x^5+x^2+1=x^3+x^2+x+1\)
\(Y2=Z2*X=(x^3)(x^3+x^2+1)=x^6+x^5+x^3=x\)
\((X,Y)=(x^3+x^2+1,x^3+x^2+x+1)=(g^{13},g^{12})\)和\((x^3+x^2+1,x)=(g^{13},g)\)
-----------
當\(X=x^3+1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(x^3+1)+(x^2+1)+\frac{x^2}{(x^3+1)^2}=\frac{x^2}{(x^3+1)^2}+x^3+x^2+2=\frac{x^2}{x^6+2x^3+1}+x^3+x^2+2\)
\(\displaystyle =\frac{x^9+x^8+4x^6+2x^5+5x^3+2x^2+2}{x^6+2x^3+1}=\frac{x^9+x^8+x^3}{x^6+1}=\frac{x^2+x+1}{x^3+x^2+1}=(x^2+x+1)(x^2)=x^4+x^3+x^2=x^3+x^2+x+1\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(x^3+x^2+x+1)=0\)
\(Z\)無解
-----------
當\(X=1\)時
\(\displaystyle \beta=X+a+\frac{b}{X^2}=(1)+(x^2+1)+x^2=2x^2+2=0\)
解方程式\(Z^2+Z+\beta=Z^2+Z+(0)=0\)
\(Z=[0,1]\)
\(Y1=Z1*X=(0)(1)=0\)
\(Y2=Z2*X=(1)(1)=1\)
\((X,Y)=(1,0)=(1,0)\)和\((1,1)=(1,1)\)
(%o13) 16

TOP

 11 12
發新話題