# 【IS】Classical Encryption #1

## 對稱式加密

> 圖片來源：https://www.ssl2buy.com/wiki/symmetric-vs-asymmetric-encryption-what-are-differences

* 所謂的對稱式加密，即為加密和解密的Key(金鑰)為**同一把**。
* 整個系統如同上圖所示，很單純：Plain Text(明文)經過Encryption(加密)變為Cipher Text(密文)；再經由同一把Key透過Decryption(解密)變回Plain Text。

### 何謂優秀的加密

* 我們不希望訊息被所有人看到，然而傳輸時可能要透過各種公開的平台才能成功傳遞，因此我們才需要進行加密。
* 這邊需要有一個概念，由於傳遞的媒介或平台很可能是公開的，因此你的Cipher Text是會被拿到的。這裡的進行加密的目的並不是讓你的Cipher Text不被碰觸，而是即使<u>它被碰觸也沒關係</u>。
* 當然，我們還是希望訊息被應該看見的人看見。
* 所以好的加密方式應該是在擁有Cipher Text的情況下，如果沒有Key就很難得到Plain Text，但如果擁有Key卻很簡單就可以得到Plain Text。

### 對稱式加密的問題

* 對稱式加密其實從根本上有個矛盾點：如果我和對方能夠擁有同一把鑰匙，那我幹嘛不<u>將訊息當作鑰匙</u>就好？
* 如果你想通了，你可能會覺得對稱式加密根本沒有用，但其實在現今的密碼學系統中還是有許多對稱式加密的應用。
* 因此我們之後都是建立在**雙方已經擁有Key**的前提下來討論。

## 古典加密法

### Caesar Cipher

* 中文為凱薩加密法，就是著名的凱薩大帝發明的；又稱為Shift Cipher(位移加密)
* 作法就是給予一個整數當作key，讓明文中的每個字母都加上key值，轉換為新的字母。
* 解密時就反方向位移即可。

|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|

#### 範例

* Key: 3
* Plain Text: meet me after the toga party
* Cipher Text: PHHW PH DIWHU WKH WRJD SDUWB

#### 特點

1. 暴力破解
* 因為英文字母只有`26`個字，因此你加密的可能性只有`26`種。期望值而言試`13`次就被破解了。
2. 字頻分析法
* 位移並不會改變字母的頻率。以英文字來說，字母`e`出現的頻率通常是最高的，如果今天密文`G`的頻率最高，我們可以合理推測key的值為`2`(從`e`到`G`)。
3. 進階字頻分析法
* 除了單獨看每個字母的頻率之外，還可以進一步分析連字的頻率，如`th`、`st`、`er`等。

### Monoalphabetic Cipher

* Caesar Cipher的加強版，讓每個字母都做相對應的替換，做一個一對一的映射，而不是位移共同的長度。
* 改善了Caesar Cipher做26次就被破解的缺點。

#### 範例

* Key: DKVQFIBJWPESCXHTMYAUOLRGZN
* Plain Text: ifwewishtoreplaceletters
* Cipher Text: WIRFRWAJUHYFTSDVFSFUUFYA

#### 特點

1. 字頻分析法
* 雖然每個字的位移長度變得不同了，然而頻率還是可以解出一定的資訊。
2. 進階字頻分析法
* 同上。

### Playfair Cipher

1. 做一個`5*5`的表格
2. 根據Key將字母依序填入，重複的字母跳過。
* 因為字母有`26`個，通常將`I`和`J`視為同一個字。
3. 填完Key的字母後，將沒出現過的字母依序填完。
4. 開始加密，將明文兩個兩個字一組，如果
I. 兩個字母出現在同一直排，轉換為下面一格的字母。
II. 兩個字母出現在同一橫列，轉換為右邊一個的字母。
III. 其他情形，找出另外兩格使該四個字母形成一個矩形。
* 如果兩個字母一樣、或是最後只剩一個字，插入/補上字母`X`。

#### 範例

* Key: playfairexample

|P| L| A| Y| F|
|---|---|---|---|---|
|I(J)| R| E| X| M|
|B| C| D| G| H|
|K| N| O| Q| S|
|T| U| V| W| Z|

* Plain Text: HI DE TH EG OL DI NT HE TR EX ES TU MP
* Cipher Text: BM OD ZB XD NA BE KU DM UI XM MO UV IF

#### 特點

* 成功解決了頻率分析的問題，Key也不需要像Monoalphabetic Cipher那麼長。
* 少一個字母能夠轉換，且會在某些時候插入字母`X`，使明文受到影響。
* Code table的後半部分幾乎是固定的，容易從這邊遭到攻擊破解。

### Vigenère Cipher

1. 準備和Caesar Cipher一樣的表格。

|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|

2. 將一個字詞不停重複，直到和明文一樣長當作Key。
3. 將Key和明文相加成為密文。
* 如果超過`26`就modulo `26`。

#### 範例

* Key: SESAME
* Plain Text: T H I S I S A T E S T M E S S A G E
* Key Stream: S E S A M E S E S A M E S E S A M E
* Cipher Text: L L A S U W S X W S F Q W W K A S I

#### 特點

* 明文中同樣的字母會被不同的Key加工，成功迴避掉字頻的問題。
* 如果Key的長度被得知，被破解的可能性會大幅上升。

### Autokey Cipher

* 針對需要Key和明文一樣長的加密法，提供Key的產生法，因此可搭配其他加密法使用。
* 在提供一個字詞當作Key之後，不是不停重複Key來完成Key Stream，而是將明文放到Key後面當作新的Key。

#### 範例(搭配Vigenère Cipher)

* Key: deceptive
* Key Steam: deceptive**wearediscoveredsav**
* Plain Text: wearediscoveredsaveyourself
* Cipher Text: ZICVTWQNGKZEIIGASXSTSLVVWLA

#### 特點

* 解密時需要先解開前段，然後用解出來的明文放到Key後面繼續解。

### Vernam Cipher

* 和Vigenère Cipher基本上一樣，只是將運算方法從加法改為XOR。
* XOR需要先將字母對應的數字轉為五位元的二進制碼，再將每個位元分別做XOR。

| Plain Text | Key | Cipher Text |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
|0|1|1|
|1|0|1|
|1|1|0|

#### 範例

* Plain text: H → 7(十進位) → 00111(二進位)
* Key: X → 23(十進位) → 10111(二進位)
* Cipher Text: 10000(二進位) → 16(十進位) → Q

#### 特點

* XOR有個特別的地方，將明文`X`對金鑰`K`做**兩次**XOR運算，其結果必定為`X`(不變)。
* XOR的這個特點，也常常在之後的其他加密法被運用，因為同樣的運算可以同時加密和解密，在實際上可以節省硬體成本。
* 不過在Vernam Cipher會導致結果可能超過`A`~`Z`的範圍，結果會出現非英文字母的東西。

### One-Time Pad

* 給予和明文一樣長的密碼本，做XOR的運算即可加解密。
* 安全性是**絕對安全**，完全不可能破解；然而需要以下前提：
1. 密碼產生的方式**完全隨機**。
2. 密碼本使用一次便銷毀。
* 在世界大戰期間被大量使用，掌握敵軍的密碼本便會大幅影響戰況。

### Rail Fence Cipher

* Key為一個數字，代表籬笆的數量。
* 將明文用籬笆的方式寫下(↘↗)，然後用橫排的方向去重新排列，得到密文。

#### 範例

* Key: 3
* Plain Text: HELLOWORLD

H       O       L
  E   L   W   R   D
    L       O

* Cipher Text: HOLELWRDLO

#### 特點

* 相較於前面的加密法，這個加密法只進行字母的**換位**而不進行**替換**。

### Row Transposition Ciphers

* Key為row的順序，將明文寫成矩形後，再按照key的順序一個一個直排重新排列。
* 有點難描述，請直接看範例。

#### 範例

* key: 4312567
* Plain Text: attackpostponeduntiltwoamxyz

4 3 1 2 5 6 7

a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z

* Cipher Text: TTNAAPTMTSUOAODWCOIXKNLYPETZ

### Product Ciphers

* 直接給予一個Table代表新的順序。

#### 範例

* Key:

15 11 19 18 16 03 07 14 02 20
04 12 09 06 01 05 17 13 10 08

* Plain Text : thestrengthofthispig

t h e s t r e n g t
h o f t h i s p i g

* Cipher Text : HHIPIEETHGSOGRTTSFTN

H H I P I E E T H G
S O G R T T S F T N

###### tags: `IS` `note`