0CTF 2018 Quals: g0g0g0

[[ 0CTF Quals 2018 ]]の [[ rev ]]問。リベンジしたいと思っていてやっと手を付け始めた模様。 GolangプログラムのトレースがSSAっぽい形で渡されるので、grep(ag)を駆使して読むところまでは大体できたがそこからどうするのかさっぱり… やっぱり難しいな〜 ということでwrite-upを見る。

• [http://westerns.tokyo/writeups/0ctf2018quals.html]
• [https://github.com/xiaohuajiao/my-ctf/tree/master/2018/0ctf/g0g0g0]

trace.logを読む

func4が何をしているのかわからなかったが、今メモを見返してみると掛け算の筆算を真似していることに気がついた。

また、func*とfunc*の間にあるmain.mainの処理を見ると、t63の値がt61のコピーで10固定だとわかる。

29992-Leaving main.func2, resuming main.main at /tmp/gogo.go:231:16.
29993-   t61 = new [1]int (slicelit)
29994-   t62 = &t61[0:int]
29995-   *t62 = 10:int
29996-   t63 = slice t61[:]
29997-   t64 = func4(t51, t52)
29998:Entering main.func4 at /tmp/gogo.go:104:6.

ここからa/(b+c) + b/(a+c) + c/(a+b) = 10という式が出る。

式を解く

write-upによると楕円曲線の式らしい(泣)。 ただググってみると有名な式らしく、ちょうど答えがあった。

Quoraに親切な解説を見つけたが後半が何言ってるかわからない… a/(b+c)+b/(c+a)+c/(a+b)=4の自然数解(a,b,c)を求めるも見たが余計わからなくなった。

整数論とか借りて読んでみようかなぁ…

[[ CTF ]]