zer0pts CTF 2022 writeup
人々もすなる writeup といふものを私もしてみむとするなり
こういうのは堂々としていたほうがいいらしいです
Anti-Fermat
いつものみたいな RSA が置いてあって、素数を生成する方法だけ怪しくて、q と p の xor が下数桁以外違うみたい。ここに至るまでに 33 時間かかった（ HUPC とか ARC とかが悪いよ）。
結局素因数分解をすれば良くて、n の下数桁と p, q の下数桁の積が等しいような p, q は全探索することにして、あと xor の情報から下数桁以外が復元できたらいいんだけど、これはできる。
p, q の bit を下から立てていくことにすると、p * q の i 番目の bit は畳み込みみたいな感じで求まって、例えば p, q の最下位 bit が違う場合だと p, q のどちらかの i 番目の bit を立てるかで p * q の i 番目の bit が変わってくるので、はい。最下位 bit が異なることは実はないので、うまくやらないとだめ。
ところで、実は繰り上がりっていうのがあって、困る。
なんか適当な writeup をみると賢いことをしていて賢いねになった。
OK
競技プログラマ、OK好きそうだと思ってるので解いてください
— 日暮唯愛🌇 (@keymoon_) 2022年3月20日
助かりまくり。問題は長くて、まず nc に v を渡すと k1 = (v - x1)**d mod n, k2 = (v - x2)**d mod n として k1 + key mod n と k2 + ciphertext mod n を返してくれる。こういうの典型として v = (x1 + x2)/2 とすると、k1 = -k2 になる（ d は奇数 ）。返してくれるものを足すと、 key + ciphertext mod n みたいなのが得られる。実は 0 <= key + ciphertext < 2*n なので、key + ciphertext は 2 択になる。実は ciphertext は flag を暗号化したやつ = f と key の xor なので f ^ key + key が得られた。
2 択なのは嫌なので絞っておくと、＾key + key によって偶奇は変わらない（睨めばわかる）ので f と偶奇が同じ方があたり。nc をいっぱいすると key が毎回変わって f ^ key + key がいっぱい得られる。偶奇が同じ f ^ key + key を集めておくとどちらかが全部本物でどちらかが全部偽物です。
f ^ key + key いっぱいから f を求めるパート。ありがたい話として、xor では繰り上がりは起こらず、+ では繰り上がりは 1 つしか起こらない。
表を書くと、こんな感じになる。f の i bit 目に着目すると、1 のときは key の i bit 目によらない。0 のときはよって、これを使って決定していきたい。あといい感じの性質として i bit 目自体は key によらず、0 のときの繰り上がりにのみ関係する。これらの観察から、
- まず f ^ key + key の i bit 目が同じものを集める。
- もし、i bit 目が同じなのに i+1 bit 目が違っていたら、繰り上がりの有無が異なるということなので、f の i bit 目は 0。
- 同じだったら、2 択を当てまくるのは確率的にすごいことなので、高確率で 1。
というように復元できる。
あとは f を復号してやれば ok（しゃれ）。
— w2w2 (@w2w2_222) 2022年3月22日
コードとか貼れるのか？f を求めるパートは C++ で頑張ればよかったんだけど、nc をいっぱい叩くパートで Python を書いたのがちょっと辛かった。
感想
おもしれ～。CTF、crypto 以外もやりたいね。ところで句点を書くのすごい抵抗ある
