發新話題
打印

用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

例子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])
)$


生成數P=[0,1]
(%i3) P:[0,1];
(P) \(\left[0,1 \right]\)

計算P,2P,3P,...,15P,結果放在L
(%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]]}\)

將P,2P,...,15P各點坐標畫出來
(%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

前面兩篇文章利用\(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)]\)

TOP

上一篇文章以\(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\)

TOP

橢圓曲線加密的安全性倚賴橢圓曲線離散對數問題(\(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

TOP

發新話題