楕円曲線演算の実装
楕円曲線の選択とパラメータ
楕円曲線暗号で用いる楕円曲線のパラメータは，暗号の安全性に関わるため十分注意して選択する必要がある． $\mathrm{GF}(q)$ 上の楕円曲線 $E$ をランダムに選んだ時，その $E$ が楕円曲線暗号に適しているかの判定は，主に位数 $N = \#E(\mathrm{GF}(q))$ の値で判定される． 例えば， $N$ が小さな素数の積に分解されるような場合は，既存の(一般の有限群に適用できる) 離散対数計算アルゴリズムが適用されるので好ましくない．
また，楕円曲線を定義する体の選択により，実装の容易性や性能が変化する．
- 素体上で定義された楕円曲線
- 実装が容易である．
- パラメータが比較的容易に生成できる．
- 拡大体上で定義された楕円曲線
- 実装はやや複雑になる．
- 演算の高速化が期待できる．
- 素体
体 $\mathrm{GF}(p)$ 上の楕円曲線パラメータは，以下の6つの値で定義される．
\[ T= (p, a, b, G, n, h) \] ここで，$p$ は有限体 $\mathrm{GF}(p)$ を決める整数，$a, b \in \mathrm{GF}(p)$ は楕円曲線 $E(\mathrm{GF}(p))$ を定義する値，$G$ は $E(\mathrm{GF}(p))$ 上のベースポイント，$n$ は $G$ の位数，$h$ はコファクタと呼ばれ $h = \#E(\mathrm{GF}(p))/n$ である．
以下に，標準化等で規定されている楕円曲線パラメータの名称を示す．- SEC2
secp160k1, secp160r1, secp160r2, secp192k1, secp192r1, secp224k1, secp224r1
secp256k1, secp256r1, secp384r1, secp521r1
- SEC2
- 標数 2 の体
体 $\mathrm{GF}(2^m)$ 上の楕円曲線パラメータは，以下の7つの値で定義される． \[ T= (m, f(x), a, b, G, n, h) \] ここで，$m$ は有限体 $\mathrm{GF}(2^m)$ を決める整数，$f(x)$ は $\mathrm{GF}(2^m)$ の 次数 $m$ の既約多項式，$a, b \in \mathrm{GF}({2^m})$ は楕円曲線 $E(\mathrm{GF}(2^m))$ を定義する値， $G$ は $E(\mathrm{GF}(2^m))$ 上のベースポイント，$n$ は $G$ の位数，$h$ はコファクタと呼ばれ $h = \#E(\mathrm{GF}(2^m)) / n$ である．
以下に，標準化等で規定されている楕円曲線パラメータの名称を示す．
$a,b \in \{0,1\}$ なる曲線は，Koblitz曲線として知られており，楕円演算を効率化することができる．- X.9-62
163V1, 163V2, 163V3, 176W1, 191V1, 191V2, 191V3, 208W1, 239V1, 239V2, 239V3
272W1, 304W1, 359V1, 368W1, 431R1 - NIST
K-163, B-163, K-233, B-233, K-283, B-283, K-409, B-409, K-571, B-571 - SEC2
sect113r1, sect113r2, sect131r1, sect131r2, sect163k1, sect163r1, sect163r2
sect193r1, sect193r2, sect233k1, sect233r1, sect239k1, sect283k1, sect283r1
sect409k1, sect409r1, sect571k1, sect571r1
- X.9-62
- その他
IDベース暗号では，次の体も用いられる．- 拡大体 ($\mathrm{GF}(p^m)$)
- 標数3の体 ($\mathrm{GF}(3^m)$)
座標系の選択
楕円曲線上の演算を行う上で，どのような座標系を選択するかにより演算性能に差が現れる． 座標系により，楕円のスカラー倍算に使用する逆元と乗算の回数が異なり，利用するプラットフォーム上での逆元と乗算の性能の影響を受けるからである．
以下のような座標系がある．
- アフィン座標
アフィン座標では，座標点は $(x, y)$ で表され，楕円曲線は以下となる．$y^2 = x^3 + ax+ b\quad \mbox{for}\ \mathrm{GF}(p)$
$y^2 + xy = x^3 + ax^2+ b\quad \mbox{for}\ \mathrm{GF}(2^m)$
無限遠点 ${\cal O}$ は， $(x,y) = (0,0)$，($b \ne 0$) で表される． - 射影座標系
- プロジェクティブ座標
平面上の点 $(x, y)$ を空間内の点 $(X, Y, Z)\ (Z \ne 0 \bmod p)$ に
$x = X/Z \bmod p$
$y = Y/Z \bmod p$
で変換する．$(x, y) \rightarrow (X, Y, Z)$ は一対一対応であり，平面上の点 $(x, y)$ を空間内の「原点と点 $(X, Y, Z)$ を通る直線」に対応させるとき，$(x, y)$ はこの直線と一対一対応である．
無限遠点 ${\cal O}$ は，平面 $Z = 0 \bmod p$ に対応する．
楕円曲線は以下となる．$Y^2Z = X^3 + aXZ^2 + bZ^3\quad \mbox{for}\ \mathrm{GF}(p)$
$Y^2Z + XYZ = X^3 + aX^2Z + bZ^3\quad \mbox{for}\ \mathrm{GF}(2^m)$
- ヤコビ座標 (重み付きプロジェクティブ座標)
平面上の点 $(x, y)$ を空間内の点 $(X, Y, Z)\ (Z \ne 0 \bmod p)$ に
$x=X/Z^2 \bmod p$
$y=Y/Z^3 \bmod p$
で変換する．
楕円曲線は以下となる．$Y^2 = X^3 + aXZ^4 + bZ^6\quad \mbox{for}\ \mathrm{GF}(p)$
$Y^2 + XYZ = X^3 + aX^2Z^2 + bZ^6\quad \mbox{for}\ \mathrm{GF}(2^m)$
無限遠点 ${\cal O}$ は，$(\gamma^2, \gamma^3, 0),\ \gamma \in {\mathrm{GF}(p)}^*$ で表される．
ヤコビ座標において，座標点を $(X, Y, Z, Z^2, Z^3)$ で表すことにより，楕円演算の効率化を図ることができる．この座標表現をチョビンスキー座標という．
- プロジェクティブ座標
- 座標系の変換
- アフィン座標 $(x_A, y_A)$ からプロジェクティブ座標 $(x_P, y_P, z_P)$ への変換
$x_P = x_A \bmod p$
$y_P = y_A \bmod p$
$z_P = 1\ $ ($x=0, y=0$ ならば $z_P = 0$)
- プロジェクティブ座標 $(x_P, y_P, z_P)$ からアフィン座標 $(x_A, y_A)$ への変換
$x_A = x_P/z_P \bmod p$
$y_A = y_P/z_P \bmod p$ ($z_P = 0$ のとき，$x_A = 0, y_A = 0$ )
- アフィン座標 $(x_A, y_A)$ からヤコビ座標 $(x_J, y_J, z_J)$ への変換
$x_J = x_A \bmod p$
$y_J = y_A \bmod p$
$z_J = 1$ ($x=0, y=0$ ならば $z_J = 0$)
- ヤコビ座標 $(x_J, y_J, z_J)$ からアフィン座標 $(x_A, y_A)$ への変換
$x_A = x_J/z_J^2 \bmod p$
$y_A = y_J/z_J^3 \bmod p\ $ ($z_J = 0$ のとき，$x_A = 0, y_A = 0$)
- アフィン座標 $(x_A, y_A)$ からプロジェクティブ座標 $(x_P, y_P, z_P)$ への変換
座標点の圧縮
楕円曲線暗号においては，楕円曲線上の点を保存したり鍵交換のために送信したりすることが必要になる．このとき，記憶領域や送信データ量を減らすために点を表現するビット数を減少させることが行われる．これを点圧縮 (Point compression)と呼ぶ．
有限体 $\mathrm{GF}(q)$ ($q$ が $2^m$ または $m$ ビットの素数)において，アフィン座標系で点の情報を保持するためには $2m$ ビット必要になる．しかし，曲線上の点の $x$ 座標が分かれば，$y$ 座標は $y$ に関する二次方程式を解くことにより求めることができる．このとき，二次方程式の2つの解を区別するために1ビットあれば十分である．したがって，$m+1$ ビットで点を表現することができる．
$y$ 座標は以下に示すように常に圧縮することが可能であり，これを $\tilde{y}$ (1ビット)で表す．
- $q$ が奇素数ならば，$\tilde{y} := y\ \bmod\ 2$ とする．ここで，$y$ は $q$ より小さい正整数とみなされる．さもなくば，$y$ の最右ビットを $\tilde{y}$ とする．
- $q$ が $2$ のべきならば，$\tilde{y}$ は体要素 $yx^{-1}$ の最右ビットである．($x = 0$ を除く，$x = 0$ ときは $\tilde{y} := 0$).
楕円曲線上の点の圧縮形式から $y$ 座標を復元するアルゴリズム
- $y$ 座標の復元 (素数の場合)
入力: 素数 $p$，法 $p$ で定義された楕円曲線 $E$，$E$ 上の点 $(x, y)$ の $x$ 座標 ，および座標 $y$ の圧縮表現 $\tilde{y}$
出力: 点の $y$ 座標
- $g := x^3 + ax + b\ \bmod\ p$
- $p$ での $g$ の平方根 $z$ を求める．平方根が存在しない場合，終了．
- $z$ の最右ビット($z \bmod 2$) を $\tilde{z}$ とする．
- If $\tilde{z} = \tilde{y}$ then $y \leftarrow z$, else $y \leftarrow p-z$
- Return $y$
- $y$ 座標の復元 (標数2の体の場合)
入力: 有限体 $\mathrm{GF}(2^m)$，$\mathrm{GF}(2^m)$ で定義された楕円曲線 $E$，$E$ 上の点 $(x, y)$ の $x$ 座標，および座標 $y$ の圧縮表現 $\tilde{y}$
出力: 点の $y$ 座標
- If $x = 0$ then $y := \sqrt{b}$ and go to step 7
- $\alpha := x^3 + ax^2 + b$ in $\mathrm{GF}(2^m)$
- $\beta := \alpha (x^2)^{-1}$
- $z^2 + z = \beta$ を満たす体の要素 $z$ を求める． 解がない場合，終了．
- $z$ の最右ビットを $\tilde{z}$ とする．
- $y := (z + \tilde{z} + \tilde{y} ) x$
- Return $y$
楕円点データ変換
楕円点とオクテット列の相互変換を行う方法である．
- 楕円点からオクテット列への変換：ECP2OSP}
無限遠点の場合は1オクテットの 0x00 を返す．
無限遠点でない場合は次の3通りの変換を選択する．- 非圧縮形式
非圧縮形式を表す1オクテット(0x04)，$x$ 座標をFE2OSP変換したオクテット列 ，$y$ 座標をFE2OSP変換したオクテット列を連結して返す． - 圧縮形式
圧縮形式であることと $y$ 座標の符号を表す1オクテット(0x02または0x03)，$x$ 座標をFE2OSP変換したオクテット列を連結して返す． - ハイブリッド形式
ハイブリッド形式であることと $y$ 座標の符号を表す1オクテット(0x06または0x07)，$x$ 座標をFE2OSP変換したオクテット列，$y$ 座標をFE2OSP変換したオクテット列を連結して返す．
- 非圧縮形式
- オクテット列から楕円点への変換：OS2ECPP
オクテット列の第1オクテットにより変換方式を判断し，2番目以降のオクテット列を変換する．- 第1オクテットが 0x00 の場合(無限遠点)
無限遠点を返す． - 第1オクテットが 0x04 の場合(非圧縮形式)
第2オクテット以降を，$x$ 座標へ変換すべきオクテット列と $y$ 座標へ変換すべきオクテット列に分割し，それぞれを有限体の演算で $x$ 座標，$y$ 座標に変換する(OS2FEP)． - 第1オクテットが 0x02 または 0x03 の場合(圧縮形式)
第2オクテット以降を $x$ 座標に変換し(OS2FEP)，$x$ 座標から $y$ 座標を求める．求めた $y$ 座標の符号と1番目の 0x02 または 0x03 で表される $y$ 座標の符号が一致しなければ，$y$ 座標を符号反転して返す． - 第1オクテットが 0x06 または 0x07 の場合(ハイブリッド形式)
第2オクテット以降を $x$ 座標へ変換すべきオクテット列と $y$ 座標へ変換すべきオクテット列に分割し，それぞれを有限体の演算で $x$ 座標，$y$ 座標に変換する(OS2FEP)．変換した $y$ 座標の符号と1番目の 0x06 または 0x07 で表される $y$ 座標の符号が一致しなければ変換失敗となる．
- 第1オクテットが 0x00 の場合(無限遠点)
／