# Introduction to Cryptography
> 資料來源：NCKU 李南逸教授之**密碼學**課程－密碼學概論。

## 密碼系統（Cryptographic System）
> Kerckhoff's principle：密碼系統的安全性，需「僅依賴其秘密金鑰」，而非其密碼演算法的隱藏。

- 可提供之安全服務種類：機密性（Confidentiality）、確認性（Authentication）、完整性（Integrity）、不可否認性（Non-repudiation）、存取控制（Access Control）、可使用性（Availability）。
- **安全**密碼系統之定義：
- 無條件安全（Unconditionally Secure）：攻擊者計算能力多強都無法破密。
> 只有 One-time pad system 可達成，但並無真正的系統存在。
- 計算安全（Computationally Secure）
- 破解密碼系統的「代價」超過獲益。
- 破解密碼系統的「時間」超過明文可利用的時間。
- 一般以「**金鑰數目**」來分類。

## 古典密碼學（Classical Cryptography）

### 代換法（Substitution）

#### 凱撒加密法

#### Mono-alphabetic Cipher

#### Poly-alphabetic Cipher

### 換位法（Transposition）

#### Rail Fence Technique

#### Playfair Cipher

## 現代密碼學（Modern Cryptography）

### DES（Data Encryption Standard）
- 屬於**區塊加密法**，對「一定大小（64 bits）」的明文或密文作加解密。
- 最後一個區塊的大小可能小於 64 bits，此時就要用 0 去作補位。
- 使用金鑰也是 64-bit，但其中 8-bit 是用來作錯誤更正，故**金鑰有效長度只有 56-bit**。

加解密架構如下圖所示：

其中，**加密流程**如下圖：

另外，**回合金鑰的產生方式**如下：

#### 應用：Triple DES EDE2

### AES（Advanced Encryption Standard）
- 新一代 NIST/FIPS 的加密標準。
- 明/密文區塊擴充為 128 bits。
- 主金鑰的長度有 128 / 192 / 256 bits 三種選擇。

整體**加解密框架**如下圖：
> 注意：第一輪之前會先做一次 `AddRoundKey`；最後一輪無 `MixColumns`。

#### `SubBytes`

#### `ShiftRows`

#### `MixColumns`

#### `AddRoundKey`

#### Key Expansion

### RSA

「確定式」公開金鑰加密演算法，可用來**加密**或**簽章**。
> 破解難度：植基於 Factorization Problem。

#### Key Generation

#### Encryption

#### Decryption

**加解密**範例：

**數位簽章**範例：
- 簽章：$M = 19$；$S = M^d\ mod\ n = 19^{77}\ mod\ 119 = 66\ mod\ 119$。
- 驗證：**?** - $M = S^e\ mod\ n = 66^5\ mod\ 119 = 19$。

### ElGamal

「機率式」公開金鑰加密演算法，可作**加密器**或**簽章**。
> 破解難度：植基於 Discrete Logarithm Problem。

#### 加解密
- 使用參數
- 系統參數。
- `p`：大質數。
- `g`：primitive root on modulo `p`。
- $x_B$：使用者 B 之私鑰。
- $y_B$：使用者 B 之公鑰，其中 $y_B = g^{x_B}\ mod\ p$。
- **加密**：A 傳送明文 $M$ 給 B
1. 選一亂數 `k`（$1<k<p-1$）。
2. 計算 $C_1 = g^k\ mod\ p$。
3. 計算 $C_2 = M*y^k_B\ mod\ p$。
4. 密文：($C_1$, $C_2$)。
- **解密**：B 收到密文後
1. 計算 $C_2*(C^{x_B}_1)^{-1} \ mod\ p$。
2. 結果即為明文 $M$。

#### 數位簽章
- **簽章**：B 欲簽署明文 $M$（可先透過雜湊函數，算出 $h(M)$）
1. 選一亂數 `k`（$1<k<p-1$；`GCD(k, p-1) = 1`）。
3. 計算 $r = g^k\ mod\ p$。
4. 計算 $s$：$h(M) = x_B*r\ +\ k*s\ mod\ (p-1)$。
5. 數位簽章：($r$, $s$)。
- **驗證**：
1. 檢查 $g^{h(M)}\ ?=\ y^r_B * r^s\ mod\ p$。

### ECC（Elliptic Curve Cryptography）

橢圓曲線是一方程式：$y^2 = x^3\ +\ ax\ +\ b$，其中 $x$, $y$, $a$, $b$ 皆為實數。

而在橢圓曲線上的點 $E(a,b)$，可在「加法運算」上形成 **Abelian group**，特性如下：

部分圖像化：

部分證明：

#### Finite Elliptic Curves
- ECC 使用之曲線的「變數」和「係數」取自有限集合（例如有限域）。
- **Prime curves**：
- $E_P(a, b)$，在質數域 $F_P$ 上定義的。
- 使用的是質數 P 的模整數。
- 容易在軟體中實現。
- **Binary curves**：
- $E_2^m(a, b)$，在二元有限域 $GF(2^m)$ 上定義的。
- 使用的是二進制係數的多項式。
- 更適合硬體中的實現。
- 密碼學中，**橢圓曲線上的加法 = 整數中的乘法**：
- 故「重複加 = 指數運算」。
- 易於計算 $Q = P + P + \dots + P = kP$，其中 $Q$, $P$ $\in E$ 。
- 然而，用 $Q$ 和 $P$ 來求 $k$ 非常困難，稱橢圓曲線離散對數問題（ECDLP）。

#### 加解密
如下圖：

範例：

#### 數位簽章
如下圖：

#### ECC Diffie-Hellman（ECDH）
ECC 應用之一，透過 ECC 加密作**安全金鑰交換**，雙方可以安全地共享金鑰，如下圖範例：