14 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)
CountingPoints(ReductionPoly,a,b):=block
([count:1,Points:[[inf,inf]]/*將無窮遠點先放入*/,Degree,beta,PrintList,X,Y:[0,0],Z:[0,0]],
print("當X=0時,Y"^2,"+XY=X"^3,"+aX"^2,"+b=>Y"^2,"=b"),
Degree:hipow(ReductionPoly,x),
print("解方程式Y"^2,"=b,得Y=b^2^",(Degree-1),"=(",b,")^2^",(Degree-1),"=(",b,")"^2^(Degree-1),"=",Y[1]:gf_exp(b,2^(Degree-1))),
print("(X,Y)=(0,",Y[1],")=(0,","g"^gf_index(Y[1]),")"),
Points:append(Points,[[0,gf_exp(b,2^(Degree-1))]]),/*當X=0時Y=b^2^(Degree-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),Degree),
    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]),")"),
       Points:append(Points,[[X,Y[1]],[X,Y[2]]]),
       count:count+2
      )
   ),
return([count,Points])
)$


以\(x=0,1,g^1,\ldots,g^{14}\)計算橢圓曲線點個數
(%i13) CountingPoints(ReductionPoly,a,b);
當\(X=0\)時,\(Y^2+XY=X^3+aX^2+b\)=>\(Y^2=b\)
解方程式\(Y^2=b\),得\(Y={b^2}^{3}={(x^2)^2}^{3}=(x^2)^{8}=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) \(\matrix{[16,[[\infty,\infty],[0,x],[x,x^2],[x,x^2+x],[x^3,x^3+x],[x^3,x],[x^3+x+1,x^2+1],[x^3+x+1,x^3+x^2+x],[x^2+1,x^2],\cr
[x^2+1,1],[x^3+x,x^2+x+1],[x^3+x,x^3+x^2+1],[x^3+x^2+1,x],[x^3+x^2+1,x^3+x^2+x+1],[1,0],[1,1]]]}\)

TOP

將上一篇文章濃縮成一個副程式



要先載入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

計算橢圓曲線點個數和坐標副程式
(%i3)
CountingPoints(ReductionPoly,a,b):=block
([count:1,Points:[[inf,inf]]/*將無窮遠點先放入*/,p,g,n,m,Degree,beta,X,Z:[0,0]],
gf_set_data(2,ReductionPoly),/*F[2]/(x^4+x+1)的Galois體*/
[p,ReductionPoly,g,n,m]:gf_infolist(),
ec2_set_curve(ReductionPoly,gf_p2n(a),gf_p2n(b)),/*設定橢圓曲線參數*/
Degree:hipow(ReductionPoly,x),/*x^4+x+1的最高次方Degree=4*/
Points:append(Points,[[0,gf_exp(b,2^(Degree-1))]]),/*當X=0時Y=b^2^(Degree-1)*/
count:count+1,/*當X=0時,Y只有一解(重根)*/
for i:1 thru m do/*m為gf_infolist()除了0之外的Galois體的元素個數*/
   (X:gf_exp(g,i),/*X坐標*/
    beta:gf_add(gf_add(X,a),gf_div(b,gf_mult(X,X))),/*計算β=X+a+b/X^2*/
    Z:f2_solve_quadratic(gf_p2n(beta),Degree),/*解方程式Z^2+Z+β=0*/
    if Z#false then/*若Z有解*/
      (Z:[gf_n2p(Z[1]),gf_n2p(Z[2])],
       Points:append(Points,[[X,gf_mult(X,Z[1])],[X,gf_mult(X,Z[2])]]),/*計算Y=X*Z得到Y坐標*/
       count:count+2/*得到2個點坐標*/
      )
   ),
return([count,Points])
)$


計算\(Y^2+XY=X^3+aX^2+b\pmod{2}\pmod{x^4+x+1}\)橢圓曲線的點個數和坐標
\(a=x^2+1,b=x^2\)

(%i4) [count,Points]:CountingPoints(x^4+x+1,x^2+1,x^2);
(%o4) \(\matrix{[16,[[\infty,\infty],[0,x],[x,x^2],[x,x^2+x],[x^3,x^3+x],[x^3,x],[x^3+x+1,x^2+1],[x^3+x+1,x^3+x^2+x],[x^2+1,x^2],\cr
[x^2+1,1],[x^3+x,x^2+x+1],[x^3+x,x^3+x^2+1],[x^3+x^2+1,x],[x^3+x^2+1,x^3+x^2+x+1],[1,0],[1,1]]]}\)

計算以不同的不可分解多項式p(x)的\(Y^2+XY=X^3+aX^2+b\pmod{2}\pmod{p(x)}\)橢圓曲線點個數
\(a=0,b=1\)

(%i7)
a:0$
b:1$
for k:1 thru 10 do
  (gf_set_data(2,k),
   [p,ReductionPoly,g,n,m]:gf_infolist(),
   print("Y"^2,"+XY=X"^3,"+",a,"X"^2,"+",b,"(mod 2) (mod",ReductionPoly,")",
           ",橢圓曲線點個數#E(F",2,""^k,")=",CountingPoints(ReductionPoly,a,b)[1])
  )$

\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x}\),橢圓曲線點個數#\(E(F_{2})=4\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^2+x+1}\),橢圓曲線點個數#\(E(F_{2^2})=8\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^3+x+1}\),橢圓曲線點個數#\(E(F_{2^3})=4\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^4+x+1}\),橢圓曲線點個數#\(E(F_{2^4})=16\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^5+x^2+1}\),橢圓曲線點個數#\(E(F_{2^5})=44\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^6+x+1}\),橢圓曲線點個數#\(E(F_{2^6})=56\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^7+x+1}\),橢圓曲線點個數#\(E(F_{2^7})=116\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^8+x^4+x^3+x+1}\),橢圓曲線點個數#\(E(F_{2^8})=288\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^9+x+1}\),橢圓曲線點個數#\(E(F_{2^9})=508\)
\(Y^2+XY=X^3+0X^2+1 \pmod{2} \pmod{x^{10}+x^3+1}\),橢圓曲線點個數#\(E(F_{2^{10}})=968\)

計算以不同的不可分解多項式p(x)的\(Y^2+XY=X^3+aX^2+b\pmod{2}\pmod{p(x)}\)橢圓曲線點個數
\(a=1,b=1\)

(%i10)
a:1$
b:1$
for k:1 thru 10 do
  (gf_set_data(2,k),
   [p,ReductionPoly,g,n,m]:gf_infolist(),
   print("Y"^2,"+XY=X"^3,"+",a,"X"^2,"+",b,"(mod 2) (mod",ReductionPoly,")",
           ",橢圓曲線點個數#E(F",2,""^k,")=",CountingPoints(ReductionPoly,a,b)[1])
  )$

\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x}\),橢圓曲線點個數#\(E(F_{2} )=2\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^2+x+1}\),橢圓曲線點個數#\(E(F_{2^2})=8\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^3+x+1}\),橢圓曲線點個數#\(E(F_{2^3})=14\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^4+x+1}\),橢圓曲線點個數#\(E(F_{2^4})=16\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^5+x^2+1}\),橢圓曲線點個數#\(E(F_{2^5})=22\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^6+x+1}\),橢圓曲線點個數#\(E(F_{2^6})=56\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^7+x+1}\),橢圓曲線點個數#\(E(F_{2^7})=142\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^8+x^4+x^3+x+1}\),橢圓曲線點個數#\(E(F_{2^8})=288\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^9+x+1}\),橢圓曲線點個數#\(E(F_{2^9})=518\)
\(Y^2+XY=X^3 + 1 X^2 + 1 \pmod{2} \pmod{x^{10}+x^3+1}\),橢圓曲線點個數#\(E(F_{2^{10}})=968\)

TOP

美國國家標準暨技術研究院(National Institute of Standards and Technology,NIST)在FIPS.186-4文件中推薦數個二元橢圓曲線參數
二元橢圓曲線還分為pseudo-random curve(\(E:y^2+xy=x^3+x^2+b\))和koblitz curve(\(E:y^2+xy=x^3+ax^2+1,a=0\)或1)兩類。
其中koblitz curve可由二階遞迴數列算出在不同\(GF(F_{q^n})\),\(q=2\)下橢圓曲線點個數,計算方式如下(第107頁)。
1.計算在\(GF(F_q)\)下的橢圓曲線點個數#\(E(F_q)\)。
2.求出frobenius trace \(t=q+1-\)#\(E(F_q)\)。
3.二階遞迴數列\(V_n\)為
 \(V_0=2,V_1=t\)
 \(V_n=V_1V_{n-1}-qV_{n-2}\)
4.在\(GF(F_{q^n})\)的橢圓曲線點個數為#\(E(F_{q^n})=q^n+1-V_n\)

以下就koblitz curve不同\(a\)值進行公式推導
當\(a=0\)時
\(E:y^2+xy=x^3+0x^2+1\)
當\(a=1\)
\(E:y^2+xy=x^3+1x^2+1\)
1.在\(GF(F_2)\)下的橢圓曲線點個數
\(E(F_2)=\{\;(\infty,\infty),(0,1),(1,0),(1,1) \}\;\)
#\(E(F_2)=4\)
2.frobenius trace \(t\)
\(t=q+1-\)#\(E(F_2)=2+1-4=-1\)
3.二階遞迴數列\(V_n\)
\(V_0=2,V_1=t=-1\)
\(V_n=V_1V_{n-1}-qV_{n-2}=-V_{n-1}-2V_{n-2}\)
4.在\(GF(F_{2^n})\)的橢圓曲線點個數
#\(E(F_{2^n})=2^n+1-V_n\)
1.在\(GF(F_2)\)下的橢圓曲線點個數
\(E(F_2)=\{\;(\infty,\infty),(0,1) \}\;\)
#\(E(F_2)=2\)
2.frobenius trace \(t\)
\(t=q+1-\)#\(E(F_2)=2+1-2=1\)
3.二階遞迴數列\(V_n\)
\(V_0=2,V_1=t=1\)
\(V_n=V_1V_{n-1}-qV_{n-2}=V_{n-1}-2V_{n-2}\)
4.在\(GF(F_{2^n})\)的橢圓曲線點個數
#\(E(F_{2^n})=2^n+1-V_n\)


再解出\(V_n\)一般式
求二階遞迴數列\(V_n+V_{n-1}+2V_{n-2}=0\)一般式
特徵方程式為\(x^2+x+2=0\),得二根\(\displaystyle x={-1\pm \sqrt{7}i \over 2}\)
設一般式\(\displaystyle V_n=c_1 \left({-1-\sqrt{7}i}\over 2\right)^n+c_2 \left({-1+\sqrt{7}i}\over 2\right)^n\)
將\(V_0=2,V_1=-1\)代入得到\(\cases{\displaystyle c_1+c_2=2 \cr c_1 \left({-1-\sqrt{7}i}\over 2\right)+c_2 \left({-1+\sqrt{7}i}\over 2\right)=-1}\)
解出\(c_1=c_2=1\)
一般式\(\displaystyle V_n=\left({-1-\sqrt{7}i}\over 2\right)^n+ \left({-1+\sqrt{7}i}\over 2\right)^n\)
求二階遞迴數列\(V_n-V_{n-1}+2V_{n-2}=0\)一般式
特徵方程式為\(x^2-x+2=0\),得二根\(\displaystyle x={1\pm \sqrt{7}i \over 2}\)
設一般式\(\displaystyle V_n=c_1 \left({1-\sqrt{7}i}\over 2\right)^n+c_2 \left({1+\sqrt{7}i}\over 2\right)^n\)
將\(V_0=2,V_1=1\)代入得到
\(\cases{\displaystyle c_1+c_2=2 \cr c_1 \left({1-\sqrt{7}i}\over 2\right)+c_2 \left({1+\sqrt{7}i}\over 2\right)=1}\)
解出\(c_1=c_2=1\)
一般式\(\displaystyle V_n=\left({1-\sqrt{7}i}\over 2\right)^n+ \left({1+\sqrt{7}i}\over 2\right)^n\)




當\(a=0\)時\(E:y^2+xy=x^3+0x^2+1\)的二階遞迴數列
(%i3)
V[0]:2;
V[1]:-1;
V[n]:=V[1]*V[n-1]-2*V[n-2];

(V[0]) 2
(V[1]) \(-1\)
(V[n]) \(V_n:=V_1V_{n-1}-2V_{n-2}\)

利用二階遞迴數列計算\(GF(F_{2^2})\)到\(GF(F_{2^{10}})\)橢圓曲線點個數,符合上一篇執行結果
(%i4)
for n:2 thru 10 do
  (print("V[",n,"]=V[1]*V[",n-1,"]-2V[",n-2,"]=(",V[1],")*(",V[n-1],")-2*(",V[n-2],")=",V[n],
           ",橢圓曲線點個數#E(F 2"^n,")=2"^n,"+1-V[",n,"]=",2^n+1-V[n])
  );

\(V[2]=V[1]*V[1]-2V[0]=(-1)*(-1)-2*(2)=-3\),橢圓曲線點個數#\(E(F_{2^2})=2^2+1-V[2]=8\)
\(V[3]=V[1]*V[2]-2V[1]=(-1)*(-3)-2*(-1)=5\),橢圓曲線點個數#\(E(F_{2^3})=2^3+1-V[3]=4\)
\(V[4]=V[1]*V[3]-2V[2]=(-1)*(5)-2*(-3)=1\),橢圓曲線點個數#\(E(F_{2^4})=2^4+1-V[4]=16\)
\(V[5]=V[1]*V[4]-2V[3]=(-1)*(1)-2*(5)=-11\),橢圓曲線點個數#\(E(F_{2^5})=2^5+1-V[5]=44\)
\(V[6]=V[1]*V[5]-2V[4]=(-1)*(-11)-2*(1)=9\),橢圓曲線點個數#\(E(F_{2^6})=2^6+1-V[6]=56\)
\(V[7]=V[1]*V[6]-2V[5]=(-1)*(9)-2*(-11)=13\),橢圓曲線點個數#\(E(F_{2^7})=2^7+1-V[7]=116\)
\(V[8]=V[1]*V[7]-2V[6]=(-1)*(13)-2*(9)=-31\),橢圓曲線點個數#\(E(F_{2^8})=2^8+1-V[8]=288\)
\(V[9]=V[1]*V[8]-2V[7]=(-1)*(-31)-2*(13)=5\),橢圓曲線點個數#\(E(F_{2^9})=2^9+1-V[9]=508\)
\(V[10]=V[1]*V[9]-2V[8]=(-1)*(5)-2*(-31)=57\),橢圓曲線點個數#\(E(F_{2^{10}})=2^{10}+1-V[10]=968\)
(%o4) done

當\(a=0\)時,NIST建議以下4種koblitz橢圓曲線
(%i5) Degree:[233,283,409,571];
(Degree) \(\left[233,283,409,571 \right]\)

計算橢圓曲線點個數
(%i6)
for d in Degree do
  (print("K-",d,"橢圓曲線"),
   print("V[",d,"]=(",(-1-sqrt(7)*%i)/2,")"^d,"+(",(-1+sqrt(7)*%i)/2,")"^d,"=",V[d]),
   print("橢圓曲線點個數#E(F 2"^d,")=2"^d,"+1-V[",d,"]=",2^d+1-V[d])
  );

\(K-233\)橢圓曲線
\( \displaystyle V[\;233]\;=\left({-\sqrt{7}\%i-1 \over 2}\right)^{233}+\left({\sqrt{7}\%i-1\over 2}\right)^{233}=-137381546011108235394987299651366779\)
橢圓曲線點個數#\(E(F_{2^{233}})=2^{233}+1-V[\;233]\;=13803492693581127574869511724554051042283763955449008505312348098965372\)
\(K-283\)橢圓曲線
\( \displaystyle V[\;283]\;=\left({-\sqrt{7}\%i-1\over 2}\right)^{283}+\left({\sqrt{7}\%i-1\over 2}\right)^{283}=7777244870872830999287791970962823977569917\)
橢圓曲線點個數#\(E(F_{2^{283}})=2^{283}+1-V[\;283]\;=\)
\(15541351137805832567355695254588151253139246935172245297183499990119263318817690415492\)
\(K-409\)橢圓曲線
\( \displaystyle V[\;409]\;=\left({-\sqrt{7}\%i-1\over 2}\right)^{409}+\left({\sqrt{7}\%i-1\over 2}\right)^{409}=10457288737315625927447685387048320737638796957687575791173829\)
橢圓曲線點個數#\(E(F_{2^{409}})=2^{409}+1-V[\;409]\;=\)
\(1322111937580497197903830616065542079656809365928562438569297580091522845156996764202693033831109832056385466362470925434684\)
\(K-571\)橢圓曲線
\( \displaystyle V[\;571]\;=\left({-\sqrt{7}\%i-1\over 2}\right)^{571}+\left({\sqrt{7}\%i-1\over 2}\right)^{571}=-148380926981691413899619140297051490364542574180493936232912339534208516828973111459843\)
橢圓曲線點個數#\(E(F_{2^{571}})=2^{571}+1-V[\;571]\;=\)
\(7729075046034516689390703781863974688597854659412869997314470502903038284579120849072535914090826847338826851203301405845094699896266469247718729686468370014222934741106692\)
(%o6) done

刪除\(V_n\)數列定義
(%i7) kill(V);
(%o7) done

當\(a=1\)時\(E:y^2+xy=x^3+1x^2+1\)的二階遞迴數列
(%i10)
V[0]:2;
V[1]:1;
V[n]:=V[1]*V[n-1]-2*V[n-2];

(V[0]) 2
(V[1]) 1
(V[n]) \(V_n:=V_1V_{n-1}-2V_{n-2}\)

利用二階遞迴數列計算\(GF(F_{2^2})\)到\(GF(F_{2^{10}})\)橢圓曲線點個數,符合上一篇執行結果
(%i11)
for n:2 thru 10 do
  (print("V[",n,"]=V[1]*V[",n-1,"]-2V[",n-2,"]=(",V[1],")*(",V[n-1],")-2*(",V[n-2],")=",V[n],
           ",橢圓曲線點個數#E(F 2"^n,")=2"^n,"+1-V[",n,"]=",2^n+1-V[n])
  );

\(V[2]=V[1]*V[1]-2V[0]=(1)*(1)-2*(2)=-3\),橢圓曲線點個數#\(E(F_{2^2})=2^2+1-V[2]=8\)
\(V[3]=V[1]*V[2]-2V[1]=(1)*(-3)-2*(1)=-5\),橢圓曲線點個數#\(E(F_{2^3})=2^3+1-V[3]=14\)
\(V[4]=V[1]*V[3]-2V[2]=(1)*(-5)-2*(-3)=1\),橢圓曲線點個數#\(E(F_{2^4})=2^4+1-V[4]=16\)
\(V[5]=V[1]*V[4]-2V[3]=(1)*(1)-2*(-5)=11\),橢圓曲線點個數#\(E(F_{2^5})=2^5+1-V[5]=22\)
\(V[6]=V[1]*V[5]-2V[4]=(1)*(11)-2*(1)=9\),橢圓曲線點個數#\(E(F_{2^6})=2^6+1-V[6]=56\)
\(V[7]=V[1]*V[6]-2V[5]=(1)*(9)-2*(11)=-13\),橢圓曲線點個數#\(E(F_{2^7})=2^7+1-V[7]=142\)
\(V[8]=V[1]*V[7]-2V[6]=(1)*(-13)-2*(9)=-31\),橢圓曲線點個數#\(E(F_{2^8})=2^8+1-V[8]=288\)
\(V[9]=V[1]*V[8]-2V[7]=(1)*(-31)-2*(-13)=-5\),橢圓曲線點個數#\(E(F_{2^9})=2^9+1-V[9]=518\)
\(V[10]=V[1]*V[9]-2V[8]=(1)*(-5)-2*(-31)=57\),橢圓曲線點個數#\(E(F_{2^{10}})=2^{10}+1-V[10]=968\)
(%o11) done

當\(a=1\)時,NIST建議以下1種koblitz橢圓曲線
(%i12) d:163;
(d) 163

計算橢圓曲線點個數
(%i15)
print("K-",d,"橢圓曲線")$
print("V[",d,"]=(",(1-sqrt(7)*%i)/2,")"^d,"+(",(1+sqrt(7)*%i)/2,")"^d,"=",V[d])$
print("橢圓曲線點個數#E(F 2"^d,")=2"^d,"+1-V[",d,"]=",2^d+1-V[d])$

\(K-163\)橢圓曲線
\(\displaystyle V[\;163]\;=\left( {1-\sqrt{7}\%i \over 2} \right)^{163}+\left( {\sqrt{7}\%i+1 \over 2} \right)^{163}=-4845466632539410776804317\)
橢圓曲線點個數#\(E(F_{2^{163}})=2^{163}+1-V[\;163]\;=11692013098647223345629483507196896696658237148126\)

TOP

橢圓曲線加密的安全性倚賴橢圓曲線離散對數問題(Elliptic Curve Discrete Logarithm Problem,ECDLP)的困難度上,橢圓曲線離散對數問題敘述如下:

令\(E\)為基於二元體\(F_{2^n}\)的橢圓曲線,\(P,Q\)為橢圓曲線上的點坐標(\(P,Q\in E(F_{2^n})\))且\(Q=kP,k\in N\),當\(n\)很大時,計算\(k\)值非常困難。

解決橢圓曲線離散對數問題的方法會在另一篇文章討論,這裡僅示範暴力搜尋法找出\(k\)值。
可惜在C:\maxima-5.43.0\share\maxima\5.43.0\share\contrib\elliptic_curves\ec2.lisp程式碼中沒有解橢圓曲線離散對數問題的指令



要先載入elliptic_curves.mac才能呼叫ec2_set_curve,ec2_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+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}\)的橢圓曲線
\(a=g^8=x^2+1=101_2=5_{10}\),\(b=g^2=x^2=100_2=4_{10}\)

(%i3)
[ReductionPoly,a,b]:[x^4+x+1,5,4];
ec2_set_curve(ReductionPoly,a,b);

(%o2) \([x^4+x+1,5,4]\)
(%o3) true

\(P,Q\)兩點坐標
\(P=[g^3,g^9]=[x^3,x^3+x]=[1000_2,1010_2]=[8_{10},10_{10}]\)
\(Q=[g^{13},g^1]=[x^3+x^2+1,x]=[1101_2,10_2]=[13_{10},2_{10}]\)

(%i5)
P:[8,10];
Q:[13,2];

(P) \([8,10]\)
(Q) \([13,2]\)

計算\(2P,3P,\ldots,kP\),看何時等於\(Q\)
(%i7)
kP: P$
for k:2 thru 15 do
  (print(k," P=",kP:ec2_add(P,kP)),
   if kP=Q then
      (return(k))
  );

\(2P=[2,6]\)
\(3P=[10,13]\)
\(4P=[5,4]\)
\(5P=[11,5]\)
\(6P=[1,0]\)
\(7P=[13,15]\)
\(8P=[0,2]\)
\(9P=[13,2]\)
(%o7) 9

TOP

 14 12
發新話題