楕円曲線についての覚書

数学

Posted at 2026-01-11

はじめに

楕円曲線の解説記事については、先人の方々がまとめてくださっているので、以下の記事などを参照して下さい。

本投稿は、主に以下の内容を備忘的にまとめておくものです。

加算後の点の計算式の表記が2種類ある件について同値であることを確認する
楕円曲線で鍵共有ができること

加算後の点の計算式について

前提として、以下のようにします。

元の楕円曲線 : $ y^2 = x^3 + ax + b$
加算する点 : $P = (x_1, y_1), Q = (x_2, y_2)$
加算後の点の座標 : $(x_3, y_3) = P + Q$

楕円曲線、及び楕円曲線暗号について調べていると、加算後の点の計算式は、以下のどちらかのパターンで紹介されています。

パターン1

$ P \neq Q $のとき

$$
\begin{aligned}
\phi &= \frac{y_2 - y_1}{x_2 - x_1} \\
\psi &= \frac{y_1 x_2 - y_2 x_1}{x_2 - x_1}
\end{aligned}
$$

このとき、加算後の点の座標は以下の様になります。

$$
\begin{aligned}
x_3 &= \phi^2 - x_1 - x_2 \\
y_3 &= -\phi x_3 - \psi
\end{aligned}
$$

P = Q のとき

$$
\begin{aligned}
\phi &= \frac{3x_1^2 + a}{2y_1} \\
\psi &= \frac{-3x_1^3 - ax_1 + 2y_1^2}{2y_1}
\end{aligned}
$$

このとき、加算後の点の座標は以下の様になります。

$$
\begin{aligned}
x_3 &= \phi^2 - 2x_1 \\
y_3 &= -\phi x_3 - \psi
\end{aligned}
$$

パターン2

$ P \neq Q $のとき

$$
\lambda = \frac{y_2 - y_1}{x_2 - x_1}
$$

このとき、加算後の点の座標は以下の様になります。

$$
\begin{aligned}
x_3 &= \lambda^2 - x_1 - x_2 \\
y_3 &= \lambda (x_1 - x_3) - y_1
\end{aligned}
$$

P = Q のとき

$$
\lambda = \frac{3x_1^2 + a}{2y_1}
$$

このとき、加算後の点の座標は以下の様になります。

$$
\begin{aligned}
x_3 &= \lambda^2 - x_1 - x_2 \\
y_3 &= \lambda (x_1 - x_3) - y_1
\end{aligned}
$$

※ $x_3, y_3$の計算式は $P \neq Q$と同様

パターン1とパターン2が同値であること

上記の2パターンは同値です。
これは、以下の式変換を行うことによって確認できます。

$P \neq Q$のとき

以下の様に$\phi$と$\lambda$は同一なので、$x_3$の計算式も同一である。

$$
\begin{aligned}
\phi &= \frac{y_2 - y_1}{x_2 - x_1} & x_3 = \phi^2 - x_1 - x_2 \\
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} & x_3 = \lambda^2 - x_1 - x_2
\end{aligned}
$$

$y_3$の計算式について考える。
まず$\psi$を以下の様に、$\phi$を利用した式に変換します。

$$
\begin{flalign}
\psi & = \frac{y_1 x_2 - y_2 x_1}{x_2 - x_1} \\
& = \frac{y_1 x_2 - y_2 x_1 + y_1 x_1 - y_1 x_1 }{x_2 - x_1} \\
& = \frac{ y_1 (x_2 - x_1) - x_1 (y_2 - y_1)}{x_2 - x_1} \\
& = y_1 - x_1 \phi
\end{flalign}
$$

$y_3$に上記の変換式を代入すると、以下の様になる。

$$
\begin{array}{ll}
y_3 & = \phi x_3 - \psi \\
& = -\phi x_3 - (y_1 - x_1 \phi) \\
& = \phi (x_1 - x_3) - y_1
\end{array}
$$

$\phi = \lambda$であったので、以下の$\lambda$の式と同一である。

$$
y_3 = \lambda (x_1 - x_3) - y_1
$$

P = Q のとき

こちらも$\phi$と$\lambda$が同一なので、$x_3$も同一である。

$$
\begin{aligned}
\phi &= \frac{3x_1^2 + a}{2y_1} & x_3 = \phi^2 - 2x_1 \\
\lambda &= \frac{3x_1^2 + a}{2y_1} & x_3 = \lambda^2 - 2x_1
\end{aligned}
$$

$y_3$の計算式について考える。
こちらも$\psi$を以下の様に、$\phi$を利用した式に変換します。

$$
\begin{aligned}
\psi & = \frac{-3x_1^3 - ax_1 + 2y_1^2}{2y_1} \\
& = \frac{-3x_1^3 - ax_1}{2y_1} + \frac{2y_1^2}{2y_1} \\
& = -x_1 \frac{3x_1^2 + a}{2y_1} + y_1 \\
& = -x_1 \phi + y_1
\end{aligned}
$$

$y_3$に上記の変換式を代入すると、以下の様になる。

$$
\begin{aligned}
y_4 & = -\phi x_3 - \psi \\
& = -\phi x_3 - (-x_1 \psi + y_1) \\
& = \phi (x_1 - x_3) - y_1
\end{aligned}
$$

$\phi = \lambda$であったので、以下の$\lambda$の式と同一である。

$$
y_3 = \lambda (x_1 - x_3) - y_1
$$

以上で、表面上は異なった式の様に見えた計算式が同一であることがわかりました。

楕円曲線で鍵共有ができること

実際に、楕円曲線を利用して、鍵共有ができることを確認してみます。
以下のAWSの資料に例がありますが、手計算できないので、もっと簡単な条件にしてみます。

https://sbcr-dl-and-idea.s3.ap-northeast-1.amazonaws.com/2021-07-13-02567-CentOS8%E6%A7%8B%E7%AF%89%E3%83%BB%E9%81%8B%E7%94%A8%E3%83%BB%E7%AE%A1%E7%90%86%E3%83%91%E3%83%BC%E3%83%95%E3%82%A7%E3%82%AF%E3%83%88%E3%82%AC%E3%82%A4%E3%83%89/15-A%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7.pdf

まず、楕円曲線を $y^2 = x^3 + 2x + 3 (\mod 5)$とします。

鍵共有のアルゴリズムは以下のようになります。

生成元(G)を楕円曲線上の点から任意に選ぶ
スカラー倍を行い位数(n)を計算する
秘密鍵(d)を以下の範囲からランダムに選ぶ
- $ 1 \le d \lt n $
公開鍵(Q)を計算
- $Q = dG$
共有鍵(K)計算
- $K = dQ$

実際に計算してみる

楕円曲線上の点を計算する

まず、mod 5(5で割った余り)で考えるので、$x = 0, 1, \ldots , 4$ を代入して楕円曲線上の点を計算します。

$x$	$x^3 + 2x + 3 (\mod 5)$
0	3
1	1 (= 6)
2	0 (= 15)
3	1 (= 36)
4	0 (= 75)

次に $ y $ が $ 0, \cdots, 4 $ の各ケースについて計算します。

y	$y^2 (\mod 5)$
0	0
1	1
2	4
3	4 (= 9)
4	1 (= 16)

$ y^2 = x^3 + 2x + 3 $であるので、上記の表で、一番右側の列の結果が一致するものを列挙すると、以下の6点になります。

(1, 1), (1, 4)
(2, 0)
(3, 1), (3, 4)
(4, 0)

生成元の決定

鍵交換を行うに当たって、生成元の情報は予め公開しておきます。
今回は、生成元として $G = (1, 4)$ を利用することにします。

位相nを計算する

位相は $n G = O$(無限遠点) となるようなnのことである。
無限遠点は、以下の記事などを参照して下さい。楕円曲線上の代数計算で、ゼロとして扱う特殊値になります。

https://ja.wikipedia.org/wiki/%E7%84%A1%E9%99%90%E9%81%A0%E7%82%B9

$G = (1, 4)$のスカラー倍を計算していきます。

$$
\begin{aligned}
2G &= 2(1, 4) = (-2, -4) = (3, 1) \\
3G &= 2G + G = (3, 1) + (1, 4) = (-3, 5) = (2, 0) \\
4G &= 3G + G = (2, 0) + (1, 4) = (3, 4) \\
5G &= 4G + G = (3, 4) + (1, 4) = (1, 1) \\
6G &= 5G + G = (1, 1) + (1, 4) = O
\end{aligned}
$$

詳細な計算は省略しましたが、上述のλに関する計算式を利用して算出しています。

よって位相は $n = 6$ となります。

公開鍵の計算 (Alice)

暗号通信の慣例に従って、AliceとBob間で鍵交換を行うとします。
以下の情報が共有されるので、ランダムに秘密鍵を生成します。

生成元 : $G = (1, 4)$
位相 : $n = 6$
楕円曲線パラメータ : $a = 2$, $b = 3$, $p = 5$
- つまり $ y^2 = x^3 + ax + b (\mod p) = x^3 + 2x + 3 (\mod 5)$ のこと

秘密鍵は $ 1 \le d_a \lt n $ の間でランダムに決定してよいですが、今回の場合は $n = 6$が素数ではないため、$d_a$と$n$が互いに素である(約数にならない)ようなものを選択します。

1, 5のいずれかが候補となりますが、$d_a = 1$とします。

公開鍵($Q_a$)を計算すると、自明ですが以下の様になります。

$Q_a = d_a G = 1 (1, 4) = (1, 4)$

公開鍵の計算 (Bob)

事前に共有される情報はAliceと同じです。

Bobの秘密鍵はAliceと同一でも良いですが、自明になってしまうので、$d_b = 5$とします。

公開鍵($Q_b$)を計算します。

$Q_b = d_b G = 5 (1, 4) = (1, 1) $ (※ 計算過程は上記の位数計算を参照)

共有鍵の計算 (Alice)

Bobの公開鍵を利用して、共有鍵($S_a$)を計算します。

$S_a = d_a Q_b = 1 (1, 1)$

共有鍵の計算 (Bob)

$S_b = d_b Q_a = 5 (1, 4) = (1, 1)$ (※ 計算過程は上記の位数計算を参照)

今回の場合、自明な計算例になってしまったが、$S_a = S_b$となることがわかります。

鍵共有のまとめ

この計算の重要な点としては、AliceとBobがそれぞれ独立して、同一の値を算出できたということです。
共有鍵を直接相手に渡す場合、第三者による盗聴を危惧する必要がありますが、楕円曲線の仕組みにより、公開しても問題のない値(公開鍵)から秘密したい値(共有鍵)を共有できています。
後続の暗号通信では、この値を暗号アルゴリズムに組み込んで行うことになります。

参考サイト

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up