nullcon 2013 Battle Underground Programming 1 Writeup

3月2日に開催されたnullcon2013 Battle Undergroundにyokaromonのみんなで出場しました。

各自担当とかは決めていませんでしたが、僕はなんとなくProgrammingの問題ばっかりやってました。CTFでこの手の問題出るのって珍しい気がします。

まずは問題文

This is a very easy problem. You just need to find the number of primes which can be generated using the polynomial n2-n+41 and is lesser than 1 trillion (1,000,000,000,000). Flag is the MD5 sum of the answer.

で、英語が読めなすぎて今回チームでネタにされました・・・・。最終的にこんな感じっぽい意訳

非常に簡単な問題です。多項式n^2-n+41を使って生成される1,00,000,000,000以下の素数の数を答えるだけです。フラグは答えのMD5チェックサムです。

今更ですが、改めて読むと、普通にこう読めますね・・・。最初” Flag is the MD5 sum of the answer “を答えの合計のMD5と勘違いしてしまって、ずっと一兆以下の整数の合計のMD5ハッシュ値を答えとして提出していました・・・。お恥ずかしい・・・。

というわけで以下が書いたスクリプトです。勘違いして書いた合計を算出する処理も残ってますが、まぁいいでしょう・・・。

 

忘れないように書くと、” n^2-n+41 ” という多項式は、数学者オイラーさんが発見した素数生成式で、1から39までの整数をnとすると、求められるのは全て整数です!ただ、完璧な素数生成式というのは現代では導かれておらず、40以上は、素数でない数も導かれることがあります。

処理の内容としては、1から順番に前検索して、求められた整数が素数かどうかを判定する、これの繰り返しを1,00,000,000,000まで行います。

最初は、それぞれの答えをretに足して最終的に出力していましたが、答えの合計ではなく、導かれる素数の数なので、primeを素数判定がTrueのときにインクリメントして、最後に出力です。

これで導かれる数字が、” 261081 ”

それのMD5したもの” e1d9e8bf5c39c6778f8ceed19bfad0a3 ”

これで正解でした。問題さえ読めれば(笑)すぐに解ける問題ですね・・・。

コメントを残す

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