ふるつき

v(*'='*)v かに

TSGCTF 2023参加記

TSGCTF 2023にzer0ptsとして参加していました。これという問題を解けなかったのでwriteupを書くつもりはなかったのですが、運営になんのお礼もしてないなということを（自分でCTFを開催して）思い出したので、こういう感じで取り組んでいましたという参加記を書きます。運営がこれを見て楽しんでくれたり、開催して良かったと思える度が少しでも上がれば嬉しい

[crypto] Complicated Function

素数pに対してqが次のような関数fを用いて q = f(p)と計算されるRSAです。

def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

warmup問題にもかかわらずかなり悩んでいたのですが、途中で急にfの単調増加性が気になる天啓を受けて解けました

[crypto] Streamer

onetime padで鍵を使いまわしシリーズです。こういう系統の問題に辟易して、solverを書いたことがあったので使ってみたけどうまく行かず、気合で解きました。 cが(になってたりNが|\| になってたりpが|*になってたりして解くの大変だった〜

賢い人は後ろのhexからkeyを探索していい感じにするんだろうなぁ

[crypto] Unique Flag

yoshikingが気合で解いた。DP〜とか言ってるけど普通にDFS + 目grepで良さそうでした

[web] dance

webと書いてあったけどcryptoだったので解きました。CakeCTF 2022に出したhi yoshiking!と同じだね。これがcryptoではなくwebで出されているのmisleadingっぽくてあまり好きではないです……。というのはSurveyに書いた

[crypto] Delta Force

ずっとこれに時間を溶かしてしまった。解けませんでした……。

Nが与えられているからには何らか素因数分解するんだろう。ぱっと思いつくのはECMかgcdだな〜と思って、gcdがちゃがちゃやったら素因数分解できてしまったのが良くなくて、解けそう〜と思って粘着してしまった……

片方の素数ではcusp, もう片方の素数ではnodeになるようなsingular curveに分解できるということまでは気がついて*1、cuspでは解けたけど、nodeでは y^2 \equiv x^3 + Ax^2が y^2 \equiv x^2(x + w^2)にうまく落とし込めなくて（＝Aがquadratic residueじゃなくて）一生困り続けていた。

ここで12時間溶かしたけど、のこり40分くらいでptr-yudaiに相談したら拡大体とかって言われて「！！！！」になってやってみたら変形できた。でも \mathbb{F_p^2*}上でのDLPが解けずに敗北。ここは正確には \mathbb{F_p*}とisomorphicな \mathbb{F_p^2*}の部分群らしいし、位数は p+1でこれがsmoothだったらしい。

楕円曲線の局所的なテクは知ってても、基礎的な代数の知識がなくてそういうことがわからないにゃんです……

面白かったです。手を出せてない問題も面白いと思うのでこれからやっていきたい。Delta Forceに時間奪われた〜。解けない問題に取り組むの楽しすぎる

*1:強い人は問題設定を見たときからこう分けられるんだろうな〜と思って素因数分解し始めていたみたいなのをTLで見てすげーってなった