---
# System prepended metadata

title: 世界第一簡單密碼學筆記

---

# 世界第一簡單密碼學筆記

## 古典加密系統:
### 凱撒加密
將字母向前或向後順移得出密文
### 替代密碼法
凱薩加密的複雜化，有分為:
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$ 則為解密金鑰





