nullcon 2013 Battle Underground Programming 2 writeup

引き続きnullcon 2013 Battle Undergroundの自分の担当した問題のwriteupを書いて行きたいと思います。

以下問題文

Connect to nullcon-e1.no-ip.org:2000

意訳するまでもないですね。すぐに対象アドレスにブラウザでアクセスしてみます。(大会終了と同時に対象アドレスは無効になってます。)

ごめんなさい、スクリーンショットを撮っていなかったので、完全に覚えているわけではないのですが、大体こんな感じだった(オリジナルは英語です)

マトリックスへようこそ

===================

認証のため、100に質問に答えてください。

Q 001/100 三乗して最後が888になる数の、3番目の数字はなんでしょう?

認証失敗です

アクセスしたと同時に、これがブラウザに表示されます。意味がわかりませんでした(笑)とりあえず計算します。最初に書いたスクリプトがこれ。

これで出力されるのが692

三乗すると、331373888で確かに末尾が888になってます!おっしゃ!これラクショーじゃん!

そう思ってた時期が私にもありました。

ブラウザに表示されたものには特に解答するフォームもないし、これでフラグゲット!!意気揚々とシステムのフラグ解答欄に入力し、コミット!!

しかし、無論不正解・・・・orz

そりゃそうですよね・・・こんな簡単なのにProgramming1より高得点とかありえないですよね・・・。

しかもブラウザにアクセスする度に最後の3桁”888″と”3番目”っていうところはランダムで変わって、”777″とか”999″になったり、8番目とか5番目になったり、じゃーこの問題どうやって解くんじゃーーーーーーーー!!!!

「この問題意味わかんなすぎワロタwwwww」ってなってたところにリーダからアドバイス

「connectしてrecvするだけ」

その発想はなかった・・・・・orz

ていうかむしろブラウザで表示すること以外に頭になかった自分に絶望した(笑)

というわけで、その方向でスクリプト書くことに。

それが以下です。

socket通信でコネクションを確立して、問題をrecvして、さきほどのプログラムを関数化したものに渡す。関数内では、問題文中のランダムで変わる箇所を抽出して、整数へ変換、それを計算処理内に当てはめて、あとは算出されたものを、sendする。

仮に問題100問連続正解した後に、どんな出力が来るかはわからなかったので、とりあえず無限ループで様子を見ることに。

良し!これでいける!!と思って実行。

おぉーーーーーーーーー!!順番に問題を解いてる解いてる!!!

次々と問題が出され、それを解答していく!しかし、8問目が出題されるたところで

問題文

三乗すると最後が”888″になる250万番の数字はなんでしょう?(オリジナルは英語です)

ちょwwwwwww桁数半端じゃなくなってるwwwwwww

ここで先ほどのスクリプトが沈黙。あまりの数字のでかさに、計算にとてつもなく時間がかかってる模様・・・・。おぉおおお・・・・・。まじかよ・・・・。8問目でこれだと100問目どうなっちゃうの・・・・。

様子見で放置していましたが、30分くらい放置しても進展なし(笑)こりゃ、大会中に100問解答は無理そうですね。

何かしら効率のいいアルゴリズムがあるはず・・・。ということで模索。一番最初のスクリプトをちょこっと改造して規則性を探します。

これで三乗したら末尾が”777″,”888″,”999″になる数字をそれぞれ10個出してみます。

以下が結果。

Screen Shot 2013-03-03 at 16.00.16

 

それぞれ規則性がありますね。

“777”は (繰り返し回数-1) + 753

“888”は(繰り返し回数%4 -1) + (“192”, “442”, “692”, “942”を繰り返し)

“999”は(繰り返し回数-1) + 999

この規則性を利用して、計算せずに文字列の組み合せのみで計算結果を得ることができます。これなら桁数が莫大になっても、計算回数は一回で済みます。

スクリプトを書いて実行したのですが、実はランダムで出る数字に”999″, “333”, “111”も登場することが判明したので、それも追加して改めて実行したのが、こちら

これを実行したところ、サクサクと100問目まで自動的に正解していきました、やったね!!!100問目まで正解したところ出力されたのがこちら

ここで、今までrecvしていた問題文と、形式が変わってしまったのでエラー。

最後この文字列に関数を合わせて

出力されたのがこちら

66403497218968692334695330508944906707308363163348623993643740434773122725325545748596174761000192

これで正解でした!規則性に早く気をつけてれば、もっともっと早かったかなあ・・・。あとはsocket通信で問題を解くところに直感的に気がつくべきでした・・・頭が固いですね・・・・でもこの問題最高に気持ちよかったww

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です