nullcon 2013 Battle Underground Programming 3 writeup

前回に引き続き、nullcon 2013 Battle Underground の自分が担当した問題のwriteup書いていきます。

Programming3です。

以下問題文

Mr. X is fond of prime numbers. Recently, Mr. X learnt of some special numbers called Smarandache-Wellin numbers. The n’th Smarandache-Wellin number is obtained by concatenating the first n primes. For example, 2, 23, 235, 2357, 235711 are the first 6 decimal Smarandache-Wellin numbers. Mr. X is interested in binary Smarandache-Wellin numbers. Furthermore, Mr. X is only interested in those numbers which are prime. He found the first 3 such numbers 2, 11 and 751 and now needs your help in finding the next 2 numbers. Enter the next 2 binary Smarandache-Wellin primes. The flag is the MD5 hash of the next 2 binary Smarandache-Wellin primes separated by _ (underscore). For eg. if the numbers are 23 and 235, the flag would have been MD5SUM(“23_235”)

ざっくり意訳(これも何度も意味を履き違えて、なかなか解答にたどり着かなかった・・)

Xさんは素数が好きです。 最近、XさんはSmarandache-Wellin numbers呼ばれる数について学びました。n番目のSmarandache-Wellin numberはn番目までの素数を連結させることによって得ることができます。Xさんは2進数のSmarandache-Wellin numberのうち、素数だけに興味があります。彼は2, 11, 751という最初の3つの2進数Smarandache-Wellin numberを見つけました。その次の2つの数字を見つけてください。次の2つのSmarandache-Wellin numberを_(アンダースコア)で連結したものの、MD5チェックサムがこの問題のフラグです。

http://en.wikipedia.org/wiki/Smarandache%E2%80%93Wellin_number

問題文にも書いてありますが、簡単に言うと、素数は2, 3, 5, 7, 11….とあり、Smarandache-Wellin numberとは2, 23, 235, 2357, 235711….というのがそれに当たります。

Xさんはそれを2進数でやりたくて、しかもそのうちの素数だけを抜き出したい。

2, 11, 751までは見つけたので、あと2つ見つけてくれ、という問題です。

2は2進数で 10

11は2進数で 1011

751は2進数で101110111

後ろに素数を2進数にしたものをくっつけて、2進数全体が素数かどうかを判定します。それで751の次に当てはまるものを得るスクリプトを書いていきます。

最初、問題に着手したばかりのときは、2, 11, 751までのプロセスも明確ではなかったので、そこから計算して出力するようにしています。

751以降は桁数が莫大になっていくので、デバッグ用の出力はうっとおしいだけですが、規則性にちゃんと気がつけたのでよかったです。

以下は2,11,751までの出力をキャプチャしたものです。

Screen Shot 2013-03-03 at 17.07.03

  1. 最初に2が素数で、それを2進数にしたものが10
  2. 10に、次の素数である3を2進数したもの(11)をくっつけて 1011(10進数の11)
  3. ここからがキモで、1011に次の素数である5(2進数で101)をくっつけて1011101(10進数で93)を得るが、これ自体は素数じゃないので次の処理へ
  4. 次の素数である7(2進数で11)を前回の結果1011101にくっつけて101110111(10進数で751)を得る。751は素数なので、これで3つ。

Xさんがどういうプロセスで3つ目までを見つけたかは知りませんが、今回求めるべき数列の規則性はこれだということがわかりました。

そのまま処理を続けていけば、次の二つも見つかります。

13499925319356478420482627384338205627134397423032950243093776977656290637381356029088437508765876860004145536363528373584239891642207051418759823661775098400822064249224107957394151475347641577607291008219620857887840743942302339494275640240389954171415859751242018684702291309687871788001082502981179843710955968305626219107882381173932042111051037558216690866104363093437124046556014178911539242991232498163764379843984059581618991857509603695132829301769

4178024520048464687377630333781717879404075971768776245420063857617925088891489606176607287044369960037018902011849289176641296067768886109727422734188064023638022562254733564342171478053064724114411765870377775349657496322378512525142999031090251164168452641800241733625987554996534416882012963991102408146223868356497622554970987902356644145730512464281093744854608796407077859318984359976335400473918261877085825298647843735060014896081070785205019798426736815795971430257132698691

ですね。もうこの数字をなんて呼べばいいかもわからないくらいの大きい数です(笑)751の次がこんなにでかくなるなんて、思ってもいませんでしたw

あとは問題文通り、この二つを_(アンダースコア)でつなげてMD5ハッシュ値を得れば正解。答えは以下の通りです。

554ec7e8fa6830da4ed6b265f1a08fe0

この問題、解法には割と早く近づいたのですが、その時動かしていた素数判定のアルゴリズムに不良があって、最初何度も正確な数字を得ることができずに苦しみました・・・・。そこに関しては改めて別の記事で比較検証したいと思います。ネットって探すとなんでも落ちてますね・・・w

今回、Programming1,2,3を解いて一番の反省点は「英語読むのが遅いし、正確じゃない!」ということですね。恥ずかしい・・・。writeupを読みながら改めて問題文を読むと、「普通に書いてあることだったじゃん・・・」って思うこともしばしば・・・。

あとは、Programming以外の問題がまるで駄目でした・・・。REとCryptは問題を見てもいないのがほとんどですが、Exploitationは1つくらい解きたかった・・・。

でも楽しかった!!3位嬉しい!!!

 

 

 

コメントを残す

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