最近このテクを使う問題をいくつか解いたのでメモ。楕円曲線と上のいくつかの点みたいなのがあって、は与えられておらずの座標だけがある、みたいな状況。
(今回なら)4点の座標と、その座標が満たすべき制約(Weierstrass標準形なら)から、のパラメータ()を求めたい。知っている限りだとASIS CTF 2019 QualsのHalloween Partyとか、UIUCTF 2020のnook cryptoが出題例。
上記writeupにもあるようにこれは愚直な式変形でできる。やのような知らないパラメータがなくなるように式変形して、複数の式でGCDを取ると剰余の法(か、その小さい倍数)が得られるので、あとはだけが不明とかだけが不明みたいな式を作って剰余方程式を解いていく、という方針。
そんなに難しいということはないんだが、式変形というのは結構大変なので自分でやらなくていいならやりたくない。幸い変数をどんどん消去するように式変形する、という処理は自動化できる。
どうやるかというと消去式(resultant)というやつを使う*1。細かい内部の挙動は置いておいて、これは2式と消したい変数を与えると、その消したい変数を消去した形の式を返すようなインタフェースを持つ関数だと思って良い。
みたいに2つ式を立てておいて、g = f1.resultant(f2, b)
とするとみたいな式を返してくれる。このくらいなら人間がやってもわけないが、でなくを消したいという場合にも勝手にやってくれるので便利。
ただしこの方法も万能ではないので、resultantが使えないような式と変数の組み合わせや、そもそもresultantを呼び出せないような環が存在する。それぞれ消したいと指定した変数が消えてない式が帰ってきたりする場合や、除算が定義されていない集合上の多項式を定義している場合。
ということで、最近ではとりあえずあらゆる値を変数にして上の多変数多項式環上で立式して、あらゆる式の組み合わせでとにかう消去式を試して変数を片っ端から消していきうまく消えているやつを使う、という方法をとっている。
例えば ASIS CTF Finals 2022で出題されたmonwardという問題や、idekCTF 2022で出題されたECRSAという問題でこのテクを使った。monwardはWeierstrass標準形ではなくてEdwards曲線でパラメータを求める問題だったが、同じテクが使えた。
(idekCTF 2022のwriteupはまだ書いてないので、書いたら載せます)
グレブナー基底で全てを一発でやるとか、そうでなくても処理を一般化&関数化するとか、もうちょっと洗練されたやり方がありそうだが、今のところはこれで満足しているし他に良い方法も知らない。
何かのタイミングでこのテクがお役に立てば幸いです && もっと良いテクを知っていたら教えてください。
*1:Sagemathではresultantというそのままの名前のメソッドが存在するのでこれを使ったら良いが、巷のCTFプレイヤーのコードを読んでいるとSylvester行列を経由して変数を消去するコードもよく見かける。どういう違いがあるかはわかっていないので、知っている人がいたら教えてください。