# 【密碼學 X - Public-Key Cryptography】

## 01. 公開金鑰密碼學基礎

### 01-01. 對稱式 vs. 非對稱式金鑰系統
這兩種體系並非互相排斥，而是**互補的**。實務上常將兩者結合，利用其中一個的優點來補償另一個的缺點。（例如用非對稱加密來交換對稱加密的「會議金鑰」）。

**基礎差異：**
- **對稱式 (Symmetric)**：基於分享的秘密 (Shared Secret)。對數據的處理方式主要是符號的重新**排列與取代 (Permutation & Substitution)**。
1. **運作**：加密與解密使用 **同一把** 金鑰。
2. **缺點**：金鑰管理困難。若要與 N 人通訊，需要管理 N 把不同的金鑰，且金鑰分配過程需高度保密。
- **非對稱式 (Asymmetric)**：基於**個人的秘密 (Personal Secret)**。對數據的處理方式是將明文與密文視為整數，進行數字的操作處理 (如指數、模數運算)。
1. **運作**：使用一對金鑰。**公開金鑰 (Public Key)** 用於加密，**私密金鑰 (Private Key)** 用於解密。
2. **優點**：解決了金鑰管理問題（只需公開一把鑰匙），且具備數位簽章功能。
3. **缺點**：計算速度較慢，運算成本高。

**金鑰架構：**
* 非對稱式使用兩把不同的金鑰：**公開金鑰 (Public Key)** 與 **私密金鑰 (Private Key)**。
* **加密 (Encryption)：** $C = f(K_{\text{公開}}, P)$
* **解密 (Decryption)：** $P = f^{-1}(K_{\text{私密}}, C)$
* 其中 $P$ 為明文 (Plaintext)，$C$ 為密文 (Ciphertext)。

:::success
**重點筆記**：白話小例子
- **對稱式**：像是家裡的門鎖，你和家人都拿同一把鑰匙，誰弄丟了鑰匙，全家都要換鎖。
- **非對稱式**：像是一個投入式信箱（公開金鑰），任何人（Bob）都可以往裡面丟信（加密），但只有擁有信箱鑰匙（私密金鑰）的郵差（Alice）才能打開把信拿出來（解密）。
:::

### 01-02. 為何需要公開金鑰系統？
**解決金鑰管理問題：**
- 在對稱式系統中，若要與 $N$ 個人進行秘密通訊，必須分別持有 $N$ 把不同的秘密金鑰，管理困難。
- 公開金鑰系統中，每人只需要維護 **1 把私密金鑰** 和 **1 把公開金鑰** 即可。

**系統優缺點：**
* **優點：** 無金鑰管理問題、高安全性、具備**數位簽章**功能。
* **缺點：** 加解密速度較慢（因此常與對稱式混合使用）。

**著名的公開金鑰系統**：Diffie-Hellman (1976)、RSA (1977)、Rabin (1979)、ElGamal 與 ECC (1985)

:::success
**重點筆記**：混合系統的應用
就像網購時（HTTPS），瀏覽器會先用「非對稱加密（慢、安全）」來跟伺服器交換一把臨時鑰匙，之後傳送大量的信用卡資料時，就改用這把臨時鑰匙進行「對稱式加密（快）」。這就是互補的體現。
:::

### 01-03. 單向暗門函數 (Trapdoor One-Way Function)
非對稱金鑰密碼學的核心數學概念。

**單向函數 (One-Way Function):**
* 給定 $x$，計算 $y = f(x)$ 很簡單。
* 給定 $y$，要反推 $x = f^{-1}(y)$ 非常困難（在多項式時間內無解）。

**單向暗門函數**：如果擁有一個特殊的「**暗門資訊（Trapdoor）**」（祕密），即使給定 $y$，也能輕易計算出 $x$。)

**常見數學難題:**
- **質因數分解 (Factorization):**
1. 給定 $p, q$ 求 $n=p \times q$ 很簡單
2. 給定很大的 $n$ 要反推 $p, q$ 很難（除非知道其中一個因數）。
3. 應用：Rabin 系統。

- **離散對數問題 (Discrete Logarithm):**
1. 函數 $y = x^k \mod n$ 。給定 $x, k, n$ 算 $y$ 很容易（快速指數運算）
2. 給定 $y, k, n$ 要反推 $x$ 很難。（ElGamal 的基礎）
3. 暗門機制： 若知道 $k$ 的模反元素 $k^{-1}$ (即 $k \times k^{-1} \equiv 1 \mod \phi(n)$)，則可透過 $x = y^{k^{-1}} \mod n$ 輕鬆解出 $x$。
4. 應用：RSA 系統。

<br>

## 02. Diffie-Hellman 金鑰交換

### 02-01. 運作原理
這是第一個公開金鑰協議 (1976)，主要目的是讓雙方在不安全的通道上，安全地協商出一把「共用的密鑰」。

**公開參數**雙方同意使用一個大質數 $p$ 和一個生成元 $g$。

**交換過程**：
- **Alice (產生私鑰 $x_a$)**： 計算公鑰 $y_a = g^{x_a} \mod p$ 並傳送給 Bob。
- **Bob (產生私鑰 $x_b$)**： 計算公鑰 $y_b = g^{x_b} \mod p$ 並傳送給 Alice。

**計算共享金鑰 $K$**：
- Alice 計算：$K = (y_b)^{x_a} \mod p = (g^{x_b})^{x_a} \mod p$
- Bob 計算：$K = (y_a)^{x_b} \mod p = (g^{x_a})^{x_b} \mod p$
- 雙方現在擁有一樣的秘密 $K$，可用於後續對稱式加密通訊。

:::success
**重點筆記**：數字小例子假設 $p=23, g=5$。
- Alice 選私鑰 $x_a=6$，送出公鑰 $5^6 \mod 23 = 8$。
- Bob 選私鑰 $x_b=15$，送出公鑰 $5^{15} \mod 23 = 19$。
- Alice 計算 $K = 19^6 \mod 23 = 2$。
- Bob 計算 $K = 8^{15} \mod 23 = 2$。
- 結果： 兩人都算出了金鑰 2。
:::

### 02-02. 中間人攻擊 (Man-in-the-Middle Attack)
由於 Diffie-Hellman 協議本身缺乏身分認證 (Authentication) 機制，攻擊者 (Eve) 可以攔截並篡改訊息。

**攻擊場景：**
- Alice 送出 $g^{x_a}$，Eve 攔截下來，改送自己生成的偽造公鑰 $g^c$ 給 Bob。
- Bob 送出 $g^{x_b}$，Eve 攔截下來，改送 $g^c$ 給 Alice。

**結果**：
- Alice 以為在跟 Bob 通訊，其實跟 Eve 建立了金鑰 $K_1 = (g^c)^{x_a} \mod p$。
- Bob 以為在跟 Alice 通訊，其實跟 Eve 建立了金鑰 $K_2 = (g^c)^{x_b} \mod p$。
- Eve 夾在中間，可以解密 Alice 的訊息（用 $K_1$），再用 $K_2$ 加密傳給 Bob，雙方完全不知情。

### 02-03. 可能的解決方案 (Possible Solutions)
**為了防禦中間人攻擊，必須引入認證機制，確認公鑰真的來自對方。**
- 建立認證的安全通道： 利用雙方預先擁有的「前置共享密鑰」(Pre-shared Secret) 來加密交換的訊息。
- 雜湊認證 (Hash Authentication)：
1. 在 Diffie-Hellman 交換之後，緊接著傳送「共享數值 + 名稱 + 前置共享密鑰」的雜湊值，供對方驗證。
2. 或者傳送「前置共享密鑰 + 所傳送參數」的雜湊值。

<br>

## 03. RSA 密碼系統

### 03-01. 背景與概念
- **發展歷史**：由 MIT 三位教授 Rivest、Shamir、Adleman 於 1977 年發展。
- **功能**：可同時達成資料加密 (機密性) 與數位簽章 (認證、不可否認性)。
- **運作模式**：
1. RSA Encryption (加密)：使用接收者的公開金鑰 (Public Key) 加密明文。
2. RSA Decryption (解密)：接收者使用自己的私密金鑰 (Private Key) 解密密文。

### 03-02. 演算法詳解
RSA 是最經典的非對稱加密算法 (1977)，安全性建立在「大整數質因數分解」的困難度上。

**金鑰產生演算法 (Key Generation):**
1. **選數:** 選擇兩個大質數 $p$ 和 $q$ (兩者不相等)。建議長度: $p, q$ 至少 512 bits，模數 $n$ 至少 1024 bits。
2. **模數:** 計算 $n = p \times q$ (作為公開與私密金鑰的模數)。
3. **歐拉函數:** 計算 $\phi(n) = (p-1)(q-1)$。(代表小於 $n$ 且與 $n$ 互質的正整數個數)
4. **選公鑰:** 選擇一個整數 $e$，滿足 $1 < e < \phi(n)$ 且 $e$ 與 $\phi(n)$ 互質。滿足 $\gcd(e, \phi(n)) = 1$。（**公開金鑰:** $(e, n)$)
5. **算私鑰:** 計算 $d$，使得 $e \times d \equiv 1 \mod \phi(n)$ (即 $d$ 是 $e$ 的模反元素)。(**私密金鑰:** $d$)

RSA_Key_Generation
{
    Select two large primes p and q such that p != q.
    n <- p x q
    ф(n) <- (p - 1) × (q - 1)
    Select e such that 1 < e < ф(n) and e is coprime to (n) 
    d <- e^(-1) mod ф(n) # d 是 e 在模 ф(n) 底下的乘法反元素
    Public_key <- (e,n) # 公開宣布
    Private_key < d # 保持秘密
    return Public_key and Private_key

**加密與解密假設明文為**
- $P$ (需將資料切分為區塊，每次加密範圍需小於 $n$)，密文為 $C$。

    RSA_Encryption (P, e, n) # P 是在 Zn 下的明文且 P < n
    {
        C <- Fast_Exponentiation (P, e, n) # 計算 (P^e mod n)
        return C
    }
    RSA_Decryption (P, e, n) # C 是在 Zn 下的密文
    {
        P <- Fast_Exponentiation (C, d, n) # 計算 (C^d mod n)
        return P
    }

- **加密**：$C = P^e \mod n$

- **解密**：$P = C^d \mod n$

:::success
**重點筆記**：數字小例子：
1. 選 $p=3, q=11$, $n = p \times q = 33$。
3. $\phi(n) = (3-1)(11-1) = (2)(10) = 20$。
4. 選 $e=3$ (與 20 互質)。**公鑰: (3, 33)**。
5. 求 $d$，使得 $3 \times d \equiv 1 \mod 20$。因為 $3 \times 7 = 21 = 1 \mod 20$，所以 $d=7$。**私鑰: 7**。
6. **加密:** 設明文 $P=19$。$C = 19^3 \mod 33 = 6859 \mod 33 = 28$。
7. **解密:** $P = 28^7 \mod 33 = ... = 19$。
:::

### 03-03. 安全性分析 (因數分解問題)
- **核心難題**：RSA 的安全性完全取決於大整數質因數分解的困難度。
- **攻防關鍵**：
1. 公開資訊為 $(e, n)$。
2. 私密資訊為 $d$，而 $d$ 是從 $\phi(n) = (p-1)(q-1)$ 算出來的。
3. 如果攻擊者能將 $n$ 分解成 $p, q$，就能算出 $\phi(n)$，進而利用歐幾里得演算法算出私鑰 $d$。
- **RSA 數 (RSA Numbers) 挑戰**：
1. 自 1991 年起 RSA 實驗室提出的分解挑戰。
2. RSA-200 (663 bits): 2005 年被分解 (用了 80 顆 2.2GHz CPU 跑了 3 個月)
3. RSA-768: 2009 年被分解。
4. RSA-1024 / 2048: 目前被認為是安全的標準 (建議 $n$ 至少 2048 bits)。

### 03-04. 公開金鑰系統的四項特性
一個完善的公開金鑰密碼系統 (Public-Key Cryptosystem) 應具備以下特性：
1. **可還原性 (Reversibility)**: $D(d, E(e, P)) = P$。用私鑰解密經過公鑰加密的訊息，必須能還原明文。
2. **易計算性**: 產生金鑰對 $(e, d)$ 很容易；加密與解密運算在已知金鑰下很容易 (多項式時間)。
3. **單向暗門**：若公開 $(e, n)$，別人很難從 $(e, n)$ 去求得 $d$，即只有自己知道如何解以 $d$ 加的密
4. **可驗證性**：$D(e, E(d, P)) = P$

**單向暗門 (Trapdoor One-Way)**:
- 僅知公鑰 $(e, n)$，在計算上無法推導出私鑰 $d$。滿足 1~3 項稱為 Trapdoor One-Way Function。
- 若能用私鑰加密、公鑰解密，則該系統可支援數位簽章。同時滿足 1~4 項稱為 Trapdoor One-Way Permutation。

:::info
**注意事項**：
- 加密用公鑰，解密用私鑰 $\rightarrow$ 保密 (Encryption)
- 加密用私鑰，解密用公鑰 $\rightarrow$ 簽章 (Authentication/Signature)
:::

<br>

## 04. Rabin 密碼系統

### 04-01. 基本概念
Rabin 系統可以被視為 RSA 密碼系統的一個特例，其中指數 $e$ ($e=2$) 和 $d$ 被固定。

**數學原理**：
- 加密： $C \equiv P^2 \mod n$ (平方運算)。
- 解密： $P \equiv C^{1/2} \mod n$ (求平方根)。

**演算法流程：**
- **金鑰產生 (Key Generation)**：
1. 接收者 Bob 選擇兩個大質數 $p, q$ (建議形式為 $4k+3$ 以簡化計算)。
2. 計算 $n = p \times q$。
3. 公開金鑰： $n$。
4. 私密金鑰： $(p, q)$。

    Rabin_Key_Generation
    {
        Choose two large primes p and q in the form 4k + 3 and p != q.
        n <- p x q
        Public_key <- n # 公開宣佈
        Private_key <- (p, q) # 保持秘密
        return Public_key and Private_key
    }

- **加密 (Encryption)**：
1. Alice 取得 $n$，確保明文 $0 \le P < n$。
2. 計算密文 $C = P^2 \mod n$。

    Rabin_Encryption (n, P) # m 是公開金鑰； P 是在 Zn* 下的明文
    {
        c <- p^2 mod n # Ｃ 是密文 
        return C
    ｝

- **解密 (Decryption)**：
1. Bob 收到 $C$ 後，使用私鑰 $p, q$ 計算 $C$ 在模 $n$ 下的四個平方根 $(P_1, P_2, P_3, P_4)$。
2. 這通常透過計算 $C$ 在模 $p$ 和模 $q$ 的根，再利用 中國餘數定理 (CRT) 組合而成。

    Rabin_Decryption (P, q, C) # C 是密文； p 及 q 是私密金鑰
    {
        a1 <- +(C^((p+1)/4) mod p
        a2 <- -(C^((p+1)/4) mod p
        b1 <- +(C^((q+1)/4) mod q
        b2 <- -(C^((q+1)/4) mod q # 呼叫四次中國餘數定理演算法
        P1 <- Chinese_Remainder (a1, b1, P, q)
        P2 <- Chinese_Remainder (a1, b2, P, q)
        P3 <- Chinese_Remainder (a2, b1, P, q)
        P4 <- Chinese_Remainder (a2, b2, P, q)
        return P1, P2, P3, and P4
    }

### 04-02. 二次剩餘與非確定性 (Indeterministic)
Rabin 系統最大的特點（也是問題）在於其非確定性：解密同一個密文會得到 4 個同樣可能的明文。
- **問題**： Bob 算出 **4 個可能的明文根** $(P_1, P_2, P_3, P_4)$，不知道哪一個才是 Alice 原本傳送的訊息。
- **解決方案 (識別格式)**：
1. 在明文中加入特定的預設格式或冗餘資訊 (Redundancy)。
2. 例如：將明文的後幾位元複製並接在後面 (如範例 10.9：$P = 1001...$ 變為 $1001...1001...$)。
3. 解密後，Bob 檢查哪一個根符合這個格式，該根即為正確明文。

:::success
**重點筆記**：題目目標：已知 $n = 161$ ($p=23, q=7$)，密文 $C = 93$。求解 $x^2 \equiv 93 \pmod{161}$。

**Step 1: 分解為兩個子問題**
將 $x^2 \equiv 93 \pmod{161}$ 拆解為：
- $x^2 \equiv 93 \pmod{23}$
- $x^2 \equiv 93 \pmod 7$

**Step 2: 求解子問題 (找出模 p 與模 q 的根)**
- **針對 $p=23$**：
1. 先化簡密文：$93 \pmod{23}$$93 \div 23 = 4 \dots 1$，所以 $93 \equiv 1 \pmod{23}$。方程式變為：$x^2 \equiv 1 \pmod{23}$。
2. 因為 $p=23$ 是 $4k+3$ 形式 ($4 \times 5 + 3$)，代入公式 $x = \pm C^{(p+1)/4}$：指數計算：$(23+1)/4 = 6$。$x \equiv \pm 1^6 \equiv \pm 1 \pmod{23}$。
3. 得到兩個根 ($a_1, a_2$)： $1$ 和 $22$ (即 $-1$)。
- **針對 $q=7$**：
1. 先化簡密文：$93 \pmod 7$$93 \div 7 = 13 \dots 2$，所以 $93 \equiv 2 \pmod 7$。方程式變為：$x^2 \equiv 2 \pmod 7$。
2. 因為 $q=7$ 是 $4k+3$ 形式 ($4 \times 1 + 3$)，代入公式：指數計算：$(7+1)/4 = 2$。$x \equiv \pm 2^2 \equiv \pm 4 \pmod 7$。
3. 得到兩個根 ($b_1, b_2$)： $4$ 和 $3$ (即 $-4$)。

**Step 3: 利用 CRT 組合解我們現在有四種組合 $(x_p, x_q)$ 需要合併**：$(1, 4)$$(1, 3)$$(22, 4)$$(22, 3)$CRT
- 參數準備：
1. $M = 161$
2. $M_1 (對應 p=23)$：$M_1 = 161/23 = 7$。求 $7$ 在模 $23$ 下的反元素：$7 \times y \equiv 1 \pmod{23}$。觀察 $7 \times 10 = 70 = 3 \times 23 + 1$，故反元素 $M_1^{-1} = 10$。
3. $M_2 (對應 q=7)$：$M_2 = 161/7 = 23 \equiv 2 \pmod 7$。求 $2$ 在模 $7$ 下的反元素：$2 \times y \equiv 1 \pmod 7$。$2 \times 4 = 8 \equiv 1$，故反元素 $M_2^{-1} = 4$。
CRT 通解公式：
$$x = (a_1 \times M_1 \times M_1^{-1} + b_1 \times M_2 \times M_2^{-1}) \pmod M$$
$$x = (x_p \cdot 7 \cdot 10 + x_q \cdot 23 \cdot 4) \pmod{161}$$
$$x = (70 x_p + 92 x_q) \pmod{161}$$
- 計算四個解：
1. 組合 $(1, 4)$：$x = (70 \times 1 + 92 \times 4) = 70 + 368 = 438$$438 \pmod{161} = 438 - 2(322) = \mathbf{116}$
2. 組合 $(1, 3)$：$x = (70 \times 1 + 92 \times 3) = 70 + 276 = 346$$346 \pmod{161} = 346 - 2(322) = \mathbf{24}$ (此為原始明文)
3. 組合 $(22, 4)$ (技巧：用 $-1$ 代替 $22$ 計算較快)：$x = (70 \times (-1) + 92 \times 4) = -70 + 368 = 298$$298 \pmod{161} = 298 - 161 = \mathbf{137}$
4. 組合 $(22, 3)$ (技巧：用 $-1$ 代替 $22$)：$x = (70 \times (-1) + 92 \times 3) = -70 + 276 = 206$$206 \pmod{161} = 206 - 161 = \mathbf{45}$

**最終結果**：解集合為 $\{116, 24, 137, 45\}$。這四個數平方後 mod 161 都會等於 93，Bob 必須從中判斷出 24 是正確的明文。

Bob 收到 93，並計算下面四個值：
- $a_1 = +(93^{(23+1)/4}) \pmod {23} = 1 \pmod {23}$
- $a_2 = −(93^{(23+1)/4}) \pmod {23} = 22 \pmod {23}$
- $b_1 = +(93^{(7+1)/4}) \pmod 7 = 4 \pmod 7$
- $b_2 = −(93^{(7+1)/4}) \pmod 7 = 3 \pmod 7$
:::

:::success
**重點筆記**
- 系統參數設定
1. 選取質數：$p = 277$，$q = 331$。
2. 計算模數：$n = p \times q = 91687$。
- 加密過程 (加入識別格式)
1. 原始訊息：$P_{raw} = 1001111001$ (二進制)。
2. 加入冗餘：為了能在解密時辨識，將後方部分位元複製並接在後面。格式策略：$P = P_{raw} \parallel \text{末 6 碼}$新明文：$P = 1001111001\mathbf{111001}_2$
3. 轉十進制：$P = 40569_{10}$。
4. 計算密文：$$C = P^2 \mod n = 40569^2 \mod 91687 = 62111$$
- 解密與驗證Bob 收到 $62111$ 後，算出模 $n$ 的四個平方根（候選明文），並轉回二進制檢查格式：
1. $P_1 = 10001000000010110_2$ $\rightarrow$ (格式不符)
2. $P_2 = 101011000010001_2$ $\rightarrow$ (格式不符)
3. $P_3 = 1001111001\mathbf{111001}_2$ $\rightarrow$ (符合！ 後 6 碼與前文對應)
4. $P_4 = 1100011110101110_2$ $\rightarrow$ (格式不符)
- 結論：因為 $P_3$ 呈現了預先約定的重複樣式（後 6 碼重複），故 Bob 可以確定 $P_3$ 即為 Alice 發送的正確明文。
:::

### 04-03. 安全性分析
**安全性基礎**： Rabin 系統的破解難度在數學上等同於大整數因數分解 (Factorization)。這是它理論上的一大優勢（證明若能破解 Rabin 就能分解 $n$）。

**弱點**：選擇密文攻擊 (Chosen Ciphertext Attack)
- 這是 Rabin 系統最致命的弱點。
- **攻擊過程**：
1. 攻擊者隨機選一個數 $x$，計算 $C = x^2 \mod n$。
2. 攻擊者將 $C$ 傳給 Bob (假裝是密文)，要求 Bob 解密。
3. Bob 解密後隨機回傳其中一個明文 $P$。
- **破解原理**：
1. 若 Bob 回傳的 $P$ 剛好不等於 $\pm x \mod n$ (發生機率為 $1/2$)。
2. 攻擊者就掌握了 $n$ 的兩個不同的平方根 ($x$ 和 $P$)。
3. 攻擊者只需計算 $\gcd(x - P, n)$，就能直接求出 $n$ 的因數 $p$ 或 $q$，從而完全破解系統。

<br>

## 05. ElGamal 密碼系統

### 05-01. 背景與原理
- **起源**：由 Taher ElGamal 提出，以其姓氏命名。
- **數學基礎**：安全性建立在 **離散對數問題 (Discrete Logarithm Problem)** 的困難度上。
- **特性**：是除了 RSA 與 Rabin 之外，另一種著名的公開金鑰系統。其加密與解密的位元運算複雜度皆為多項式時間 (Polynomial Time)。

### 05-02. 金鑰產生與加密解密
**Step 1: 金鑰產生 (Key Generation)**
- 選擇一個大質數 $p$。
- 選擇群 $Z_p^*$ 的一個 原根 (Primitive Root) $e_1$。
- 選擇私密金鑰 $d$，滿足 $1 \le d \le p-2$。
- 計算 $e_2 = e_1^d \mod p$。
1. 公開金鑰： $(e_1, e_2, p)$
2. 私密金鑰： $d$

ElGamal_Key_Generation
{
    Select a large prime p
    Select d to be a member of the group G = < Zp*, x > such that 1 <= d <= p-2
    Select e, to be a primitive root in the group G = < Zp*, x >
    e^2 <- e1^d mod p
    Public_key < (e1, e2, p) # 公開宣布
    Private_key < d # 保持秘密
    return Public _key and Private _key
}

**Step 2: 加密 (Encryption)** Alice 欲傳送明文 $P$ 給 Bob (需先取得 Bob 的公鑰)
- 選擇一個 隨機整數 $r$ (注意：每次加密都必須使用全新的 $r$)。
- 計算 $C_1 = e_1^r \mod p$ (保護隨機數)。
- 計算 $C_2 = (P \times e_2^r) \mod p$ (隱藏明文)。
- 傳送密文對 $(C_1, C_2)$。

ElGamal_Encryption (e1, e2, p, P) # P 是一個明文
{
    Select a random integer r in the group G = < Zp*, x>
    C1 <- e1^r mod p
    C2 < (P x e2^r) mod p # C1 及 C2 是密文
    return C1 and Cz
}

**Step 3: 解密 (Decryption)** Bob 收到 $(C_1, C_2)$ 後，使用私鑰 $d$ 還原明文：
- 方法一 (標準解法)： $P = [C_2 \times (C_1^d)^{-1}] \mod p$。(需計算乘法反元素)
- 方法二 (費瑪小定理)： 避免計算反元素，改用指數運算 $P = [C_2 \times C_1^{p-1-d}] \mod p$。

:::success
**重點筆記**：設定： Bob 選 $p=11$，原根 $e_1=2$。
- 選私鑰 $d=3$。
- 算公鑰： $e_2 = 2^3 \mod 11 = 8$。公鑰為 $(2, 8, 11)$。
- 加密： Alice 欲傳送明文 $P=7$，選擇隨機數 $r=4$。
1. $C_1 = 2^4 \mod 11 = 16 \mod 11 = 5$。
2. $C_2 = (7 \times 8^4) \mod 11$。因為 $8^4 = 4096 \equiv 4 \mod 11$，所以 $C_2 = 7 \times 4 \mod 11 = 28 \mod 11\equiv 6$。
3. 傳送密文 $(5, 6)$。
- 解密 (使用方法二)： Bob 收到 $(5, 6)$。
1. 計算指數 $p-1-d = 11-1-3 = 7$。
2. 計算 $P = [6 \times 5^7] \mod 11$。
3. $5^7 = 78125 \equiv 3 \mod 11$。
4. $P = 6 \times 3 = 18 \equiv 7$。成功還原明文！
:::

### 05-03. 安全性注意事項
- **金鑰長度要求**：為了確保安全，質數 $p$ 建議至少要有 300 位數字 (約 1024 bits) 以上。實際應用中常見 512 bits 或更高。
- **隨機數 $r$ 的重要性**：
1. 不可重複使用：對每一次加密，都必須採用一個全新的隨機數值 $r$。
2. 若重複使用 $r$，將導致安全性大幅降低，攻擊者可能透過分析密文找出規律。
- **效率與空間**：密文長度是明文的兩倍 ($C_1$ 與 $C_2$)，資料傳輸量較大。