橢圓曲線數論與密碼學（1）

橢圓曲線-無限遠點

無限遠點一般可以看作一個點 ( ∞ , ∞ ) (\infty,\infty ) (∞,∞)，簡單用 ∞ \infty ∞表示。在圖像上表示在y軸的頂端和底端。

• 如果一條直線是垂直的，那麼我們就認為這條直線穿過點 ∞ \infty ∞。
• 兩條垂直的直線在點 ∞ \infty ∞相交。

橢圓曲線 - 加法規則

橢圓曲線上點的集合可以看作一個加法群。如圖所示， P 1 P_1 P1​和 P 2 P_2 P2​是一條橢圓曲線 E E E 上的兩個點，那麼 P 3 = P 1 + P 2 P_3 = P_1+P_2 P3​=P1​+P2​ 作為兩個點的合，即為穿過 P 1 P_1 P1​ 和 P 2 P_2 P2​ 的直線與橢圓曲線 E E E 上的交點。

一些特别的規則( E : y 2 = x 3 + A x + B E: y^2 = x^3 + Ax +B E:y2=x3+Ax+B)：

• 當 x 1 ≠ x 2 x_1 \neq x_2 x1​​=x2​ 時， x 3 = m 2 − x 1 − x 2 x_3 = m^2 - x_1 -x_2 x3​=m2−x1​−x2​， y 3 = m ( x 1 − x 3 ) − y 1 y_3 = m(x_1 - x_3 ) - y_1 y3​=m(x1​−x3​)−y1​， m = y 2 − y 1 x 2 − x 1 m= \frac{y_2-y_1}{x_2 - x_1} m=x2​−x1​y2​−y1​​。
• 當 x 1 = x 2 x_1 = x_2 x1​=x2​時， x 3 = m 2 − 2 x 1 x_3 = m^2 - 2 x_1 x3​=m2−2x1​， y 3 = m ( x 1 − x 3 ) − y 1 y_3 = m(x_1-x_3)-y_1 y3​=m(x1​−x3​)−y1​， m = 3 x 1 2 + A 2 y 1 m = \frac{3x_1^2+A}{2y_1} m=2y1​3x12​+A​
• x 1 = x 2 x_1 = x_2 x1​=x2​ 且 y 1 ≠ y 2 y_1 \neq y_2 y1​​=y2​，那麼 P 1 + P 2 = ∞ P_1 + P_2 = \infty P1​+P2​=∞。
• P 1 = P 2 P_1 = P_2 P1​=P2​ 且 y 1 = 0 y_1 = 0 y1​=0，那麼 P 1 + P 2 = ∞ P_1 + P_2 = \infty P1​+P2​=∞。
• P 1 + ∞ = P 1 P_1 + \infty = P_1 P1​+∞=P1​。
• ∞ + ∞ = ∞ \infty + \infty = \infty ∞+∞=∞。

Projective Coordinates

Let P i = ( x i : y i : z i ) P_i = (x_i : y_i : z_i) Pi​=(xi​:yi​:zi​) be points on the elliptic curve y 2 z = x 3 + A x z 2 + B z 3 y^2z = x^3 + Axz^2 + Bz^3 y2z=x3+Axz2+Bz3. Then

( x 1 : y 1 : z 1 ) + ( x 2 : y 2 : z 2 ) = ( x 3 : y 3 : z 3 ) (x_1 : y_1 : z_1) + (x_2 : y_2 : z_2) = (x_3 : y_3 : z_3) (x1​:y1​:z1​)+(x2​:y2​:z2​)=(x3​:y3​:z3​)

在此坐标下，加法計算規則為：

• 當 P 1 ≠ ± P 2 P_1 \neq \pm P_2 P1​​=±P2​,

  

• 當 P 1 = P 2 P_1 = P_2 P1​=P2​，

  

• 當 P 1 = − P 2 P_1 = -P_2 P1​=−P2​， P 1 + P 2 = ∞ P_1 + P_2 = \infty P1​+P2​=∞。

Point addition takes 12 multiplications and 2 squarings, while point doubling takes 7 multiplications and 5 squarings.

Jacobian Coordinates

Let ( x : y : z ) (x : y : z) (x:y:z) represent the affine point ( x / z 2 , y / z 3 ) (x/z^2, y/z^3) (x/z2,y/z3). The function x x x has a double pole at ∞ \infty ∞ and the function y y y has a triple pole at ∞ \infty ∞.

The elliptic curve y 2 = x 3 + A x + B y^2 = x^3 + Ax +B y2=x3+Ax+B becomes y 2 = x 3 + A x z 4 + B z 6 y^2 = x^3 + Axz^4 + Bz^6 y2=x3+Axz4+Bz6. The point at infinity has the coordinates ∞ = ( 1 : 1 : 0 ) \infty = (1 : 1: 0) ∞=(1:1:0).

在此坐标下，加法計算規則為：

Addition of points takes 12 multiplications and 4 squarings. Doubling takes 3 multiplications and 6 squarings.