# 【密碼學 I - Overview of Cryptography】

## 01 - 密碼學基礎

### 01-01. 什麼是密碼學？
**詞源**：Cryptography (或 cryptology) 一詞源自古希臘文，由 kryptós (意為「隱藏訊息的」) 和 graphein (意為「書寫」) 組成 。

**核心分支**：
- 密碼學 (Cryptography)：專注於「創造密碼」(Code-making) 的技術 。
- 密碼分析 (Cryptanalysis)：專注於「破解密碼」(Code-breaking) 的技術 。

**科學定義**：密碼學是一門透過數學方法，在資訊傳輸中達成**保密性(secrecy)與鑑定性 (authenticity)** 的科學 。

**理論奠基**：資訊理論的創始人克勞德·夏農 (Claude Shannon) 於 1949 年發表了史上第一篇探討密碼系統通訊理論的論文 。

:::success
**重點筆記**：範例
- 東方：清代的紀曉嵐曾使用「反切法」來加密訊息。
- 西方：二戰時期，美軍使用**納瓦霍語 (Navajo code)** 作為密碼，因為該語言結構複雜且未曾有書面紀錄，使敵軍難以破解。

:::

### 01-02. 密碼學的目標
密碼學主要有兩大核心目標：**保密性**與**鑑定性**。

* **保密性 (Secrecy / Privacy)**：確保資訊不被未授權者讀取。
* **鑑定性 (Authenticity)**：驗證資訊來源與完整性。
1. **訊息鑑定 (Message)**：包含完整性 (Integrity) 與不可否認性 (Non-repudiation)。
2. **傳送方鑑定 (Sender)**：即身份驗證 (Authentication)。

**核心術語**
- **明文 (Plaintext)**：原始的、可識別的訊息。
- **密文 (Ciphertext)**：經過轉換後，難以識別的訊息。
- **金鑰 (Key)**：用於加密和解密的關鍵資訊，僅傳送方與接收方知曉。
- **加密 (Encryption)**：使用密碼和金鑰，將明文轉換為密文的過程。
- **解密 (Decryption)**：使用密碼和金鑰，將密文還原為明文的過程。

:::success
**重點筆記**：範例
1. **明文**："HELLO"
2. **金鑰**：凱撒密碼的位移 3
3. **加密**：將每個字母往後推 3 位
4. **密文**："KHOOR"
5. **解密**：將每個字母往前拉 3 位，還原為 "HELLO"
:::

### 01-03 為什麼需要密碼學？
在 OSI 網路模型中，應用層（第 7 層）預設使用超文本傳輸協定 (HTTP)，該協定以明文傳輸資料 。這使得網路資料交換不安全 。

因此，為了解決這個問題，在 HTTP 之上加入了 SSL/TLS 來加密資料，將其轉換為密文，從而建立了 HTTPS (安全超文本傳輸協定) 。這確保了即使資料被攔截，也無法輕易被解讀 。

### 01-04 密碼系統的組成元件
一個密碼系統 (Cryptographic System) 包含以下元件 ：

* **偽隨機數生成器 (Pseudo Random Number Generator, PRNG)**：產生看似隨機、無法預測的數字序列，用於生成金鑰或加密過程中的隨機因子。
* **簽章 (Signature)**：用於驗證訊息來源和不可否認性，確保訊息是由特定發送者發出且未被竄改（詳見 04-04）。
* **雜湊 (Hash)**：將任意長度的資料轉換為固定長度的摘要，用於確保資料的完整性（詳見 05）。


<br>

### 02-01. 柯克霍夫原則 (Kerckhoffs's Principle)
這是一條現代密碼學的基礎假設：一個密碼系統的安全性，應**僅依賴於金鑰的保密性**，而非加解密演算法的保密性。

夏農將此詮釋為：「敵人了解整個系統」。這意味著，即使攻擊者知道演算法、持有密文，甚至掌握部分明文與密文的配對，只要沒有金鑰，系統依然是安全的。

:::success
**重點筆記**：**AES (進階加密標準)**
演算法是全世界公開的，任何人都可以查閱其運作的每一步驟。但只要您使用的 256 位元金鑰是保密的，您的資料就是安全的。安全性不在於演算法是秘密，而在於金鑰是秘密。
:::

### 02-02. 密碼分析的攻擊類型
根據攻擊者掌握的資訊量，可分為四種攻擊等級：
- **僅知密文攻擊 (Ciphertext-Only Attack)**：
1. 攻擊者只擁有密文序列 $c_1, c_2, ..., c_n$。
2. 攻擊目標是找出對應的明文 $m_1, m_2, ..., m_n$ 或金鑰 $K$。
3. 【範例】：攻擊者攔截了一封加密郵件，只能看著加密後的亂碼，並試圖透過統計分析（如字母頻率）來破解它。

- **已知明文攻擊 (Known-Plaintext Attack)**：
1. 攻擊者擁有一些明文與其對應的密文配對 $\{m_1, c_1\}, \{m_2, c_2\}, ... , \{m_n, c_n\}$，但這些配對的內容無法由攻擊者控制。
2. 攻擊目標是推導出金鑰 $K$，或從新的密文 $c_{n+1}$ 中找出 $m_{n+1}$。
3. 【範例】：二戰時，盟軍知道德軍的每封電報固定以 "Heil Hitler" 開頭。這使得他們擁有了已知的明文 ("Heil Hitler") 和對應的密文，大大幫助了 Enigma 的破解。

- **選擇密文攻擊 (Chosen-Ciphertext Attack)**：
1. 攻擊者可以選擇特定的明文，並取得其加密後的密文。
2. 攻擊者可透過取得其所選擇的明文之加密結果來蒐集資訊。公開金鑰系統必須能抵抗此類攻擊。
3. 【範例】：攻擊者誘使一個加密系統（例如一個網站伺服器）加密特定訊息（如 "admin_login"），並觀察其產生的密文，以此來推測金鑰或系統弱點。

- **選擇明文攻擊 (Chosen-Plaintext Attack)**：
1. 攻擊者可以選擇特定的密文，並取得其解密後的明文。
2. 攻擊者可透過取得其所選擇的密文之解密結果來蒐集資訊。
3. 【範例】：攻擊者傳送一個精心構造的（可能是略微損壞的）密文給解密伺服器，伺服器解密失敗並回傳一個錯誤訊息。攻擊者可以利用這個錯誤訊息（例如「填充錯誤」）來反推金鑰的資訊，這被稱為「Padding Oracle 攻擊」。

**安全性的層級**
- **理論安全 (Theoretical Security)**：無論攻擊者有多少計算能力與時間，都無法破解 。只有「一次性密碼本 (One-Time Pad, OTP)」系統能達到此標準 。其必要條件是金鑰長度必須大於等於明文長度 ($k \ge n)$ 。
- **實際安全 (Practical Security)**：雖然理論上可被破解，但在有限的資源與時間內是不可行的。今日安全的系統，不保證未來也安全 。

:::success
**重點筆記**：
**密碼學中的工作特性 (Work Characteristic)**
- 理論工作特性 (Theoretical Work Characteristic, $W(n)$)：理論上破解一個密碼系統所需的最低成本 。
- 歷史工作特性 (Historical Work Characteristic, $W_h(n)$)：目前已知破解一個密碼系統所需的最低成本 。

一個密碼系統若其歷史工作特性 $W_h(n)$ 在合理的資源內無法達成，則被認為是安全的。換言之，今日安全的系統不代表未來也必定安全 。

**窮舉式金鑰搜尋的時間估算**
下表顯示了針對不同金鑰大小進行窮舉搜尋（暴力破解）所需的時間 。

| 金鑰大小 (bits) | 替代金鑰數量 | 1 次解密 $/\mu s$ 所需時間 | $10^⁶$ 次解密 $/\mu s$ 所需時間 |
| :--: | :---: | :--: | :--: |
| $32$ | $2^{32} = 4.3 \times 10^{9}$ | $2^{31} \mu s = 35.8$ 分鐘 | $2.15$ 毫秒 |
| $56$ | $2^{56} = 7.2 \times 10^{16}$ | $2^{55} \mu s = 1142$ 年 | $10.01$ 小時 |
| $128$ | $2^{128} = 3.4 \times 10^{38}$ | $2^{127} \mu s = 5.4 \times 10^{24}$ 年 | $5.4 \times 10^{18}$ 年 |
| $168$ | $2^{168} = 3.7 \times 10^{50}$ | $2^{167} \mu s = 5.9 \times 10^{36}$ 年 | $5.9 \times 10^{30}$ 年 |
:::

**窮舉式金鑰搜尋攻擊範例**

一個實際的攻擊範例是使用 Microsoft Office 或 WinZip 等常見工具建立一個加密檔案（密文） 。接著，可以使用 ElcomSoft 公司的家用工具（例如 Advanced Office Password Recovery）來進行窮舉式金鑰搜尋（暴力破解攻擊），以還原明文和金鑰 。請注意，為避免觸法或不道德的行為，僅應在您自己擁有或獲得明確授權的檔案上進行測試 。

<br>

## 03 密碼系統的分類
密碼系統可依據三個規則進行分類，其中最常用的是依「金鑰數量」分類 。
- **依轉換方式：**
1. **代換法 (Substitution)**：將原始字母替換為其他字母 。例如：Pigpen Cipher。
3. **換位法 (Transposition)**：將原始字母重新排列順序 。例如：Rail Fence Cipher。

- **依金鑰數量**：在實務上最常見。
1. **秘密金鑰密碼學 (Secret-Key Cryptography)**：又稱**對稱式加密 (Symmetric Encryption)**。加解密使用同一把金鑰 。其安全性仰賴通訊雙方共享一個秘密 。
2. **公開金鑰密碼學 (Public-Key Cryptography)**：又稱**非對稱式加密 (Asymmetric Encryption)**。加解密使用不同的金鑰（公鑰與私鑰）。其安全性仰賴通訊雙方擁有共同的信任資訊 。
- **依處理方式：**
1. **區塊加密 (Block Cipher)**：將明文分塊處理 。例如 DES、Triple DES、IDEA、AES 。**（最廣泛使用）**
:::info
**注意事項**：區塊加密法的設計特性
1. **迷惑性 (Confusion)**：金鑰與明文、密文之間的關係不易被分析 。
2. **擴散性 (Diffusion)**：明文或金鑰中的任何一個位元發生改變，都可能影響到密文中的所有位元 。
3. **規則性 (Regularity)**：易於實現 。
4. **簡單性 (Simplicity)**：計算速度快 。
5. **相似性 (Similarity)**：加密與解密的設計相同，可降低成本 。

:::
3. **串流加密 (Stream Cipher)**：逐位元或位元組處理明文 。例如 RC4 。
4. **區塊加密操作模式 (Block Cipher Mode of Operation)**：例如 ECB、CBC、CFB、OFB 。
5. **基於密碼的密碼學 (Password-based Cryptography)**：例如 PKCS #5 。

<center>

| 特性比較 | 秘密金鑰 (對稱式) | 公開金鑰 (非對稱式) |
| :--: | :--: | :--: |
| 功能 | 保護機密資訊、驗證身份、確保完整性 | 保護機密資訊、數位簽章 |
| 優點 | 速度快、金鑰短、計算需求低 | 金鑰分配管理簡單、可提供不可否認性 |
| 缺點 | 金鑰分配問題、多人通訊時金鑰數量過多、無法提供不可否認性 | 速度慢、金鑰長、計算需求高 |

</center>

由於效能差異懸殊（硬體實現的 DES 比 RSA 快約 1000 倍），實務上常採用**混合型密碼系統**：使用公開金鑰系統來傳遞秘密金鑰，再用秘密金鑰加解密大量訊息 。

:::success
**重點筆記**
- **對稱式加密 (Symmetric Encryption)**：當加密金鑰 $K_1$ 與解密金鑰 $K_2$ 相同時（$K_1 = K_2$），此系統稱為對稱式加密 。此時，$K_1$和$K_2$都被稱為秘鑰 (secret keys) 。
- **非對稱式加密 (Asymmetric Encryption)**：當加密金鑰 $K_1$ 與解密金鑰 $K_2$ 不同時（$K_1 \neq K_2$），此系統稱為非對稱式加密 。此時，$K_1$ 被稱為公鑰 (public key)，$K_2$ 被稱為私鑰 (private key) 。
:::

### 03-01 密鑰加密
**資料加密標準 (Data Encryption Standard, DES)**
- 1976 年，美國國家標準暨技術研究院 (NIST) 宣布 DES 為資料加密標準 。
- 此演算法採用 16 回合的操作，包含擴展轉換、位元加法、替換及排列 。
- 安全性：
1. DES 的金鑰長度為 56 bits 。
2. 若破解速度為每秒 $10^6$ 個金鑰，透過暴力破解需要大約 3000 年的時間 。
3. 然而，若使用 100 萬台電腦平行運算，破解時間將縮短至約 26.28 小時 。

**三重 DES (Triple DES)**
- Triple DES 是一種 DES 的強化版本，有兩種金鑰模式 ：
1. $K_1 \neq K_2 \neq K_3$，金鑰長度為 168 bits 。
2. $K_1 = K_3 \neq K_2$，金鑰長度為 112 bits 。

**進階加密標準 (AES)**
- AES 由兩位比利時密碼學家 Vincent Rijmen 和 Joan Daemen 於 2000 年開發 。
- 它支援 128、160、192、224、256 bits 的金鑰大小 。
- 2002 年，NIST 宣布 AES 為新的資料加密標準 。
- 其常見變體包含 AES-128 (10 回合)、AES-192 (12 回合) 及 AES-256 (14 回合) 。
- AES 的特性是需要較少的記憶體且效率高 。

### 03-02 公鑰加密
**基本概念**
- 非對稱式密碼學基於數學上的困難問題，使其運算速度較慢 。然而，它無需進行金鑰分發，使其適合加密小量資料，例如對話金鑰 (session keys) 或用戶的個人資訊 。
- 常見的演算法範例有 RSA、ElGamal 等 。
- 無論是非對稱式加密或數位簽章 (digital signature)，都會使用一對公鑰與私鑰 。
- **數位憑證 (Digital Certificate)**：若一個使用者的公鑰經過認證（由一個受信任的憑證機構之私鑰所簽署），它便可用於身分鑑別 (authentication) 。

**基礎數學原理**
- **常見的數學運算**：有限體 (Finite Field)
:::success
**代數 (Algebra) 的定義與性質**
- 群 (Group)：一個集合配備單一運算，且滿足封閉性、結合性、單位元素及反元素等性質 。
- 交換群 (Commutative Group / Abelian Group)：一個群若額外滿足交換性 (commutative property)，則稱為交換群 。
- 體 (Field)：一個集合配備兩種運算（例如 + 和 ×），並滿足以下條件 ：
1. 在加法 + 運算下，它形成一個交換群 。
2. 在乘法 × 運算下，排除加法單位元素後，它形成一個群 。
3. 乘法對加法滿足分配律，即 a×(b+c)=(a×b)+(a×c)。

**有限體 (Finite Field)**
- 定義：有限體，又稱為伽羅瓦域 (Galois Field)，是一個僅包含有限個元素的體 。其元素的數量稱為它的階 (order) 。
- 在密碼學中的應用：許多密碼學的原始元件都是定義在伽羅瓦域 (GF) 之上 。
- 存在性：對於每一個質數 p 和每一個正整數 n，都存在一個唯一的有限體 $GF(p^n)$。
- 常見的伽羅瓦域：
1. $GF(p)$ ：其運算可視為模 $p (mod p)$ 的運算 。
2. $GF(2^n)$ ：其運算可視為模一個 $(n−1)$ 次多項式的運算 。
:::
- **主要的數學困難問題**
1. **背包問題 (Knapsack Problem)**
2. **質因數分解問題 (The Factoring Problem)**：由 Rivest、Shamir 和 Adleman 提出的 RSA 演算法 (1977年) 基於此問題 。
3. **離散對數問題 (Discrete Logarithm Problem)** ：Diffie 和 Hellman (DHKE, 1976年) 。ElGamal (1985年) 。
4. **橢圓曲線 (Elliptic Curve) 離散對數問題**：由 Koblitz 和 Miller 提出的 ECC (1985年) 基於此問題 。
5. **容錯學習問題 (Learning with Errors Problem)** ：由 Oded Regev 於 2005 年提出 。

:::success
**常見的數學運算是**
- **Modular Reduction (模運算)**：𝑏 = 𝑎 (mod 𝑛)
- **Modular Multiplication (模乘法)**：𝑐 = 𝑎 × 𝑏 (mod 𝑛)
- **Modular Exponentiation (模指數運算)**：𝑐 = 𝑎𝑏 (mod 𝑛)
- **Modular Multiplicative Inverse (模運算的乘法反元素)**：Find 𝑏 (commonly denoted as 𝑎−1) such that 𝑎 × 𝑏 = 1 (mod 𝑛)
:::

<br>

## 04 公開金鑰密碼學與其應用
公開金鑰密碼學的安全性基於數學困難問題 。

- **核心數學問題**：單向函數 (One-way Function)：一個函數 `y=f(x)`，計算 `f(x)` 很容易，但從 `y` 反推 `x` （$f^{-1}(y)$）很困難 。
- **單向暗門函數 (One-way Trapdoor Function)**：在單向函數的基礎上，若掌握額外資訊（暗門），則反推 `x` （$f^{-1}(y)$） 會變得很簡單 。
- **常見的困難問題：**
1. **背包問題 (Knapsack Problem)**：給定 $S = m_1B_1 + m_2B_2 + ... + m_nB_n$，計算 $S$ 很容易，但反而找出 $m_1, m_2, ..., m_n$ 很困難。
2. **質因數分解問題 (The Factoring Problem)**：將一個大數分解成兩個質數的乘積很困難 。RSA 演算法基於此問題 。給定 $N=p×q$，將兩個質數 $p$ 和 $q$ 相乘很容易，但將 $N$ 分解回質因數卻很困難 。
4. **離散對數問題 (Discrete Logarithm Problem, DLP)**：在 $y=g^x(mod p)$ 中，已知 $y$、$g$、$p$ 要反推 $x 很困難 。Diffie-Hellman 金鑰交換基於此問題 。橢圓曲線可用來建構基於離散對數問題的密碼系統 。
5. **容錯學習問題 (Learning with Errors, LWE)**：從許多帶有微小誤差的線性方程組中反推出秘密向量很困難 。這是許多後量子密碼學的基礎 。

:::success
**重點筆記**：容錯學習問題補充
- 給定許多向量配對 $(A_i, b_i)$ ，滿足 $b_i = A_i \cdot s + e_i (mod q)$，其中 $A_i$ 是矩陣，$s$ 是秘密向量，$e_i$ 是微小的錯誤向量 。若已知 $s$，計算 $b_i$ 很容易，但從這些帶有雜訊的方程式中還原 $s$ 卻很困難 。
- LWE 問題構成了許多實用的、基於晶格 (lattice-based) 的後量子密碼系統的計算基礎，例如 ML-KEM（通用加密）和 ML-DSA（數位簽章） 。
:::

### 04-01 金鑰交換協定：
**目標 (Objective)**：允許使用者在公開的通道上交換秘密資訊。

**使用情境 (Usage Scenario)**：指的是兩個或多個使用者透過公開通道建立一個對話金鑰 (session key) 的程序。這個對話金鑰通常是對稱式加密系統中使用的秘鑰 ，並且可以在每次對話時更新以確保安全 。

**代表性系統 (Representative System)**：Diffie-Hellman (DH) 金鑰交換系統。它基於 Ralph Merkle 提出的概念，Merkle 是 Hellman 在史丹佛大學指導的博士生。此協定也被稱為金鑰協商 (Key Agreement) 或金鑰測定 (Key Determination) 協定。

:::success
**重點筆記**：
- **起源**：金鑰交換協定的想法最初由 Ralph Merkle 於 1974 年在一場大學講座中提出，並在他就讀研究所期間的 1978 年發表 。
- 目標：讓 Alice 和 Bob 能在一個公開的網路上建立一個共同的秘密金鑰，同時讓竊聽者 Eve 在計算上難以取得此金鑰 。
- 假設：Alice 和 Bob 初始時沒有共享任何秘密金鑰 。 Alice 和 Bob 使用相同的對稱式加密演算法 。 每次加密或解密操作需要 $10^{-4}$ 秒。

**核心工具：謎題 (Puzzles)**
- Merkle Puzzle 的核心工具是「謎題」，這是一種需要花費一些努力才能解決的問題 。
- **範例**：一個謎題的解答 puzzle_key 可透過加密 $puzzle_{key} = E(key, "message")$ 得到，其中 $key$ 的格式為 $0^{96} || b_1...b_{32}$。
- **目標**：解決謎題的目標是嘗試所有 $2^{32}$ 種可能性來找出 $key$ 。

協定流程
- **Alice 準備謎題**：
1. Alice 準備 $2^{32}$ 個謎題。
2. 對於每個謎題 $i$，她會隨機選擇一個 32 位元的金鑰 $k_i$、一個 128 位元的謎題 ID $x_i$ 以及一個 128 位元的秘密 $s_i$。 她將這三者組合成明文 $M_{AB}||x_i||s_i$，並用金鑰 $k_i$ 加密，產生謎題 $puzzle_i$。 最後，Alice 將所有謎題 $puzzle_1, ..., puzzle_{2^{32}}$ 傳送給 Bob 。
- **Bob 解決謎題**：
1. Bob 從所有謎題中隨機選擇一個 $puzzle_j$。
2. Bob 嘗試所有可能的金鑰（暴力破解）來解密 $puzzle_j$，直到成功得到格式正確的明文 $M_{AB}||x_j||s_j$。
3. Bob 將謎題 ID $x_j$ 傳回給 Alice 。
- **建立共同秘密**：
1. Alice 透過查表，用 $x_j$ 找出對應的秘密 $s_j$。
2. 完成後， $s_j$ 就成為了雙方約定好的共享秘密金鑰 。
- **複雜度分析**：$n=2^{32}$
1. **Alice**：需要準備 $n$ 個謎題，其工作量為 $O(n)$。
2. **Bob**：需要解決一個謎題，其工作量為 $O(n)$ 。
3. **竊聽者 Eve**：Eve 必須竊聽並解決平均一半的謎題才能找到 Bob 選擇的那一個，其工作量為 $O(n^2)$ 。

:::

### 04-02 代表性演算法與協議
**Diffie-Hellman (DH) 金鑰交換協議**：
- 最早提出公開金鑰概念的協議之一，由 Diffie 和 Hellman 於 1976 年提出 。
- 允許兩方在一個不安全的公共頻道上，建立一個共享的秘密金鑰，而竊聽者無法輕易得知該金鑰 。
- 其安全性基於離散對數問題 。
- 以下兩個協定都採用了 Diffie-Hellman 金鑰協商系統：
1. Oakley 金鑰測定協定 (RFC 2412)
2. 網際網路協定的簡易金鑰管理 (SKIP)
- 參數設定：在標準協定中，通常會使用固定的系統參數 。
1. 系統參數 (所有使用者預先共享的參數)：
- $p$：一個足夠大的質數，通常為 1024 bits 或以上 。
- $g$：模 $p$ 的一個原根 。
2. 使用者參數 ：
- 私鑰：$x$，其中 $x \in [1,p−1]$ 。
- 公鑰：$y$，計算方式為 $y=g^x(modp)$ 。
- 雙方金鑰協商流程 (Alice 與 Bob)
1. Alice 選擇一個秘密值 $x_a$ 並計算 $y_a = g^{x_a}(mod p)$。
2. Bob 選擇一個秘密值 $x_b$ 並計算 $y_b = g^{x_b}(mod p)$。
3. Alice 將 $y_a$ 傳送給 Bob，Bob 則將 $y_b$ 傳送給 Alice 。
4. Alice 計算共享金鑰：$k_{ab} = y_b^{x_a} (modp)$。
5. Bob 計算共享金鑰： $k_{ba} = y_a^{x_b} (modp)$。
6. 雙方計算出的金鑰是相同的，因為 $k_{ab} = y_b^{x_a} = (g^{x_b})^{x_a} = g^{x_ax_b} = (g^{x_a})^{x_b} = y_a^{x_b} = k_{ba} (mod p)$。
7. 一個竊聽者即使知道 $y_a$ 和 $y_b$，若無法解決離散對數問題，就無法推導出共享金鑰 $k_{ab}$ 或 $k_{ba}$。
- 多方金鑰協商
1. 若有 $N$ 個參與者，則必須重複進行 $N−1$ 次資料交換才能建立一個共享金鑰 。
2. 例如，三個參與者需要經過 2 回合 (passes) 的交換才能建立共享金鑰 。

**RSA 加密演算法：**
- 簡介：RSA 是由 Ron Rivest、Adi Shamir 和 Leonard Adleman 三位學者於 1977 年在麻省理工學院 (MIT) 工作時共同提出的，並以他們姓氏的第一個字母命名 。
- 它的安全性基於分解大質因數的困難性 。若使用足夠長的金鑰，目前使用傳統電腦在計算上是無法破解的 。
- 演算法範例
1. 選擇兩個質數：$p=17, q=11$ 。
2. 計算 $N$ 與 $\Psi(N)$：$N=p \times q=187$、$\Psi(N)=(p−1)(q−1)=160$
3. 選擇公鑰 $e$：選擇 $e=7$（$e$ 必須與 $\Psi(N)$ 互質）。
4. 計算私鑰 $d$：計算 $d=23$，使其滿足 $e \cdot d=1(mod \Psi(N))$ 。
5. 加密：將明文 $M$ 加密為密文 $C=M^e(modN)$。例如，加密 $M=88$：$C=88^7(mod187)=11$
6. 解密：將密文 $C$ 解密還原為明文 $M=C^d(modN)$。例如，解密 $C=11：M=11^{23} (mod187)=88$ 。
- 安全性基於質因數分解的困難度、廣泛應用於加密與數位簽章 。
:::success
**重點筆記**：**質因數分解問題 (The Factoring Problem)**
- 由於 $\Psi(N)=(p−1)(q−1)$，若公鑰參數 $N$ 的兩個質因數 $p$ 和 $q$ 被找出，那麼 $\Psi(N)$ 就不再是秘密 。
- 因為公鑰 $e$ 是公開的，且滿足 $e \cdot d≡1(mod \Psi(N))$，所以一旦知道 $\Psi(N)$，攻擊者就可以使用歐幾里得演算法 (Euclidean algorithm) 來計算出私鑰 $d$ 。
- 因此，如果質因數分解可以被有效率地執行，RSA 密碼系統將完全沒有安全性可言 。
- 分解小數字很簡單（例如 $15=3 \times 5$），但分解極大的數字則非常困難 。
:::

### 04-03 延伸應用
**數位簽章與憑證 (Digital Signature and Certificate)**：使用私鑰對訊息摘要進行簽署，接收方可用公鑰驗證簽章，以確認訊息來源與完整性 。
- 盲簽章 (Blind Signature)：簽署者在不知道訊息內容的情況下進行簽署 。此技術可用於保護隱私，如電子投票或數位現金 。盲簽章是一種數位簽章，最早由 David Chaum 於 1983 年提出 。
- 在簽署前，訊息的內容對簽署者是隱藏的 。
- 簽署完成後的盲簽章，可以在原始、未盲化的訊息上進行公開驗證，如同一般的數位簽章一樣 。
- 由於簽署者和訊息作者是不同的實體，盲簽章能有效保護隱私，其應用範例包含電子投票與數位現金 。
- 運作流程 ：
1. Alice 擁有一對 RSA 金鑰 $(e,d)$ 。
2. Bob 擁有訊息 $m$ 和一個隨機數 $r$ 。
3. Bob 計算 $m' = m \cdot r^e (modN)$ 並將其傳送給 Alice 。
4. Alice 對收到的 $m'$ 進行簽署，得到 $s' = (m')^d = m^d \cdot r (mod N)$，並將 $s'$ 傳回給 Bob 。
5. Bob 移除盲化因子，得到原始訊息的簽章 $s = s' \cdot r^{-1} = m^d (mod N)$。

**模糊傳輸 (Oblivious Transfer)**
- 由 Michael Rabin 於 1981 年提出，模糊傳輸允許一方傳送一個位元給另一方，接收方有 50% 的機率取得該位元，另有 50% 的機率什麼也收不到 。
- 這種「二選一」的機率性傳輸協定主要基於 RSA 和二次剩餘問題，並結合一個僅發送方知道的隨機值 。
- 此概念可擴展為「n 選一」或「n 選 t」的模糊傳輸，在過程中需確保正確性，並保護 Alice (發送方) 與 Bob (接收方) 的隱私 。
1. **1-out-of-n**
2. **t-out-of-n**

:::success
**重點筆記**：資料來源
- **1-out-of-n**：M. Naor and B. Pinkas, “Oblivious transfer and polynomial evaluation,” In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 245-254. 1999.
- **t-out-of-n**：O. Wakaha and S. Ryota, “k out of n Oblivious transfer without random oracles,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 87(1): 147-151, 2004.
:::

**零知識證明 (Zero-Knowledge Proof)**
- 一方（證明者）可以向另一方（驗證者）證明他/她擁有某些資訊的知識，而無需向驗證者揭露該資訊的實際內容 。

:::success
**重點筆記**：資料來源
- J.-J. Quisquater, L. C. Guillou, and T. A. Berson, “How to explain zero-knowledge protocols to your children,” CRYPTO' 89 Proceedings, Lecture Notes in Computer Science, vol. 435, pp. 628–631, 1990.
:::

**同態加密 (Homomorphic Encryption)**：允許在密文上直接進行運算，解密後的結果與在明文上運算的結果相同 。適用於雲端安全計算等場景 。
- 由美國密碼學家 Craig Gentry 於 2009 年首次提出，同態加密允許在密文上執行某些運算，而無需將其解密為明文 。
- 主要類型 ：
1. 全同態加密 (FHE)：支援在密文上進行加法與乘法運算 。
2. 部分同態加密 (PHE)：僅支援一種運算（通常是加法或乘法） 。
3. 基於屬性的同態加密 (ABHE)：基於資料的屬性而非特定密文進行計算 。
- 主要應用：包含雲端安全運算、隱私保護資料分析及安全多方計算 。
- 實作範例：使用 RSA 很容易實現乘法同態加密 。對於兩個明文 $m_1$ 和 $m_2$，其同態性質如下：$E(m_1) \cdot E(m_2) = m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e = E(m_1 \cdot m_2) (mod N)$。
<br>

## 05 單向雜湊函數 (One-Way Hash Function)

**定義**：一種能將任意長度的輸入資料，轉換為**固定長度**輸出的函數 。

**功能與用途**
- **功能**：給定一個任意長度的輸入 $x$，單向雜湊函數可以計算出一個固定長度的輸出 $h(x)$ 。
- 用途：常與數位簽章一起使用，以提升簽章速度並增強安全性 。
- 常見範例：MD5、SHA-1、SHA-2 等 。

**演算法結構**
- 單向雜湊演算法的建構方法稱為 Merkle–Damgård 結構 。
- MD5、SHA-1 和 SHA-2 等演算法都使用了這種結構 。

**特性：**
1. **易於計算**：對於任意輸入 `x`，計算 `H(x)` 使其硬體和軟體實現都切實可行 。
2. **單向性 (Pre-image Resistance)**：已知輸出 `h`，要找到一個輸入 `x` 使得 `H(x)=h` 是不可行的 。
3. **弱碰撞抵抗 (Second Pre-image Resistance)**：已知輸入 `x`，要找到另一個不相等的輸入 `y` 使得 `H(x)=H(y)` 是不可行的 。
4. **強碰撞抵抗 (Collision Resistance)**：要找到任意一對相異的輸入 `(x,y)` 使得 `H(x)=H(y)` 是不可行的 。

**使用單向雜湊函數進行訊息鑑別**：有三種主要方式可以利用雜湊函數來驗證訊息的完整性與來源
1. **使用傳統加密**：將訊息的雜湊值用對稱式金鑰加密後傳送 。

2. **使用非對稱式加密 (數位簽章)**：將訊息的雜湊值用私鑰加密（簽章）後傳送 。

4. **使用秘鑰 (HMAC)**：將秘鑰與訊息結合後進行雜湊運算，產生訊息鑑別碼 。

<br>

## 06 E-Commerce
**電子支票 (E-Check)**：電子支票是一種**先交易後付款（Post-Transaction Payment）**的支付方式，**適合金額較大的交易（Suitable for High-Value Transactions）** 。它利用基於非對稱式密碼學的數位簽章來達成**簽名效果（Signature Effect）**，並透過**數位憑證（Identity Verification）** 確認付款人與銀行的身分 。
- 交易流程 ：
1. 消費者選擇商品並以電子支票付款 。
2. 線上商店驗證支票 。
3. 商店出貨 。
4. 商店存入電子支票 。
5. 進行清算與結算 。
6. 更新帳戶紀錄 。

**電子旅行支票 (E-Traveler’s Check)**：相較於傳統旅行支票使用護照和簽名進行驗證，可能因護照**仿冒（Forged passport）**而導致**盜領（Fraudulent withdrawal）**，電子旅行支票採用智慧卡和生物辨識（如聲紋、指紋）等方式 。它是一種先付款的預付形式 ，並使用非對稱式密碼學的數位簽章 。
- 交易流程 ：
1. 憑證發行 。
2. 購買電子旅行支票 。
3. 提出兌換請求 。
4. 提出驗證請求 。
5. 核准貸款/付款 。
6. 現金轉帳 。
7. 金額結算 。

**電子競標 (E-Auction)**
- 英式拍賣 (English Auction)：從低價開始，價格遞增，出價最高者得標 。賣家可設定底價 。例如 eBay、Amazon Auctions 。
- 荷式拍賣 (Dutch Auction)：從高價開始，價格遞減，第一個接受當前價格的投標者得標 。
- 封閉式拍賣 (Sealed-bid Auction)：每位投標者提交機密標單，互不知曉對方出價 。此模式通常採用數位簽章和通訊金鑰來增強安全性 。

**電子投票 (E-Voting)**：相較於傳統投票有時間、地理限制且開票慢的缺點 ，電子投票具有可在任何時間、任何地點進行且效率高的優點 。
- 安全特性 ：
1. 合法性 (Legitimacy)：透過非對稱式密碼學達成 。
2. 正確性 (Correctness)：透過 AES 等對稱式加密達成 。
3. 匿名性 (Anonymity)：透過盲簽章達成 。

**其他相關研究領域**
- **秘密分享 (Secret Sharing)**：將一個秘密 `S` 分割成 `n` 份，需要集滿 `t` 份（$t \le n$） 才能還原秘密，而少于 `t` 份則無法獲得任何關於秘密的資訊 。
- **視覺密碼學 (Visual Cryptography)**：將秘密影像分解成數張看似雜亂無章的圖片（透明片），將這些圖片疊加後，即可用肉眼直接辨識出原始的秘密資訊 。
- **資訊偽裝學 (Steganography)**：將秘密訊息隱藏在一個正常的載體（如圖片、音訊、影片）中，使其不被察覺 。例如，LSB (最低有效位) 方法就是將秘密訊息的位元嵌入到圖片像素值的最低位元中 。