## 必考懶人包 checklist
* 基礎知識
* secure
* Attack種類
* mod運算
* 輾轉相除法
* Euler’s Theorem
* Modular Exponentiation(left to right, right to left)
* Extended Euclidean
* CRT 中國剩餘定理
* 質數檢測演算法的知識
* Classical Encryption Techniques
* Playfair Cipher
* DES
* 相關知識(key size, block size, round)
* S-Box計算
* AES
* 相關知識(NK,key size, block size, round)
* Shift-row計算
* Mix column計算
* IDEA, RC2, RC5
* 相關知識和特色(speed, key size ...)
* General Form: RC5-w/r/b
* Binary Field GF(2^n)多項式
* 加法(做XOR)
* 乘法、除法
* Inverse(基本上不會考)
* 2DES, 3DES
* 相關知識(block size, affect key)
* meet in the middle attack原理
* ECB CBC CFB OFB CTR mode
* 相關知識比較(基本上就是CFB跟OFB比較會考)
## 基礎知識

### Unconditionally Secure

理論上無法破解

An encryption scheme is unconditionally secure if the ciphertext
* generated by it does not contain enough information to determine uniquely the corresponding plaintext, no matter how much ciphertext is available. (i.e., perfect cipher)
### Computationally Secure

現實中破解所需的時間太長，以至於基本上無法被破解

An encryption scheme is computationally secure if it meets
* the cost of breaking the cipher exceeds the value of the encrypted information;
* the time required to break the cipher exceeds the useful lifetime of the information

### 攻擊種類
* Brute-force
* Brute-force 攻擊是一種嘗試所有可能的密碼或金鑰組合來破解加密系統的方法
* Known-plaintext
* 攻擊者已經知道某些加密前的明文及其對應的密文，並利用這些對應關係來推導出加密金鑰或解密過程
* Frequency Analysis
* 攻擊者透過分析密文中符號出現的頻率，對應到可能的明文字母來逐步還原出原文
* key reuse attacks
* 金鑰重用攻擊利用重複使用的加密金鑰來破解系統
* meet in the middle attack(Known-plaintext的一種)
* 攻擊者同時從明文和密文進行雙向搜索，尋找匹配的中間結果
* bit-flipping attacks
* 攻擊者可以透過故意更改密文中的某個bit，導致解密後的明文產生預期的變化
* Padding Oracle Attack
* 攻擊者可以透過不斷修改密文並觀察解密後系統返回的填充驗證錯誤訊息來確定填充是否合法，逐位猜測出密文的每個字節。

## 模(mod)運算

### 輾轉相除法
* 求最大公因數


### Extended Euclidean Algorithm(求模數的inverse)

gcd(a,b) = 1 則有inverse存在



### Modular Exponentiation Methods(x^e mod n)[必考]
* left to right
* right to left



### Euler’s Theorem(求模數的inverse或x^e mod n)[必考]

* 計算$x^e (modN)，以5^{1202}(mod13)為例$


* 計算模數的inverse


### Find Primitive Root(generators)


### CRT 中國剩餘定理


### 其他
* Montgomery Method
* left to right等的改良版本，用於計算模數的inverse
* Miller-Rabin Primality Test
* 用於檢測數字是否為質數

## Classical Encryption Techniques

* Substitution
* Caesar Cipher
* Playfair Cipher
* Transposition (Permutation)
* Product of Substitution and Transposition

### Caesar Cipher(Substitution)


### Playfair Cipher[必考]

* 加密過程


* 解密過程


## DES[必考]

### DES基礎
* Block Cipher
* Security basis
* Confusion
* Diffusion
* Block size: 64 bits
* Key size: 64 bits = actual key (56 bits) + parity (8 bits)
* Number of rounds: 16

### DES 加密過程
> 黑色數字為建議閱讀順序


### DES S-Boxes計算(必考)
* **Substitution(替換式)**，也是**F不可逆**的原因


### DES的解碼(必考)


### Padding Scheme


## IDEA, RC2, RC5[必考]

### Speed
* Blowfish > RC5 > RC2 > DES > IDEA

### IDEA
Basic Features
* **64-bit block**
* **128-bit key**
* 8 rounds

Security
* In 2011, IDEA **was broken** using a meet-in-the-middle attack.

### RC2

Characteristics
* Block cipher
* Block size: 64 bits
* **Key size: 8 ~ 1024 bits** (must be multiple of 8 bits)
* Number of rounds: 16

### RC5

**General Form: RC5-w/r/b (必考)**

* Block size: 2xw bits
* range: 32-bit block, 64-bit block, 128-bit block
* Key size: 8xb bits
* range: 0-bit key, 8-bit key, 16-bit key, ..., 2040-bit key
* Number of rounds: 0 to 255

## Binary Field GF(2^n)多項式[必考]
* 直接上題目了


### Multiplicative Inverse in GF(p ) 基本不會考


## AES[必考]

### AES介紹

**AES種類**
* AES-128
* AES-192
* AES-256


**AES 優點**
* Secure(尚未被破解)
* Efficient(AES效率>DES)
* Flexible(多個種類)
* 支援在軟體和硬體上使用
* code length較短(DES > AES)
* 任何processor架構上都可以使用

### AES cipher(加密)

AES加密單一個round會經過以下四個流程

* SubBytes(State)
* 可逆
* 根據表格的行列，填入對印的數值
* ShiftRows(State)
* 可逆
* 將列往左移
* MixColumns(Stase)
* 可逆
* 以矩陣相乘的方式進行加密
* AddRoundKey(State, RoundKey)
* 可逆
* 將加密後的矩陣與某個矩陣XOR


### SubBytes Transformation

透過對照表格的方式替換數值
* 如第E行，第A列在大表格中對印的格子為87，則EA加密後為87


**SubBytes解密**

透過對照同一個表格，使用上述的動作即可


### ShiftRows Transformation

* 將矩陣左移n格
* 第一行不用移
* 第二行向左移1格
* 第三行向左移2格
* 第四行向左移3格


**ShiftRows解密**

* 將矩陣右移n格
* 第一行不用移
* 第二行向右移1格
* 第三行向右移2格
* 第四行向右移3格


### MixColumns Transformation[必考]

用矩陣乘法的方式計算加密後的內容


**MixColumns Transformation解密**

用於解密的矩陣就是MixColumns(State)的inverse


### AddRoundKey(State, RoundKey)
跟某個矩陣做XOR
* 不分加解密(因 A XOR B = C 則 B XOR C = A)
* 自己為自己的Inverse


### Key Expansion
* The length of each Round Key is **4 words (128 bits).**


### 其他補充

round跟Final round差別在於final round沒有Mix-column(期中曾經考過)


## 2DES, 3DES

### 2DES(Broken)

2DES provides only **57 (= 56+1) effect key bits** because Meet-in-the-Middle Attack


**Meet-in-the-Middle Attack in 2DES**
* 屬於一種已知明文攻擊
* The MAX number of encryption trials are $2^{56} + 2^{56} = 2^{57}$

破解流程
1. 算出**k2**(共$2^{56}$種)的所有可能
2. 算出**k1**(共$2^{56}$種)
3. 比退使用(1)加密過後和(2)解密過後相同的結果


> 來源: [[Cryptography] DES筆記: meet in the middle attack](https://bryceknowhow.blogspot.com/2018/05/cryptography-des-meet-in-middle-attack.html)

### 3DES(Broken)

Block size: 64 bits
Key size: 112 bits (2-key), 168 bits (3-key)
The 3-key 3DES provides 112 (= 56x2) effect key bits.(Meet-in-the-Middle Attack)


## ECB CBC CFB OFB CTR mode

:::info
基本上就是CFB跟OFB比較會考
:::

* ECB (Electronic Codebook)
* 每一個區塊都是用同一個金鑰進行加密
* Encryption parallelizable: Yes
* Decryption parallelizable: Yes
* Preprocessing capability: No
* Security: 不太安全
* CBC (Cipher Block Chaining)
* Encryption parallelizable: No
* ecryption parallelizable: Yes
* Preprocessing capability: No
* CBC模式跟ECB模式的運作原理很類似，但是加密中又加了前一個密文區塊做XOR運算
* Security: vulnerable to the **Bit Flipping Attack** and **Padding Oracle Attack**
* **CFB (Cipher Feedback)** 老師好像很愛考
* CFB模式，前一個密文區塊會先用加密演算法加密，才與明文區塊做XOR運算
* Encryption parallelizable: No
* Decryption parallelizable: Yes
* Preprocessing capability: Yes
* Security: vulnerable to the Bit Flipping Attack
* OFB (Output Feedback)
* 跟CFB差異不大，但是feedback是獨立於plaintext的(加密時不依賴於加密過後的密文)
* Encryption parallelizable: Yes
* Decryption parallelizable: Yes
* Preprocessing capability: Yes
* Security: OFB is **seriously vulnerable to the Bit Flipping Attack**
* CTR (Counter)
* A **Stream mode** for Block Cipher(**Suitable for high-speed network** encryption)
* Encryption parallelizable: Yes
* Decryption parallelizable: Yes
* Preprocessing capability: Yes
* Security: CTR is seriously vulnerable to the Bit Flipping Attac
* XTS-AES
* Encryption parallelizable: Yes
* Decryption parallelizable: Yes
* Preprocessing capability: Partial
* Random access to encrypted data stored in a sector-based device
* uses AES twice for each block
* Security: Secure for encrypting stored data in a sector-based devic

### CBC (Cipher Block Chaining)

CBC模式跟ECB模式的運作原理很類似，但是加密中又加了前一個密文區塊做XOR運算
一開始的時候會有一個IV (Initialization Vector)跟第一筆加密做XOR


### CFB (Cipher Feedback)[有考過畫圖]

CFB模式，前一個密文區塊會先用加密演算法加密，才與明文區塊做XOR運算
s: segment size (bits)會決定有多少會作為下次加密所使用(feedback bits)


### OFB Mode (Output Feedback Mode)

A Stream mode for Block Cipher
跟CFB差異不大，但是feedback是獨立於plaintext的(加密時不依賴於加密過後的密文)
Nonce(IV)兩方都必須知道


### CTR Mode (Counter Mode)

Similar to OFB but encrypts counter value
Widely used for ATM network security and IPSec