前回はksnctfの30ポイント問題 Reservedについて解説しました。
今回は同じく30ポイントの問題であるksnctf＃20 G00913を解いていこうと思います。
問題を見ると、
FLAG_Q20_{first 10-digit prime found in consecutive digits of π}
このようにFLAGそのものが問題文となっています。
つまり、「first 10-digit prime found in consecutive digits of π」という部分を解けばFLAGが得られるというわけですね。
また、問題のタイトルであるG00913とはどういう意味なんでしょうか…。
first 10-digit prime found in consecutive digits of πについて
とりあえず、first 10-digit prime found in consecutive digits of πを訳してみました。
機械翻訳では「πの連続する桁で見つかった最初の10桁の素数」と出ます。
つまり、この問題は
無限に続くπ（円周率）の桁を左から順番に見ていった際に最初に現れる10桁の素数は何か
ということを問われているわけですね。
しかし、求められていることは分かったけれどもどうやって解答を導くか分からんなぁといった感じです。
そこで、Googleで検索したところ、素数判定をするコードが多数公開されていましたのでその内の１つを利用させてもらいました。
素数判定が出来るのであれば、
・適当な桁数のπを用意する（今回は100桁）
・左から10桁ずつ見ていく
・10桁の素数が見つかった時点でその値を出力する
というコードを用意すれば今回のFLAGがゲット出来ます。
Pythonスクリプトを書いてみる
今回はPythonで以下のようなコードをスクリプトを作成しました。
このスクリプトの内容はスクリプト内のコメントの記載内容のとおり、
・piという円周率100桁分の整数を準備
・素数判定の関数の定義
・piの頭から10桁ずつ読み込んで素数判定を繰り返す
・10桁の素数にヒットすれば、その値を出力して終了する
という動作となります。
では、このスクリプトを実行してみます。
スクリプトを実行した結果、すぐに10桁の素数が出力され、FLAGが判明しました。
100桁のπで素数が見つかってよかったです。
解答フォームにFLAGを入力すると正解となりました。
「G00913」はGoogleの求人広告との関係がある!?
無事、正解となりましたがこの問題のタイトルがなぜ「G00913」となっているのか少し調べてみました。
結論から言えば、G00913というのはGoogleのleet表記です。
leet表記というのは、アルファベットを別の数字や記号に置き換えるものです。英語圏で使われる文字の変換方法です。
例えば、
For you ⇒ 4U
Peer to Peer ⇒ P2P
MAKE IT BOUNCE ⇒ M4K3 1T B0UNC3
といった感じに表記されます。
つまり今回は、
Google ⇒ G00913
と変換されているわけですね。
では、なぜ問題のタイトルがGoogleなのかというと、元々は今回の問題に非常に似た問題がGoogleの入社試験に使われていたからです↓
Googleは2004年に上の画像のような「first 10-digit prime found in consecutive digits of e」と書かれたユニークな看板をシリコンバレーの主要道路沿いに出していたそうです。
この問題を解いて辿り着けるサイトでも別の入社試験問題が待ち受けていたようです。この看板の内容も採用募集の方法もGoogleらしい遊び心のあるアイディアですね。
今回のksnctfの問題はeの部分がπになっており、Googleの入社試験問題をオマージュした問題となっています。
今回の#20 G00913はGoogleの入社試験を仮体験できる良い問題だと思いました。
まとめ
さて、今回は30ポイントの問題を解いてみました。
数学的な考え方が要求される問題で、素数判定の部分さえクリアできれば、FLAGがゲットできるので30ポイント問題といったところでしょうか。
個人的にはGoogle社の入社用の試験問題をオマージュした問題という点が面白かったです。
皆さんも是非チャレンジしてください。
コメント