楕円曲線暗号で用いる楕円曲線のパラメータは,暗号の安全性に関わるため十分注意して選択する必要がある. $\mathrm{GF}(q)$ 上の楕円曲線 $E$ をランダムに選んだ時,その $E$ が楕円曲線暗号に適しているかの判定は,主に位数 $N = \#E(\mathrm{GF}(q))$ の値で判定される. 例えば, $N$ が小さな素数の積に分解されるような場合は,既存の(一般の有限群に適用できる) 離散対数計算アルゴリズムが適用されるので好ましくない.
また,楕円曲線を定義する体の選択により,実装の容易性や性能が変化する.
楕円曲線上の演算を行う上で,どのような座標系を選択するかにより演算性能に差が現れる. 座標系により,楕円のスカラー倍算に使用する逆元と乗算の回数が異なり,利用するプラットフォーム上での逆元と乗算の性能の影響を受けるからである.
以下のような座標系がある.
$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 = X/Z \bmod p$
$y = Y/Z \bmod p$
で変換する.$(x, y) \rightarrow (X, Y, Z)$ は一対一対応であり,平面上の点 $(x, y)$ を空間内の「原点と点 $(X, Y, Z)$ を通る直線」に対応させるとき,$(x, y)$ はこの直線と一対一対応である.$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=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_P = x_A \bmod p$
$y_P = y_A \bmod p$
$z_P = 1\ $ ($x=0, y=0$ ならば $z_P = 0$)
$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_J = x_A \bmod p$
$y_J = y_A \bmod p$
$z_J = 1$ ($x=0, y=0$ ならば $z_J = 0$)
$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$)
楕円曲線暗号においては,楕円曲線上の点を保存したり鍵交換のために送信したりすることが必要になる.このとき,記憶領域や送信データ量を減らすために点を表現するビット数を減少させることが行われる.これを点圧縮 (Point compression)と呼ぶ.
有限体 $\mathrm{GF}(q)$ ($q$ が $2^m$ または $m$ ビットの素数)において,アフィン座標系で点の情報を保持するためには $2m$ ビット必要になる.しかし,曲線上の点の $x$ 座標が分かれば,$y$ 座標は $y$ に関する二次方程式を解くことにより求めることができる.このとき,二次方程式の2つの解を区別するために1ビットあれば十分である.したがって,$m+1$ ビットで点を表現することができる.
$y$ 座標は以下に示すように常に圧縮することが可能であり,これを $\tilde{y}$ (1ビット)で表す.
入力: 素数 $p$,法 $p$ で定義された楕円曲線 $E$,$E$ 上の点 $(x, y)$ の $x$ 座標 ,および座標 $y$ の圧縮表現 $\tilde{y}$
出力: 点の $y$ 座標
入力: 有限体 $\mathrm{GF}(2^m)$,$\mathrm{GF}(2^m)$ で定義された楕円曲線 $E$,$E$ 上の点 $(x, y)$ の $x$ 座標,および座標 $y$ の圧縮表現 $\tilde{y}$
出力: 点の $y$ 座標
楕円点とオクテット列の相互変換を行う方法である.