TDUCTF Crypto (large file, My RSA)

large fileとMy RSAの作問担当しました。

• large file

flag.tar.gzをダウンロードして解凍すればよいのだが、競技中にはダウンロードが終わらないサイズ。
オンサイトみたいな時間制限があるCTFならではの問題を作ろうと考えて思いついた。

tar.gzとは、tarでアーカイブした後にgzipで圧縮したファイルである。
tarはそれぞれのファイルを符号化せずにヘッダを付けて連結する。
gzipはdeflateという形式で符号化するが、これは逐次的に複合できる。

以上から、tar.gzの先頭部分が取得できれば、その部分だけ複合しファイルを取り出し得ることが分かる。

ここまで考察してgzipのソースコードとRFCを読み漁り、これは難問だと思っていた。
のだが、なんとgzipにredirectionして渡せば逐次的に複合した平文が取れた。
この時の悲しみをフラグに込めた。
公式ページhttp://www.gzip.org/recover.txtにも載っているテクだった。

多少エスパーっぽいがtar.gzの仕様について調べたことがある人なら解けるだろう。

• My RSA

線形合同法で擬似乱数を生成し、連続して素数であればそれをkeyとして暗号化する。

十分大きな数であるから、普通には素因数分解できない（余談だが300桁程度の数なら数分で素因数分解出来てしまい、最初に設定した値だとそれだけで解けてしまった）。

鍵となる考えは線形合同法で連続した素数をkeyとしているところである。定義からMODの二次方程式を解けば良いことが分かる。

MODの二次方程式の解には逆数、sqrtが含まれる。
MOD逆数は拡張ユークリッド互除法で求まる。
sqrtはM%4 == 3である場合に限り（そしてMはメルセンヌ数であるから明らかに成り立つ）、(n+1)/4乗すれば求まることが知られる。

フラグにあるようにPARI/GPを使えばこの辺の考察を飛ばして二次方程式の解の公式を書くだけで答えを求めてくれる。

• 所感

Cybozuで問題管理をしていたのだが、その時は20問ほどだった。
当日になるとどうやら問題数が倍になったらしく難易度が崩壊した。
Cybozuとは何だったのか……