こんにちは。SECCON CTF 2019以来のオンサイトでありSECCON CTF 2019以来の決勝であるSECCON CTF 2022 Finals (international/domestic) が開催され、無事閉幕しました。私はSECCON CTF 2022 Quals から引き続きCTF WGとして作問に携わっていましたので、自分が出題した問題についていくらか感想や解説を書こうと思います。オンサイトCTF自体の感想や反省などについては別途どこかに書きます。
[Crypto 200] authenticator
解説
次のようなスクリプトが与えられる問題です。5秒単位で切り替わるタイムスタンプtと秘密の値key、そして自由に指定できる入力codeをもとに が計算されるので、その値が
code に帰ってくるような入力codeを入力できればフラグがもらえる、という問題設定です。
ただし、ヒントとしての値をもらうことができます。
この問題では、まずヒントを利用してkeyの値を求め、その後制約を満たすようなcodeの値を計算することになります。CRCの計算が途中にあって難しそうに見えますが、単なる商環上の演算なので以下のように愚直にやると解けます。CRCの演算と多項式環（商環）上の操作の対応についてはCRC - crypto-writeup-publicなどを参考にしてください。
感想
一見そこそこ複雑そうな問題設定ですが、多項式環で考えると割と素直に解けるのでそこそこ気に入っています。
難易度でみれば簡単な部類だと思っていたのでCrypto warmup枠で出題しましたが、国内では4チームしか解けているチームがなかったのでもしかしたら少しむずかしかったのかもしれません。競技後に問いたプレイヤーに聞いてみるとCrypto jeopardyの中で一番苦戦したという声もありました。
一方、国際チームは順調に攻略して結局すべてのチームが正解したので、過去にCRCに関する問題や似たようなコンセプトの問題を解いたことがあるかどうかで感じる難易度が違ったかもしれません。CRCを多項式の理論からみるというのはなかなか便利で面白い技なので、もし知らなかった場合はこの機会に憶えてもらうと今後役に立つこともあるかもしれません。
[Crypto 300] hell
解説
超楕円曲線（Hyperellipticcurve）に関する問題です。下記のSageスクリプトとその実行結果が与えられます。
このスクリプトは有限体上の超楕円曲線
（今回は
）を、ある点
が
上に含まれるように生成し、この点によって生成されるヤコビアン上の（半）被約因子
に対して、
（のMumford表現）を出力しています。この問題では
がフラグになっているので、これを求めるのが目的です。
おそらく超楕円曲線について詳しくない皆様は何を言われているか全くわからないとは思いますが、そういう問題です。超楕円曲線についてざっくりと知りたい方は以下のエントリを参考にしてください。
さて、この問題ではまず3つの被約因子のMumford表現から超楕円曲線を復元する必要があります。これについては超楕円曲線とそのヤコビアン上の被約因子の間には、被約因子を
と表現して
という関係があります。今回の問題では
ですから
で、これを変形すると
となります。
今3つの被約因子を持っているのでそれぞれについて上記の式が成り立つので、中国剰余定理より
が復元できます*1。これで超楕円曲線のパラメータが求まりました
続いてはこの3点と超楕円曲線のパラメータを利用してを求めたいです。まずは
を計算し、その後
から
の座標を求めることになります。
与えられた3点からを求めるには単に（ヤコビアン上の）被約因子の演算をすればよく、
を計算すると
が求まります。
続いてを求める方法ですが、ヤコビアンの位数を効率的に求める方法は今の所知られていないので
に対して
の逆数をかけて
を求めることはできません。しかし、特定のケースにおける被約因子の2倍算ではx座標が単に2乗されるので*2、
のx座標の
における平方根を求めれば
のx座標が計算できます。x座標が与えられたときに対応するy座標を計算することは簡単なので、これで
が求まりました。
……以上の理屈をコードに落とし込むと以下のようになります。なんだか騙されたみたいに短くて簡単ですね。
感想
以前のyoshi-campでmitsuくんに超楕円曲線について教わってからずっと超楕円曲線に関する問題を作りたいと思っていて、ついに形にしました。私も学びながら作ったので、超楕円曲線を知らないひとでも競技中に調べたり実験したりして解き切れる程度の難易度を目標にしています。実際、多くの国際チームや一部の国内チームではまさにそのようにしてこの問題を解いてくれていたようです。
個人的にはそのせいで捻りの少ない問題になってしまって難易度の観点では微妙かなと思っていましたが、いくつかの国際チームのプレイヤーから教育的で勉強になったし面白かったという感想をもらえたので良かったです。
私の知る限りでは超楕円曲線についてCTFの問題で取り扱っているのはhxp CTF 2020のhyper/hyperhyperに続いて2例目だと思うので、これをきっかけにいろんなプレイヤーが超楕円曲線に関する問題を解いたり、取り組んだりするようになってくれたら一番良いなと思っています
おわりに
数を作れなかったことは悔やまれますが、観測した範囲では私の作った問題は概ね楽しまれていそうで安心しています。いろんなプレイヤーに問題を褒められると（あるいは欠点を指摘されても）嬉しいので、感想・writeupなどお待ちしています。来年も引き続きこのくらいのクオリティは維持しつつ、もう少したくさん作れるようになるとか進歩していきたいと思っています
*1:3点で十分が求められるようなサイズになるように問題が作られています
*2:https://github.com/sagemath/sage/blob/293dd7255b231ff9cd17407ee3c23841a06b5c5b/src/sage/schemes/hyperelliptic_curves/jacobian_morphism.py#L255 においてd=1の場合
