この記事はCTF tools/tips Advent Calendar 2022 - Adventarの13日目の記事です
数学の話ですけど、群の要素には位数というパラメータがあって、それはその要素
自身を
回演算した時に単位元になるような最小の値です。
具体例を出すと、ある有限体上の楕円曲線の点
について
となるような最小の
が位数です。
CTFの文脈では（それ以外でも）特定の位数を持った点が欲しくなることがあります。典型的にはInvalid Curve AttackやSmall Subgroup Attackと呼ばれる攻撃を試みるときや、同種写像を求めたいのでtorsion pointを求めたいと言った場合です。
こういう場合に特定の位数を持つ点を生成するの方法の一つに、適当に点を生成して後から位数がいい感じになるように調整する、というテクがあるので紹介します。
適当な有限体上の楕円曲線の、位数が
であるような点が欲しいという例を考えてみます。
まず適当に点を生成し、この点の位数を
とします。
この時、が
を割り切るなら、
の位数は
になります。
これはと計算することで確認できます。厳密にはこれが最小の自然数であるということまでちゃんと示したほうが良い気がしますが、テクとしてはこう計算できるよ、ということが言えれば十分かなと思います。
このようなテクはPohlig-Hellman attackなどでも計算量削減のために使われたりしています。例に挙げたのは楕円曲線の場合ですが、単なる乗法群でも同じように位数を調整できます。
楕円曲線の場合は他にもdivision polynomialの根から点を生成するなどとして欲しい位数の点を生成できますが、愚直で一番楽な方法をご紹介しました
