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

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

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

前回の記事はこちら

2020.06.12【第２回】セキュリティエンジニアを目指して「CTF」を解く！【第2回】セキュリティエンジニアを目指して「CTF」を解いていくセキュリティエンジニアへの需要が高まっているこの時代。...

注意事項

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 を作成）します。

[mathjax]

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

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

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

フラグを求める！

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

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

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

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

プログラムにすると

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

1#include <stdio.h>
2using namespace std;
3int main(void)
4{
5    unsigned long int i, k;
6    for (i = 0;; i++)
7    {
8        k = i * 3438478 + 193127;
9
10        if (k % 1584891 == 32134)
11        {
12            // 結果を出力
13            printf("result: %ld\n", k);
14
15            // 3438478で割った時の余りをチェック
16            printf("result % 3438478: %ld\n", k % 3438478);
17
18            // 1584891で割った時の余りをチェック
19            printf("result % 1584891: %ld\n", k % 1584891);
20            
21            break;
22        }
23    }
24}

結果

結果は以下の通りです。

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

結果は「35430270439」です。

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

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

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

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

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

結果の確認コマンド

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

1# Q26
2bach check-c.sh 26

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

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

さいごに

いかかでしたでしょうか！

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

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

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

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

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