Ecasdqina's MEMO.

メモ帳.

17'高専セキュリティコンテストに参加した[write-up]

はじめに

チーム名 "BiPhpne" で

bi0o = 0b100 (@sei0o) | Twitter, Akashi_SN (@Akashi_SN) | Twitterさん, Snow (@Snow_Poijio) | Twitterさんと出ました。
ぼくはセキュリティコンテスト未経験だったのであまり難しい問題はできなかったけど、とても楽しかったです。
2位をとれてよかった。
以下にぼくが解いた問題のwrite upを書きます。

write up

サンプル

問題文にFlagが書かれてるのでそれを送るテスト問題。

フラグを答えろ

Problem Fileが置かれていたのでstringsをするとFlagが出てくるのでそれを整形すると答え。

ボスを倒せ

ncでアクセスするとボスとプレイヤーとの戦いが始まるがボスのHPが異常に高く全く倒せない。
プレイヤーの名前を入力する段階があったので適当にAAAAAAAAAAAAAAAAAAAAAAAAAAとか入力するとバッファオーバーフローしたので、メモリ上にプレイヤー名|プレイヤーHP|ボスHPと並んでるのかと考え境界をうまく探るとプレイヤーのHPを大きくし、ボスのHPを小さくできるようになり、ボスを倒せるようになる。

素数を数えろ

7桁で最大の素数が答えなので素数辞書でさがしてAC。

RSA2

同じ法で異なる2つの鍵を使い暗号化された2つの暗号文が渡されるので復号化する。
復号の手順を以下に示す。
定数: N:法, M:平文, e_1:鍵1, e_2:鍵2, c_1:暗号文1, c_2:暗号文2
まず次の2つの合同式が成り立つことが分かる。
c_1=M^{e_1}\ \left(mod\ N\right)
c_2=M^{e_2}\ \left(mod\ N\right)
また、これらより次の式も成り立つ。
c_1\times c_2=M^{e_1}\times M^{e_2}=M^{e_1+e_2}\ \left(mod\ N\right)
c_1^{a}\times c_2^{b}=M^{ae_1}\times M^{be_2}=M^{ae_1+be_2}\ \left(mod\ N\right)
ここでae_1+be_2=1となるようなa,bがあると嬉しい。
このような方程式を1次不定方程式といい、e_1e_2が互いに素なとき、解が必ず存在する(証明は読者に任せる)。
今回はe_1e_2は差が2の奇数なのでe_1e_2は互いに素(証明は演習問題とする)。
またaかbが負になることは明らか、今回はbが負と仮定する。
e_2が小さかったのでO(e_2)アルゴリズムで解を探した。

for i in range(e2):
    if (e1*i)%e2==1:
        a=i
        b=-(e1*i)//e2
        break

aとbがわかったのであとは計算すればよい、bが負なのでc_2の(mod\ Nでの)逆元を計算する(iとおく)。
M=c_1^{a}\times i^{|b|}\ \left(mod\ N\right)
平文MがわかったのでASCIIに変換するとFlagが出る。

途中まで与えられた数値がおかしかったようで、8時間くらい溶かした......

Homomorphic Encryption

準同型暗号、暗号化したまま計算できる。
準同型とは群/環準同型写像で次の性質がある。
\phi(a\times b)=\phi(a)\times \phi(b)
問題文に論文(英語)が添付されていた。
結局論文を読むだけで終わりました。

おわりに

CTFの楽しさを知ってしまった、ずぶずぶ(沼へ沈む音)......