# 世界第一簡單密碼學筆記 ## 古典加密系統: ### 凱撒加密 將字母向前或向後順移得出密文 ### 替代密碼法 凱薩加密的複雜化，有分為: 1. 簡單替代法: 將字母一對一的對應到其他字母 ```flow st=>start: 明文 op=>operation: 變換規則 e=>end: 密文 st->op->e ``` 2. 多字母密碼法: 將明文區分成數個區塊，區塊內的文字以特定規則 $\sigma$ 做替換 ex: MOMOTARA $\sigma$ = 1->5 2->5 3->3 4->1 1. MOMO -> OTPP 2. TRAR -> VFUP 因為不知道推遲幾個數，每個字元都必須算過 26 次，若明文長度為 n ，則金鑰數為 $26^n$ 3. 置換密碼法: 將明文區分為數個區塊，區塊內的文字以特定規則 $\sigma$ 交換順序 因為無論改變，密文上的字都是由明文改變順序而來，因此金鑰長度為 $n!$ (n = characters per block) #### 解讀條件 1. 知道加密的演算法 2. 明文具備的統計資料 3. 大量的加密的範本 #### 絕對安全的密碼 1. 使用一次性密碼本(不具再現性): ex. Vernam Cipher: * 絕對解不出來 * 通訊效率非常差 3. 計算量非常之龐大的密碼 ## 共通金鑰(對稱金鑰): ### XOR 計算 明文 ^ 金鑰 = 密文 密文 ^ 金鑰 = 明文 ex. 3人聯繫需要3把金鑰(每個對應另外兩個) ex. 4人聯繫需要6把金鑰(每個對應另外三個) formula: $n = \frac{(n-1)\,n}{2}$ ### 特徵: 1. 需要小心保管、配送 2. 加解密計算量小，適用於大量資料傳遞 3. 需要管理多數金鑰，不適用於不特定人數 ### 分類: 1. stream: * 每個 bit 逐一加密 * 計算簡單 * 可以嘗試每個金鑰破解之 * 金鑰以偽隨機亂數產生 * RC4, SEAL 3. block: * 明文分成區塊，每個區塊做加密，不足則以 padding 填充 * 會出現相同明文產生相同密文的情況 * 可以用 CBC 模式防禦，將前一個 block 加密結果和下一個區塊明文做 加密 * 還有 OFB, CFB 等等 * 若各個區塊用不同金鑰加密則稱之為 ECB (electric code block) ### DES 密碼 data encryption standard #### 密文輸出流程: 1. 明文以 64 bit 為單位為 block 2. 以 $IP$ 對每個 block 做初始置換 3. 分為 L0, R0 4. 使用加密金鑰 $K$ 的非線性函數 $f$ 對 R0 做置換排序 > $K$ 每個回合都會不一樣 6. 用 R0 和 L0 做 XOR 運算得出來的結果為新的 R1 ， R0 變為 L1 7. 以此類推做個 15次 8. 對 R16, L16 做重組 9. 再一次 $IP$ 對每個 block 做置換 > 裡面運用到對合原理: a->b->a ，做兩次轉換就會得到原始值 > #### 每回合金鑰 K 的形成: 1. 將一個初使共通金鑰 $K$ 扣掉用做驗證的 8 bit 2. 剩下的 56 bit 分成 C0, D0 3. C0, D0 分別左移 LS1 得到 C1, D1 4. C1, D1 合起來除去 8 bit 並排列 ，所得即為金鑰 $K1$ 5. 重複 3, 4 即為各回合的金鑰 #### 非線性函數 $f$: 1. 輸入左邊的 32bit 跟金鑰做結合擴充為 48 bit ，稱之為 $E$ 2. 金鑰與 $E$ 做 XOR 3. 運算結果以 6bit 為一組，透過 S-BOX 將 6 bit 變換為 4 bit 4. 所有 4 bit 重新合併成 32 bit 5. 透過 P-BOX 將 32bit 重新排列，所得即為 $f$ 的輸出 #### 弱點 * S-box 沒有標準，實作上容易出現漏洞 * 金鑰長度短，長度短則處理時間長且容易被解讀 * 暴力破解 * 利用輸入的差距 == 輸出差距( XOR 特性)找金鑰 * S-BOX 排列成線性，以機率推測輸出 為了解決弱點，提出 3-DES ，利用 encrypt -> decrypt -> encrypt ，藉以增加金鑰長度，但問題的本質沒解決XD #### 取代 AES (advanced encryption standard) 採用 Rijndael 演算法 ## 公開金鑰密碼(非對稱金鑰加密系統): 這種系統的密碼金鑰會有兩個，公開金鑰用來加密，秘密金鑰用來解密 ex: 商店 A 發布公開金鑰給任何想要跟商店通訊的客戶，客戶的明文用公開金鑰加密後傳送到 A ， A 再用秘密金鑰解密 若有 1000 個人要互相通話，則每個人需要一個公開金鑰給想跟你對話的人，一個秘密金鑰用來解密，因此總共需要 1000*2 個金鑰，遠遠少於共通金鑰加密的金鑰數 ### 加密技巧: * 質因數分解問題: * RSA * Rabin 密碼 * 離散對數問題: * ElGamal 密碼 * 橢圓曲線密碼 * DSA 認證 兩種技巧都用了單向函數的原理: 單向計算可以知道答案，反向逆推卻很難，但若是持有金鑰反向逆推就可以解密 模數用於密碼的優點: 其餘數不可能大於等於除數，換言之，範圍是可以掌控的 * 費馬小定理: $n$ is prime $a \in Z, a \perp n$ $a^{n-1} \equiv ({mod\ n})$ 用來檢驗數 $n$ 是否為質數 * 歐拉定理: $n \in N$ $a \in Z, a \perp n$ $a^{ \varphi (n)} \equiv (mod\ n)$ 若 $n$ 為質數，則 $\varphi(n) = n-1$ 也就是費馬小定理 假設: $N = pq$ $p,q\ is\ prime$ 則 1~pq 中屬於 p 的倍數有: $1,p,2p,3p,4p....qp$ q 個 1~pq 中屬於 q 的倍數有: $1,q,2q,3q,4q....qp$ p 個 故 $\varphi(N) = pq - q-p + 1$ $\varphi(N) = (p-1)(q-1)$ $\varphi(N) = \varphi(p)\varphi(q)$ $a^{p-1} \equiv 1 (mod\ p)$ $a^{q-1} \equiv 1 (mod\ q)$ 令 $(p-1)(q-1)$ 的最小公倍數為 $L$ $a^L \equiv 1 (mod\ pq)$ $a^L \equiv 1 (mod\ N)$ 又 $(p-1)(q-1) = LG$ $G$為$(p-1)(q-1)$的最大公因數 RSA 加密: $P$ 為明文 $C$ 為密文 $C = P^e(mod\ N)$ $e$ 為公開金鑰 1 且 $N$ 為公開金鑰 2 RSA 解密: $P = C^d(mod\ N)$ $d$ 為秘密金鑰且 $N$ 為公開金鑰 2 假設知道 $e\ C\ N$則可以解讀密文，但代數字很費時間，若計算 $\varphi(N)$ 應該可以由歐拉定理算出來，但 $N$ 必須作質因數分解，而 $N$ 為極大值時幾乎不可能作到 RSA 金鑰生成法: 1. 任選擇兩個相當大的相異質數 $p$, $q$ 2. 求歐拉函數 $\varphi(N)\ =\ (p-1)(q-1)$ 3. 求 $(p-1)(q-1)$ 的最小公倍數 $L$ 4. 選擇與與 $L$ 互質且小於 $L$ 的任意正整數 $e$ 5. 對於任意正整數 $e$ 求出滿足下式的正整數 $d$: $ed=1(mod\ L)$ $d<\varphi(N)$ $d>p\ \&\ d>q$ 其中 $N$ 為公開金鑰之一，$e$亦為公開金鑰但必須符合 $P^e>N$ $d$ 則為解密金鑰