1. HOME
  2. ブログ
  3. IT技術
  4. 【最終回】セキュリティエンジニアを目指して「CTF」を解く!

【最終回】セキュリティエンジニアを目指して「CTF」を解く!

セキュリティエンジニアを目指してまだまだ「CTF」を解いていく

セキュリティエンジニアには、「セキュリティ技術をはじめ、幅広い分野の知識や技術」が求められています。

前回の『【第2回】セキュリティエンジニアを目指して「CTF」を解く!』に引き続き、今回も、 CTF(Capture the flag)を解いていきます。

前回の記事はこちら

注意事項

  1. 前回に引き続き、常設 CTF のCpawCTFを利用します。
  2. 今回のコードは、Docker Official Images の gcc イメージ を使用して動作確認を行っています。
  3. 情報は、2020年4月6日現在のものです。
  4. 今回紹介する問題を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」を解くために必要な知識のみを説明します。

まず、以下のような定数を定義します。

  1. n:(公開されている値)
  2. e:(公開されている暗号鍵)
  3. d:(秘密の復号鍵)

次に、暗号化鍵を使って、以下のような方法で暗号化(平文 m から 暗号文 c を作成)します。

$$c = (m の e 乗を n で割ったときの余り)$$

これに対して、復号化(暗号文 c から 平文 m を得る)は、以下のような方法で行う事ができます。

$$m = (c の d 乗を n で割ったときの余り)$$

フラグを求める!

それでは実際にフラグを求めていきます!

今回は C 言語を使用します。

問題の内容を、「1584891 で割ると余りが 32134 になり、3438478 で割ると余りが 193127 になる数を求めよ」と再設定して解いていきます。

「1584891 で割って余りが 32134」かつ「3438478 で割って余りが 193127」の数字を、総当たりで探して行きます。

プログラムにすると

プログラムにすると、以下のような感じになります。

結果

結果は以下の通りです。

result: 35430270439
result % 1584891: 32134
result % 3438478: 193127

結果は「35430270439」です

「1584891 で割って余りが 32134」、「3438478 で割って余りが 193127」となっていることも確認できるので、これで間違いなさそうです。

今回作成したソースコード

今回作成したソースコードは、以下のリポジトリにまとめてあります。

【 rightcode / ctf-trial 】
https://github.com/rightcode/ctf-trial

ソースコードや結果を確認する場合は、上記のリポジトリをクローンしてください。

結果の確認コマンド

以下のコマンドで、結果を確認できます。

※ 結果の確認には Docker と Docker Compose を使用しています。

Docker をインストールしていない場合は、確認用のコードを環境に合わせて調整してください。

さいごに

いかかでしたでしょうか!

今回も問題文に多くの「ヒント」が隠れていました。

記号の意味やタイトルの意味から、出題者の意図を読み取る事が重要です。

実際のセキュリティインシデントでも、攻撃者の自己顕示欲の一部をくみ取る事が大切です。

みなさんも是非 CTF にチャレンジしてみてください!

(株)ライトコードは、WEB・アプリ・ゲーム開発に強い、「好きを仕事にするエンジニア集団」です。
システム開発依頼・お見積もりはこちらまでお願いします。
また、WEB・アプリエンジニアを積極採用中です!詳しくはこちらをご覧ください。

※現在、多数のお問合せを頂いており、返信に、多少お時間を頂く場合がございます。

こちらの記事もオススメ!

書いた人はこんな人

ライトコード社員ブログ
ライトコード社員ブログ
「好きなことを仕事にするエンジニア集団」の(株)ライトコードです!
ライトコードは、福岡本社、東京オフィスの2拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。

システム開発依頼・お見積もりは大歓迎!
また、WEBエンジニアとモバイルエンジニアも積極採用中です!

ご応募をお待ちしております!

関連記事

採用情報

\ あの有名サービスに参画!? /

バックエンドエンジニア

\ クリエイティブの最前線 /

フロントエンドエンジニア

\ 世界を変える…! /

Androidエンジニア

\ みんなが使うアプリを創る /

iOSエンジニア