ふるつき

v(*'='*)v かに

2022年に読み始めて面白かったWeb小説

kotatsugame リスペクトです。途中までしか読んでなくても、その途中までが面白かったら載せています

l-torsion pointを生成元としたカーネルを持つ同種写像がl-isogenyになることの説明

伝わるようなタイトルを考えるのが難しすぎる！

同種写像計算の基本命題*1というやつがあって、詳しくは説明しないんですが主張としては、

（有限体上の）楕円曲線 Eを定義域とする同種写像 \phi: E \to E'（とその終域 E'）は Eと代数閉包上の楕円曲線 E(\bar{\mathbb{F_p}})の有限部分群 Cから同型を除いて一意に定まり、 \ker \phi = Cである

というものです。

つまり、適当な楕円曲線と同種写像の核にしたい群があれば同種写像が決まります。さらにここで核にしている Cが素数位数なら、 Cの代わりにその生成元 Hだけあれば良いです（そしてVéluの公式などで E, Hから \phiを具体的に計算できます）。

この時 Hが l-torsion pointであれば、 \phiは l-isogenyとなるのですが、その理屈がわからなくて考えたので説明します。

というわけで素数 lを位数とする適当な点 H \in E(\bar{\mathbb{F_p}})をとってきて、 Hが生成する巡回群 \langle H \rangleを核とする同種写像 \phiを求めたとします。

この時、 \deg \phi = \#\langle H \rangle = lが成り立ちます*2。なぜなら、 \ker \phi = \lbrace H, 2H, \dots, (l-1)H ,lH \rbrace より \phiは l個の根を持ち、 l個の根を持つためには \phiは l次の多項式である必要があるからです。

従って、 l-torsion point Hを生成元としたカーネルを持つ同種写像 \phiは l-isogenyです

……という理屈で私は納得したけど、皆さんはどうですか。ミスってるよとか行間がデカすぎるとか、ここに厳密な証明書いてありますよとかあれば教えてください。

*1:初めてこれを知った https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_03aikawa.pdf での呼称を使ってますが、もうちょっと名前っぽい名前がありそうな気がする

*2:書いてなかったけど \phiは有理多項式なので次数が定まります

点の位数を整えるテク

この記事はCTF tools/tips Advent Calendar 2022 - Adventarの13日目の記事です

数学の話ですけど、群の要素 eには位数というパラメータがあって、それはその要素 e自身を n回演算した時に単位元になるような最小の値です。

具体例を出すと、ある有限体上の楕円曲線 Eの点 P \in Eについて nP = \mathcal{O}となるような最小の nが位数です。

CTFの文脈では（それ以外でも）特定の位数を持った点が欲しくなることがあります。典型的にはInvalid Curve AttackやSmall Subgroup Attackと呼ばれる攻撃を試みるときや、同種写像を求めたいので l-torsion pointを求めたいと言った場合です。

こういう場合に特定の位数を持つ点を生成するの方法の一つに、適当に点を生成して後から位数がいい感じになるように調整する、というテクがあるので紹介します。

適当な有限体上の楕円曲線 Eの、位数が lであるような点が欲しいという例を考えてみます。

まず適当に点 P \in Eを生成し、この点の位数を n = |P|とします。
この時、 lが nを割り切るなら、 P' = \frac{n}{l}Pの位数は lになります。

これは lP' = (\frac{l}{l})nP = \mathcal{O}と計算することで確認できます。厳密にはこれが最小の自然数であるということまでちゃんと示したほうが良い気がしますが、テクとしてはこう計算できるよ、ということが言えれば十分かなと思います。

このようなテクはPohlig-Hellman attackなどでも計算量削減のために使われたりしています。例に挙げたのは楕円曲線の場合ですが、単なる乗法群でも同じように位数を調整できます。

楕円曲線の場合は他にもdivision polynomialの根から点を生成するなどとして欲しい位数の点を生成できますが、愚直で一番楽な方法をご紹介しました