楕円曲線の構造

楕円曲線の選択

有限体の選択
楕円曲線を定義する有限体の選択により，実装の容易性や性能が変化する．
- 素体上で定義された楕円曲線
  - 実装が容易である．
  - パラメータが比較的容易に生成できる．
- 拡大体上で定義された楕円曲線
  - 実装はやや複雑になる．
  - 演算の高速化が期待できる．
楕円曲線の選択
楕円曲線暗号で用いる楕円曲線を規定するパラメータは，暗号の安全性に関わるため十分注意して選択する必要がある．有限体 $\mathbb{F}_q$ 上の楕円曲線 $E$ をランダムに選んだ時に，その楕円曲線 $E$ が楕円曲線暗号に適しているかの判定は，主に位数 $N = \#E(\mathbb{F}_q)$ の値で判定される．例えば，$N$ が小さな素数の積に分解されるような場合は，既存の(一般の有限群に適用できる) 離散対数計算アルゴリズムが適用されるので好ましくない．
現状では，
- $N = l$（$l$ は $\mathbb{F}_q$ の標数以外の素数）
- $N = l' v\ ((l', v) = 1$，$l'$ は $N$ と近いビット長の素数）
のいずれかであることが必要とされている．

また，ある条件のもとで楕円曲線暗号を弱体化させる特別なクラスの曲線がある．
- Anomalous曲線
  Frobenius のトレース $t$ が 1 の曲線 ($\#E(\mathbb{F}_q) = q$ となる曲線)
楕円ペアリングにおける楕円曲線の選択
楕円ペアリング暗号(IDベース暗号) は，RSA 暗号や一般的な楕円曲線暗号などと比較するとその計算コストが大きく，効率的な演算手法の選択が必要である．この場合，楕円曲線の選択も従来の楕円曲線暗号とは異なってくる．
IDベース暗号に用いられる楕円曲線には，次の種類がある．
- Ordinary (OD) 曲線
  標数 $p$ が Frobenius のトレース $t$ を割り切らない曲線である．
- Supersingular (SS) 曲線
  標数 $p$ が Frobenius のトレース $t$ を割り切る曲線である．
  これと同値な性質は，
  - $p = 2$ または $p = 3$ かつ $j(E) = 0$　$(j(E)$ は $j$ 不変量)
  - $p \ge 5$ かつ $t = 0$
  である．

位数とトレース

位数 (Order)
有限体 $\mathbb{F}_q$ 上で定義された楕円曲線 $E$ 上の点(無限遠点 ${\cal O}$ を含む) の数は有限であり，$E$ の位数と呼ばれ $\#E(\mathbb{F}_q)$ で表す．
楕円曲線上の点 $P$ の位数とは，$ r P = {\cal O}$ となる最小の正整数 $r$ である．位数は常に存在し，楕円曲線の位数 $\#E(\mathbb{F}_q)$ を割り切る．
$k$ と $m$ が整数で，$k P = m P$ となるのは，$k \equiv m \pmod{r}$ のときのみであり，そのときに限られる．
トレース
楕円曲線の位数 $\#E(\mathbb{F}_q)$ を用いて，$t$ を次のように定義する．
$t = q + 1 - \#E(\mathbb{F}_q)$
この $t$ を $q$ における Frobenius のトレースと呼ぶ．
(例) $\mathbb{F}_{13}$ 上の楕円曲線を $E: y^2 = x^3 + 10x + 5$ とする．このとき，$E$ 上の点は，

$\{ {\cal O}, (1,4), (1,9), (3,6), (3,7), (8,5), (8,8), (10,0), (11,4), (11,9) \}$
である．したがって，$E$ の位数 $\#E(\mathbb{F}_{13})$ は $10$ であり，トレースは $4$ である.
Hasse の定理
Frobenius のトレース t は
$|t| \le 2\sqrt{q}$
を満たす．
Hasse の定理より楕円曲線上の点の個数は，大きな $q$ の値に対して，$q + 1$ をはさんだ $4\sqrt{q}$ の範囲にある．
Weil の定理
$\mathbb{F}_p$ 上で定義された楕円曲線を $E$，$t = p + 1 - \#E(\mathbb{F}_p)$ とする．このとき，
$\#E({\mathbb{F}_p}^k) = p^k + 1 - \alpha^k - \beta^k$
となる．ここで，$\alpha$，$\beta$ は，
$1 - tT + pT^2 = (1 - \alpha T)(1 - \beta T)$
を満たす値である (${\mathbb{F}_p}^k$ は $\mathbb{F}_p$ の $k$ 次拡大体)．
Weil の定理より， $\mathbb{F}_p$ 上で定義された楕円曲線 $E$ に対して，$\#E(\mathbb{F}_p)$ が分かれば，$\#E({\mathbb{F}_p}^k)$ を求めることができる．
例えば， $k = 2$ のとき，
$\#E({\mathbb{F}_p}^2) = p^2 + 1 - (\alpha^2 + \beta^2)$
となるが，これは，$\alpha + \beta = t$，$\alpha \beta = p$ の関係より，
$\#E({\mathbb{F}_p}^2) = p^2 + 1 - (t^2 - 2p)$
で求めることができる．
一般的には，$t_k = \#E({\mathbb{F}_p}^k) - (p^k + 1)$ とするとき，$\#E(\mathbb{F}_p)$ が決定されれば，$t_1$ が求まり順次 $t_k$ を求めることができる．
入力： $(p, t, k)$，$\#E(\mathbb{F}_p) = p + 1 - t,\ k \ge 1$
出力： $t_k$
1. $t_0 \leftarrow 2$
2. $t_1 \leftarrow t$
3. For $i = 1$ to $k - 1$ do
4. 　$t_{i+1} \leftarrow t・t_i - p・t_{i-1}$
5. Return $t_k$

ねじれ群とねじれ点

ペアリング暗号(IDベース暗号) では，楕円曲線上のねじれ群が用いられる．

楕円曲線 $E$
楕円曲線は係数 $a, b\ (\in \mathbb{F}_p)$ によって $y^2 = x^3 + ax + b$ で定義されるもので，点の集合としてみれば， \[ E = \{(x, y) | x, y \in \overline{\mathbb{F}_p},\ y^2 = x^3 + ax + b \cup \{{\cal O}\} \] であり，群をなす．ここで $\overline{\mathbb{F}_p}$ は $\mathbb{F}_p$ の代数的閉包である．
$E(\mathbb{F}_p)$，$E(\mathbb{F}_{p^m})$
それぞれ楕円曲線 $E$ の $\mathbb{F}_p$ 有理点，$\mathbb{F}_{p^m}$ 有理点からなる $E$ の部分群．
ねじれ群
楕円曲線 $E= E(\mathbb{F}_p)$ 上の各点 $P$ が $n P = {\cal O}$ となるような $n$ を持つならば，$E$ をねじれ群 (torsion group) と言う．そのような整数の最小のものを $P$ の位数と言う．
ねじれ点
正整数 $n$ と $P \in E(\mathbb{F}_p)$ に対し，$n P = {\cal O}$ を満たすとき，$P$ を $n$ ねじれ点 ($n$-torsion point) と言う．$n$ は $P$ の位数の倍数になる．
$E(\mathbb{F}_p)$ の点で $n$ ねじれ点であるものの集合は $E(\mathbb{F}_p)$ の部分群になり，これを $E(\mathbb{F}_p)[n]$ で表す．
$E(\mathbb{F}_p)$ の $n$ ねじれ点の集合 $E(\mathbb{F}_p)[n]$ を単に $E[n]$ と書く．このとき， \[ E(\mathbb{F}_p)[n] = E(\mathbb{F}_p) \cap E[n] \] である．
$n$ と $p$ が互いに素であるとき， $E[n]$ のすべての元は，基底 $P_1$，$P_2$ を用いて \[ n_1 P_1 + n_2 P_2\quad (n_1, n_2 \in Z) \] の形で表現可能である．
$E[q]$，$E(\mathbb{F}_p)[q]$，$E(\mathbb{F}_{p^m})[q]$
それぞれ， $E$，$E(\mathbb{F}_p)$，$E(\mathbb{F}_{p^m})$ の $q$-torsion point からなる部分群．
$q$ は，$q | \#E(\mathbb{F}_p)$ なる十分大きな自然数で torsion 数である．

Page Top