ksnctf #20 G00913
問題
http://ksnctf.sweetduet.info/problem/20
考えたこと
問題文に FLAG_Q20_{first 10-digit prime found in consecutive digits of π} とあったが、そもそもG00913ってなんだよ聞いたこともないぞと思い、タイトルをググった。そうすると、下の写真が出てきた。これはgoogleの求人広告らしい。どう見てもこれをオマージュした問題である。答えそのものはググったときについでに出てきた。
おまけというかついで
これまたこいつをオマージュした問題でYet Another G00913という問題もある。
http://ctf.katsudon.org/problem/13
これの厄介なところは200桁を判定しなければならないところである。上の10桁程度ならRubyのPrimeクラスとか使えそうだが、さすがに200桁は無理なので、別の方法を考えないといけない。他のアルゴリズムとして桁が小さければエラトステネスのふるい、フェルマーの小定理(フェルマーテスト)があったりするが、それは疑素数といって素数でなくても通ってしまう数字が出てくる。それを改良しても通ってしまうカーマイケル数というものもあるが、まあ詳しくはググってください(細かく書くのが面倒)。そこで今回用いるミラーラビンテストの登場である。こいつは200桁の素数判定でも一瞬で終わる優れものである。これも確率的素数判定なので間違いが出ることはあるが、その確率は判定回数をk回とすると「4^-k」なので、kを大きくすればほぼなくなる。実装はさほど難しいわけではないが、PHPならgmp_prob_prime()という組み込み関数がミラーラビンの確率的テストによっておそらく素数であるか調べてくれる。この辺のもう少し詳しい話は気が向けばMathIについての記事を書いた時にやろうと思う。
ksnctf #10 #!
問題
http://ksnctf.sweetduet.info/problem/10
考えたこと
ただの知識問題なので特にない。知らなかったらググったら即答できるやつ。
指示に書いてある通り、最初の文字だけ大文字にすることを忘れなかったらさほど問題ないと思う。
おまけというかついで
見かけたことがあるとすれば、シェルで出てくる
#!/bin/sh
#!/usr/bin/env ~
みたいなやつだと思う。前者については、パスを直接指定するものである。後者は、Unix/Linux系の環境では、スクリプトの1行目に記載しておき、スクリプト自体を実行することで記載されたプログラム(例えばPython)を実行しそのプログラムに、スクリプトの内容を渡し動作させることができる、といったものである。例えば、sample.pyみたいなのを作ったら、$./sample.pyとかやると、#!によってプログラムが実行され、プログラムにsample.pyが渡され処理されるといった流れになる。(あいまいな知識なので、間違ってるかも)
akictf #3 cheap cipher(revenge)
問題
http://ctf.katsudon.org/problem/3
考えたこと
タイトルからして前にあったcheap cipher類の問題であろうと予想はできた。
cheap cipherでは問題の文字列の前後を逆にしてbase64でデコードすると答えが出たけど、これはちょっとひねりを加えて逆にしないといけない。逆の仕方としては、base64の変換表を逆にする。そして、逆にした後の変換表に基づいて文字列を更新する。
どういうことかというと、たとえば、A→＝、B→/、C→＋、D→9といった具合
こうすることでbase64でエンコードされた答えが手に入る。それで解けた。
おまけというかついで
実はこれ自分ではパッと思いつけなくて、知り合いにヒントをもらって解けたものである。まあ正直新しい知識があるかって言われたらないけど、base64のそれっぽい実装の練習というか、新しいテーブルを作って自分で変換するっていう面白さみたいなのがあった。
ksnctf #5 Onion
問題
http://ksnctf.sweetduet.info/problem/5
考えたこと
アルファベット+数値だけなのでBase64でデコードしてみると、ほとんど何も変わらない文字列が出力される。は？と思って何回かやるとおおよそ15回で
begin 666 <data>......みたいなものが出てきた。なんじゃこれと思ってググってみると、uuencodeなるものがあるらしい。なので、さっき出てきたbegin云々ってやつをテキストに保存して、uudecode flag.txtってやったらフラグが出てきた。
おまけというかついで
まずタイトル、お前はなんだって感じで未だに実はよくわかってない（）
uuencodeっていうのは、初期のUNIX系OSではUUCPというプロトコルで電子メールの配送が行われていたが、これらはでキスとデータしか扱えないため、バイナリファイルをテキストデータに変換して送る手法として用いられたものらしい(wiki参照)。これも知らなかったので、またひとつ勉強になった。
akictf #2 cheap cipher
問題
http://ctf.katsudon.org/problem/2
考えたこと
今回も"=="があったので、base64であるという予想は立てた。しかし前回と違い先頭にあるので、なんやこれってなったけど、単純に前後入れ替えたらさっきと一緒じゃね？って思い、後ろから変換していったらちゃんとフラグが出てきた。
おまけというかついで
base64は、PythonやPHPなどでは組み込みとして使えるが、前回の問題や今回みたいにそれをするだけならいちいちコードを書く必要はない気がする(後ろから変換するというのはPythonのスライスを使えば楽だろって言われたら確かにそうなんだけど)。前回はターミナル上でもデコードできるということを書いたので、今回は必要になったrevコマンドについて少し書こうと思う。
revコマンドは名前の通り、入力した文字列、あるいは指定したファイルの行の文字列を逆にして出力するコマンドである。それ以上の何物でもないので、オプションもクソもない。これを使えば後ろから変換するとかしなくてもパイプライン処理ですぐ終わったのだが、私がこれを知らなかっただけである。またひとつ勉強になった。
ksnctf #2 EasyCipher
問題
http://ksnctf.sweetduet.info/problem/2
考えたこと
cipherと言う単語は、暗号という意味で直訳すると簡単な暗号という意味になる。なので、何か文章を表しているだろうなという予想はついた。4単語目にnが一文字だけ出てくるので、これは"I"か"a"という風に予想できる。これが"a"だったら、シーザー暗号という有名な暗号なのでまあそれかなあと思い、以下のページに投げてみたら読める文章になったので、そこの指示通りにしたら通った。
http://lazesoftware.com/tool/strgen/
ついでというかおまけ
ROT13はPythonやPHPに組み込みであるので、それを使えば簡単にコードとして実装できる。私は偶然、秘密の国のアリスという本でそれを読んだことがあったので簡単に解けた。何故シーザー暗号と呼ばれるかというと、昔ローマのカエサル（ジュリアス・シーザー）がこれを用いたからである。
akictf #1 Capture the flag!
問題
http://ctf.katsudon.org/problem/1
考えたこと
最初だから一応単純に貼り付けをしてみたらさすがに違った。まあでも"=="っていうのがあるから、Base64かなとおおよそ予想はついたので、ターミナルで、
echo 'Q1RGCg==' | base64 -D
とデコードし、入力したら通った。
ついでというかおまけ
Base64の具体的な変換手順としては、
まず、元データを6ビットづつに分割する。もし6ビットに足りなければ、0を追加して6ビットにする。次に、各6ビットの値を変換表を使って4文字に変換していく。変換表は、wikipediaなどを参照していただきたい。このとき4文字に満たない場合は、イコールを追加して4文字にする。
といったものである。これによりイコールがあるとBase64かなあという予想を立てている。この技術は電子メールやBasic認証などに用いられている。
