---
# System prepended metadata

title: Cryptography - Introduction to Cryptography
tags: [Information Security]

---

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

## 密碼系統（Cryptographic System）
![image](https://hackmd.io/_uploads/r1YMLtiAC.png =80%x)
> Kerckhoff's principle：密碼系統的安全性，需「僅依賴其秘密金鑰」，而非其密碼演算法的隱藏。

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

## 古典密碼學（Classical Cryptography）

### 代換法（Substitution）

#### 凱撒加密法
![image](https://hackmd.io/_uploads/rJVfLco00.png =70%x)

#### Mono-alphabetic Cipher
![image](https://hackmd.io/_uploads/HJNZUcjAC.png =70%x)

#### Poly-alphabetic Cipher
![image](https://hackmd.io/_uploads/Hy5wLcsCA.png =60%x)

### 換位法（Transposition）

#### Rail Fence Technique
![image](https://hackmd.io/_uploads/SJPv_5s0R.png =50%x)

#### Playfair Cipher
![image](https://hackmd.io/_uploads/ByXcO9j0A.png =70%x)

## 現代密碼學（Modern Cryptography）

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

加解密架構如下圖所示：
![image](https://hackmd.io/_uploads/S1bw55sRC.png =40%x)

其中，**加密流程**如下圖：
![image](https://hackmd.io/_uploads/rk4qq5oC0.png =40%x)

另外，**回合金鑰的產生方式**如下：
![image](https://hackmd.io/_uploads/SJAA5ci0A.png =40%x)

#### 應用：Triple DES EDE2
![image](https://hackmd.io/_uploads/r1YSicoR0.png =50%x)

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

整體**加解密框架**如下圖：
![image](https://hackmd.io/_uploads/H16b0cj0R.png =70%x)
> 注意：第一輪之前會先做一次 `AddRoundKey`；最後一輪無 `MixColumns`。

#### `SubBytes`
![image](https://hackmd.io/_uploads/HkeZ1ioR0.png =75%x)
![image](https://hackmd.io/_uploads/HJQPksoAC.png =65%x)

#### `ShiftRows`
![image](https://hackmd.io/_uploads/ry_A1ojA0.png =70%x)

#### `MixColumns`
![image](https://hackmd.io/_uploads/B1jMgojAA.png =70%x)

#### `AddRoundKey`
![image](https://hackmd.io/_uploads/Bkh4goiRR.png =70%x)

#### Key Expansion
![image](https://hackmd.io/_uploads/B1CqeojAC.png =70%x)

### RSA

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

#### Key Generation
![image](https://hackmd.io/_uploads/B1w6-isA0.png =55%x)

#### Encryption
![image](https://hackmd.io/_uploads/Hy-yGji0C.png =55%x)

#### Decryption
![image](https://hackmd.io/_uploads/r1FJzssCC.png =55%x)

**加解密**範例：
![image](https://hackmd.io/_uploads/By287soAA.png =80%x)

**數位簽章**範例：
- 簽章：$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**，特性如下：
![image](https://hackmd.io/_uploads/Bk0uqij0C.png =60%x)

部分圖像化：
![image](https://hackmd.io/_uploads/rkOtqsi0C.png =70%x)

部分證明：
![image](https://hackmd.io/_uploads/rJRNisi0A.png =70%x)

#### 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）。

#### 加解密
如下圖：
![image](https://hackmd.io/_uploads/Hym0gnsCR.png =60%x)

範例：
![image](https://hackmd.io/_uploads/B1QJWnjRA.png =50%x)

#### 數位簽章
如下圖：
![image](https://hackmd.io/_uploads/rJUQbho0A.png =70%x)

#### ECC Diffie-Hellman（ECDH）
ECC 應用之一，透過 ECC 加密作**安全金鑰交換**，雙方可以安全地共享金鑰，如下圖範例：
![image](https://hackmd.io/_uploads/HkwOehjAR.png =60%x)