第十章              橢圓曲線與公鑰密碼系統

pages 217 - 232

例題01畫橢圓曲線 (y^2)=x(x+1)(x-1), (y^2)=(x^3)+73 及 (y^2)=((x(x - 1))^2)的圖形。首先，載入<<Graphics`ImplicitPlot` 並設定各自 x 的範圍，此三曲線如圖1由左而右所示。

<< Graphics`ImplicitPlot`
p1 = 
        ImplicitPlot[
          y^2 == x*(x + 1)*(x - 1), {x, -1.75, 
            1.75}];
p2 = 
        ImplicitPlot[y^2 == x^3 + 57, {x, -4.2, 9}];
p3 = 
        ImplicitPlot[
          y^2 == x (x - 1)^2, {x, -0.5, 2.5}];
Show[GraphicsArray[{p1, p2, p3}]]

模 5 下的橢圓曲線 (y^2)==(x^3)+2x+3 上的點為 (1,1),(1,4),(2,0),(3,1),(3,4),(4,0),∞。

Table[
        Solve[{y^2 == x^3 + 2  x + 3, Modulus == 5}, 
          Mode -> Modular], {x, 0, 4}] // ColumnForm

例題03 在剛剛所考慮過的曲線上，讓我們來算算 (1,4)+(3,1)=(2,0)。

例題04 現在來看一個稍微大一些的例子。令 n=2773, 且令
E: (y^2)=(x^3)+4x+4 mod 2773, 且 P=(1,3)。計算 2P=P+P=?

n = 2773;  PowerMod[6, -1, n]
m = Mod[7*PowerMod[6, -1, n], n]

x1 = 1; y1 = 3; x2 = 1; y2 = 3;
x3 = PowerMod[m, 2, n] - x1 - x2
y3 = Mod[m (x1 - x3) - y1, n]

Exit

例題05 令 E 為橢圓曲線 (y^2)=(x^3)+5x-5 mod 599, 試計算其元素個數 N。

p = 599; PrimeQ[p]
L = 
      Table[Solve[{y^2 == x^3 + 5  x - 5, Modulus == p}, y, 
          Mode -> Modular], {x, 0, p - 1}]; Count[L, {}]

Solve[{0 == x^3 + 5  x - 5, Modulus == p}, x, 
      Mode -> Modular]

L[[144]]
n = 2 (599 - 279 - 1) + 1 + 1
Abs[n - p - 1] < 2  Sqrt[p]

例題06 令 E 為橢圓曲線 (y^2)=(x^3)+5x-5 mod 761, 試計算其元素個數 N。

p = 761; PrimeQ[p]
L = 
      Table[Solve[{y^2 == x^3 + 5  x - 5, Modulus == p}, y, 
          Mode -> Modular], {x, 0, p - 1}]; Count[L, {}]

Solve[{0 == x^3 + 5  x - 5, Modulus == p}, x, 
      Mode -> Modular]

n = 2 (761 - 373) + 0 + 1
Abs[n - p - 1] < 2  Sqrt[p]

例題07 令 p=179 假設橢圓曲線為 (y^2)=(x^3)+2x+7。若可接受 1/(2^10) 的失敗率，則取K=10。

p = 179; K = 10; m = 5; j = 1; x = m*K + j
Solve[{y^2 == x^3 + 2  x + 7, Modulus == p}, 
      Mode -> Modular]

Exit

模 n 下的橢圓曲線的加法運算ecadd,ecmus,ecmlt

ecadd[p1_, p2_, a_, b_, n_] := 
        Module[{z, m, x3, y3, p3}, z = 0; z1 = 1; 
          If[p1 == {"infinity", "infinity"}, p3 = p2; 
            z = 1, " "]; 
If[z == 1, " ", 
            If[p2 == {"infinity", "infinity"}, p3 = p1; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1[[1]] == p2[[1]] && 
                p1[[2]] == p2[[2]] == 0, 
              p3 = {"infinity", "infinity"}; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1[[1]] == p2[[1]] && 
                p1[[2]] ≠ p2[[2]], 
              p3 = {"infinity", "infinity"}; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1 == p2 && GCD[p1[[2]], n] ≠ 1 && 
                GCD[p1[[2]], n] ≠ n, z = 1; 
              z1 = GCD[p1[[2]], n], " "]]; 
If[
            z == 1, " ", 
            If[p1 == p2, 
              m = Mod[(3*p1[[1]]^2 + a)*
                    PowerMod[2*p1[[2]], -1, n], 
                  n]; 
z = 1; 
              x3 = m^2 - p1[[1]] - p2[[1]]; 
y3 = 
                m*(p1[[1]] - x3) - p1[[2]]; 
              p3 = Mod[{x3, y3}, n], " "]]; 
If[
            z == 1, " ", 
            If[GCD[p2[[1]] - p1[[1]], n] ≠ 1, 
              z = 1; 
z1 = 
                GCD[p2[[1]] - p1[[1]], 
                  n], " "]]; 
If[z == 1, " ", 
            m = Mod[(p2[[2]] - p1[[2]])*
                  PowerMod[p2[[1]] - p1[[1]], -1, n], 
                n]; 
x3 = m^2 - p1[[1]] - p2[[1]]; 
            y3 = m*(p1[[1]] - x3) - 
                p1[[2]]; 
p3 = Mod[{x3, y3}, n]]; 
          If[z1 == 1, p3, {"factor=", z1}]];
ecmus[p1_, m_, a_, b_, n_] := 
      Module[{z}, 
        z = {p1}; 
For[i = 1, 
          i < m && z[[Length[
                      z]]][[1]] ≠ "factor=", i++, 
          z = Append[z, ecadd[p1, z[[Length[z]]], a, b, n]]]; 
        z]
ecmlt[p1_, m_, a_, b_, n_] := Last[ecmus[p1, m, a, b, n]]

例題08 用上述指令來檢驗例題03及例題04的結果，無誤如下：

ecadd[{1, 4}, {3, 1}, 2, 3, 5]

ecmlt[{1, 3}, 2, 4, 4, 2773]

例題09 在橢圓曲線  (y^2)=(x^3)-5x+13 mod 29 中, (a) 求 (1,3)+(3,5)=? 及 (1,3)+∞=?
(c) 求 7(1,3)=? 並求 k(1,3)=?,k=1,...40。

ecadd[{1, 3}, {3, 5}, -5, 13, 29]

ecadd[{1, 3}, {"infinity", "infinity"}, -5, 13, 
      29]

ecmlt[{1, 3}, 7, -5, 13, 29]

ecmus[{1, 3}, 40, -5, 13, 29]

例題10 上例在質數模 29 之下進行。若改成在合成數模之下進行，那麼在無限遠處的情況就變得更加的複雜，此乃因為前面所提到抵達 ∞ 在不同因子模之下，其速度不同所致。譬如說，我們試著計算 8P, 此處 P=(1,3) 在橢圓曲線  (y^2)=(x^3)-5x+13 mod 29 上：

ecmlt[{1, 3}, 20, -5, 13, 209]

ecmus[{1, 3}, 20, -5, 13, 209]

ecmus[{1, 3}, 20, -5, 13, 19]

ecmus[{1, 3}, 20, -5, 13, 11]

例題11 分解 n=455839。選橢圓曲線 E 及點 P 如下：E: (y^2)=(x^3)+5x-5 mod n, P=(1,1)。

n = 455839; p[1] = {1, 1}; 
    p[i_] := ecmlt[p[i - 1], i, 5, -5, n]

Table[p[i], {i, 10}] // ColumnForm

例題12 用橢圓曲線法來分解 193279。

ecmlt[{1, 2}, 12!, 17, -14, 193279]

例題13 用橢圓曲線法來分解 10993522499。

ecmlt[{1, 2}, 12!, 17, -14, 10993522499]

例題14 (y^2)=(x^3)-3x+2 mod 143

ecmus[{-1, 2}, 5, -3, 2, 143]

Solve[{x^2 == 3, Modulus == 143}, 
      Mode -> Modular]

k = 17; 
    f[x_, y_] := 
      Mod[(y + k (x - 1))*
          PowerMod[(y - k (x - 1)), -1, 143], 
        143]
{f[-1, 2], f[2, 141], f[112, 101], f[10, 20]}

PowerMod[15, {1, 2, 3, 4, 5}, 143]

例題18 我們必須首先產生一橢圓曲線。且用質數 p=9431, 點 α=(x,y)=(7,11) 及 a=3。為了使點 α 位於曲線 E: (y^2)=(x^3)+ax+b mod p 上，我們得取 b=9188。三毛有一信息表示成 E 上之點為 (Subscript[P, m])=(5,9081), 她想將此傳送給四郎。且看她如何完成此一任務。

p = 9431; alp = {7, 11}; a = 3;
b = 
      Mod[alp[[2]]^2 - alp[[1]]^3 - a*alp[[1]], p]

PowerMod[5^3 + a*5 + b, (p + 1)/4, p]

PowerMod[9081, 2, p] == Mod[5^3 + a*5 + b, p]

bet = ecmlt[alp, 3, a, b, p]

k = 8; x = {5, 9081}; y1 = ecmlt[alp, k, a, b, p]
y2 = ecadd[x, ecmlt[bet, k, a, b, p], a, b, p]

u = ecmlt[y1, 3, a, b, p]; v = {u[[1]], -u[[2]]}

ecadd[y2, v, a, b, p]

橢圓曲線版的 Diffie-Hellman 鑰匙交換演算法

p = 7879; alp = {3, 5}; a = 1;
b = 
      Mod[alp[[2]]^2 - alp[[1]]^3 - a*alp[[1]], p]

k3 = 31; k4 = 49; 
    alp3 = ecmlt[alp, k3, a, b, p]
alp4 = ecmlt[alp, k4, a, b, p]

ecmlt[alp4, k3, a, b, p]
ecmlt[alp3, k4, a, b, p]