ASIS CTF Quals 2017 writeup

m1z0r3で参加、1006ptで51位でした。cryptoを3問解いて523ptを入れました。

なお、終了後すぐDLPも解けたので一応載せておく。

RSA暗号の暗号文が与えられるが、e=3であり平文も比較的短いので3乗根をとるだけ。後のSecured OTP serverで言及するのでここではソルバは省略。（3乗根で解けることに最初は気づかず、Secured OTP serverと同じソルバで解いた）

ASIS{0f4ae19fefbb44b37f9012b561698d19}

適当な素数pを元に、ランダムな2bitを反転させたもののnext_primeをqとしたRSA暗号。またeは65537ではなく大き目な値。

(なお、最初はwiener's attackを試したりもしたがダメだった)

反転させるランダムな2bitに注目すると、pとqが比較的近い値になる場合があることがわかる。この場合フェルマー法により素因数分解できるので、このようなnを引けるまでガチャる。

都合の良いnを素因数分解すると、φ(n)とeが互いに素ではないため秘密鍵dが計算できないことがわかる。計算してみると、素数pに対してeはp-1の素因数となっている。

なので、ひとまず素数qを用いて $d_q \equiv e^{-1} \pmod{q-1}$ を計算し、 $m_q \equiv c^{d_q} \pmod{q}$ を導く。

同様に、素因数分解可能なnをもう１つ入手して $m_q$ を計算する。

あとは、これらの $m_q$ をCRTにより持ち上げるとmが求まる。いわゆるRSA-CRTの計算である。

ASIS{Still____We_Can_Solve_Bad_F4!}

ある平文の末尾に、ランダムな18文字を連結したものを平文としたRSA暗号の暗号文を2つ与えられる。なお、2つの平文の差は、 $n^{\frac{1}{9}}$ より小さい。

わざわざこの条件が与えられていることから、Short Pad AttackやFranklin-Reiter Related Message Attackをすると考えられる。が、手持ちのソルバを用いてもShort Pad Attackで解が得られなかった。

そこで、平文の上位bitがわかっていることから、シンプルにCoppersmith's theoremから解いた。

ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter's_attack_CongratZ_ZZzZ!_!!!}

開催中には解けなかったやつ。

暗号文として、 $(n+1)^{msg} \pmod{n^{s+1}}$ とnが得られる。

$n^{s+1}$ 以上の項はすべて消える。つまり、s=11としたとき、 $a_0*n^{11} + a_1*n^{10}+ ... + msg*n + 1$ となる。なので、 $n^2$ でmodをとれば $msg*n+1$ のみ残るので、あとは計算して終わり。

ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

都合上日曜日しか参戦できなかったとはいえ、DLPとunsecure ASIS sub-dは解けるべきだと思った。start_hardも少し手をつけたので気になるところ。

きゅうり。