【最終回】セキュリティエンジニアを目指して「CTF」を解く！
2021.12.20
セキュリティエンジニアを目指してまだまだ「CTF」を解いていく
セキュリティエンジニアには、「セキュリティ技術をはじめ、幅広い分野の知識や技術」が求められています。
前回の『【第２回】セキュリティエンジニアを目指して「CTF」を解く！』に引き続き、今回も、 CTF（Capture the flag）を解いていきます。
前回の記事はこちら
注意事項
- 前回に引き続き、常設 CTF の「CpawCTF」を利用します。
- 今回のコードは、Docker Official Images の gcc イメージ を使用して動作確認を行っています。
- 情報は、2020年4月6日現在のものです。
- 今回紹介する問題を「CpawCTF」で解くには、level 1、level 2までのすべての問題を解いておく必要があります。
CpawCTF「Q26.[PPC]Remainder theorem」を解く！
さあ、「Q26.[PPC]Remainder theorem」という問題を解いてみましょう！
問題内容は、以下の通りです。
x ≡ 32134 (mod 1584891)
x ≡ 193127 (mod 3438478)x = ?
フラグはcpaw{xの値}です！
引用：CpawCTF
「問題文」から読み解く！
CTFの問題文には、その問題を解く「ヒント」が隠れていることがほとんどです。
「≡」って何？
まずは「≡」の記号について見ていきます。
一般的に、「≡」は「図形の合同」を表すのに使われます。
他にも恒等式の両辺をつなぐときや、定義を表すときにも用います。
つまり「常に等しい」というような意味と考えてください。
「mod」とは？
次に「mod」についてですが、「mod」はエクセルで使ったことのある方も多いのではないでしょうか。
mod 関数は「除数で割った時の余り」、つまり「割り算の余り」を表します。
問題文を読み解く
以上の情報から問題文を読み解くと…
1584891 で割ると余りが 32134 になり、3438478 で割ると余りが 193127 になる数を求めよ
といったところでしょうか。
問題の「タイトル」から読み解く！
早速 解読した問題を解いていきたいところですが、まずは問題タイトルをチェックします。
問題のタイトルは「Remainder theorem」です。
それぞれ、remainder は「残り」、theorem は「定理」という意味で、全体では「剰余定理」という意味です。
セキュリティ分野における「剰余」と「RSA暗号」
数学における「剰余定理」は、多項式の余りを求めるものです。
セキュリティの世界では、剰余は暗号化に用いられます。
剰余を用いる暗号化形式といえば、「RSA 暗号」です。
「RSA 暗号」とは、大きな二つの素数を用いて鍵を生成する暗号化方式です。
ここでは簡易的に、「Q26.[PPC]Remainder theorem」を解くために必要な知識のみを説明します。
まず、以下のような定数を定義します。
- n:（公開されている値）
- e:（公開されている暗号鍵）
- d:（秘密の復号鍵）
次に、暗号化鍵を使って、以下のような方法で暗号化（平文 m から 暗号文 c を作成）します。
$$c = (m の e 乗を n で割ったときの余り)$$
これに対して、復号化（暗号文 c から 平文 m を得る）は、以下のような方法で行う事ができます。
$$m = (c の d 乗を n で割ったときの余り)$$
フラグを求める！
それでは実際にフラグを求めていきます！
今回は C 言語を使用します。
問題の内容を、「1584891 で割ると余りが 32134 になり、3438478 で割ると余りが 193127 になる数を求めよ」と再設定して解いていきます。
「1584891 で割って余りが 32134」かつ「3438478 で割って余りが 193127」の数字を、総当たりで探して行きます。
プログラムにすると
プログラムにすると、以下のような感じになります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <stdio.h> using namespace std; int main(void) { unsigned long int i, k; for (i = 0;; i++) { k = i * 3438478 + 193127; if (k % 1584891 == 32134) { // 結果を出力 printf("result: %ld\n", k); // 3438478で割った時の余りをチェック printf("result % 3438478: %ld\n", k % 3438478); // 1584891で割った時の余りをチェック printf("result % 1584891: %ld\n", k % 1584891); break; } } } |
結果
結果は以下の通りです。
result: 35430270439
result % 1584891: 32134
result % 3438478: 193127
結果は「35430270439」です。
「1584891 で割って余りが 32134」、「3438478 で割って余りが 193127」となっていることも確認できるので、これで間違いなさそうです。
今回作成したソースコード
今回作成したソースコードは、以下のリポジトリにまとめてあります。
【 rightcode / ctf-trial 】
https://github.com/rightcode/ctf-trial
ソースコードや結果を確認する場合は、上記のリポジトリをクローンしてください。
結果の確認コマンド
以下のコマンドで、結果を確認できます。
1 2 | # Q26 bach check-c.sh 26 |
※ 結果の確認には Docker と Docker Compose を使用しています。
Docker をインストールしていない場合は、確認用のコードを環境に合わせて調整してください。
さいごに
いかかでしたでしょうか！
今回も問題文に多くの「ヒント」が隠れていました。
記号の意味やタイトルの意味から、出題者の意図を読み取る事が重要です。
実際のセキュリティインシデントでも、攻撃者の自己顕示欲の一部をくみ取る事が大切です。
みなさんも是非 CTF にチャレンジしてみてください！
こちらの記事もオススメ！
書いた人はこんな人
- 「好きを仕事にするエンジニア集団」の（株）ライトコードです！
ライトコードは、福岡、東京、大阪の3拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。
システム開発依頼・お見積もり大歓迎！
また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」「WEBディレクター」を積極採用中です！
インターンや新卒採用も行っております。
以下よりご応募をお待ちしております！
https://rightcode.co.jp/recruit
ITエンタメ10月 13, 2023Netflixの成功はレコメンドエンジン？- ライトコードの日常8月 30, 2023退職者の最終出社日に密着してみた！
- ITエンタメ8月 3, 2023世界初の量産型ポータブルコンピュータを開発したのに倒産!?アダム・オズボーン
- ITエンタメ7月 14, 2023【クリス・ワンストラス】GitHubが出来るまでとソフトウェアの未来
関連記事
採用情報
\ あの有名サービスに参画!? /
バックエンドエンジニア
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界を変える…！ /
Androidエンジニア
\ みんなが使うアプリを創る /
iOSエンジニア
