はじめに
楕円曲線の無限遠点を調べた際の備忘録。
以下のような人向け
- プログラマで数学系より実装寄り
- 無限遠点の概念にピンとこなかった
- 射影座標系（プロジェクティブ座標系）を知らない
経緯
楕円曲線を調べていると確定で出てくる謎の点、無限遠点。
楕円曲線上で計算を行う際、実質0として扱われているが、原点のことではない。
無限遠点はいろいろなサイトで解説されており、大体
- 座標値が無限な点
- 楕円曲線上の点二つと接する直線との交点（どこの交点とかを指しているわけではない）
- 線を伸ばした先で集合するなぞの点..
のように書かれている。
うーん 概念やイメージとしてはわかるが、実際に実装する方法がいまいちピンとこない。
自分が感じた疑問点
- どうやって実装するの？
- 原点のような固定の値？
- 例えば整数で1-1=0となるように、楕円曲線でもI+O = I or I-I=Oとして使用できる点が存在するのか？それは0ではないの？
などなどを気になったので無限遠点を追いかけてみた。
先に結論から書くと、アフィン座標ではそれはそういう点のオブジェクトとして考えると実装時にも違和感がなかった。
もっといえばプロジェクティブ座標系で考えると明確な値を設定することができる。
よくわからないと思うので、疑問点の解消とともに、実際に書かれている実装の解説を行っていく。
Opensslでの実装
int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
{
if (group->meth->point_set_to_infinity == 0) {
ERR_raise(ERR_LIB_EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
return 0;
}
if (group->meth != point->meth) {
ERR_raise(ERR_LIB_EC, EC_R_INCOMPATIBLE_OBJECTS);
return 0;
}
return group->meth->point_set_to_infinity(group, point);
}
methにセットされている内容はこれとか
int ossl_ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
if (EC_POINT_is_at_infinity(group, point)) {
ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
if (EC_POINT_is_at_infinity(group, a))
if (EC_POINT_is_at_infinity(group, b))
if (EC_POINT_is_at_infinity(group, a)) {
if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
return BN_usub(point->Y, group->field, point->Y);
}
これ
/*
* Set an EC_POINT to the point at infinity. A point at infinity is
* represented by having Z=0.
*/
int ossl_ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
EC_POINT *point)
{
point->Z_is_one = 0;
BN_zero(point->Z);
return 1;
}
これ
/* Indicates whether the given point is the point at infinity. */
int ossl_ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
const EC_POINT *point)
{
return BN_is_zero(point->Z);
}
見ての通りpointのZ要素を見ているか0を入れるだけ。
さらに深堀してみるとどうにもポイント型に入っている値がなにかおかしい。
struct ec_point_st {
const EC_METHOD *meth;
/* NID for the curve if known */
int curve_name;
/*
* All members except 'meth' are handled by the method functions, even if
* they appear generic
*/
BIGNUM *X;
BIGNUM *Y;
BIGNUM *Z; /* Jacobian projective coordinates: * (X, Y,
* Z) represents (X/Z^2, Y/Z^3) if Z != 0 */
int Z_is_one; /* enable optimized point arithmetic for
* special case */
};
二次元座標でのZって何？
Jacobian projective coordinatesってなんだろう？
ヤコビアンプロジェクティブ？
ヤコビ行列的な？
疑問点がさらに増える。
よくわからないのでここを調査した。
射影座標系（プロジェクティブ座標系）
数学用語を用いずに言えば、一対一の点移動した座標。
いわゆる一般の座標（アフィン座標）は（x,y)の二次元だが、これを(x,y,z)で表現したもの。
よく画像の回転で用いるアフィン変換では、(x,y,w)みたいな変数wをつかうが、それとは完全に別物。
つまりこの座標系においては、 (x,y,0)=無限遠点といえる。
これでopensslで
point->Z_is_one = 0;
BN_zero(point->Z);
return 1;
のような処理を書くわけだ、(∞,∞)と言われるよりよほどわかりやすい。
非常にすっきり！
わけわからん無限とかいうオブジェクトは出現しないし、演算速度も速くできるし、一石二鳥。
というわけでEC系のライブラリは、ほとんどがこの座標系での実装を行っているみたい。
アフィン座標（通常の座標系）
色々いったけど、プロジェクティブ座標系とか実装するのだるい。。
アフィン座標系でどうにかならんか？
結論 普通にできる
よくよく無限遠点を使用した計算を考えてみる。
- O＋P=P+O=P
- P-P=O つまり PでPを引いた場合
...これって無限遠点に具体的な数字いらなくない？
基本的に、楕円曲線での演算は少なくそれぞれ
- 点Pと点Qの足し算
- 点のスカラー倍（同じ点の足し算だが、とりあえず）
とかしかない。
fn add(p : Point, q : Point) -> Point{
if p == -q{
return 無限遠点
}
if p == 無限遠点{
return q;
}else {
return p;
}
//ここで計算処理詳しくは書かない
p + q
}
fn double(P : Point) -> Point{
if p == 無限遠点{
return 無限遠点
}
//ここで計算処理
2*p
}
疑似コードを書いたが、こんな感じで点が無限遠点かどうかさえ分かっていれば、数値がなにであるのか等は必要ない。
fn infinity(){
Point{infinity_flag : true, x : 100, y : 100 }
}
こんなんでも良い。
なんでかこれが理解できなかった。。。
まとめ
無限遠点とは、
アフィン座標系では、楕円曲線に触れない点オブジェクトとして実装すればよく、
プロジェクティブ座標系では、単純に(X,Y,Z)=(,,0)の座標ということになる。
...長々と色々書いていたが、ここだけしっていれば正直良いと思う。
楕円曲線を実装することはないと思うけど、実装するくらいならライブラリ使ったほうが良いし。
正直、まとめる必要があるか不明だけど、せっかく調べたので。
参考文献