# 2023 成大資訊安全課程 期末範圍整理筆記
:::info
本文內容全文參考自授課教授李南逸所著之簡報。本人未於任何形式上擁有任一部分之著作權。如有任何疑慮或侵權情形，本文將立即修改或下架。
:::
## 非對稱式密碼系統

### 非對稱式金鑰密碼系統介紹
密碼系統可分為兩種：
1. 對稱式金鑰密碼系統 (Symmetric Key Cryptosystem)/ 秘密金鑰密碼系統 (Private Key Cryptosystem)
2. 非對稱式金鑰密碼系統 (Asymmetric Key Cryptosystem)/ 公開金鑰密碼系統 (Public Key Cryptosystem)

其中，對稱式金鑰密碼系統的主要缺點為：
1. 金鑰分配與管理問題 (Key Distribution Problem / Key Management Problem)
2. 數位簽章問題
因為接收方與發送方共用同一把金鑰，所以能驗證之接收者必能偽造發送方之密文。

另外，作為最被接受的簽署方式，手寫簽章之認證可透過其他人共同簽署來支持首簽名者之真確性。這包含了用墨水筆簽名、指印、或印章。
而手寫簽章可被偽造，因此證明一手寫簽名是否為該人所寫可能會需要法庭尋求辨識專家的協助。

民國 90 年時本國開始實施電子簽章法，針對電子文件可依附電子簽章作為簽署方式，這包含了以觸控筆簽名、指紋圖像、印章圖像、聲紋辨識、與數位簽章。

數位簽章是指使用數學演算法以簽署人之私密金鑰對文件進行簽章處理，並得以以對應之公開金鑰驗證者。

這代表數位簽章與電子簽章和手寫簽章具有同等效力，其包含
1. 表示同意
2. 數位資料
3. 簽章技術
4. 憑證機構
5. 憑證效力

這表示使用者可以請一憑證機構 (Certificate Authority) 以其私鑰對自己之公開金鑰進行簽署，使任何人可透過憑證機構之公開金鑰驗證使用者之公開金鑰之真偽，此為[公開金鑰基礎建設 (Public Key Infrastructure)](https://zh.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%87%91%E9%91%B0%E5%9F%BA%E7%A4%8E%E5%BB%BA%E8%A8%AD)。只要憑證仍在期限內，其就保有效力，得以認證使用者之公鑰。

兩密碼系統之特性比較：
| Symmetric Key Cryptosystem | Asymmetric Key Cryptosystem |
|-|-|
| 雙方使用同一套演算法以同一把金鑰進行加密或解密 | 雙方使用同一套演算法以兩把金鑰分別進行加密或解密 |
| 接收方與發送方必須共享這套演算法與金鑰 | 接收方與發送方必須共享這套演算法並各自拿一把金鑰 |
| 這把金鑰必須對外保密 | 發送方的那把金鑰要對外保密 |
| 在不知道金鑰的情形下，對一密文進行解密計算上不可能 | 在不知道保密的那把金鑰的情形下，對一密文進行解密計算上不可能 |
| 在知道演算法與密文的情形下，得知金鑰計算上不可能 | 在知道演算法、密文與公開的那把金鑰的情形下，得知金鑰計算上不可能 |

兩密碼系統之功能比較：
|| 功能 | 優點 | 缺點 |
|-|-|-|-|
| 對稱式金鑰密碼系統 | 1. 保護機密資訊 2. 鑑定收送方之身分 3. 確保資訊完整性 | 1. 速度快 (1000 倍) 2. 秘密金鑰長度短 3. 計算能力弱的機器亦可執行 | 1. 金鑰分配問題 KDP 2. 為能與多人秘密通訊，須保存的金鑰太多 KMP 3. 無法達到不可否認性 |
| 非對稱式金鑰密碼系統 | 1. 保護機密資訊 2. 可做數位簽章 | 1. 簡化金鑰分配與管理 2. 可達到不可否認性 | 1. 速度慢 2. 金鑰長度長 3. 計算能力弱的機器執行吃力 |

兩者優缺點互補，不可相互取代。

#### Diffie-Hellman 公開金鑰分配系統
Diffie 和 Hellman 在 1976 年提出公開金鑰之概念，但僅為金鑰分配系統，而非密碼系統
已知一極大質數 q 與其一原根 $\alpha$。
1. 隨機產生一 $X_A < q$ 為 A 之私鑰。
2. 計算 $Y_A = \alpha^{X_A}\mod{q}$ 為 A 之公鑰，傳送至 B。
3. 隨機產生一 $X_B < q$ 為 B 之私鑰。
4. 計算 $Y_B = \alpha^{X_B}\mod{q}$ 為 B 之公鑰，傳送至 A。
5. B 計算 $K = Y_A^{X_B} = \alpha^{X_AX_B}\mod{q}$，此即為 A、B 共享之秘密金鑰。
6. A 計算 $K = Y_B^{X_A} = \alpha^{X_BX_A}\mod{q}$，此即為 A、B 共享之秘密金鑰。

縱使有人竊聽得知雙方公鑰 $Y_A$、$Y_B$ 也無從得知 $X_A$、$X_B$、或 $K$。

但是，可以透過 man-in-the-middle attack，攔截雙方通訊，替換兩者公鑰為自己的公鑰 $Y_C$，使得 A 所得 K 為 $Y_C^{X_A}\mod{q}$，B 所得 K 為 $Y_C^{X_B}\mod{q}$，而 C 可透過 $Y_A^{X_C}\mod{q}$ 或 $Y_B^{X_C}\mod{q}$ 作為各自的 K 與雙方通訊，對雙方維持正常通訊的假象，但同時完全得知雙方嘗試秘密交換之訊息。

#### 公開金鑰密碼系統之原理
1. 發送方以自身鑰匙圈內收發方之公鑰透過加密演算法 (如：RSA) 加密明文訊息
2. 將密文傳送給接收方
3. 接收方以自己的私鑰透過同一加密演算法解密
4. 得到原始明文訊息

對竊聽者而言，密文與接收方之公鑰已知，所求為明文或接收方之私鑰。

#### 數位簽章系統
1. 發送方以自己的私鑰透過加密演算法 (如：RSA) 加密明文訊息
2. 將密文傳送給接收方
3. 接收方以自身鑰匙圈內收發方之公鑰透過同一加密演算法解密
4. 得到原始明文訊息

對竊聽者而言，密文與發送方之公鑰已知，所求為發送方之私鑰。

思考：若要同時進行，要先加密還是先簽章呢？
答案：先簽章。因為加密只需進行一次，用以安全傳輸，到達目的地後密文型態便不再有用。相反地，驗證會進行很多次，每次進行文件驗證時都需要。因此若先加密後簽章，則每次需要驗證都需要先驗證並解密才能確定該簽章是在驗證什麼文件。反之，先簽章後加密則只需要進行一次解密即可將密文丟棄，並保存明文在每次需要驗證時驗證即可。

### RSA Cryptosystem
RSA 由 Rivest, Shamir, Adleman 於 1978 年提出，為確定式公開金鑰加密法，是現今商業界加密標準。
其困難度根基於 Factorization Problem，即為大數質因數分解之困難性。
1. 隨機取兩極大質數 p、q，得 $n = p \times q$，。
2. 由尤拉定理可得 $\phi(n) = (p - 1) \times (q - 1)$。
3. 隨機取一整數 $e$ 使得 $e$ 與 $\phi(n)$ 互質，且 $e < \phi(n)$，此與 $n$ 即為公鑰。
4. 隨機取一整數 $d$ 使得 $d = e^{-1} \mod{\phi(n)}$ 互質，此即為私鑰。
5. 公開 $e$ 與 $n$，銷毀 $p$ 與 $q$。

則針對一明文 $M < n$ 進行加密，可得
1. $C = M^e \mod{n}$，其中 $C$、$e$、$n$ 皆對外公開。
2. 傳送 $C$ 至接收方。
3. 則因為 $d = e^{-1} \mod{\phi(n)}$，$C^d = M^{ed} = M^{k\phi(n) + 1}$ 明顯可得，又由尤拉公式可得 $M^{k\phi(n)} = 1 \mod{n}$，因此 $C^d = M^{k\phi(n) + 1} = M^1 = M \mod{n}$，接收方便可順利得知 $M$。

因此對於一公鑰 $e$ 與 $n$ 而言，得知 $d$ 需要得知 $\phi(n)$ 並計算 $e^{-1} \mod{n}$，而得知 $\phi(n)$ 需要得知一對質數 $p$ 與 $q$ 使得 $n = p \times q$ 使得 $\phi(n) = (p - 1)\times(q -1)$，即對 $n$ 進行質因數分解。

範例一：針對一密文 $C = 10$，已知公鑰 $e = 5$、$n = 35$，求密鑰 $d$ 與明文 $M$ 為何？
答案：
$\because n = 35 = 5 \times 7\ while\ 5\ and\ 7\ are\ both\ prime\ numbers.$
$\therefore \phi(n) = (5 - 1) \times (7 - 1) = 4 \times 6 = 24$
$\therefore d = e^{-1} \mod{24} = 5^{-1} \mod{24}\ while$
|||5|24|
|-|-|-|-|
|-|24|0|1|
|-|5|1|0|
|4|4|-4|1|
|1|1|5|-1|

$\therefore d = 5$
$\therefore M = C^d = 10^5 \mod{n} = 100000 \mod{35} = 30$

範例二：針對一明文 $M = 19$，已知私鑰 $d = 77$、$n = 119$，求公鑰 $e$ 與簽章 $S$ 為何？
答案：
1. $\because d = 77\ while\ M = 19.$
$\therefore S = M^{d} \mod{n} = 19^{77} = 4^{38} \times 19 = 18^{9} \times 16 \times 19 = 66 \times 86^{4} \times 18 = 117 \times 86 = 66 \mod{119}$
2. $\because n = 119 = 7 \times 17\ while\ 7\ and\ 17\ are\ both\ prime\ numbers.$
$\therefore \phi(n) = (7 - 1) \times (17 - 1) = 6 \times 16 = 96$
$\therefore e = d^{-1} \mod{\phi(n)} = 77^{-1} \mod{96}\ while$

|||77|96|
|-|-|-|-|
|-|96|0|1|
|-|77|1|0|
|1|19|-1|1|
|4|1|5|-4|

$\therefore e = 5$

範例三：已知公鑰 $e = 31$、$n = 3599$，求私鑰 $d$？
答案：
$\because n = 3599 = 3600 - 1 = (60 - 1) \times (60 + 1) = 59 \times 61\ while\ 59\ and\ 61\ are\ both\ prime\ numbers.$
$\therefore \phi(n) = (59 - 1) \times (61 - 1) = 58 \times 60 = 3480$
$\therefore d = e^{-1} \mod{\phi(n)} = 31^{-1} \mod{3480}\ while$

|||31|3480|
|-|-|-|-|
|-|3480|0|1|
|-|31|1|0|
|112|8|-112|1|
|3|7|337|-3|
|1|1|-449|4|

$\therefore e = 3480 - 449 = 3031$

#### One way Hash Function
輸入任意長度的明文 m 於雜湊函數 h，所得固定長度之雜湊值 h(m)，其可視為 m 之摘要 (Digest)，可用於明文之鑑定和簽章上 (Authentication) 以降低加密所輸入之明文長度或驗證所需比較明文長度 (注意非對稱式加密碼執行很慢，任何加速的方案都是必須的)。其著名之例子有：MD5、SHA256。
(其實輸入也是固定長度的，但會經過切割 (segmenting) 與填充 (padding)。)
其條件為：
1. 對任意長度之明文 m，可得固定長度之雜湊值 h(m)。
2. 對任意明文 m，可透過軟體或硬體得出雜湊值 h(m)。
3. 對任意雜湊值 $x$，得出一明文 $m$ 使得 $x = h(m)$ 在計算上不可能。
4. 針對一明文 $m_1$，得出一明文 $m_2$ 使得 $h(m_1) = h(m_2)$ 在計算上不可能。
5. 對任意明文 $m_1$，得出一明文 $m_2$ 使得 $h(m_1) = h(m_2)$ 在計算上不可能。

滿足條件之難度隨 1~5 遞增，而針對其攻擊之難度也隨 1~5 遞減，因此滿足 1~4 者稱作弱雜湊函數 (Weak Hash Function)，滿足 1~5 者稱作強雜湊函數 (Strong Hash Function)。

### ElGamal Cryptosystem
ElGamal 為 SSL 之父 ElGamal 於 1985 年提出，亦可用於加密與簽章，為機率式公開金鑰密碼系統。其困難度根基於 Discrete Logarithm Problem，即離散對數難題，即給定 $Y_B = kg^{X_B} \mod{p}$，求 $X_B = \log{g}{\frac{Y_B}{k}} \mod{p}$ 在計算上不可能。。
已知一大質數 $p$，其原根 $g$。針對一明文 $M$ 進行加密，得：
1. B 產生一亂數 $X_B$，是為其私鑰。
2. B 計算得出 $Y_B = g^{X_B} \mod{p}$，是為其公鑰公開於大眾。
3. A 針對此次傳送產生一亂數 $k$ 使得 $1 < k < (p - 1)$。
4. A 以 B 之公鑰 $Y_B$ 計算得出 $C_1 = g^{k} \mod{p}$ 與 $C_2 = M \times {Y_B}^{k} \mod{p}$，是為密文傳送至 B。
5. B 計算 $C_2 \times {C_1^{X_B}}^{-1} = M \times {Y_B}^{k} \times (g^{kX_B})^{-1} = M \times {g}^{kX_B} \times (g^{kX_B})^{-1} = M \mod{p}$，是以得明文 $M$。

針對一明文 $M$ 進行簽章，得：
1. B 產生一亂數 $X_B$，是為其私鑰。
2. B 計算得出 $Y_B = g^{X_B} \mod{p}$，是為其公鑰公開於大眾。
3. B 針對此次傳送產生一亂數 $k$ 使得 $1 < k < (p - 1)$ 且 $k$ 與 $(p-1)$ 互質。
4. B 以其私鑰 $X_B$ 與明文雜湊值 $h(M)$ 計算得出 $r = g^{k} \mod{p}$ 與 $s = k^{-1} \times (h(M) - {X_B} \times r) \mod{p}$，是為簽章傳送至 A。
6. A 以 B 之公鑰 $Y_B$ 計算 ${Y_B}^r \times r^s = g^{rX_B} \times g^{k \times k^{-1} (h(M) - r{X_B})} = g^{rX_B+h(M)-rX_B} = g^{h(M)} \mod{p}$，將其與明文 $M$ 代入 $g^{h(M)} \mod{p}$ 之結果比較即可驗證。

注意兩者中 $C_1$ 與 $r$ 是相同的值，他們皆是用以傳遞本次傳輸之亂數 $k$ 所用。這也代表密文與簽章皆會與明文相比膨脹至多兩倍；相較之下，RSA 的密文與簽章與明文相比是不太會膨脹的。

#### DSS 數位簽章系統 (Digital Signature Standard)
DSS 為 NIST 於 1991 年公布，採用DSA (Digital Signature Algorithm)，其為 ElGamal 改良而來。
DSS 只能用於簽章。
已知一大質數 $p$ 與 $q$，其中 $q$ 為 $(p - 1)$ 之一質因數，與一數 $g = \alpha^{\frac{p - 1}{q}} \mod{p},\ 1 \leq \alpha \leq (p - 1)$。針對一明文 $M$ 進行簽章，得：
1. B 產生一亂數 $X_B$，是為其私鑰。
2. B 計算得出 $Y_B = g^{X_B} \mod{p}$，是為其公鑰公開於大眾。
3. B 針對此次傳送產生一亂數 $k$ 使得 $1 < k < q$。
4. B 以其私鑰 $X_B$ 與明文雜湊值 $h(M)$ 計算得出 $r = g^{k} \mod{p}$ 與 $s = k^{-1} \times (h(M) + rX_B) \mod{q}$ 是為簽章傳送至 A。
6. A 以 B 之公鑰 $Y_B$ 計算 $g^{s^{-1}h(M)} \times {Y_B}^{rs^{-1}} = g^{s^{-1}h(M)} \times g^{s^{-1}(rX_B)} = g^{k \times (h(M) + rX_B)^{-1} \times (h(M) + rX_B)} = g^k \mod{p}$，若結果等於 $r$ 則驗證成功。

注意 $s < q$，這意味者簽章大小只有 $\abs{p + q}$，而非 ElGamal 的 $\abs{2p}$。

#### 比較
|演算法|加密|簽章|金鑰交換|
|-|-|-|-|
|DH|x|x|v|
|RSA|v|v|v|
|ElGamal|v|v|v|
|DSS|x|v|x|

思考一：針對一 8 GB 之相片，128 bits 之 AES 要加密幾次？
答：$\frac{8 \times 2^{30} \times 8}{2^7} = \frac{2^{36}}{2^7} = 2^{29}$ 次

思考二：針對一 8 GB 之相片，1024 bits 之 RSA 要加密幾次？
答：$\frac{8 \times 2^{30} \times 8}{2^{10}} = \frac{2^{36}}{2^{10}} = 2^{26}$ 次

思考三：針對一 8 GB 之相片，1024 bits 之 AES 混合 1024 bits 之 RSA 要加密幾次？
答：全部以 AES 加密，再以 RSA 加密 session key，得 $\frac{8 \times 2^{30} \times 8}{2^{10}} + 1 = \frac{2^{36}}{2^{7}} + 1 = 2^{29} + 1$ 次

### Elliptic Curve Cryptosystem (ECC)
一個橢圓曲線以兩係數 $a$ 與 $b$ 所定義，而具有兩變數 $x$ 和 $y$，使得 $y^2 = x^3 + ax + b$。
設其上點集合為 $E(a, b)$，則當 $4a^3 + 27b^2 \neq 0$ 時，$E(a, b)$ 會對於加法形成一阿貝爾群。
加法之定義條件如下：
1. 橢圓曲線上任兩點 $P$、$Q$ 之和為 $\overrightarrow{PQ}$ 與橢圓曲線交點以 y 軸對稱點。
2. $O(\infty, \infty)$ 為加法運算之單位元素。
3. 橢圓曲線上之點 $P$ 之兩倍為其在橢圓曲線上之切線與橢圓曲線交點以 $y$ 軸對稱點。
4. 滿足封閉性 $P + Q \in E$。
5. 滿足結合性 $(P + Q) + R = P + (Q + R)$。
6. 滿足單位元素 $P + O = P$ ($\overrightarrow{PO}$ 為垂直線，唯一與橢圓曲線之交點為 $P$ 以 $y$ 軸對稱點)。
7. 滿足反元素 $-P \in E$ 即 $P$ 以 $y$ 軸對稱點。
8. 滿足交換性 $P + Q = Q + P$。

橢圓曲線上任兩點 $P$、$Q$，其和 $R = P + Q= (\Delta^2 - x_P - x_Q,\ -y_P + \Delta(x_P - x_R))$ 其中 $\Delta$ 為 $\overrightarrow{PQ}$ 之斜率；$2P = ((\frac{3{x_P}^2 + a}{2y_P})^2 - 2x_P,\ -y_P + (\frac{3{x_P}^2 + a}{2y_P})(x_P - x_R)))$ 即 $\Delta = (\frac{3{x_P}^2 + a}{2y_P})$。

#### Finite Elliptic Curves
有限橢圓曲線為一般橢圓曲線但其上點皆模一整數。
1. 質數曲線 $E_P(a,\ b)$ 為一 $E(a,\ b) \mod{P}$，其中 $P$ 為一質數，軟體實現較為容易。
2. 二元曲線 $E_{2^m}(a,\ b)$ 為一 $E(a,\ b) \mod{2^m}$，硬體實現較為容易。

有限橢圓曲線上的點加法會造成實際整數數值指數增加，且給定一對 $P$、$Q$ 使得 $Q = kP$，求 $k = \frac{Q}{P}$ 在計算上不可能。

範例一：針對一 $E_{23}(1,\ 1): y^2 = x^3 + x + 1 \mod{23}$，求點 $P(3,\ 10)$ 是否在其上？若是，求 $2P =?$
解：
$\because 10^2 = 100 = 8 = 3^3 + 3 + 1 = 31 \mod{23}$
$\therefore P \in E_{23}(1,\ 1)\ while\ \Delta = \frac{3{x_P}^2 + a}{2y_P} = \frac{28}{20} = \frac{7}{5} = 7 \times 5^{-1} \mod{23},$
|-|-|5|23|
|-|-|-|-|
|-|23|0|1|
|-|5|1|0|
|4|3|-4|1|
|1|2|5|-1|
|1|1|-9|2|

$\therefore \Delta = 7 \times 5^{-1} = 7 \times 14 = 98 = 6 \mod{23}$
$\therefore x_{2P} = \Delta^2 - 2x_P = 36 - 6 = 30 = 7 \mod{23}$
$\ \ \ \ y_{2P} = -y_P+\Delta(x_P-x_R) = -10 + 6 \times (3 - 7) = -10 - 24 = -34 = -11 = 12 \mod{23}$
$\therefore 2P=(7,\ 12)$

範例二：$E_{17}(10, 5)$ 是否形成一加法阿貝爾群？
解：
$\because 4a^3+27b^2 = 4000 + 27 \times 25 = 4000 + \frac{2700}{4} = 4000 + 675 = 4675 = 0 \mod{17}$
$\therefore E_{17}(10, 5)$ 並不形成一加法阿貝爾群。

範例三：針對三點 $P(5,\ 8)$、$Q(3,\ 0)$、$R(0,\ 6)$，求在 $F_{17}$ 上之 $-P$、$-Q$、$-R$。
解：
$-P = (5,\ -8) = (5,\ 9) \mod{17}$
$-Q = (3,\ 0) \mod{17}$
$-R = (0,\ -6) = (0,\ 11) \mod{17}$

範例四：求點 $P(2,\ 0)$ 和 $Q(6,\ 3)$ 是否在 $E_{17}(1,\ 7)$ 上？
$\because E_{17}(1,\ 7):\ y^2 = x^3 + x + 7 \mod{23}\ while$
$\ \ \ \ 2^3 + 2 + 7 = 17 = 0 = 0^2 \mod{17}$
$\ \ \ \ 6^3 + 6 + 7 = 229 = 59 = 8 \neq 3^2 \mod{17}$
$\therefore P \in E_{17}(1,\ 7)\ while\ Q \notin E_{17}(1,\ 7).$

#### ECC Diffie-Hellman (ECDH)
已知一橢圓曲線 $E_q(a,\ b)$，其上一點 $G$ 使得 $nG = O$。
1. A 產生一亂數 $x_A < n$，是為其私鑰。
2. A 計算 $y_A = x_AG$，是為其公鑰公開於眾。
3. B 產生一亂數 $x_B < n$，是為其私鑰。
4. B 計算 $y_B = x_BG$，是為其公鑰公開於眾。
5. B 以 A 之公鑰計算 $K = y_Ax_B = x_Ax_BG$，是為其與 A 之秘密金鑰。
6. A 以 B 之公鑰計算 $K = y_Bx_A = x_Ax_BG$，是為其與 B 之秘密金鑰。

#### ECC Encryption/Decryption
已知一橢圓曲線 $E_q(a,\ b)$，其上一點 $G$ 使得 $nG = O$。
針對一明文 $M$。
1. B 產生一亂數 $x_B < n$，是為其私鑰。
2. B 計算 $y_B = x_BG$，是為其公鑰公開於眾。
3. A 針對此傳送產生一亂數 $k$。
4. A 以 B 之公鑰產生 $C_1=kG$ 與 $C_2=M+ky_B$，是為密文送至 B。
5. B 以其私鑰計算 $C_2 - x_BC_1 = M + ky_B - kx_BG = M + kx_BG - kx_BG = M$ 得明文。

#### Elliptic Curve Digital Signature Algorithm
已知一橢圓曲線 $E_q(a,\ b)$，其上一點 $G$ 使得 $nG = O$。
針對一明文 $M$。
1. B 產生一亂數 $x_B < n$，是為其私鑰。
2. B 計算 $y_B = x_BG$，是為其公鑰公開於眾。
3. B 針對此傳送產生一亂數 $k$。
4. B 計算 $P = kG = (x_P,\ y_P)$，計算 $s = k^{-1}(x_B \times x_P + h(M))$，隨 $M$ 傳送 $x_P$ 與 $s$ 至 A，是為其簽章。
5. A 以簽章計算 $s^{-1}(x_P \times y_B + h(M)G) = kG(x_B \times x_P + h(M))^{-1}(x_B \times x_P + h(M)) = kG = P$，將其 $x$ 座標與 $x_P$ 比對以驗證。

#### ECC Security
1. 根基於橢圓離散對數問題，即求 $k = \frac{Q}{P}$。
2. 相同安全性下，計算所需金鑰大小遠小於 RSA。
3. 相同安全性下，計算略簡於 RSA。

範例：針對一橢圓曲線 $E_{257}(0,\ -4)$，明文 $(112,\ 26)$。已知 B 私鑰為 $x_B = 101$、$G = (2,\ 2)$、$k = 41$，求 B 之公鑰 $y_B$？密文 $C_1$、$C_2$？
解：
$\ \ \ \ y_B = x_BG = 101(2, 2)$
$\ \ \ \ E_{257}(0,\ -4) = x^3 - 4 \mod{257}$
$\ \ \ \ \Delta = \frac{3{x_B}^2 + a}{2y_B} = \frac{12}{4} = 3$
$\ \ \ \ 2G = (\Delta^2 - 2x_G, -y_G + \Delta(x_G - x_{2G})) = (9-4, -2+3(2 - x_{2G})) = (5,\ -2 - 3 \times 3) = (5,\ -11) = (5,\ 246) \mod(257)$
$\ \ \ \ \Delta = \frac{3{x_B}^2 + a}{2y_B} = \frac{75}{492} = 75 \times 492^{-1} \mod{257} = 75 \times 235^{-1} \mod{257}\ while$
|-|-|235|257|
|-|-|-|-|
|-|257|0|1|
|-|235|1|0|
|1|22|-1|1|
|10|15|11|-10|
|1|7|-12|11|
|2|1|35|-32|

$\ \ \ \ \Delta = 75 \times 35 = 2625 = 55 \mod{257}$
$\ \ \ \ 4G = (\Delta^2 - 10, 11 + \Delta(10 - x_{4G})) = (3015, 11-55 \times 3013)) = (188,\ -165704) = (188,\ 61) \mod(257)$
$\ \ \ \ \Delta = \frac{3{x_B}^2 + a}{2y_B} = \frac{106032}{122} = 148 \times 122^{-1} \mod{257}\ while$
|-|-|122|257|
|-|-|-|-|
|-|257|0|1|
|-|122|1|0|
|2|13|-2|1|
|9|5|19|-9|
|2|3|-40|-19|
|1|2|59|10|
|1|1|-99|-29|

$\ \ \ \ \Delta = 148 \times 158 \mod{257} = 254$
$\ \ \ \ 8G = (254^2 - 188, -61 + 254(10 - x_{8G})) = (64328,\ -16339363) = (78, 74) \mod{257}$
$\ \ \ \ \Delta = \frac{3 \times 78^2}{2 \times 74} = 5 \times 148^{-1} \mod{257}$
|-|-|148|257|
|-|-|-|-|
|-|257|0|1|
|-|148|1|0|
|1|109|-1|1|
|2|37|2|-1|
|2|35|-5|3|
|1|2|7|-4|
|17|1|-124|-31|

$\ \ \ \ \Delta = 45$
$\ \ \ \ 16G = (45^2 - 78, -61 + 45(74 - x_{16G})) = (148,\ 207) \mod{257}$
$\ \ \ \ \Delta = \frac{177}{157} \mod{257}$
|-|-|157|257|
|-|-|-|-|
|-|257|0|1|
|-|157|1|0|
|1|100|-1|1|
|1|57|2|-1|
|1|43|-3|2|
|1|14|5|-3|
|3|1|-18|11|

$\ \ \ \ \Delta = 155 \mod{257}$
$\ \ \ \ 32G = (155^2 - 148, -207 + 155(148 - x_{32G})) = (233,\ 18) \mod{257}$
$\ \ \ \ \dots$
$\ \ \ \ 101G = 64G + 32G + 4G + G = (197,\ 167)$
$\ \ \ \ C_1 = kG = 41(2,\ 2) = (136,\ 128)$
$\ \ \ \ C_2 = M + ky_B = (112,\ 26) + 41(197,\ 167) = (246,\ 174)$

## 安全電子郵件系統
PGP (Pretty good Privacy) 為 Phil Zimmermann 於 1991 年發布。
GnuPG (GPG) 具有類似功能但開源。
PGP 有：
1. 採用最佳的演算法。
2. 整合成一般應用軟體並與作業平台無關。
3. 免費
4. 可採購 Via Crypt 版本而應用在商業用途

其特色為：
1. 可在不同的作業平台執行。
2. 植基在有名的演算法上。
3. 提供可選擇及標準方法來加解密檔案，以保障秘密通訊。
4. 非政府機關所發展或控制

使其廣泛流通。

其提供：
1. Authentication
2. Confidentiality
3. Compression
4. E-mail Compatibility
5. Segmentation

### Authentication
1. 發送方以其私鑰 RSA 加密明文雜湊值，隨明文送至接收方。
2. 接收方以發送方的公鑰 RSA 解密明文雜湊值。
3. 接收方計算明文雜湊值與之比較以驗證。

### Confidentiality
1. 發送方以接收方的公鑰 RSA 加密一隨機亂數。
2. 發送方以該隨機亂數 AES 加密明文，隨前步驟密文送至接收方。
3. 接收方以其私鑰 RSA 解密隨機亂數。
4. 接收方以隨機亂數 AES 解密明文。

### Authentication-Confidentiality
1. 發送方以其私鑰 RSA 加密明文雜湊值，將其與明文一同壓縮。
2. 發送方以接收方的公鑰 RSA 加密一隨機亂數。
3. 發送方以該隨機亂數 AES 加密壓縮檔，隨前步驟密文送至接收方。
4. 接收方以其私鑰 RSA 解密隨機亂數。
5. 接收方以隨機亂數 AES 解密壓縮檔並解壓縮。
6. 接收方以發送方的公鑰 RSA 解密明文雜湊值。
7. 接收方計算明文雜湊值與之比較以驗證。

### Compression
壓縮可降低儲存空間與傳送時間。
1. 簽章後壓縮，則只需解壓縮一次將結果存取即可供日後無限次驗證，也無須保存解壓縮軟體。
2. 加密前壓縮，降低加密時間，並增加密碼分析難度。

### Email Compatibility
郵件會被編碼 8 bit 的 stream。但針對有些電子郵件系統只允許傳送 ASCII 字元，PGP 可透過 radix 64 將 8 bit stream 轉成 printable ASCII。
這樣的轉換會使訊息擴增 33%。

### Segmentation-Reassembly
Email 系統通常對郵件大小有所限制，如最大為 50kb，若郵件大於 50kb，則先切割再分批傳送。
PGP 會自動提供 Segmentation 及 Reassemble 的功能

### Cryptographic Keys and Key Rings
PGP 共使用到 4 種金鑰
1. One-time session key
2. Public key
3. Private key
4. Pass phrase

其中 One-time session key 被視為亂數產生。Pass phrase 用以存取 Key Rings。

Key Rings︰
* 用來儲存使用者的公開金鑰對。
* 用來儲存別的使用者的公開金鑰。

因此，上述 Authentication-Confidentiality 完整為：
1. 發送方以自身 ID 與 pass phrase 獲取自己的私鑰。
2. 發送方以其私鑰 RSA 加密明文雜湊值，將其與明文、自身 ID 一同壓縮。
3. 發送方以接收方的 ID 獲取對方的公鑰。
4. 發送方以接收方的公鑰 RSA 加密一隨機亂數。
5. 發送方以該隨機亂數 AES 加密壓縮檔，隨前步驟密文、對方 ID 送至接收方。
6. 接收方以自身 ID 與 pass phrase 獲取自己的私鑰。
7. 接收方以其私鑰 RSA 解密隨機亂數。
8. 接收方以隨機亂數 AES 解密壓縮檔並解壓縮。
9. 接收方以發送方 ID 獲取其公鑰。
10. 接收方以發送方的公鑰 RSA 解密明文雜湊值。
11. 接收方計算明文雜湊值與之比較以驗證。

### 公開金鑰管理問題 (Public key KEY Management Problem)
A 如何得知 B 之公鑰，又如何得知所得知之 B 之公鑰為真？

### 公開金鑰管理方法
1. 透過 A 和 B 都信任之第三者 D 以其私鑰對 B 之公鑰進行簽章，使 A 得以透過 D 之公鑰驗證 B 之公鑰含 D 之背書。
2. 透過一個憑證中心/公開金鑰信任中心/CA 對 B 之公鑰進行認證，使 A 得以透過 CA 獲得其公鑰。

其中 1 為 PGP 之解方。每把公開金鑰都有一個金鑰合法性的欄位及簽章信任欄位，及擁有者信任欄位 (每個欄位內容皆為一個flag byte)。

若單一 A 完全信任之第三者 D 為 B 公鑰進行背書，則 A 相信該公鑰為真 (但不代表 A 信任 B)。

若任一 A 完全信任之第三者 D 皆不為 B 公鑰進行背書，但數位 A 部分信任之第三者為 B 公鑰進行背書，則 A 相信該公鑰為真 (但不代表 A 信任 B)。

若任一 A 完全信任之第三者 D 皆不為 B 公鑰進行背書，且僅一位或沒有 A 部分信任之第三者為 B 公鑰進行背書，則 A 不相信該公鑰為真 (且 A 不信任 B)。

### 其他安全電子郵件系統
* S/MIME: 有成為工業界標準的趨勢。
* PEM: 提供安全的實現方法與觀念。

### Certification Authority (CA)
CA 專門為使用者的公開金鑰做保證，以避免使用者誤拿駭客或錯誤的公開金鑰來當做加密或驗證金鑰。
若 A 相信 $CA_1$，且 $CA_1$ 相信 $CA_2$，且 $CA_3$ 相信 B，則 A 相信 B。

反之，若沒有任何 CA 鏈使得 A 透過其上之數 CA 得以信任尾端之 B，則 A 不信任 B。

### CA 相關企業
* VeriSign
* GCA: 我國政府所使用。
* Hitrust: 我國商業界所使用，採用 VeriSign 之技術。