# 後量子密碼學 01：密碼學的導論
## 對稱式與非對稱式，量子電腦對他們的威脅
在現代通訊與資訊安全中，密碼學主要分為「對稱式」與「非對稱式」兩大類。隨著量子電腦的發展，傳統演算法面臨新挑戰。以下將簡要介紹這兩種密碼學的原理與量子電腦帶來的衝擊。
### 對稱式密碼學（Symmetric Cryptography）
**對稱式密碼學** 指加解密都使用同一把金鑰（key）的演算法。大家熟悉的「凱薩密碼」（Caesar cipher）就是最簡單的例子：雙方約定把英文字母往後推三個位置以產生密文，解密時再把字母往前推回三個位置即能還原原文。
在現代密碼學中，最常見的 AES（Advanced Encryption Standard）就屬於對稱是加密。其安全性主要依賴「金鑰長度」與「演算法設計」的強度。目前，128-bit 或 256-bit 的金鑰長度足以對抗一般的傳統計算攻擊。
然而，量子電腦上的 **Grover 演算法** 可以將金鑰搜尋的時間從 $O(2n)$ 降至 $O(2n/2)$。也就是說，如果原本需要 128-bit 安全性，就可能必須改用 256-bit 的金鑰，才能在量子時代維持同樣等級的安全。**事情並不嚴重，用兩倍長度的密鑰就可以。**
### 非對稱式密碼學（Asymmetric Cryptography）
非對稱式密碼學則使用「公鑰」（Public-key）和「私鑰」（Private key）兩把金鑰：公鑰用於加密或驗證，私鑰用於解密或簽章。常見的演算法包含 **RSA**（依賴大整數質因數分解）和 **ECC**（依賴橢圓曲線離散對數問題）。
量子電腦最具威脅的是 **Shor 演算法**，它能在[多項式時間](https://www.entangletech.tw/lesson/basic-algorithm-05)內完成質因數分解或離散對數計算，進而破解現行的 RSA 與 ECC。這表示只要量子電腦硬體達到足夠規模，現行普遍使用的非對稱式加密就不再安全。因此，密碼學界正在積極研究「後量子密碼學（Post-Quantum Cryptography）」，如晶格密碼學、多元二次密碼學、編碼密碼學、哈希函數簽章等演算法，用以取代或補強現有機制。
## 非對稱式密碼學的兩大應用方向
承上文，後量子密碼學主要的研究對象就是「非對稱式密碼學」，也稱為「公鑰密碼學」。因此我們要對此類的密碼學有更深入的認識。首先，這類非對稱式密碼學分為兩大應用的方向：加密模式（Encryption Mode）與簽章模式（Signature Mode）
### 加密模式（Encryption Mode）
在加密模式下，非對稱式密碼學透過「公鑰加密、私鑰解密」的方式來保護訊息機密性：
1. **公鑰發布（Public Key Distribution）**
每個用戶生成一組公私鑰對並公開公鑰，任何人都能取得這個公鑰。
2. **訊息加密（Encryption）**
傳送者（Sender）使用接收者的公鑰進行加密，產生密文。由於公鑰是公開的，任何人都能加密，但只能由對應私鑰持有者解密。
3. **訊息解密（Decryption）**
接收者（Receiver）使用自己的私鑰解開密文還原原始訊息。私鑰必須妥善保管、不對外公開。
#### 實務運用：混合加密（Hybrid Encryption）
實務上，常用「混合加密」：先用非對稱加密安全地傳送一次性金鑰（Session Key），再用對稱式加密（如 AES）快速加密大量資料。這結合了「公鑰系統的便利性」與「對稱加密的高效率」，被廣泛應用在 HTTPS、SSH、PGP 等安全通訊協定中。
### 簽章模式（Signature Mode）
簽章模式主要用於驗證訊息的真實性與完整性，並確保發送者身份，作法在公私鑰的使用上與加密模式相反：
1. **私鑰簽章（Signing with Private Key）**
發送者（Signer）使用私鑰對訊息做「數位簽章（Digital Signature）」。此簽章依賴訊息內容與私鑰，若訊息被竄改，原先的簽章即失效。
2. **公鑰驗證（Verification with Public Key）**
接收者（Verifier）或任何第三方使用對應的公鑰來驗證該簽章，藉此確認訊息完整性與簽章者身份。
#### 常見應用範例
- **電子合約與公文簽署**：可確保線上簽約的可靠性與不可否認性。
- **程式碼簽章**：開發者使用私鑰對程式碼簽章，使用者可用公鑰驗證其真實性。
- **電子郵件安全**：透過簽章驗證寄件人身份，並防止內容被竄改。
## 閱讀測驗
下列有關「簽章模式」的敘述，何者為真？
A. 使用公鑰進行數位簽章，只有私鑰持有者能驗證。
B. 使用私鑰進行數位簽章，驗證時需要對應的公鑰。
C. 數位簽章可以確保訊息的機密性與隱密性。
D. 如果訊息被修改，仍可用同一個簽章通過公鑰驗證。
下列哪一項敘述正確描述量子電腦對非對稱式密碼學的影響？
A. 若量子電腦足夠強大，便可依靠 Grover 演算法瞬間破解 RSA。
B. Shor 演算法可以在多項式時間內解決質因數分解問題，從而威脅 RSA。
C. 對於 RSA 與 ECC 而言，只要將金鑰長度增加一倍，就能完全免疫量子攻擊。
D. 量子電腦只對對稱式加密構成威脅，與非對稱式加密無關。
