今年は決勝がなかったSECCON CTFですが、Quals相当のCTFはSECCON 2020 Online CTFとして開催されました。嬉しいことに作問をやりませんか？ と誘っていただけて、cryptoの問題3問を提供しました。この記事には作問者お気持ちと想定解法を書きます。CTF全体に関するよしなしごとはtwitterとかに書いてます。
koharu (144points / 44 solves)
多項式環の上でGoldwasser-Micaliをしているだけの問題です。Goldwasser-Micali cryptosystemはInterKosenCTF 2020でも出したので大好きマンみたいになってしまった……。
irreducibleながそんなに大きくないので、sageで雑に
factorメソッドを呼べばを素因数分解することができます。あとは問題のスクリプト中にもあるように
という式で、ある式
を法とした時に
がquadratic residueか否かを判断することができるので、これを使って愚直に復号を行うだけです。
もともとは多項式体上でquadratic residucityを求められますか？ という問題にしたかったはずがうまく形に出来ず、結局題意が「多項式体上でもquadratic residuicity checkができるんですよ、おもしろくないですか？ あ、そういえば多項式が弱いと因数分解できるのが問題です」というなんとも中途半端な形になってしまいました。 個人的には不完全なまま時間に追われてこの問題を出題してしまい、実は結構悔いています。
問題名、問題文とフラグはアイドルマスターシンデレラガールズに登場する古賀小春ちゃんとそのペット、ヒョウくんから。polyとperoのフィーリングでヒョウくんぺろぺろを思い出したので。
ところで因数分解しなくても通せるらしいです。全然検証していませんでした。ごめんなさい……
urara (240pts / 14solves)
出題したなかでは一番にお気に入りの問題です。をもってきて、楕円曲線とRSAでそれぞれ平文を暗号化しています。楕円曲線の方は
で、RSAの方は
です。
変数を用意しておいて、楕円曲線上の2倍公式に基づいて
と
との間の関係式を作った上で、
と比べると、どちらも
が根になるため式
で割り切ることができ2式のGCDを取ることで
で等しい式が得られ、あとはいい感じにするとフラグが得られます。
もともとはもっとくだらない問題にするつもりだったけど、試行錯誤しているうちになんかいい感じになりました。問題も解法もすっきりとかけて、かつ多少の非自明感があってとても良い問題だとおもいます。同じSECCON 2020 Online CTFで出題されたsharsableも問題を見た時感動しましたが、この問題もタイマンを張れるかなと。
問題名、問題文とフラグはうらら迷路帖から。最近漫画の方を読みましたが、良いですね。作中で楕円曲線占いが登場しなかったのが不思議でなりません
また、非想定解として2倍公式から頑張ってcoppersmithで剰余方程式を解くことでも解けるようです。こちらは最終的には想定解に近い解き方になりますが、パラメータ次第では本当に問題として壊れていたかも知れませんね。フラグは十分な長さになるようにパディングをつけましょう。
crypto01 (393pts / 4solves)
結局これがcryptoとしてはボス問となりました。この問題はこの論文 を発見して理解して実装すれば解けます*1。それ以外にあんまり説明するところはありません。素因数のbitの一部を渡しているので、これをうまく使って力任せ素因数分解……することができたかもしれません。多少調べた感じでは出来ないと思いますが、あまり自信がないです（そのせいで問題のインスタンスを3つも用意している）。
当初はsagemathのsmall_rootsでうまく求解出来ずに困っていましたが、後でとにかくepsilonを小さい値にしておけばなんとかなるということがわかり出題できるようになりました。うまいパラメータを見つけることができればさほど時間をかけずに解けます。
問題名、問題文とフラグは仮面ライダーゼロワンから。名前を考えるのが面倒でcrypto01という仮名を置いていたところ、急にゼロワンの存在を思い出して、この作品について唯一しっている腹筋崩壊太郎をフラグにしました。
*1:そういうわけで問題としては少し気に入らない感じがあります
