読者です 読者をやめる 読者になる 読者になる

きゅうり。

主にCTF関係のことを書いていく気がします

ASIS CTF Quals 2017 writeup

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

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

 

A fine OTP server (crypto 79pt)

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

ASIS{0f4ae19fefbb44b37f9012b561698d19}

 

 

F-4 Phantom (crypto 176pt)

 適当な素数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をもう1つ入手してm_qを計算する。

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

ASIS{Still____We_Can_Solve_Bad_F4!}

Secured OTP server (crypto 268pt)

ある平文の末尾に、ランダムな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!_!!!}

おまけ。DLP

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

暗号文として、(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も少し手をつけたので気になるところ。