# 古典暗号でcrypto入門-教科書
## 1. CTFにおけるcryptography
Capture The Flag (CTF) コンテストにおける「暗号」カテゴリは、参加者が暗号学的な問題を解決することを要求される競技分野です。
これらの問題は、暗号理論、暗号解析技術、および様々な暗号システムの実践的な応用をテストすることを目的としています。
以下は、CTFで一般的に見られる暗号カテゴリのいくつかの例です
- **古典暗号**
- シーザー暗号、ヴィジュネル暗号、転置暗号など、古典的な暗号技術に関する問題。
- **現代暗号**
- RSA、AES、デジタル署名、公開鍵暗号など、現代の暗号技術に基づいた問題。
- **暗号解析**
- 与えられた暗号文を解読するための手法、例えば周波数分析、既知の平文攻撃、選択平文攻撃など。
- **ハッシュ関数とMAC**
- ハッシュ関数（例: SHA-256）やメッセージ認証コードの問題。

基本的には、暗号化のために必要な情報(ソースコードや鍵、暗号化方式の記述)が書いていて、
暗号化の情報から、復号する方法を考える問題となっています。
※そのため、多くの場合でプログラミング力/数学力が必要な事があります。

## 2. 古典暗号とは？
暗号化技術の中でも、主に19世紀以前に使用された暗号化技術のことを指します。
古典暗号の多くは、現在は簡単に解読できるので、安全ではありませんし、それが理由で使われていません。

しかし、本演習では暗号技術を学ぶ上で大事な基本的な概念の理解、プログラミングにより復号化手順に慣れることを目的として、暗号技術の入門として古典暗号を学びます。

古典暗号は主に以下の3つに分類されます。
-　換字式暗号
-　転置式暗号
-　分置式暗号

## 3. 換字式暗号
### 3-1. シーザー暗号
シーザー暗号とは、Julius Caesarが使用していた暗号で、換字式暗号の一種です。
具体的な暗号化方式は、平文をn文字シフトしたものが暗号になります。
※シフト時に、"Z"を超えた場合は、"A"に戻ります。
なので、この暗号文における「鍵」はシフト数です。

暗号文を復号するためには、鍵の数だけシフトを戻せばいいだけです。

例）
平文： `Hello IdoHack Users`
鍵：`3`
暗号文：`Khoor LgrKdfn Xvhuv`

#### 攻撃手法
- シフト数の総当たり攻撃
- シフト数には100通りもないので、簡単に総当たり攻撃が成功する。
- アルファベットのみを使うなら26通り
- 英数字なら36通り
- その他文字を使っている可能性がある場合は、その文字もシフト数にカウントする

### 3-2. ヴィジュネル暗号
ヴィジュネル暗号は、多文字置換暗号の一種で、シーザー暗号を拡張したものです。
ヴィジュネル暗号では、異なるシフト量を使用するため、複数のシーザー暗号のようなものと考えることができます。
これは、鍵となる単語またはフレーズを使用して行われます。

#### 暗号化方法
$C_i = (P_i + K_i) \quad mod \quad 26$

$ここで、C_i は暗号文の i 番目の文字、P_iは平文の i 番目の文字、K_iは鍵の i 番目の文字（鍵は必要に応じて繰り返される）$
$mod 26 は、結果が 0 から 25 の範囲になるようにするためのものです。$

| | | | | | | | | | | | | | | | | |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| **平文** | h | e | l | l | o | i | d | o | h | a | c | k | u | s | e | r |
| **鍵** | h | a | c | k | h | a | c | h | a | c | k | h | a | c | k | h |
| **暗号分** | o | e | n | v | v | i | f | y | o | a | e | u | b | s | g | b |

平文**1文字目**の鍵は`h`なので、平文1文字目の`h`を7文字分ずらします。
平文**2文字目**の鍵は`a`なので、平文1文字目の`e`を0文字分ずらします。
平文**3文字目**の鍵は`c`なので、平文1文字目の`l`を2文字分ずらします。
平文**4文字目**の鍵は`k`なので、平文1文字目の`l`を10文字分ずらします。
平文**5文字目**の鍵は`h`なので、平文1文字目の`o`を7文字分ずらします。
以降はこの繰り返しで、暗号化を図ります。

#### 復号化方法
$P_i = (C_i - K_i) \quad mod \quad 26$
$ここで、
P_iは平文の i 番目の文字、C_iは暗号文の i 番目の文字、K_iは鍵の i 番目の文字です。$

#### 攻撃手法
- 短い鍵を使っている暗号を解読する。
- ５文字程度の単語であれば、一般的なPCでも現実的な時間で総当たり攻撃が成功します。
- 26^5 = 11,881,376
- 辞書ファイルを使用して解読する。
- 一般的に公開されている辞書ファイルを利用して、総当たり攻撃を行います。
- 辞書ファイルには以下のようなものがあります。
- **RockYou**
- **SecLists**
- **John the Ripper**
- **DirBuster/DirSearch**

### 3-3. アフィン暗号
アフィン暗号は、暗号学における古典的な換字式暗号の一種です。この暗号方式は、数学的な関数を用いて平文の各文字を暗号文の文字に変換します。具体的には、アルファベットの各文字をある数値に対応させ、その数値に基づいて暗号化を行います。

アフィン暗号の暗号化プロセスは以下のようになります：

#### 暗号化方法
1. アルファベットを数値に変換
まず、アルファベットの各文字を数値に変換します。
例えば、英語アルファベットの場合、`'A' = 0, 'B' = 1, ..., 'Z' = 25 ` のように割り当てることが一般的です。
2. 暗号化関数の適用
暗号化関数$E(x) ~ = ~ (ax+b) ~ mod ~ m$ を各文字に適応します。ここで、
- $x は平文の文字に対応する数値$
- $aとbは暗号化の鍵$
- $m はアルファベットの文字数（英語の場合は26）$
- aとアルファベットの文字数が互いに素であることが条件

3. 数値を文字に戻す
暗号化関数によって得られた数値を再び文字に変換して暗号文を得ます。

#### 復号化
暗号の解読には逆関数$D(y) ~ = a^{-1}(y-b) ~ mod ~ m$を使用します。
ここで、$a^{-1}$はaの逆元で、$ax \equiv 1$を満たす数です。
逆元とは、$aとbが互いに素(gcd(a,b)=1)$の場合にのみ存在します。

アフィン暗号はシーザー暗号の一般化と見なすことができます。
（シーザー暗号は a=1 の特別なケース）
しかし、この暗号も基本的な暗号解読技術によって容易に解読されるため、現代のセキュリティ基準では安全とは言えません。

### 3-4. 単一換字式暗号
単一換字式暗号は、古典暗号の一種で、平文の各文字を異なる文字に置換する暗号化方法です。
この方式では、平文の文字群を別の文字群に置き換えます。
重要な点は、同じ文字は常に同じ文字に置き換えられるということです。
例えば、平文で「A」は常に「X」に置き換えられ、平文で「B」は常に「N」に置き換えられます。

有名な例として、シャーロックホームズの「踊る人形」があります。
#### 主な特徴
- 一対一の置換
- 各平文文字は、暗号文字群の一つの特定の文字に置き換えられます。
- 決定論的
- 同じ平文文字は常に同じ暗号文字に置き換えられます。

#### 暗号化の例
暗号化の例(今回はアルファベット同士での置き換え)
平文アルファベット: ABCDEFGHIJKLMNOPQRSTUVWXYZ
暗号アルファベット: QWERTYUIOPASDFGHJKLZXCVBNM

この場合、平文の「A」は「Q」に、「B」は「W」に置き換えられ、以下同様に進みます。

#### 攻撃
単一換字式暗号は、比較的簡単に解読できることが多いです。その理由は、言語には特定の文字や文字の組み合わせが頻繁に現れる傾向があり（例えば英語では「E」が最も一般的な文字）、暗号文中で最も頻繁に現れる文字を分析することで、元の文字を推測できるからです。また、文字のペアや三文字の組み合わせ（バイグラムやトリグラム）、単語の長さなどの言語学的特徴を分析することで、さらに解読を進めることが可能です。

このため、単一換字式暗号は現代のセキュリティ基準では不十分とされ、主に教育用や趣味の暗号パズルなどに使用されます。現代のセキュリティでは、より複雑な多層的な暗号方式（例：AES、RSAなど）が一般的に用いられています。

## 4. 転置式暗号
### 4-1. スキュタレー暗号
スキュタレー暗号は古代ギリシャ時代に起源を持つ、古典的な暗号化方法の一つです。
この暗号は、特定の方法で巻かれた紙や革などの素材に文字を記述することによって機能します。
スキュタレーとは、この暗号化に使用される木製の棒のことを指します。

## 5. 分置式暗号
分置式暗号（Transposition Cipher）は、暗号化の手法の一つで、文字の位置を変更することによって暗号化を行います。
このタイプの暗号では、元のメッセージの文字の順序が変更されるため、暗号文は平文と同じ文字を含みますが、異なる順序で配置されています。

### 基本的な原理
分置式暗号の基本的な原理は、平文の文字を並べ替えることです。これには様々な方法がありますが、一般的な方法の一つに「列転置暗号」があります。この方法では、平文を行列に書き込み、列を基にして暗号文を生成します。

### 列転置暗号の例
**平文の準備：** 平文を用意し、必要に応じてパディング（余白埋め）を行います。
**行列の作成：** 平文を行列に配置します。行列のサイズや形は、暗号の鍵となることが多いです。
**暗号文の生成：** 行列の列を基にして暗号文を生成します。

### その他の分置式暗号
他にも様々な分置式暗号が存在します。
- **レールフェンス暗号**
- 平文を互い違いの行に書き、それらを順に読むことで暗号文を生成します。
- **ルート暗号**
- 特定のパターン（例えば螺旋状）で文字を配置し、そのパターンに従って暗号文を生成します。

分置式暗号は、頻度分析に対して比較的強いですが、暗号文のパターン分析によって解読される可能性があります。特に単純な分置式暗号は、現代の暗号解析手法には容易に破られます。したがって、より複雑な暗号化手法や、分置式暗号を他の種類の暗号（例えば換字式暗号）と組み合わせることが推奨されます。

## 6. その他の暗号
### 6-1. アナグラム
アナグラムとは、文字の順序を入れ替えることによって、別の単語やフレーズを作る技術です。
一般的にはパズルや言葉遊びとして知られていますが、暗号学においても独特の役割を果たしてきました。