ハッカーは、CTFでSubstitution Cipher(置換暗号)の基本から攻略法を学ぶ

ペネトレーションテスト&バグバウンティ

頻度解析で置換暗号を解読します。「Crypto」カテゴリの中でも「Substitution Cipher(置換暗号)」は、古典的でありながら奥深い問題が多く出題されるそうです。

ここでは、置換暗号の基本から攻略法や、Pythonによる頻度解析まで、分かりやすく解説します。

Substitution Cipherとは(サブスティテューションサイファー)

Substitution Cipher(置換暗号)とは、アルファベットを別の文字に一対一で置き換える暗号方式です。

たとえば

平文: A B C D E ...

暗号: Q W E R T ...

このように「A → Q」「B → W」…のような対応関係によって、文章が暗号化されます。

シーザー暗号との違いと難易度

よく似た暗号に「Caesar Cipher(シーザー暗号)」がありますが、違いは以下の通りです。

項目	Caesar Cipher	Substitution Cipher
仕組み	一定の文字数ずらす	ランダムな文字置換
通り数(パターン)	26通り	26!(約4×10²⁶)通り
攻略法	総当たり	頻度解析＋推測

つまり、シーザー暗号みたいに簡単ではないと言うことです。

Substitution Cipher(置換暗号)を解く方法

どうやって解くのか

英語には「よく使われる文字」があります。

英文字の頻出ランキング：E > T > A > O > I > N ...

暗号文の中で、一番多く出現する文字は「E」である可能性が高いという考え方を使うのが、頻度解析(Frequency Analysis)です。

CTFでの典型的な出題形式

暗号化されたテキスト：

"ZHOFRPH WR WKH ZRUOG RI FUBSWRJUDSKB"

英語に見えるけど意味不明ですね。でもよく見ると、何度も出てくる文字があるのです。

→ 頻度解析をして、出現回数の多い文字を「E」などに対応させて推測していきます。

攻略手順：暗号文の観察から推測へ

攻略のステップは次の通り。

1.暗号文を読み取る

2.各文字の出現回数を数える(Counter)

3.英語の文字頻度と比較

4.対応関係表(マッピング)を仮作成

5.読めそうな単語をもとに調整する

Pythonで頻度解析をしてみよう

開発環境はKali Linuxを利用しています。
インストールされていない方は、仮想環境(VirtualBox 7.1)にKali Linux 2024.3をインストール手順をご覧ください。

1.ターミナルを開いてnanoエディターを立ち上げてファイルを作成します。

nano substitution_cipher.py

2.以下のPythonコードをコピー＆ペーストします。

# Python標準ライブラリの'collections'モジュールから、'Counter'という便利なクラスを読み込みます。'Counter'は、文字や単語の出現回数を自動で数えてくれる命令です。

from collections import Counter

# 解読対象の暗号化された文字列です。

ciphertext = "ZHOFRPH WR WKH ZRUOG RI FUBSWRJUDSKB"

# 暗号文から「空白(スペース)」除いた文字列に対して、'Counter'を使って各文字の出現回数を数えます。

counter = Counter(ciphertext.replace(" ", ""))

# 出現回数が多い順に並べて表示します。

print("頻度順：", counter.most_common())

3.書き終えたら、以下の手順で保存してエディタを終了します。

Ctrl + O → Enter(保存)

Ctrl + X(終了)

4.ファイルを保存したら、次のように実行します。

python3 substitution_cipher.py

5.実行結果

実行結果から、たとえば「R」が一番多い。もしかして「E」かも。というように仮置換して推測します。

頻度順： [('R', 5), ('H', 3), ('W', 3), ('U', 3), ('Z', 2), ('O', 2), ('F', 2), ('K', 2), ('B', 2), ('S', 2), ('P', 1), ('G', 1), ('I', 1), ('J', 1), ('D', 1)]