楕円曲線上の複数の点からその曲線のパラメータを思考停止で求めるテク

最近このテクを使う問題をいくつか解いたのでメモ。楕円曲線 $E$ と $E$ 上のいくつかの点 $P, Q, R, S \in E$ みたいなのがあって、 $E$ は与えられておらず $P, Q, R, S$ の座標だけがある、みたいな状況。

（今回なら）4点の座標と、その座標が満たすべき制約（Weierstrass標準形なら $y^2 \equiv x^3 + ax + b \mod p$ ）から、 $E$ のパラメータ（ $a, b, p$ ）を求めたい。知っている限りだとASIS CTF 2019 QualsのHalloween Partyとか、UIUCTF 2020のnook cryptoが出題例。

scrapbox.io

上記writeupにもあるようにこれは愚直な式変形でできる。 $a$ や $b$ のような知らないパラメータがなくなるように式変形して、複数の式でGCDを取ると剰余の法 $p$ （か、その小さい倍数）が得られるので、あとは $a$ だけが不明とか $b$ だけが不明みたいな式を作って剰余方程式を解いていく、という方針。

そんなに難しいということはないんだが、式変形というのは結構大変なので自分でやらなくていいならやりたくない。幸い変数をどんどん消去するように式変形する、という処理は自動化できる。

どうやるかというと消去式（resultant）というやつを使う*1。細かい内部の挙動は置いておいて、これは2式と消したい変数を与えると、その消したい変数を消去した形の式を返すようなインタフェースを持つ関数だと思って良い。

$f_1 = y_1^2 - (x_1^3 + ax_1 + b)$

$f_2 = y_2^2 - (x_2^3 + ax_2 + b)$

みたいに2つ式を立てておいて、g = f1.resultant(f2, b)とすると $g = (y_1^2 - y_2^2) - (x_1^3 - x_2^3+ a(x_1 - x_2))$ みたいな式を返してくれる。このくらいなら人間がやってもわけないが、 $b$ でなく $a$ を消したいという場合にも勝手にやってくれるので便利。

ただしこの方法も万能ではないので、resultantが使えないような式と変数の組み合わせや、そもそもresultantを呼び出せないような環が存在する。それぞれ消したいと指定した変数が消えてない式が帰ってきたりする場合や、除算が定義されていない集合上の多項式を定義している場合。

ということで、最近ではとりあえずあらゆる値を変数にして $\mathbb{Q}$ 上の多変数多項式環 $\mathbb{Q}\lbrack x_1, x_2, \dots \rbrack$ 上で立式して、あらゆる式の組み合わせでとにかう消去式を試して変数を片っ端から消していきうまく消えているやつを使う、という方法をとっている。