はじめに
今回から、暗号プロトコルを理解するシリーズを始めます。暗号プロトコルは、セキュリティの基礎となる重要な技術ですが、その仕組みや原理を理解するのは難しいこともあります。第一回では、暗号技術の中でも最近話題の非対称性暗号の一種である楕円曲線暗号（ECC）について学んでいきます。
楕円曲線暗号（ECC）とは？
まず、Wikipediaの説明を見てみましょう。
楕円曲線暗号(Elliptic Curve Cryptography, ECC)は、楕円曲線上の離散対数問題の困難性を安全性の根拠とする暗号。
はて？楕円曲線上の離散対数問題とは？
どうやら、以下のようなことを言っているようです。
- 楕円曲線$E$を$y^2 = x^3 + \alpha x + \beta$で定義する。
- ある素数pに対して、有限体$F_p$を考える。この有限体上の離散的楕円曲線上においての加法を考える。
また、RSA暗号と比べ、より短い鍵でかつ処理時間も短く、同等の安全性を提供できるとのことです。
有限体とは
有限体とは、有限個の元を持つ体のことです(そのまま)。つまり、有限体とは、1~p-1までの整数のみを元として持ち、加法と乗法において閉じている集合のことです。例えば、$p=2$の場合、以下のような有限体が考えられます。
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| x | -x |
|---|---|
| 0 | 0 |
| 1 | 1 |
| * | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| x | $x^{-1}$ |
|---|---|
| 0 | - |
| 1 | 1 |
また、$p=5$の場合、以下のようになります。
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| x | -x |
|---|---|
| 0 | 0 |
| 1 | 4 |
| 2 | 3 |
| 3 | 2 |
| 4 | 1 |
| * | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
| x | $x^{-1}$ |
|---|---|
| 0 | - |
| 1 | 1 |
| 2 | 3 |
| 3 | 2 |
| 4 | 4 |
なお、有限体$F_p$について、pが素数であるものを素体と呼びます(今井, 2024)。 このような、演算が閉じた性質のおかげで、有限体上における楕円曲線はかなり複雑な軌道を描くことになります。
楕円曲線上の加法の定義
楕円曲線上の加法は、以下のように定義されます。
- 楕円曲線上の2点$P=(x_1, y_1), Q=(x_2, y_2)$に対して、PとQを結ぶ直線と楕円曲線の交点をRとする。この時、Rをx軸に対して対称移動した点$R'$が、PとQの和である。
これはつまり、
$$ R' = P + Q $$であることを意味します。ここで、R’の座標(x_3, y_3)は、以下のように計算されます。
$$\phi = \frac{y_2 - y_1}{x_2 - x_1}, \psi = \frac{y_1 x_2 - y_2 x_1}{x_2 - x_1}$$のとき、
$$ x_3 = \phi^2 - x_1 - x_2, y_3 = \phi (x_1 - x_3) - y_1 $$ただし、$P = Q$の場合は、点Pの接線を代わりに用いるので、
$$\phi = \frac{3 x_1^2 + \alpha}{2 y_1}, \psi = \frac{-x_1^3 + \alpha x_1 - 2 \beta}{2 y_1}$$となります。
楕円曲線暗号の安全性の根拠
「離散対数問題の困難性」を簡単にいうと、「ある点Pと整数kが与えられたとき、kPを計算するのは簡単だが、kPからkを求めるのは非常に難しい」となります。上の内容から、kPが簡単に求められるのは容易に理解できますが、kPからkを求めるのは、有限体上の楕円曲線の性質から、非常に難しいとされているのです。 これは、pの値が大きいことが前提です。実際によく使われるpの値の1つとしては、$p = 2^{521} - 1$などがあります。
まとめ
- 楕円曲線暗号（ECC）は、楕円曲線上の離散対数問題の困難性を安全性の根拠とする暗号。
- 楕円曲線上の加法は、2点を結ぶ直線と楕円曲線の交点を用いて定義される。
- 楕円曲線暗号の安全性は、kPからkを求めることが非常に難しいことに基づいている。