楕円点の加算と減算
有限体上の楕円曲線における楕円点の加算,減算のアルゴリズムを示す.
アフィン座標
加算と減算 (FullAdd)
- 標数 $p \gt 3$ の体の場合
アフィン座標系を用いた $\mathrm{GF}(p)$ 上の楕円曲線加算アルゴリズム
入力: 素数 $p\ (\gt 3)$,楕円曲線 $E: y^2=x^3+ax+b \bmod p$ の係数 $a$,$b$,$E$ 上の点 $P_0 = (x_0, y_0)$ と $P_1 =
(x_1, y_1)$
出力: 点 $P_2 := P_0 + P_1$
- If $P_0 = {\cal O}$ then return $P_2 \leftarrow P_1$
- If $P_1 = {\cal O}$ then return $P_2 \leftarrow P_0$
- If $x_0 \ne x_1$ then
- $\lambda \leftarrow (y_0-y_1) / (x_0- x_1) \bmod p$
- Go to step 9
- If $y_0 \ne y_1$ then return $P_2 \leftarrow {\cal O}$
- If $y_1 = 0$ then return $P2 \leftarrow {\cal O}$
- $\lambda \leftarrow (3 x_1^2 + a) / (2y_1) \bmod p$
- $x_2 \leftarrow \lambda^2 -x_0 -x_1 \bmod p$
- $y_2 \leftarrow (x_1-x_2)\lambda-y_1 \bmod p$
- Return $P_2 \leftarrow (x_2, y_2)$
このアルゴリズムは,3ないし4回の剰余乗算と1回の剰余逆元を必要とする.
点 $P = (x, y)$ の減算は,点 $-P = (x, -y)$ の加算を行えばよい.
- 標数 2 の体の場合
アフィン座標系を用いた $\mathrm{GF}(2^m)$ 上の楕円曲線の加算アルゴリズム
入力: 有限体 $\mathrm{GF}(2^m)$;$\mathrm{GF}(2^m)$ 上の楕円曲線 $E: y^2+xy=x^3+ax^2+b$ の係数 $a, b$;$E$ 上の点 $P_0 = (x_0, y_0)$ と $P_1 =
(x_1, y_1)$
出力: 点 $P_2 := P_0 + P_1$
- If $P_0 = {\cal O}$, then return $P_2 \leftarrow P_1$
- If $P_1 = {\cal O}$, then return $P_2 \leftarrow P_0$
- If $x_0 \ne x_1$ then
- $\lambda \leftarrow (y_0 + y_1)/(x_0 + x_1)$
- $x_2 \leftarrow a + \lambda^2 + \lambda + x_0 + x_1$
- Go to step 11
- If $y_0 \ne y_1$ then return $P_2 \leftarrow {\cal O}$
- If $x_1 = 0$ then return $P_2 \leftarrow {\cal O}$
- $\lambda \leftarrow x_1 + y_1 / x_1$
- $x_2 \leftarrow a + \lambda^2 + \lambda$
- $y_2 \leftarrow (x_1 + x_2)\lambda + x_2 + y_1$
- Return $P_2 \leftarrow (x_2, y_2)$
このアルゴリズムは,2回の乗算,1回の2乗,1回の乗法逆元の演算を必要とする. 点 $P = (x, y)$ の減算は,点 $-P = (x, x - y)$ の加算を行えばよい.
プロジェクティブ座標(ヤコビ座標系)
2倍算 (Double)
- 標数 $p \gt 3$ の体の場合
楕円曲線 $y^2 = x^3 + ax + b \bmod p$ 上での点の2倍算
$2 (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は,次の式により求められる.
$M = 3 X_1^2 + a Z_1^4,$
$Z_2 = 2Y_1Z_1,$
$S = 4X_1 Y_1^2,$
$X_2 = M^2 - 2S,$
$T = 8Y_1^4,$
$Y_2 = M (S - X_2)- T.$
- 標数 $2$ の体の場合
有限体 $\mathrm{GF}(2^m)$ 上の楕円曲線 $y^2 + xy = x^3 + ax^2 + b$ 上での点の2倍算
$2 (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は,次の式により求められる.
$c := b^{2^{m-2}},$
$Z_2 = X_1 Z_1^2,$
$X_2 = (X_1 + c Z_1^2 )^4,$
$U = Z_2 + X_1^2 + Y_1Z_1,$
$Y_2 = X_1^4 Z_2 + UX_2.$
加算 (Add)
- 標数 $p \gt 3$ の体の場合
楕円曲線 $y^2 = x^3 + ax + b \bmod p$上での点の加算
$(X_0, Y_0, Z_0) + (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は,次の式により求められる.
$ U_0 = X_0 Z_1^2,$
$ S_0 = Y_0 Z_1^3,$
$ U_1 = X_1 Z_0^2,$
$ S_1 = Y_1 Z_0^3,$
$ W = U_0 - U_1,$
$ R = S_0 - S_1,$
$ T = U_0 + U_1,$
$ M = S_0 + S_1,$
$ Z_2 = Z_0Z_1W,$
$ X_2 = R^2 -TW^2,$
$ V = TW^2 - 2X_2,$
$ 2Y_2 = VR - MW^3.$
- 標数 $2$ の体の場合
有限体 $\mathrm{GF}(2^m)$ 上の楕円曲線 $y^2 + xy = x^3 + ax^2 + b$ 上での点の加算
$X_0, Y_0, Z_0) + (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は,次の式により求められる.
$ U_0 = X_0 Z_1^2,$
$ S_0 = Y_0 Z_1^3,$
$ U_1 = X_1 Z_0^2,$
$ W = U_0 + U_1,$
$ S_1 = Y_1 Z_0^3,$
$ R = S_0 + S_1,$
$ L = Z_0 W,$
$ V = RX_1 + LY_1,$
$ Z_2 = LZ_1,$
$ T = R + Z_2,$
$ X_2 = a Z_2^2 + TR + W^3,$
$ Y_2 = TX_2 + VL^2.$
加算と減算 (FullAdd)
- 標数 $p \gt 3$ の体の場合
入力: $q$ 個の要素からなる有限体;$\mathrm{GF}(q)$ 上の楕円曲線を定義する体の要素 $a, b$;$E$ 上の点 $P_0$ と$P_1$ を表す射影座標 $(X_0, Y_0,
Z_0)$,$(X_1, Y_1, Z_1)$
出力: 点 $P_2= P_0 + P_1$ に対するプロジェクティブ座標$(X_2, Y_2, Z_2)$
- If $Z_0 = 0$ then return $(X_2, Y_2, Z_2) \leftarrow (X_1, Y_1, Z_1).$
- If $Z_1 = 0$ then return $(X_2, Y_2, Z_2) \leftarrow (X_0, Y_0, Z_0).$
- $(X_2, Y_2, Z_2) \leftarrow \mathrm{Add}\ [(X_0, Y_0, Z_0), (X_1, Y_1, Z_1)].$
- If $(X_2, Y_2, Z_2) = (0, 0, 0)$ then $(X_2, Y_2, Z_2) \leftarrow \mathrm{Double}\ [(X_1, Y_1, Z_1)].$
- Return $(X_2, Y_2, Z_2).$
楕円曲線の減算(Subtract)は以下のように行える.
\[ \mathrm{Subtract}\ [(X_0, Y_0, Z_0), (X_1, Y_1, Z_1)] = \mathrm{FullAdd}\ [(X_0, Y_0, Z_0), (X_1,U,Z_1)] \]
ここで,
\[ U = \left\{
\begin{array}{ll}
-Y_1\ \bmod\ p & \text{if}\ q = p,\\
X_1 Z_1 + Y_1, & \text{if}\ q = 2^m.\\
\end{array}\right.
\]
である.