# 第一章
## 密碼學基本目標
* Confidentiality: 只有傳送訊息的雙方可以知道訊息內容
* Integrity: 訊息不應該被修改
* Authentication: 訊息應該真的來自真正的發送者
* Non-repudiation: 發送訊息者不能否認送過的訊息

## 名詞介紹
* plaintext (m): 待加密的訊息
* 加解密
* encryption: 加密, c = $e_{k1}$( m )
* decryption: 解密, m = $d_{k2}$( c )
* k1, k2 是 key, 依照加密種類可以進一步分成
* k1 = k2: Symmetric cipher, 對稱式金鑰
* k1 != k2: Asymmetirc cipher, 非對稱式金鑰
* crypto-system: (P, C, K, E, D)
* P: plaintexts, 代表待加密的訊息，又稱為明文
* C: ciphertexts, 代表加密後的訊息，又稱為密文
* K: key space, 代表可能 key 的集合
* E: 加密函數，必須是一對一的
* D: 解密函數

## Symmeric cipher (重要)
* 雙方取得 key 的方式
* Pre-shared: 在交換訊息前就預先建立好 (如手動等)
* Out-of-band channel: 透過其他溝通管道分享 key
* Key establishment: 透過安全協議協商出一個臨時 key
* key transport: 訊息傳輸的某方自行生成出 key，並安全的傳給另一方
* key agreement: 用訊息傳輸雙方的參數，共同生成 key

## 加密演算法設計原則
* Diffusion: 讓一個明文字元的改動，影響密文中多個字元
* Confusion: 讓 key 的每一字元，影響密文的方式是非線性且不可預測的

## Asymmetric cipher
* public-key crypto system: 將 key 進一步分成 public key, private key，這樣一來便可以解決 Symmeric cipher 雙方如何預先取得 key 的問題
* 如 RSA 加密演算法
* 問題: 如何得知 public key 的真實性 -> 數位憑證

## Block or stream cipher
* Block cipher: 一次處理固定長度的明文字元或位元 block
* Stream cipher: 一次處理一個明文字元或位元

## 確認訊息是否被篡改 (重要)
### Message Authentication Code (MAC)
* 發送方傳送訊息時，會使用密鑰計算出 MAC
* 接收方收到訊息後，可以使用相同的密鑰重新計算 MAC，並比對兩者是否一致
* 使用對稱式金鑰
* 只有接收方可以驗證訊息正確性

### Signature Scheme (數位簽章)
* 訊息發送者使用 private key 製作出簽名
* 這個簽名可以被訊息發送者的 public key 來驗證
* 使用非對稱式金鑰
* 全世界的人皆可以驗證訊息正確性

### Cryptographic Hash function
* 為了解決訊息過大，導致前述兩種方法跑太久的問題
* 此技術可以將原始訊息，縮減成一個長度短、看起來隨機、固定長度的摘要
* 如此一來，訊息發送者便只需要針對摘要簽名即可

## 基於密碼學的攻擊手段 (重要)
* Known ciphertext attack (已知密文攻擊): 攻擊者在只知道密文的情況下嘗試攻擊
* Known plaintext attack (已知明文攻擊): 攻擊者在知道密文及部分明文的情況下嘗試攻擊
* 在某些情況下，傳輸或協定的部分內容是固定 (已知) 的，例如壓縮檔開頭、協定 header 等等，攻擊者可能有機會利用這些資訊搭配密文反推出 key
* Chosen ciphertext attack: 攻擊者可以自己選一段密文，然後請解密者幫他解密，獲得對應的明文
* Chosen plaintext attack: 攻擊者可以自己選一段明文，然後請加密者幫他加密，獲得對應的密文

## 常見攻擊手段簡介 (重要)
1. Eavesdropping（竊聽）: 攻擊者攔截訊息，窺探通訊內容 (無論是明文還是密文)

2. Modification（篡改）: 攻擊者在訊息傳輸過程中，修改傳送的內容，使接收方收到被篡改過的訊息

3. Replay（重放攻擊）: 攻擊者紀錄已經傳送過的訊息，並在稍後將這些信息重放，目的是欺騙系統或造成不正當行為（如重複發送支付指令）

4. Preplay（預演攻擊）: 攻擊者在協議實際運行之前，就參與並進行一次協議運行，收集有用信息或者欺騙某些驗證過程

5. Reflection（反射攻擊）: 攻擊者將訊息反射回發送者，讓發送者認為消息來自於正當的接收者，並且可能觸發錯誤的行為。

6. Denial of Service (DoS)（拒絕服務攻擊）: 攻擊者透過手段阻止正常使用者使用服務。例如對 server 的過載攻擊等

7. Typing Attacks（類型攻擊）: 攻擊者替換訊息中某個字段的類型，可能破壞協議的正確性或導致錯誤的解釋

8. Crypt-analysis（密碼分析）: 攻擊者從協議中獲得一些有用的信息用於進行密碼學分析。可能幫助攻擊者破解加密內容或尋找弱點

9. Certificate Manipulation（證書篡改）: 攻擊者選擇或修改證書中的信息進行攻擊，使得攻擊者得以偽造身份或篡改身份驗證的過程

10. Protocol Interaction（協議交互）: 利用已知協議的漏洞，或強行將一個協議與另一個不相關的協議結合，造成系統漏洞

## Security level (重要)
* Computational security: 安全性依賴於攻擊者計算能力的限制
* Provable security: 破解加密系統可以在理論計算複雜度的框架下，歸約為解決某些困難的數學問題
* Unconditional security: 無論攻擊者擁有多強的計算能力，都無法破解系統，因為攻擊者根本無法獲得足夠資訊

* 其他需要考慮的 factor
* Implementation issue: 實作失誤導致程式碼中的 bug
* Side-channel attack: 透過觀察系統的物理特性或行為來推測敏感資訊。如運行時間、功耗變化等等

* 補充: 使用未被公開的加密演算法會十分危險
* 不公開代表缺乏世界頂尖的數學家和安全研究者分析與檢查，一個好的加密演算法不應依賴秘密性

## Perfect Secrecy (完全保密性) (重要)
* 即使攻擊者知道密文 （ciphertext） y，他仍然完全無法得知原始明文 （plaintext） x 的任何資訊
* 精確的說，給定密文 y，明文 x 的機率分佈沒有改變
* 範例: shift cipher
* 針對明文中的每個字元，都使用一個新的 random key 來決定偏移值 (key 長度跟明文相同)
* 因為只要使用不同的 key，每個密文都可對應到所有可能的明文，故攻擊者無法從密文學到任何明文的資訊
* 範例: One-Time Pad (OTP)
* 針對明文中的每個字元，都使用一個新的 random key (key 長度跟明文相同)
* 加密時，將明文與 key 對應位置分別進行 XOR 操作
* 解密時，將密文與 key 對應位置分別進行 XOR 操作
* 因為只要使用不同的 key，每個密文都可對應到所有可能的明文，故攻擊者無法從密文學到任何明文的資訊
* PKC (public-key 加密系統) 沒有 perfect secrecy
* 攻擊者拿到密文後，可以嘗試隨機的拿一些可能的明文，並利用 public key 進行加密
* 這樣至少可以排除掉一些明文的可能性，故不具備 perfect secrecy

## entropy
* entropy 用於衡量隨機性，entropy 越高，表示更難猜測；最大 entropy 發生在完全隨機的情況
* 多個 plaintext 使用同一金鑰加密，攻擊者能累積資訊，降低 entropy，提升攻擊成功率
* 對於兩個獨立的隨機變數 X, Y，union entropy 至少是個別 entropy 的總和
* 由於自然語言是非隨機的，故其 entropy 會比較低
* 虛假密鑰 (Spurious Keys): 表示那些錯誤但看似合理的 key
* 假設密文是 wnajw，解密後可能得到以下兩個有意義的明文：
river（密鑰 = 5）
arena（密鑰 = 22）
其中一個是正確答案，另一個是虛假密鑰。攻擊者即使成功解出一個看似正確的明文，也不一定能保證是真正的明文
* Unicity Distance: 是指使得虛假密鑰數量變為 0 所需的最小密文長度；因為當密文足夠長，語言的冗餘度會自然排除不合理的明文

## 模除相關加密演算法簡介
### Shift Cipher
* 即凱薩密碼

### Substitution Cipher (重要)
* 將字母表打亂，對應到一個隨機排列 (如 A 對應至 H, B 對應至 A 等等)
* 缺點: 容易受到頻率攻擊，因為某些英文字母出現頻率高

# 第二章: Block ciphers and stream ciphers
## substitution and permutation network (SPN 架構)
* 透過主金鑰 K 生成一系列的 round keys，每個 round key 都用於一次加密，加密有多輪
* 加密分成三種類型
* XOR 運算
* 代換 (S-box): 把輸入的位元組透過一個固定的對應關係轉換成另一組位元
* 置換 (P-box): 重新排列位元順序

## DES
* 基於 Feistel Cipher Scheme (FCS) 架構
* 由於 key 的長度只有 56 個 bit，非常容易被現代電腦破解，現今已不再使用
* 急救方案: 3DES/2，透過兩個 key、連續三次 DES 加解密操作，來防止暴力破解

## AES
* 為一種區塊加密演算法，區塊大小為 16 bytes (128 bits)，並以 4 x 4 的矩陣呈現
* 非 Feistel Cipher Scheme (FCS) 架構
* 加密與解密流程 相似但不完全對稱
* key lengths 有 128, 192, 256 bits 三種
* 至今無已知高效攻擊
* 子操作分成四個
* SubBytes：非線性代換，提供混淆 (confusion)。
* ShiftRows：線性代換，行位移，擴散行內 byte。
* MixColumns：線性代換，列混合，擴散列內 byte。
* AddRoundKey：XOR 密鑰，直接影響狀態矩陣。

* AES-128 共會分成 10 個 round，每個 round 執行一些子操作來進行加密
* AES 的 key 會經過特殊的演算法，拆分成 44 byte 的 W (subkeys) 供加密使用

## Modes of Operations (重要)
* 由於 AES 一次只能加密一個 block，故需要用以下的 Modes of Operations 方法來搭配，處理需要加密許多 block 的情況

### Electronic-Codebook Mode (ECB)
* 最簡單的區塊加密模式之一
* 每個明文區塊獨立加解密，完全不會考慮其他區塊
* 缺點: 重複的明文區塊，將被加密成一模一樣的密文區塊，攻擊者可以從中獲取有用訊息

### Cipher-Block-Chaining Mode (CBC)
* 較安全的區塊加密模式
* 每一個明文區塊在加密時都不僅僅依賴於 key，還會依賴上一個密文區塊
* 加密步驟:
* 首先準備一個隨機初始向量 (IV)，代表初始密文區塊 (可以確保每次的加密結果都不相同)
* 針對每個待加密的明文區塊，先將上一個密文區塊和當前明文區塊做 XOR，接著將結果通過 key 進行加密，生成當前密文區塊
* 解密步驟:
* 透過 key 解密當前密文區塊，然後將解密的結果與上一個密文區塊進行 XOR，得到明文區塊
* 若 plainText 並非 block 大小的倍數，則需要填充 (Padding)


### Cipher-Feedback Mode (CFB)
* 是一種能將區塊加密算法轉換為流 (stream) 加密算法的方法
* 可以自由選擇一次要加密的 bits 數量
* 與 CBC 類似，不過改成透過將上一步的密文逐步傳遞給加密演算法，得到加密流
* 會將密文加入到加密過程中來影響下一輪的加密 （即加密輸入包含當前的密文）

### Output-Feedback Mode (OFB)
* 同樣是一種能將區塊加密算法轉換為流 (stream) 加密算法的方法
* 與 CFB 最大的不同是，一旦密文中某個區塊發生錯誤，這個錯誤只會影響當前的明文區塊和密文對應的區塊，對後續的解密不會有影響
* 適用於錯誤較多的網路環境等


### Counter Mode (CTR)
* 同樣是一種能將區塊加密算法轉換為流 (stream) 加密算法的方法
* 透過加密一個不斷遞增的計數器，並將加密後的值與明文進行 XOR 來實現高效的加密


### (第三章) Galois Counter Mode (GCM)
* 上述提到的 Modes of Operations 皆無法檢查資料是否篡改
* 基於 CTR，但新增了驗證標籤 (Auth Tag) 機制防止被篡改


#### Padding Oracle Attack
* 可以透過篡改密文，結合伺服器回應的填充錯誤訊息，一個 byte 一個 byte 地解密密文

## Stream Ciphers (重要)
* 雖然任何區塊加密演算法都可以通過如 CFB 或 OFB 等模式轉換為流加密演算法，但通常會帶來額外的計算開銷
* 以下討論輕量級的流加密演算法
* 比較:
* Stream Ciphers 逐個產生 key string，並與欲加密的訊息結合
* 與 block Cipher 不同的是，Stream Ciphers 逐個 bit 或 byte 的加密資料，速度較快

問題:
* 訊息的發送者與接收者共享一個相同的 key，並使用相同的初始向量（IV），搭配 pseudo-random number generator 來生成相同的 key stream

### PRNG (偽隨機數生成器) (重要)
根據一個初始種子值（seed），透過遞迴公式生成一系列偽隨機數

已知明文攻擊 (Known plaintext attack): 若是已知明文的前幾個，便有辦法反推出前 300 位元的 key stream，進而可能計算出全部的 key stream

#### LFSR
* 是一種 PRNG 的實作方法
* 透過多個 Flip-Flops，來生成一串位元。這些 Flip-Flops 的輸出會經過某些數學運算，並被用來決定下一個輸出的位元
* 缺點: 生成的序列終究會重複，如此一來可能會被攻擊


#### ChaCha20
* 同樣是一種 PRNG 的實作方法
* 初始種子（包括密鑰、計數器、隨機數等）生成一個密鑰流
* 核心運算是 quarter-round (QR)

# 第三章 Hash functions and message authentication
* Hash functions 著重在對訊息做摘要的應用

## Data Authentication
* 最簡單但不太好的實作方法
* 訊息發送者在發送訊息 M 時，連帶發送 C = $E_k(M)$，C 用來給訊息接收者驗證訊息是否有被篡改，$E_k$ 是透過加密演算法 E 以及 key k 進行加密
* 訊息接收者使用同樣的 key k 解密 C 後，若與 M 相符則代表訊息未被篡改
* 缺點: 用於驗證的資訊未被濃縮，空間利用效率不高
* Digital Fingerprint: 不需要 key 的摘要方式
* message authentication code (MAC): 需要 key 的摘要方式
* Keyed-hash message authentication code (HMAC): 結合 Hash function 跟 key 的摘要方式

## Hash function 設計原則 (重要)
### Pre-image Resistance
計算一個字串的 Hash value 很容易，但從 Hash value 回推出原始字串非常困難

### Computational Uniqueness
* 又可以細分為
* Second pre-image resistance: 給定一個字串 𝑥，找到另一個不同的字串 𝑦 使得 H(𝑥) = H(𝑦) 非常困難 (Intractable)
* Collision resistance: 找到任意兩個字串 𝑥、𝑦 使得 H(𝑥) = H(𝑦) 非常困難 (Intractable)

Collision resistance 突破難度較低，因為從計算複查度上來說，Collision resistance 可能的情況較少

## MD4 family (MD5, SHA-1, SHA-2)

### 基本架構
* 輸入的訊息被分割成固定大小的區塊 M（以 SHA-512 來說，每個區塊 1024 bits）
* 當輸入不是 1024 的倍數時，
* IV 代表初始向量，根據質數的平方根的小數部分設計
* 每個區塊 M 經過一個壓縮函數 𝐹 的處理，並將處理結果與 H 相加 (進位超過的部分直接捨棄)
* F 的原理待補充

## SHA-3 (重要)
* 作為 SHA-2 的替代方案，SHA-3 相較於 SHA-2 最大的優勢在於
* 支援生成任意長度的 message digest
* 使用了 Sponge Construction，安全性高

### 基本架構
* 整體為 Sponge Construction (海綿結構)，分為兩大階段
* Absorbing: 吸收訊息，混進內部結構
* Squeezing: 壓出結果，直到取得所需輸出

## 基於 Hash 的攻防 (重要)
### Birthday Attack Basics
* 在一個人數較少的群體中，兩人擁有相同生日的概率遠高於直覺預期
* 假設 hash function 的輸出長度是 L 位，根據 Birthday Attack，暴力破解，找到兩組一模一樣的 hash value 的複雜度上限並非是 $2^L$，而是 $2^{L/2}$

### Set Intersection Attack

### TupleHash

### Password Hashing (重要)
* 最基本的密碼驗證機制在密碼儲存時，實際上儲存的是 Hash 後的結果；當 H(input password) = H(registered password) 時，便通過密碼驗證
* 由於相同的密碼會產生相同的 hash 結果，可能會導致一些安全性問題
* 解決方法: 加入 salt value 機制: H(input password,salt) = H(registered password,salt) 時才算做通過密碼驗證，其中 salt value 是一段與該使用者密碼綁定的隨機字串
* 適用於密碼 hash 的 hash function 設計原則:
1. 結合 salt value 機制，避免相同密碼，相同 hash value 的問題
2. 不要太快就能得出 hash 後的結果，增加攻擊者的破解時間

## MAC
### CBC-MAC
* 依賴區塊加密演算法的 MAC
* 演算法流程：
假設：
- 訊息 M 被切割成 n 個 64 位元區塊：M = M1, M2, ..., Mn
- k: 加密金鑰
- E: 加密算法（例如 AES 或 DES）
- IV: 初始化向量

計算過程：
1. 初始加密：
C₁ = Eₖ(M₁ ⊕ IV)

2. 鏈結加密：
對於第 i 個區塊：
Cᵢ = Eₖ(Mᵢ ⊕ Cᵢ₋₁)

最後一個加密區塊 Cₙ 就是 MAC

### HMAC

### Authenticated Encryption (MAC 用法)
1. MAC-and-encrypt
* 先對原始訊息計算 MAC，得到 hk₁(M)
* 接著對原始訊息加密，得到 ek₂(M)
* 訊息發送者會同時發送 hk₁(M) 以及 ek₂(M)
3. MAC-then-encrypt
* 先對原始訊息計算 MAC，得到 hk₁(M)
* 將原始訊息與 MAC 串接在一起，得到 M ∥ hk₁(M)
* 接著對串接後的訊息加密，得到 ek₂(M ∥ hk₁(M))
* 訊息發送者發送 ek₂(M ∥ hk₁(M))
5. Encrypt-then-MAC（best）
* 先對原始訊息加密，得到 ek₂(M)
* 接著對原始訊息計算 MAC，得到 hk₁(ek₂(M))
* 訊息發送者會同時發送 ek₂(M) 以及 hk₁(ek₂(M))

# 第四章 Public-Key Cryptography
## PKC (Public-Key Cryptography) 的主要功能 (重要)
* Key Establishment: 用於在不安全的通訊通道上溝通
* Non-repudiation: 確保訊息發送者無法否認他們曾經發送過的訊息
* 是數位簽章的重要特性
* Identification: 身份驗證，確保通訊雙方的身份是真實的
* Encryption: 加密
* 一般來說，不建議用 PKC 加密整個 session 的內容
* 公開金鑰加密計算成本高，非常耗時，對即時通訊系統來說不實用
* 很難在大規模系統中為每個使用者維護 private key 跟 public key
* PKC 本身是設計用來加密小資料的，並不適合直接加密整個 session 的內容

## PKC 應具備性質
* Forward Efficiency: 加密跟解密計算量不能過大
* Backward intractability: 僅憑加密後的密文以及 public key，無法回推出 private key
* Commutability (可選): 可使用 public key 加密、private key 解密；也可使用 private key 加密、public key 解密

## PKC-based key exchanged 流程
* 假設訊息溝通雙方為 Alice 及 Bob
* 整體流程:
* Alice 選擇一個 privacy key x1, 並生成 y1，接著將 y1 傳給 Bob
* Bob 選擇一個 privacy key x2, 並生成 y2，接著將 y2 傳給 Bob
* Alice 使用自己的 privacy key x1 跟 Bob 的 public key y2，生成 key K
* Bob 使用自己的 privacy key x2 跟 Alice 的 public key y2，生成 key K
* 由於交換性質，雙方的 key K 相同，完成 key 交換

## PKC 依賴的數學難題 (重要)
* 以下的數學難題提供了單向函數（容易計算但難以逆推）的數學基礎
1. Integer-factorization schemes: 大整數的質因數分解
* 一個超大的整數 n = p*q (p、q 是質數)
* 挑兩個質數計算 p*q 很容易，但從 n 回推 p 跟 q 非常困難
* **RSA 加密的核心依賴**
2. Discrete Logarithm Schemes: 離散對數問題
* y = $g^x$ % p
* g 是公開的基數
* p 是質數
* (g^x 不是一般的冪次，而是代表 "群中的重複運算"。但在乘法群中，則剛好為冪次)
* 給定 g, x, p，很容易計算出 y；但從 g, y, p 回推 x 非常困難
* Diffie-Hellman key exchange 的核心依賴
3. Elliptic Curve Cryptography: 橢圓曲線密碼學
* 基於橢圓曲線，同樣屬於一種廣義的離散對數問題
* 描述由橢圓曲線整數點及 O 構成的加法群中，使得 dP (d 倍的特定點 P) = T (另一個特定點) 的 d 是多少
* ECDH 的核心依賴

## RSA
### 前情提要: ϕ (重要)
* 對於某個數字 m, ϕ(m) 指的是從 1 到 m 中，有多少個整數與 m 互質
* 計算:
* 1. 值因數分解: m = p₁^e₁ × p₂^e₂ × ... × pₙ^eₙ
* 2. 套公式: ϕ(m) = m × Π (1 - 1/pᵢ)

### 前情提要: 費馬小定理 (重要)
* 如果 p 是質數，且 a 不是 p 的倍數，則

### RSA 加密流程 (重要)
* private key 為 (p, q, d)
* public key 為 (n, e)
* 準備步驟:
1. 選擇 p 跟 q
2. 計算 n = p * q
3. 計算 φ(n) = (p-1) * (q-1)
4. 選擇 e，e 必須跟 φ(n) 互質
5. 計算 d，使得 e * d ≡ 1(mod φ(n))
6. 以上五步，便可準備完成 private key 跟 public key
* 加密步驟:
1. 選擇明文 x
2. 密文 C = $x^e$ mod n
* 解密步驟:
1. 收到密文 C
2. 解密後的密文 x = $C^d$ mod n

### RSA padding
* 在實務上為了避免攻擊者透過觀察密文來推測原始訊息，在進行 RSA 加密前，會使用隨機的 seed 隱藏明文內容

規則:

### 如何找出大質數? Miller-Rabin 大數質數判定 (重要)
* 基於費馬小定理，若 p 是質數，則任意小於 p 的測試底數 a 將會滿足$a^{p−1} ≡ 1 (mod \ p)$
* 是一種基於隨機性的質數測試演算法，經過不同底數的多次測試後，錯誤率可以降得很低，但仍可能會出錯

規則:
判定 n 是否為質數

補充:
在 1 到 N 中，大約有 N / ln(N) 個質數

### RSA 的 Malleability (可塑性) (重要)
* RSA 是一個可篡改的加密算法
* 攻擊者可以對密文進行篡改，使得解密後得到的明文可預測的改變
1. 攻擊者可以選擇一個數字 s，並將密文 y 篡改為新的密文 $y' = s^e * y$
2. 接收者解密篡改後的密文: $(y')^d ≡ (s^ey)^d ≡ (s^ex^e)^d ≡ sx \ mod \ n$
3. 解密後的結果與原始明文相比，受到可預測的篡改

### RSA Parameter Attacks
#### Timing Attacks
* 利用計算快速冪時，bit 為 0 跟 為 1 時的計算量不同，透過執行時間推測 1 的數量，進一步減少計算複雜度

#### 已知 d 的攻擊
* 若 RSA privacy key 中的 d 意外洩漏，攻擊者可以透過隨機演算法在合理時間內計算出 p, q

#### 其他攻擊
* 當 RSA 中的 p, q 太接近，或是 e 太小時，安全性會降低

### Small Exponent Attacks
* 當挑選的 e 太小時，可能會遇到的攻擊
* 攻擊流程:
1. Alice 和 Bob 分別有自己的 RSA public key
* Alice: kA = (e, nA), e=2 (很小)
* Bob: kB = (e, nB), e=2 (很小)
2. 第三者分別使用 Alice 和 Bob 的 RSA public key 加密相同的明文 M
* CA = M^2 mod nA
* CB = M^2 mod nB
3. 攻擊者攔截 CA 和 CB，並透過中國餘數定理得到 x0 $(x0 = M^2 \ mod \ n, n=nAnB)$
4. 如果 M 比 √n 小，則攻擊者可以藉此找出原始明文 M

### Multiplicative Attack
* 若明文 M 是兩個相近整數的乘積，則可能會被此種方法攻擊
* 攻擊流程:
1. 建立兩個陣列
* $A[x] = C \ × \ x^{–e} \ mod \ n$
* $B[y] = y^e \ mod \ n$
2. 若存在某組 (x, y) 使得 $C \ × \ x^{–e} ≡ y^e \ mod \ n$，則明文 M 便是這對 (x, y) 的乘積

防禦方法: 擾亂明文結構，例如加入 padding 等等

## Diffie-Hellman Key Exchange
* PCK-base key Exchange 的實作方式之一

規則:
1. 選擇一個大質數 p 和一個生成元 a (皆可公開)
1. 每一方各自選擇一個私有金鑰 x 和 y (各自保密)。
1. 第一方計算 $Y_a$ = a^x mod p，第二方計算 $Y_b$ a^y mod p，然後彼此交換這些結果 (公開交換)。
1. 每方用對方的公開金鑰和自己的私有金鑰計算：
- 第一方計算 (a^y mod p)^x mod p
- 第二方計算 (a^x mod p)^y mod p

由於數學特性，兩方得到的結果相同，即生成了共享的密鑰

缺點: 無法驗證雙方的身份，故可能發生 man-in-the-middle attack

本演算法基於 Discrete logarithm problem
* 在特殊情況下，以下的演算法可以有限度的處理
* Shanks’ algorithm
* Index calculus algorithm

## Elgamal encryption scheme
* Bob 生成一組公私鑰。其他人 (如 Alice) 將訊息用 Bob 的公鑰加密後，傳給 Bob
* 只有 Bob 可以解密

規則:

## Elliptic Curve Cryptography
### Elliptic Curve 性質
* 在滿足 $y^2 ≡ (x^3 + ax + b) mod \ p$ ($且4a^3 + 27b^2 不等於 0$)所有的整數點 (x, y) 以及一個特殊的無窮遠點 O，可以組成一個 "加法群"，群至少需滿足封閉性、結合律、單位元、逆元
* 封閉性: 群中的元素相加後仍在群中，相加有特定規則，需分 case 討論
* 結合律: 運算順序不影響結果
* 單位元: 存在單位元 O 使得任何群中的元素 a 來說，a+O=O+a=a
* 逆元: 對於任何群中的元素 a 來說，都存在逆元 $a^{-1}$ 使得 a+$a^{-1}$=$a^{-1}$+a=O
* 此外，這個群還滿足交換律，故又被稱為阿貝爾群
* 該橢圓曲線的點數量約為 p+1 個，故可以透過控制 p 這個質數來決定安全性

補充: GF(n) 表示一個只包含 0~n-1 元素的群，且每個運算後都需要模除 n

### ECDLP
給定 P 和 T，求一個整數 d，使得

dP = P + P + ⋯ + P (d 次) = T

其中：
- P 是已知的 Base point（通常是固定選擇的）。
- T 是已知的某個曲線上的點。
- d 是未知的整數，我們要找到它。

由於可能的點數受 p 控制，通常至少有 $2^{160}$ 個，故無法輕易的暴力解

### 實務應用: Curve25519
* 曲線方程: $y^2 = x^3 + 486662x^2 + x (mod 2^255 - 19)$
* Base point: P = (9, y)

### 實務應用: ECIES
* 透過 Elliptic Curve Cryptography 實現 key exchange，使雙方擁有共同的 key 用於加解密
* 透過計算 MAC 確保訊息未被篡改

# 第五章 Digital Signature
## 數位簽章基本流程
* 發送者：
* 對訊息做 Hash，產生摘要
* 用自己的 private key 對摘要進行簽章 → 得到「數位簽章」
* 把「原始訊息 + 數位簽章」一起送出去
* 接收者：
* 用 Alice 的 public key 對簽章驗證，會得到摘要 A
* 同時自己對收到的訊息做 Hash，得到摘要 B
* 比較摘要 A 和摘要 B 是否相同

## 數位簽章簡介 (重要)
數位簽章的主要作用是：

1. 身份驗證 (Authentication)：確認發送者的身份，保證訊息來自於正確的發送者
* 由於數位簽章是用訊息發送者的 private key 簽的，並由訊息接收者用訊息發送者的 public key 進行驗證。若驗證成功的話，因為只有訊息發送者的 private key 能產生這個簽章，故可以確認發送者的身份

2. 訊息完整性 (Integrity)：確保數位訊息在傳輸過程中沒有被篡改
* 由於數位簽章是用訊息發送者的 private key 簽的，並由訊息接收者用 public key 進行驗證。若驗證成功的話，代表自己收到的那份訊息就是當初訊息發送者用來產生數位簽章的那份，未被篡改

3. 不可否認性 (Non-repudiation)：一旦訊息被數位簽章簽署，發送者無法否認已經發送該訊息。
* 由於數位簽章是用訊息發送者的 private key 簽的，並由訊息接收者用 public key 進行驗證。若驗證成功的話，代表這份訊息確實是由訊息發送者所發送，因為只有訊息發送者能簽出能成功驗證的數位簽章

## 基於 RSA 的數位簽章 (實務上不常用)

## 基於數位簽章的攻擊類型 (依攻擊者擁有的資訊分類)
1. Public Key-only Attack: 攻擊者只擁有訊息發送者的 public key 跟 vertification function
2. Known Message Attack: 攻擊者擁有訊息發送者簽過的一系列訊息
3. Chosen Message Attack: 攻擊者可以要求訊息發送者為一系列的訊息進行簽章並提供這些資訊

## 基於數位簽章的攻擊類型 (依攻擊結果分類)
1. Total Break: 攻擊者能成功計算出 private key
2. Selective Forgery: 針對指定的訊息，攻擊者能成功創建出一個簽章
3. Existential Forgery: 攻擊者能至少成功創建出一個簽章 (不針對指定訊息，只要對任意訊息成功創建出簽章都算攻擊成功)

## ElGamal signature scheme (基於離散對數問題的數位簽章)
* 參數設定
* 質數 p：一個大質數。
* 生成元 α：是 p 的一個特殊數字，用來生成公開金鑰。
* 私鑰 a：由簽名者持有，這是簽名的秘密密鑰。
* 公開金鑰 β：由簽名者計算，β = α^a mod p，並公佈給所有人。
* 簽名生成（簽名者如何簽署 message x）
1. 選擇一個隨機數 k：簽名者隨機選擇一個數字 k （k 必須與 p−1 互質）
2. 計算兩個值 γ 和 δ：
* γ = α^k mod p
* δ = (x − a ⋅ γ) ⋅ k^−1 mod (p−1)，這裡 k^−1 是 k 在模 (p−1) 下的逆元素。
3. 簽名即為數對 (γ, δ)。
* 簽名驗證（其他人如何驗證簽名）
* 假設驗證者擁有公開金鑰 (α, β) 和message x，還有簽名 (γ, δ)
* 若 β^γ ⋅ γ^δ ≡ α^x mod p，則簽名有效，代表消息 x 確實是由簽名者簽署

------------------------------------------------------------- 期中考線 -------------------------------------------------------------

## (重要) 複習
1. Discrete Logarithm Schemes: 離散對數問題
* y = $g^x$ % p
* g 是公開的基數
* p 是質數
* (g^x 不是一般的冪次，而是代表 "群中的重複運算"。但在乘法群 (multiplicative group) 中，則剛好為冪次)
* 給定 g, x, p，很容易計算出 y；但從 g, y, p 回推 x 非常困難
* Diffie-Hellman key exchange 的核心依賴
2. Elliptic Curve Cryptography: 橢圓曲線密碼學
* 基於橢圓曲線，同樣屬於一種廣義的離散對數問題
* 描述由橢圓曲線整數點及 O 構成的加法群中，使得 dP (d 倍的特定點 P) = T (另一個特定點) 的 d 是多少
* ECDH 的核心依賴

## 數位簽章演算法介紹
* 基於橢圓曲線的數位簽章演算法是目前主流

### Schnorr signature scheme
* 為一種數位簽章演算法
* 能讓使用者簽署一段訊息，並可公開驗證


### Digital Signature Algorithm (DSA)
* 基於 Schnorr signature scheme 做了一些調整 (同架構)


### Elliptic Curve DSA (ECDSA)
* 與 DSA 不同的是，ECDSA 基於橢圓曲線


### Edward-curve DSA (EdDSA)
* 同樣基於基於橢圓曲線，但較現代，更快更安全


## Public key infrastructure (PKI)
* Trusted certificate authority (CA): 受信任的第三方，用於驗證某人的 Public key 是否真的來自於他，而不是被偽造的
* CA 會驗證 Public key 持有者的身份
* 接著發出憑證（Certificate）: 包含 Public key 持有者的身份訊息、Public key 本身及 CA 的數位簽章
* (重要) 任何人都可以拿 CA 的 public key 驗證 Certificate 的有效性，也就驗證了使用者的 Public key 是真的
* (重要) Certificate 本身是公開的，任何人都可以使用 Certificate 來確認 server 持有者的身份。即使攻擊者拿到 Certificate，仍無法偽造只有 server 持有者擁有、可以簽出數位簽章的 private key，故無法冒充 server 持有者

### (重要) Certificate 生成流程
#### 方法 1 (使用者 Alice 自行產生 key)
1. Alice 自行生成 public key 跟 private key
2. Alice 提供自身的身份訊息及 public key 給 CA
3. CA 透過 email 或簡訊等驗證 Allice 身份
4. CA 拿 Alice 的 public key 及他的身份訊息做為輸入，拿 CA 自己的 private key 進行簽章
5. CA 將 Alice 的身份訊息、Alice 的 public key、以及簽章做為 Certificate，回傳給 Alice

#### 方法 2 (由 CA 代為產生 key)
1. Alice 提供自身的身份訊息 CA
2. CA 透過 email 或簡訊等驗證 Allice 身份
3. CA 生成 public key 跟 private key
4. CA 拿 public key 及 Alice 的身份訊息做為輸入，進行簽章
5. CA 將 Alice 的身份訊息、Alice 的 public key、以及簽章做為 Certificate，回傳給 Alice。同時將 private key 也另外回傳給 Alice

### Chains of CA
* CA 可能有很多個，通常會分層級。下層 CA 的憑證會由上層 CA 來簽章，形成一條信任鏈
* 通常每個瀏覽器或作業系統都會內建一組 Root CA 的 public key。只要這條信任鏈最終能回到 Root CA，整個驗證就成立

## Signing and encryption
* 先簽章後加密: 容易被接收者轉傳，失去訊息的可控性
* 先加密後簽章: 容易被攻擊者偽造
* signcryption:
* 加密訊息前，加入發送者的資訊
* 進行簽章前，加入接收者的資訊

## 零知識證明（Zero-Knowledge Proof, ZKP)
* 證明知道秘密，卻不洩漏秘密本身
* 目的: Alice 想向 Bob 證明她知道秘密 x，使 Y = g^x，但又不想直接透露 x 的值
* 步驟:
1. Alice 選擇一個隨機數 k，計算 R = g^k。將 R 傳給 Bob
2. Bob 選擇一個隨機數 c 傳給 Alice
3. Alice 計算 s = k + c * x。將 s 傳給 Bob
4. Bob 檢查 檢查 g^s 是否等於 R * Y^c。若相等，表示 Alice 確實知道 x

## (重要) Blind signature
* 是一種特殊的數位簽章技術，允許某人在不知道訊息的情況下為另一人進行簽章
* 適用於 eCash 等電子現金應用場景
* 步驟:
1. Alice 選擇一個隨機值 r (blind factor)，並計算 t = m * r^e mod n，並將 t 傳給 Bob。這個步驟的目的是隱藏原始訊息 m
2. Bob 用自己的 privacy key d 來計算計算 $t_d$ = t^d mod n。並將 $t_d$ 回傳給 Alice。這個步驟的目的是進行簽章
3. Alice 計算 s = $t_d$ * $r^{-1}$ mod n。這時 s = $m^d$ mod n。這便是 Bob 的簽章。這樣一來，Bob 便能在不知道訊息的情況下為 Alice 進行簽章

## (重要) Group signature
* 是一種適用於 group 的數位簽章技術
* 在 group 中包含一個群組管理員 (GM) 與一些普通的群組成員
* 群組成員可以為這個群組進行匿名簽章
* 任何人都可以驗證這個簽章來自該群組，但只有 GM 知道是誰簽的

# 第六章 Randomness
* (重要) 隨機數產生器的實作分成兩種:
* true random number generator (TRNG): 依賴真實世界中不可預測的自然現象來產生隨機數
* 缺點: 需要花時間取得隨機性的來源，速度慢
* pseudo-random number generator (PRNG): 從初始輸入 seed 出發，透過演算法生成一系列看似隨機的數
* 特性
* Deterministic (確定性): 給定相同的 Seed，則生成出的亂數序列相同
* Indistinguishable from random (不可區分性): 好的演算法應無法分辨 PRNG 產生的偽亂數與真正亂數之間的差別

## Key Derivation Function (KDF)
* Key Derivation 的目的是將輸入的 secret 衍生成一系列可用的 secret key
* 與 PRNG 的差異:
* KDF 不要求要生成完全隨機的 secret，只要 entropy 夠即可
* 為了使相同的操作能得到相同的 key，KDF 需具備 deterministic (確定性)
* 由於 KDF 只需產生有限數量的 secret key 即可，因此輸出可循環
* KDF 通常是 HMAC base，可以細分成兩個步驟:
* HKDF-Extract: 去除輸入 secret 的偏差
* HKDF-Expand: 產生並輸出任意長度的隨機 secret

# 第七章: Transport Layer Security Protoco
## 常見網路安全協定
1. Transport Layer Security (TLS)
* 建立在 TCP/IP 之上
* 用來保護 HTTPS、mail、檔案傳輸的加密技術
2. Secure Shell (SSH)
* 同樣建立在 TCP/IP 之上
* 用來安全的遠端登入或傳輸檔案
3. Internet Security Protocols (IPSec)
* 直接在 IP 層運作，保護整個封包

## TLS HandShake Protocol (TLS <=1.2)
* "\*" 代表可選步驟
* 單箭頭代表傳輸時未加密、雙箭頭代表傳輸時有加密
* 整體流程:
* ClientHello: Client 發送一個只用一次的隨機數 (nonce)，以及自己偏好的 ciphersuite (一系列的加密規則)
* ServerHello: Server 發送一個只用一次的隨機數 (nonce)，以及自己選擇的 ciphersuite
* ServerKeyExchange: 若使用 DH 來雙方協商出一個共同 Key 的話，會執行此步並發送對應的資訊給 Client
* CertificateRequest: 若有需要，要求 Client 的憑證
* ServerHelloDone: 結束 Server Hello 流程
* Certificate: 若有需要，Client 提供憑證
* ClientKeyExchange: 若使用 DH 來雙方協商出一個共同 Key 的話，會執行此步並發送對應的資訊給 Server
* CertificateVerify: 若有需要，Client 驗證憑證
* ChangeCipherSpec、Finish: Client 及 Server 分別改變模式後，發送第一段 Finished 訊息；

## TLS Record Layer Protocol
* Record Layer 是 TLS 最底層的資料封包處理層，負責加密與驗證
* 有三種常見的實作方法:
* Stream-cipher-based ciphersuites
* Block-cipher-based ciphersuites
* Authenticated-encryption-based ciphersuites (version ≥ 1.2)

## 其他功能
### Compression (TLS <=1.2)
* TLS 原本允許在資料加密之前，先對應用層的資料進行壓縮，以節省網路

### (重要) Session resunption
* 若 client 與 server 之前曾經連線過，則可以透過以下方法跳過繁瑣的連線流程
* Session IDs: server 在初次建立連線時儲存 Session ID、參數及 master secret，Client 也儲存 Session ID。重新連線時，Client 在 "ClientHello" 階段附上 Session ID 以快速恢復連線
* Session Tickets: server 在 "ChangeCipherSpec" 階段前送出加密的 NewSessionTicket 訊息 (包含 server's state) 交給 client 儲存。重新連線時，Client 附上這個 ticket 以快速恢復連線

### Renegotiation
* 允許在 HandShake 階段結束，資料傳輸階段開始後，重新跑一次 HandShake 流程更新 key、憑證等

## (重要) TLS 1.3 的更新 (相較於 TLS <=1.2)
* 移除一些不安全的加密演算法，例如 MD5、SHA-224 等等
* 連 HandShake 過程都會加密
* 提供新模式，需要的 round trip 數更少
* client 跟 server 可以在建立 session 時使用 preshare key，以使用 zero-round-trip mode
* client 可以不需等待 server 回應便可先送出 application data
* 使用 HKDF （HMAC-based Key Derivation Function） 來進行 key 的推導
* 移除 ChangeCipherSpec 訊息
* CertificateVerify (數位簽章的簽名)，改成涵蓋整個到目前為止的 handshake 資料而非部分

# 第八章: Quantum Computing and post-quantum cryptography
* 傳統的加密演算法依賴困難的數學難題，但量子計算可能讓這些問題不再困難
* (重要) Quantum cryptography: 設計基於量子運算的加密演算法
* (重要) Post-Quantum Cryptography: 設計能抵抗量子計算攻擊的加密演算法

## 量子電腦原理簡介
* (重要) 量子電腦使用量子位元 （qubit） 來表示資訊
* Superposition (疊加態): 在觀測之前，量子系統可以同時處於多個狀態
* Entanglement (糾纏): 兩個糾纏的 qubit，若其中一個 qubit 被觀測，無論多遠，另一個 qubit 的狀態將會被確定
* 一個 qubit 可以處於 0 跟 1 的疊加態，故 n 個 qubit 可以包含 $2^n$ 種可能性
* 可以透過量子邏輯閘 (gate) 操作 qubit
* 量子電腦的最大難題是 qubit 非常容易受到干擾，且很難進行錯誤修正

## Grover’s Algorithm
* 是一種量子搜尋演算法
* 可以在 根號N 次的計算内搜尋 N 種可能


## Post-quantum cryptography
#### NTRUEncrypt
* 是一種知名的 Post-quantum cryptography 加密演算法
* 破解的難度相當於解決 SVP 或 CVP Problem

### Lattice-based
* 一組線性獨立的向量，搭配整數係數所形成的所有線性組合的集合，稱為 Lattice basis，其中的元素稱為 lattice
* 基於 Lattice 的困難問題包括
* SVP (Shortest Vector Problem): 給定一組 lattice 基底，找出 lattice 裡除了原點以外最短的非零向量
* CVP, Closest Vector Problem: 給定一組 lattice 基底及不在 lattice 上的點 w，找出 lattice 中最接近 w 的那個
* NTRU crypto-system 便是一種 Lattice-based 的加密系統

### Learning With Errors（LWE） problem
* 在 mod q 的條件下，如何解決被加了小誤差的線性方程組

* 問: 給定所有的 (aᵢ, bᵢ)，如何找出秘密向量 s

#### Kyber
* 是一種基於 LWE 問題的 key-exchange 加密系統


# 第九章 Identification schemes and entity authentication
* 驗證身份:
* What you are: 行為或物理特徵，如臉部辨識等
* What you have: 證件等
* What you know: 只有本人知道的訊息

## Identification scheme
* 希望進行零知識證明
* Alice 向 Bob 證明自己知道某個秘密，但不會在過程中洩露這個秘密
* 希望計算效率高
* 希望避免 replay attack

## Interactive protocol
* 當二或多個參與者互相溝通時
* session: 跑完協定的全部流程
* flow: 協定中的每一步

## Freshness mechanisms
* Freshness 機制用於保證訊息是第一次產生與傳送，避免 replay attack
* replay attack: 攻擊者紀錄已經傳送過的訊息，並在稍後將這些信息重放，目的是欺騙系統或造成不正當行為（如重複發送支付指令）
* 透過 Freshness Value 來確保訊息是新的，其中來源可為
* 時間戳: 直接將當前的時間做為 Freshness Value
* (重要) Nonce: 當使用者傳送請求前，系統會先發送一個只能用一次的隨機值 n；使用者需在之後的訊息中包含 n
* 攻擊者想進行 replay attack 時，會因為 Nonce 過期或用過而失敗
* Counter: 針對雙方的互動次數計數，並做為 Freshness Value

### Schnorr identification scheme
* 基於 discrete logarithm problem
* 需要 trusted authority (TA) 的參與


## Quadratic residue
* 考慮某個整數集合 (如 $z_{11}$ 表示 {0~10})，且 p 是奇數質數
* a 是「modulo p 的平方剩餘 （quadratic residue modulo p） 的條件為
* a 是某個整數集合中的元素，平方之後的餘數（mod p）
* a 不是 0

### Euler’s criterion
* a is a quadratic modulo p if and only if $a^{(p−1)/2}$ ≡ 1 (mod p).

## Lagendre symbol
* 令 p 為奇數質數，整數 a 的 Lagendre symbol 定義為:
*　性質

## Jacobi symbol

## Feige–Fiat–Shamir (FFS) identification scheme
* 依賴大整數質數分解問題

## entity authentication
* 一般來說，會透過密碼進行使用者的身份驗證
* 缺點: 較 privacy key 好猜, 太多組記不住
* 解決方案:
* Single Sign-on (SSO): 只需一組帳密，便可存取多個服務
* 密碼管理器: 自動建議並儲存高強度密碼

### Password Authenticated Key Exchange (PAKE)
* 在基於密碼的前提下，生成出一組更安全的 key 供後續使用
* 由於多了密碼的保護，PAKE 可以有效阻止 Man-in-the-Middle 攻擊 (DH key exchange 沒辦法)
* 分成 Symmetric (Balanced)、Asymmetric (Augmented) 兩種類型

#### Symmetric (Balanced) --- 以 Cpace 為例
* Composable Password Authenticated Connection Establishment (CPace) protocol 是一種對稱式的 PAKE
* 使用者與伺服器雙方共同知道一組密碼
* (重要) 優化了 Diffie-Hellman key exchange ，避免了 Man in the Middle 攻擊
* 讓 Diffie-Hellman key exchange 中原本共享的生成元 a 不再公開，而是從雙方共同知道的密碼中導出
* 由於攻擊者不知道密碼，因此無法得到生成元，也就無法進行攻擊

#### Asymmetric (Augmented) --- 以 OPAQUE 為例
* OPAQUE 是一種非對稱式的 PAKE
* 伺服器不知道具體密碼，只知道加密後的密碼驗證資料
* 依賴 Oblivious pseudo-random function (OPRF) 技術
* 讓伺服器在不知道密碼的情況下，驗證密碼的正確性

register 階段

login 階段

# 第十章: Key distribution
* Key Establishment 是一個更廣泛的概念，包含所有能讓雙方能擁有共同 key 的所有方法，可分成
* Key pre-distribution: TA 透過安全通道分配 key 給所有參與者
* Session key distribution: 線上的 TA 透過之前分配的長期 key，加密短期的 session key 後傳給使用者
* Key agreement: 使用者們透過協定協商出 session key
* Key Transport: 一方使用者生成 key 後，安全的傳給另一方
* key 可以依照使用時間分成
* Long-lived keys: 需要事先產生並長期的安全保存
* Session keys: 用完即扔，可以基於 Long-lived keys 來產生
* 攻擊手段
* Known session key attack
* Known long-lived key attack

## 複習: Diffie-Hellman key exchange
* key exchange 流程
1. 選擇一個大質數 p 和一個生成元 a (皆可公開)
2. 每一方各自選擇一個私有金鑰 x 和 y (各自保密)。
3. 第一方計算 $Y_a$ = $a^x$ mod p，第二方計算 $Y_b$ = $a^y$ mod p，然後彼此交換這些結果 (公開交換)。
4. 每方用對方的公開金鑰和自己的私有金鑰計算：
* 第一方計算 $(a^y \ mod \ p)^x$ mod p
* 第二方計算 $(a^x \ mod \ p)^y$ mod p
* $(a^y \ mod \ p)^x$ mod p = $(a^x \ mod \ p)^y$ mod p = = $a^{xy}$ mod p
* 由於數學特性，兩方得到的結果相同，即生成了共享密鑰
* (重要) 安全性分析
* Computational Diffie-Hellman Problem (CDH): 給定 p, a, $Y_a$, $Y_b$，如何計算共享密鑰 $a^{xy}$ mod p
* Decisional Diffie-Hellman Problem (DDH): 給定 p, a, $Y_a$, $Y_b$, 及一個候選 key z，如何判定 z 是否為共享密鑰 $a^{xy}$ mod p
* 解 CDH 跟 DDH 是困難的，因此 Diffie-Hellman key exchange 是安全的

## Diffie-Hellman key pre-distribution

## Blom Scheme
* 在傳統有 n 個使用者的系統中，兩兩使用者都建立一組 key 的成本太高
* 在 Blom Scheme 架構中
* 決定安全參數 m，一個與 n 不相關的數值。攻擊者需要知道超過 m 位使用者的祕密向量，才能破解系統
* 整個系統由 TA(Trusted Authority) 管理


### 攻擊手段
* 當攻擊者擁有超過 m 位使用者的祕密向量時，便可使用 Lagrange 插值

## Key pre-distribution in sensor network
* 在資源受限的情況下進行 Key pre-distribution，每個網路中的節點沒辦法儲存太多 key, 也沒有太多算力

### Lee-Stinson linear key pre-distribution scheme
* 性質:
1. 每個密鑰 $k_{i, j}$ 正好被 p 個節點持有
2. 
4. 任意兩個節點有連結（共享金鑰）的機率是 $\frac{k}{p+1}$
5. 兩個節點的 link 被其他節點破解的機率是 $\frac{p-2}{p^2-2}$

## Session key distribution
* 讓兩個使用者透過受信任的第三方 (TA) 分配一個暫時的 session key

### Needham-Schroeder scheme

* 缺點: 沒有 timestamp，容易受到 Replay attack

### Kerberos version 5

* 使用 timestamp (t) 及 Lifetime (L) 防止 Replay attack
* 但當不同設備間的時間不同步時，會導致誤判

### Bellare-Rogaway scheme

* 最安全
* Alice 只確認來自 TA 的資訊是正確的
* 只有 Bob 知道自己的 session key

## verification by Merkle tree
* 在一棵 Completed Binary Tree 中
* 資料存在 leaf 節點
* V(j) = h(V(2j)∥V(2j + 1))，其中 h() 是 hash function
* 只需檢查 V(1) 便可確認所有資料是否遭到篡改

## Shamir’s Threshold Scheme
* (重要) Threshold scheme 指的是有門檻值機制的 secret sharing 架構
* 假設系統中共有 w 人, 門檻值為 t，secret 為 k
* 至少要集結系統中的任意 t 人，才可計算出 k，否則保證沒辦法算出 k


# 第十一章: Key agreement schemes
* 探討如何在一個不安全的網路上。雙方安全的協商出一把共同的 key
* 先前提過的 Diffie-Hellman key agreement scheme 會遇到 main-in-the-middle 攻擊，故通常不會直接採用

(Diffie-Hellman 可事後否認)

## Station-to-station (STS) key agreement scheme
* 是一種改良 Diffie-Hellman key agreement scheme 的 key agreement 架構
* 透過額外的數位簽章機制，保護雙方的公開通訊內容，有效避免 main-in-the-middle 攻擊
* 不可事後否認
* Assurance level (驗證等級) 屬於 Implicit key confirmation 類型


## key agreement 的 Assurance level (驗證等級)

## Key derivation function (KDF)
* 這個函式負責將一個共享祕密 (如 key agreement 所共同決定的)，轉成一個或多個可用的 key
* 在不知道 input 的情況下，輸出不可預測
* 通常為 one-way hash function
* 不可事後否認

## MTI key agreement scheme
* 是一種改良 Diffie-Hellman key agreement scheme 的 key agreement 架構
* 透過另一種架構設計，避免了 STS key agreement scheme 要當場簽章，計算效率低的問題
* 透過 private 跟 puplic 的機制，有效避免 main-in-the-middle 攻擊


攻擊手段:
* Known session key attack
* Burmester triangle attack:

## (重要) X3DH scheme
* 可事後否認的 Key agreement 協議


## Key updating scheme
* 長時間使用同一個 key 是不安全的，但重作一次 Diffie-Hellman key agreement 的成本又過高

### 使用 Diffie-Hellman ratchet 實現 Key updating

### 使用 KDF 實現 Key updating
* 更快，但較不安全


## Conference Key Agreement
* 支援多方的 Key Agreement

### Burmester-Desmedt conference key agreement
*　分成兩輪:
*　第一輪: 群組中的所有使用者組成一個環。每位使用者各選擇一個 private key，計算資訊後傳給其左右鄰居
*　第二輪: 每位使用者透過上一輪的接收到的中繼訊息，計算出另一個資訊，並透過廣播通道傳給全部的人


### Steiner-Tsudik-Waidner conference key agreement
* 與 Burmester-Desmedt 方法不同的是，不需要「廣播通道」。但代價是速度較慢
*　分成兩輪:
*　第一輪: 群組中的所有使用者串成一條鏈，逐步鏈接自己的 privacy key 至資訊中並串第這個資訊下去。全部傳遞完後，便能建立出一個包含所有使用者的資訊
*　第二輪: 反過來將資訊傳回來，並在這個過程中決定共同的 key


# 第十二章: Miscellaneous topics (雜談)
## Identity-Based Cryptography
* 核心概念: 「身份資訊」本身就是 public key
* 架構設計:
* 由一個受信任的中心單位 (TA) 管理
* 使用者的身份資訊做為 public key
* TA 根據身分產生對應的 private key，交給使用者
* 優點: 不需要繁瑣的數位簽章驗證流程
* 缺點: TA 將會知道所有人的 privacy key


## Cocks ID-based cryptography
* 只能一次加密一個 bit

### Composite Quadratic Residues Problems
* 難度等價於質因數分解問題


## Boneh-Franklin ID-based cryptosystem
* 可以一次加密多個 bit
* Pairing-based
* 基於 Bilinear Diffie-Hellman problem 這個困難問題上


#### Bilinear Diffie-Hellman problem

#### (重要) pairing
* pairing function e 定義如下
* e: G1 × G2 → G3
* G1 跟 G2 是 abelian groups，通常為加法群
* G3 也是 abelian groups，通常為乘法群
* pairing function 將兩個加法群中的元素 mapping 至一個乘法群中的元素
* pairing function 滿足 bilinear 的性質 (能夠將加法運算轉成乘法運算):
* $e(P1 + Q1, P2) = e(P1, P2) e(Q1, P2)$
* $e(P1, P2 + Q2) = e(P1, P2)e(P1, Q2)$
* $e(aP, bQ)$ = $e(P, Q)^{ab}$

## Homomorphic (同態) Encryption
* (重要) 能夠直接在加密後的資料上進行運算，整個過程運算方都無法知道資料的實際內容。這樣可以在不信任的環境中安全的處理敏感資料並保護隱私
* 流程:
* 使用者將待運算的機密數字加密，交給雲端服務進行運算
* 雲端服務回傳運算結果給使用者後，使用者能正確解密，得到正確的運算結果
* 用例子來說的話，便是
* ek(x1) * ek(x2) = ek(x1x2)
* ek() 是加密函數
* x1, x2 是機密數字
* 這種性質稱為 Homomorphic (同態)
* 可以細分成四個等級
* Partially homomorphic: 支援無限次加或乘運算
* Somewhat homomorphic: 支援有限次加和乘運算
* Leveled homorphic: 支援有限次加和乘運算，可設定次數
* Fully homomorphic: 支援無限次加和乘運算

### Paillier crypto-system
* 一種基於同態的加密演算法
* 加密時可以選擇隨機值 r。即使明文相同，只要選擇的 r 不同，加密後的結果也會不同
* 密文通常是明文的兩倍長


## (重要) 1-2 oblivious transfer
* 問題:
* Alice 持有兩個訊息
* Alice 不想讓 Bob 同時得到兩個訊息
* 如何讓 Bob 可以指定收到 Alice 的其中一個訊息，但不能讓 Alice 知道他指定了哪個
* 解法:
* 利用 RSA 加密的對稱性，讓 Bob 藏起他的選擇


## Garbled circuit
* 問題:
* 如何讓兩個互不信任的雙方，在不存在第三方的情況下，共同計算出一個結果
* 雙方都不知道彼此的輸入是什麼
* 解法:
* Alice 建立 garbled table
* Bob 透過 Oblivious Transfer 隱藏資訊，並利用 garbled table 計算出結果

## Yao’s millionaire problem
* 問題:
* Alice 有 i 百萬，Bob 有 j 百萬
* 如何在兩人都不透露自己實際金額的情況下，比較誰比較有錢


## Attribute-based encryption (ABE)
* 是一種 Public key 加密技術
* 任何符合夠多 attributes (屬性) 的人員都可以解密
* 可以進一步細分成:
* KP-ABE (Key-Policy ABE): attributed 跟 ciphertext 有關；access policy 跟 receiver 有關
* CP-ABE (Ciphertext-Policy ABE): 與上面相反
* 需要 TA 的參與
* TA 負責建立 public key 跟 master keys，並負責管理 attribute 集合
* 加解密概念:
* 發送者使用 Public Key 加密資料，並附上 attribute
* 接收者嘗試拿自己的 private Key 解密資料，若接收者的 private Key 能匹配的 attribute 夠多，便能順利解密資料
* 用到了 Access trees，用來定義誰能解密資料
* 非葉結點代表 threshold gate
* 葉節點代表 attribute

Key generation and update

Encryption and Decryption

## Bitcoin
* Bitcoin 是一種去中心化的貨幣
* 交易資料會記錄在區塊鏈 (Blockchain) 中
* Bitcoin Address: 任何人都可以建立一組 private key 跟 public key，並將 public key hash 後的結果做為 Bitcoin Address
* Bitcoin transfer: 例如將 X 個 bitcoin 從 Bitcoin Address1 轉移至 Bitcoin Address2
1. 需將這筆交易廣播至 bitcoin 網路
2. 需驗證交易合法性
* Bitcoin mining: 創建新區塊的過程
* 幾筆交易可以湊成一個區塊
* 創建區塊的礦工可以獲得 bitcoin 獎勵、也可以收取一些代表交易手續費 的 bitcoin
* Proof-of-Work: 找到一個 nonce，讓整個區塊頭的 SHA-256 hash 小於目標值。這樣做是為了限制區塊的產生速度
* 創建的區塊會經過其他節點驗證