はじめに
最近、社内で「セキュリティコンテスト勉強会」（通称CTF勉強会）を主催しています。
勉強会では毎回
- ksnctfを問題集として使用する
- その中から易しめの数問を選ぶ
- 参加者の誰か1人がドライバーとして主導して解く
- 他の参加者は共有された画面を見ながらあーだこーだ言う
- 必要があれば、勉強会の終わりにネット上のWrite-up（解説）を検索する
というモブプログラミング的なやり方を採用しています。
今日は#20 G00913をみんなで解いている最中に時間切れになってしまったので、
せっかくだからということで筆者は宿題としてRustで解いてみることにしました。
というわけで、以下は#20 G00913をRustで解くWrite-upです。
問題
FLAG_Q20_{first 10-digit prime found in consecutive digits of π}
つまり、「円周率の連続した数字の中で、最初に見つかる10桁の素数」を探し、それをFLAG_Q20_なんちゃらかんちゃらの形で答えなさい、ということでしょう。
解答
問題のタイトルが "G00913" 1であったため、最初は「ググればどこかに答えが書いてあるのかな？」ぐらいに思っていました。
ところがググってもそれらしき情報は見当たりません2。
なので、とりあえず下記のように愚直に探索する方針で解いていきます。
- 円周率を長めに用意する（とりあえず今回は小数点以下1,000桁を用意）
- 数値として扱うには大きすぎるので、文字列として扱う
-
i文字目からi + 10文字目までを取り出す - 取り出した10文字の文字列を10桁の数値にパースする
- その数値
nが素数かどうかを判定する- 3以上$\sqrt{n}$以下となる奇数3で順々に割っていく
- 割り切れた（剰余が0）場合、素数ではないので抜ける
- 最後まで割り切れなければ素数
- 素数でなければ
iをインクリメントして3. に戻る - 素数が見つかったら
FLAG_Q20_{見つかった素数}のフォーマットで出力して終了
それなりに実行に時間がかかりそうな予感がしたので、実行速度が高速であることが期待されるRustで書くことにしました。
（素数の判定はやり方次第でもっと高速化できそうな気もしますが、実装のスピードや簡単さを優先して単純なものにしています）
const PI: &str = "31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989";
fn main() {
for i in 0..PI.len() - 10 {
let n: u64 = PI[i..i + 10].parse().unwrap();
if is_prime(n) {
println!("The flag has been found:");
println!("FLAG_Q20_{}", n);
break;
}
}
}
fn is_prime(n: u64) -> bool {
if n == 0 || n == 1 || n == 4 {
return false;
} else if n == 2 {
return true;
}
for i in (3 as u64..=(n as f64).sqrt() as u64).step_by(2) {
if n % i == 0 {
return false;
}
}
true
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0_is_not_prime_number() {
assert_eq!(is_prime(0 as u64), false);
}
#[test]
fn test_1_is_not_prime_number() {
assert_eq!(is_prime(1 as u64), false);
}
#[test]
fn test_2_is_prime_number() {
assert_eq!(is_prime(2 as u64), true);
}
#[test]
fn test_3_is_prime_number() {
assert_eq!(is_prime(3 as u64), true);
}
#[test]
fn test_4_is_not_prime_number() {
assert_eq!(is_prime(4 as u64), false);
}
#[test]
fn test_2147483647_is_prime_number() {
assert_eq!(is_prime(2147483647 as u64), true);
}
#[test]
fn test_1000609937_is_not_prime_number() {
assert_eq!(is_prime(1000609937 as u64), false);
}
}
上記のコードはユニットテストを書いたり、0や1などを素数から弾く処理を入れたりと比較的丁寧に書いていますが、
実際に解く際は10桁の素数さえ判定できてしまえばいいので、そういったユニットテストや処理は書く必要はないでしょう。
これを実行したところ、無事解答となるフラグを得ることができました。
おわりに
当初の予感に反して、探索にかかる時間は一瞬でした。
main関数中のbreak;をコメントアウトして実行してみると分かるのですが、1000桁の円周率を全て探索する場合でも、手元のPCでわずか1秒ほどで実行を終えました。
Rust、速いですね。
会社のみんなでワイワイとCTFを解くのは、
- クイズ感覚で楽しみながら情報セキュリティの知識を身につけることができる
- よく知られた脆弱性について実際に攻撃手法を手で動かして学ぶことができ、業務の中でよりセキュアなコードを書くことができる
- 輪読会形式だとテキストとなる書籍の購入や読み込み、発表資料の準備等の事前準備が必要だが、CTFを解くのは事前準備がほとんど要らない
- 輪読会形式だと、1度休んでしまうと本の内容について行けないことがあるが、CTFは毎回別個に独立した問題を解くので休んでも復帰が安心
といったメリットがあると考えています。
今後も社内CTF勉強会を続けていきたいですね。