---
# System prepended metadata

title: 課程｜密碼學
tags: [課程]

---

# 密碼學

### **1.算數 Arithmetic**
- **1.Modular Function**
    - 定義： $n$ mod $m$ = $n-\llcorner\frac{n}{m}\lrcorner \times m$
- **2.GCD and Euclidean Algorithm**
    - 1.定義： gcd(a, 0)=a,&emsp; gcd(a, b)=gcd(|a|, |b|), &emsp;gcd(a, b)=gcd(b, a)
    - 2.定理： gcd (a, b) = gcd (a + kb, b)
        - 推論： 當b>0，則 gcd(a,b)=gcd(b,a mod b)
    - 3.演算法：Euclidean Algorithm(輾轉相除法)
        - 不斷使用gcd(a,b)=gcd(b,a mod b)，直到b=0
- **3.Extended GCD Algorithm**
    - 1.目標：給定a,b，找出**x, y** 使得 **ax+by = gcd(a, b)**
    - 2.定理：Extended GCD Algorithm
        - 證明：數學歸納法
        - set $\begin{bmatrix}r_0&x_0&y_0\\r_1&x_1&y_1\end{bmatrix}=\begin{bmatrix}a&1&0\\b&0&1\end{bmatrix}$
              while($r_1\neq0$)
        $~~~~~~~~$set $\begin{bmatrix}r_0&x_0&y_0\\r_1&x_1&y_1\end{bmatrix}=\begin{bmatrix}0&1\\1&-\llcorner r_0/r_1\lrcorner\end{bmatrix}\begin{bmatrix}r_0&x_0&y_0\\r_1&x_1&y_1\end{bmatrix}$
    - 3.應用：如果p是質數，則演算法可找$Z_p$中任一元素a的乘法反元素
    - 4.定理：Stein GCD Algorithm
        - a, b both even $~~~~~\rightarrow$ gcd (a, b) = 2gcd(a/2, b/2)
        - a is even, b is odd $\rightarrow$ gcd (a, b) = gcd(a/2, b)
        - a, b both odd $~~~~~~\rightarrow$ gcd (a, b) = gcd ((a-b)/2, b)

- **4.Fundamental Theorem of Arithmetic**
    - 1.**定理：gcd(a,b)是可以表示成ax+by的正整數中最小的一個**
    - 2.定義：$a\perp b$表示$a,b$互質
    - 3.定理：如果$a~|~bc$ 且 $a\perp b$，則 $a|c$
        - 推論：如果p是質數 且 $p~|~ab$，則 $p~|~a$ 或 $p~|~b$
        - 推論：如果p是質數 且 $p~|~a_1a_2...a_k$，則 $p~|~a_i$ 某一個i
    - 4.算術基本定理：每一個>1的整數a，要不是質數，要不可以維一表示成質數的乘積。
        - Z 是 UFD
    - 5.定理：$a\times b=gcd(a,b)\times lcm(a,b)$
- **5.Modular Arithmetic**
    - 1.定義：**a is congurent b module m** 的定義為 $a~mod~m\equiv b~mod~m$
        - 定理：$a~mod~m\equiv b~mod~m~\leftrightarrow~m|(a-b)$
            - If $a\equiv b$ and $b\equiv c~(mod~m)$, then $a\equiv c~(mod~m)$
            - If $d=gcd(a,m)$ and $ab\equiv ac~(mod~m)$, then $b\equiv c~(mod~m/d)$
                - $6\times2\equiv6\times7~(mod~15)\rightarrow 2\equiv7~(mod~5)$
    - 2.定義：a的**inverse** 為 滿足$ac\equiv 1$的最小正整數(mod m)
        - 推論：$a^{-1}存在 \leftrightarrow a\perp m$
        - 應用：$ax\equiv b\leftrightarrow x\equiv a^{-1}b~(mod~m)$
        - 演算法：
            - set $\begin{bmatrix}r_0&x_0\\r_1&x_1\end{bmatrix}=\begin{bmatrix}a&1\\m&0\end{bmatrix}$
              while($r_1\neq0$)
              $~~~~~~~~$set $\begin{bmatrix}r_0&x_0\\r_1&x_1\end{bmatrix}=\begin{bmatrix}0&1\\1&-\llcorner r_0/r_1\lrcorner\end{bmatrix}\begin{bmatrix}r_0&x_0\\r_1&x_1\end{bmatrix}$
- **6.中國剩餘定理**
    - $m_1、m_2互質~\leftrightarrow~可以用(Z_{m_1},Z_{m_2})來表示Z_{m_1m_2}$
        - ![](https://i.imgur.com/eYIazMg.png)
    - 解法一
        - $x\equiv 4$ mod 7
        - $x\equiv 3$ mod 5
        - 假設x=4+7u，帶到下一個式子，得 u=2+5k，x=18+35k，依序往後帶入
    - 解法二
        - $x=a_1M_1x_1+a_2M_2x_2+a_3M_3x_3$ mod M
    - 解法三
        - $t=m_1^{-1}(a_2-a_1)$ mod $m_2$
        - $x=a_1+m_1t$
        - ![](https://i.imgur.com/ZJCg0ec.png)
- **7.Theorems of Fermat and Euler**
    - Fermat’s Little Theorem
        - p是質數，則 $a^p\equiv a$ (mod p)
        - p是質數且a不是p倍數，則 $a^{p-1}\equiv 1$ (mod p)
        - Carmichael Numbers
            - $a^{561}\equiv a$ mod 561 ， 561=3\*11\*17
            - 費馬小定理反向不對
    - Euler’s Phi Funcrion：$\phi(n)=\prod (p^k-p^{k-1})$
        - $\phi(p)=p-1$
        - $\phi(p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)$
        - $\phi(mn)=\phi(m)\phi(n)$
    - Euler’s Theorem
        - a、m互質，則 $a^{\phi(m)}=1$ (mod m)
    - Fermat's Last Theorem
### **2.代數 Algebra**
- 群 Group
    - $Z_n=\{0,1,...,n\}$
    - ${Z_n}^*=\{a|a\in Z_n,and~gcd(a,n)=1\}$
    - **Group**：封閉、結合、單位元、反元素
        - **Symmetric Group S~n~**： ( **All permutation on {1,...,n}** , composition)
        - **Abelian Group**： commutative
            - 矩陣乘法、Permutaion運算：不可交換
        - **Cyclic Group**： 存在generator g
        - **Subgroup**： 封閉、反元素
            - <g\> is a subgroup
    - **Coset**： $a\cdot H=\{a\cdot h|h\in H\}$
        - $g_1H=g_2H~\leftrightarrow~ g_1^{-1}g_2\in H$
    - **Lagrange Theorem：|H| divides |G|**
        - $o(g)$ divides $|G|$
        - $|GL_2(Z_7)|=(7^2-1)(7^2-7)$
        - $|SL_2(Z_7)|=|GL_2(Z_7)|/6$
    - $f: G \rightarrow H$是 **isomorphism,** if
        - (1) $a,b\in G,f(a。b)=f(a)*f(b)$, **Homomorphism**
        - (2) $f$ is one-to-one and onto.
- 環 Ring
    - $(R,+,X)$
        - $(R,+)$是 Abelian Group
        - $(R,\times)$是 Semi-Group
        - $\times$ 對 $+$ 有分配律
    - Ring 不一定有乘法單位元($2Z$)
        - 我們只討論有**乘法單位元**的**交換**環
    - **Zero Divisor**：$Z_6$中的2, 3
        - n是質數：$Z_n$沒有Zero Divisor
        - n是合數：$Z_n$有Zero Divisor
    - **Integral Domain**：沒有**Zero Divisor**的**Ring**
        - **Number Field Sieve** 是目前做質因數分解最厲害的演算法
    - **Ideal**：A subset $I$ of ring $R$
        - $I$ 是加法群
        - $ar\in I$ for all $a\in I$ and $r\in R$
    - **Principal Ideal**： <$a$>:= $a R$
        - **$Z$裡的任何ideal皆為principal ideal**
        - **$<x,y>in~Q[x,y]$，不是principal ideal**
            - $<x,y>=\{Q[x,y]x+Q[x,y]y\}=常數為零的雙變數有理多項式$
            - $Q[x,y]=雙變數有理多項式$
        - **偶常數整係數多項式，不是principal ideal**
            - 假設a是generator，他可以generate 2, x
    - $R=Z,~I_1 = 4Z,~I_2 = 3Z$
        - $I_1\cap I_2=12Z$
        - $I_1+I_2=Z$
    - $a$ **is congruent to** $b$ modulo $I$， 定義為 $a-b\in I$
        - **The congruent class** of $a$ modulo $I$，$a+I$，是congruent to $a$ 的元素所形成的集合。
    - **Quotient Ring**：Cosets of $I$ form a ring $R/I$
        - $Z/4Z=\{4Z,4Z+1,4Z+2,4Z+3\}$
    - $f: G \rightarrow H$是 **isomorphism ( $f\approxeq g$ ) ,** if
        - (1) $a,b\in G,f(a。b)=f(a)*f(b)$, **Homomorphism**
        - (2) $f$ is one-to-one and onto.
- 體 Field
    - $(R,+,X)$
        - R is a Ring
        - 非零元素有乘法反元素。$\rightarrow$**必定沒有zero divisor**
    - 常見的例子
        - $Q,R,C$
        - $Z_p$：因為乘法反元素必定存在
        - $GF(2^8)$ in AES
    - **Characteristic**，$ch(F)=p$
        - 滿足 $p~個~1_F~相加的和為~0$ 的最小正整數 p
            - 如果不存在，$ch(F)=0$
        - 定理：p 必定是 質數
            - 假設$p=q_1q_2\rightarrow q_1=0~or~q_2=0$
        - $p~|~\begin{pmatrix}p\\i\end{pmatrix}，1\le i\le p-1$
        - $(a+b)^p=a^p+b^p$
        - $(a+b)^{p^n}=a^{p^n}+b^{p^n}$
    - **Subfield**
        - **Q is a subfield of R**
        - **R is a subfield of C ( C is a field extension of R with degree 2)**
    - **Irreducible Polynomial**
        - 非常數多項式，divisor只有他的associate和非零常數
        - $x^2+2~不可約~in~Z_5[x]，可約~in~Z_3[x]$
        - $x^2+1~不可約~in~Z[x]，可約~in~C[x]$
    - **Field Extension**
        - **$L:K$是 field extension**
        - **[$L:K$]是 degree of extension**
            - $[M:K]=[M:L][L:K]$
        - 如果$p(x)\in~F(x)$是不可約
            - 則$F[x]~/<p(x)>$是F的 field extension
            - $Z_2[x]/<x^2+1>=\{0,1,x,x+1\}$
            - $Z_3[x]/<x^2+1>=\{0,1,2,x,x+1,x+2,x^2,x^2+1,x^2+2\}$

### **3.有限體 Finite Field**
- Polynomial Ring $F[x]$
    - 係數是F所形成的多項式，搭配一般的加法跟乘法。
    - **Degree**：表示最高項次數
    - **Leading Term**：表示最高項
        - 對任意非零多項式p(x),q(x)
            - p(x)q(x) $\ne$ 0
            - deg(p(x)q(x)) = deg(p(x)) deg(q(x))
    - **Division Algorithm** ： 給定兩多項式a(x),b(x)
        - a(x)=b(x)q(x)+r(x)，r(x)=0或deg(r\)<deg(b)
    - **Congruent**：
        - a(x)-b(x)$\in$<m(x)>，則稱 a(x)和b(x) are congruent modulo m(x)
        - Extended GCD可以比照整數操作
    - **Euclidean domain**
        - 存在函數d把 integral domain D中的非零元素，對應到非負整數，則稱D為 Euclidean domain
            - 1.a,b $\in$ D, then d(a)$\le$d(ab)
            - 2.a,b $\in$ D, then a=bq+r, with r=0 or d(r\)<d(b)
- $GF_4$
    - 1.Linear Polynomial
        - {0, 1, x, x+1} with + and \*
        - (ax+b)+(cx+d)=((ax+b)+(cx+d)) mod 2
        - (ax+b)\*(cx+d)=((ax+b)\*(cx+d)) mod $x^2+x+1$ mod 2
    - 2.Congruent Classes 
        - Determined by Ideal <$x^2+x+1$>, which are [0], [1], [x], [x+1]
        - $GF_4\approxeq GF_2[x]/<x^2+x+1>$
    - 3.Linear Combination of Root
        - $\alpha$ is a root of $x^2+x+1$ over $GF_2$
        - $\alpha^2+\alpha+1=0,~~~\alpha^2=\alpha+1$
        - {0, 1, $\alpha, \alpha+1$}
- $GF_8$
    - $GF_8\approxeq GF_2[x]/<x^3+x^2+1>\approxeq GF_2[x]/<x^3+x+1>$
    - $x^8-x=x(x+1)(x^3+x+1)(x^3+x^2+1)$
- **Minimal Polynomial**
    - u 的 minimal polynomial，是以u為根的多項式所形成的ideal，其中係數為1的那個generator。
- $GF_{16}$
    - $GF_{16}\approxeq GF_2[x]/<x^4+x^3+1>\approxeq GF_2[x]/<x^4+x+1>\approxeq GF_2[x]/<x^4+x^3+x^2+x+1>$
    - $x^{16}-x=x(x+1)(x^2+x+1)(x^4+x+1)(x^4+x^3+1)(x^4+x^3+x^2+x+1)$
        - $o(x^4+x^3+1)=o(x^4+x+1)=15$
        - $o(x^4+x^3+x^2+x+1)=5$
    - ![](https://i.imgur.com/Siya1x0.png)
- **多項式的order**
    - $f|x^e-1$
    - f(x) 的order = 任意 f(x) 的根在${GF_{q^m}}^*$中的order
- $GF_{p^n}$
    - **Spliting Field**
        - 包含$f(x)$所有根的最小field
        - $x^2+1$的splitting field為 $C$
        - $x^{p^n}-x$的splitting field為$GF_{p^n}$
    - **定理：p是質數且q(x)是n次不可約多項式，則所有$GF_p$的n-1次多項式，搭配及以下運算，必定為field，我們稱其為$GF_{p^n}$**
        - $f(x)\oplus g(x)=f(x)+g(x)~mod~p$
        - $f(x)\otimes g(x)=f(x)\times g(x)~mod~q(x)~mod~p$
    - **底下想要說明 $x^{p^n}-x$ 的性質**
    - 推論：如果 $f(x)\in GF_p[x]$,則存在某個 n 使得 $GF_{p^n}$ 包含 $f(x)$ 的根
        - n=deg(q(x))，q(x)是f(x)的不可約因式
    - 性質：包含 $x^{p^n}-x$ 所有根形成的集合 over $GF_p$ 是一個field
        - 要證明封閉性反元素...
    - 引理：f(x)所有根都相異 $\leftrightarrow$ f(x)和f'(x)互質
        - 所有根相異，$f'(a)\ne 0$
        - 有根a相同，$f(a)和f'(a)$ 有因式 x-a
    - Remark：$f(x)=x^{p^n}-x$沒有重根
        - 根據以上引理
    - 定理：$x^{p^n}-x$ over $GF_p$ 的splitting field，就是由 $p^n$ 個相異根組成
    - 引理：n次over $GF_p$ 的多項式，最多只有n個根
        - Division Algorithm
    - Remark：n次over F 的多項式，最多只有n個根
        - Division Algorithm
    - 定理：$GF_{p^n}彼此之間同構，內有p^n個元素$
    - Remark：$GF_{p^n}$是 over {$x^{n-1},x^{n-2},...x,1$}的向量空間
    - 性質：$GF_{p^n}$的sub-field形式必為$GF_{p^d}$，其中$d|n$
        - ![](https://i.imgur.com/28cbhv2.png)
- ${GF_{p^n}}^*$所形成的乘法群
    - 定理：${GF_{p^n}}^*$=<g\>，是一個循環群。
        - $GF_{p^n}$中，order為d的元素，有$\phi(d)$個
    - f(x)是Primitive Polynomial如果他是某個primitive element的minimal polynomial
        - primitive element表示可以generate $GF_{p^n}$
        - 或是說f(x)的根可以generate $GF_{p^n}$
    - 引理：如果 f(x) 是$\alpha\in GF_{p^n}$的 minimal polynomial，則 f(x) 不可約
    - **性質：$x^{p^n}-x$ 由所有degree d 的不可約多項式相乘，d會跑遍所有n的因數。**
        - degree 7 over $GF_2$的不可約多項式，有$(2^7-2)/7=18$個
        - degree 9 over $GF_2$的不可約多項式，有$(2^9-6-2)/9=56$個
        - 考慮$x^{2^k}-x$分解，就可以得到不可約多項式的個數
    - 定理：給定 p 是質數及 n ，存在degree n的不可約單項式 $f(x)\in GF_p[x]$
        - $GF_5[x]/<x^2+3>=<x+3>$
        - $GF_5[y]/<(y+2)^2+3>=<y>$(已知generator，可以快速找到primitive polynomial)
            - $(x+3)^8=2x+2$
            - $(x+3)^{12}=4$
            - $(x+3)^{24}=1$
    - **要檢查群 G 中一個元素 a 是否為 generator，只要將 |G|直因數分解，並看對應的次方是否為1。**
        - EX：$|GF_{25}^*|=24=2^3*3$
        - $GF_{25}^*$中的任何元素a，只要檢查12次方以及8次方是否為1即可
    
### Ch1 Introduction
- 歷史
    - 1976年前：都是對稱式密碼系統
    - 1976年：Diffie, Hellman, Merkle 公鑰密碼系統
- ![](https://i.imgur.com/m410fIE.png)
- **Symmetric Cryptography 對稱密碼系統:**
    - 又稱為private key， single key， secret key cryptography
        - $y=e_K(x)$
        - $x=d_K(y)$
    - 把加密問題轉換成，Key的傳遞與保存問題
    - Key(金鑰) Space的大小與安全性
        - **Short Term ： Key Space 的 size 至少要 $2^{80}$**
        - **Long Term ： Key Space 的 size 至少要 $2^{128}$**
- Cryptanalysis 攻擊
    - **Kerckhoff's Principle**
        - 就算所有密碼學演算法都被攻擊者知道，只要key不被敵人知道，密碼系統就是安全的。
        - 只使用公開數年，且被許多密碼學專家研究得密碼系統。
    - 種類
        - Classical Cryptanalysis：暴力攻擊，數學分析。
        - Implementation Cryptanalysis：實作造成的漏洞。(電磁波、逆向工程)
        - Social Engineering：
        - Differential cryptanalysis 差分攻擊
            - 當input改變時，output的變化
        - Linear cryptanalysis 線性攻擊
            - 找一個input到output間的近似Linear function
- Substitution Cipher替換式密碼：
    - $26!\approx 2^{88}$
    - 大大增加key space的大小
        - 不會被窮舉替換可能性，所產生Brute-Force暴力攻擊
        - 但會被使用Frequency Analysis頻率分析
- **Shift (or Caesar) Cipher and Affine Cipher**
    - Caeasr Cipher凱撒密碼：
        - Key space只有26種
            - $y = x + k~mod~26$ 
            - $x = y - k~mod~26$
    - Affine Cipher仿射密碼：
        - Key space有 $12\times26$ 種 (a有12種可能性)
            - $y = ax + b~mod~26$ 
            - $x = a^{-1}(y-b)~mod~26$
- [Fiestal Cipher](https://zh.wikipedia.org/wiki/%E8%B4%B9%E6%96%AF%E5%A6%A5%E5%AF%86%E7%A0%81)
- **Stream Cipher**
    - RC4
    - Trivium
- **Block Cipher**
    - DES/3DES, IDEA, RC5, Blowfish, SMS4
    - AES(Rijndael), Serpent, Twofish, RC6, Mars
### Ch2 Stream Ciphers
- Stream Ciphers
    - 對每一個bit單獨作加密的動作，第i個bit用$S_i$來決定要不要變換
        - $y_i=x_i+S_i~mod~2$
        - $x_i=y_i+S_i~mod~2$
    - $s_i$應該要random，否則容易被攻擊
        - Synchronous：key和密文無關
        - Asynchronous：key和密文有關
    - Stream Ciphers 的Performance通常比 Block Ciphers好很多
- Random number generators
    - TRNG：不容易被攻擊，但雙方難以同步
    - PRNG：容易同步，但容易被攻擊
        - 只要知道$S_1, S_2, S_3$就可以知道$S_{i+1}=AS_i+B~的A和B$
    - CSPRNG：看到部分output，無法推算其他output
        - unpredictable的PRNG
- Unconditionally Secure(無條件安全)：
    - 就算用無窮的時間與計算能力，也無法推出明文為何
    - EX：OTP(一次性密碼本)
- LFSR (線性反饋移位暫存器)
    - 攻擊者只要知道$2L$個值，就可以透過解線性方程組得知所有sequence
    - 最大period：$2^L-1$
    - ![](https://i.imgur.com/4FAWwR2.png)
    - Matrix Representation，可以參考投影片
    - **Connection Polynomial：課本和投影片寫法不一樣，都可以**
        - $C_L=0$，一開始不一定循環，終究會循環
        - $C_L=1，一開始就一定循環
            - $C(X)$ 不可約 ： 週期N滿足 $C(X)|1+X^N$
            - $C(X)$ 可約 ： 週期為$2^L-1$
    - Linear Complexity
        - $S=s_0s_1s_2...$
        - $L(S)=$ the length of shortest LFSR that generates $S$
- [Crypto-1](https://en.wikipedia.org/wiki/Crypto-1)
    - ![](https://i.imgur.com/mmSKaUc.png)
    - 48-bit LFSR + 20 to 1 nonlinear function + 16-bit LFSR
    - **The security of this cipher is ... close to zero**
- [Trivium](https://zh.wikipedia.org/wiki/Trivium_(%E7%AE%97%E6%B3%95))
    - ![](https://i.imgur.com/L1epg9L.png)
    - ![](https://i.imgur.com/lbhRDSV.png)
    - C. De Canniere, Bart Preneel 設計
    - 出於硬體效率而設計的對稱式Stream Cipher
    - 3 NonLinear FSR

- [RC4](https://zh.wikipedia.org/wiki/RC4)
    - 產生S-box
        - ![](https://i.imgur.com/bM5xKmV.png)
    - 用S-box產生key stram
        - ![](https://i.imgur.com/Yq6j8e9.png)
    - Ron Rivest設計
    - 用在TLS、SSL、WEP
    - 演算法：
        - 第一步驟：算出key stream
        - 第二步驟：根據key stream把明文 XOR 成密文
    - 攻擊：
        - 第二byte是0的機率為1/128(而非1/256)
        - 前幾個byte被發現是non random
        - 可以透過drop開頭部位的Key stream來避免以上情形
### Ch3 DES
- Confusion and Diffusion ： Claude Shannon提出
    - Confusion混淆：透過substitution，消除密文和金鑰的關係
    - Diffusion擴散：透過bit permutation，消除明文和密文的關係，明文中任何小更動會使密文有很大差異
- DES
    - IBM提出
        - Block size：64bits
        - Key size：56bits
        - $L_i=R_{i-1}$
        - $R_i=L_{i-1}\oplus f(R_{i-1},k_i)$
    - ![](https://i.imgur.com/FBOLLnc.png)
    - 前後的Permutation
        - ![](https://i.imgur.com/ah7G5XQ.png)
    - f-Function 的處理
        - 1.32bits Expand 成48 bits
            - ![](https://i.imgur.com/UH5kAt6.png)
        - 2.48 bits 和k做XOR
            - k來自key的處理
        - 3.S-box substitution
            - 8個S-box
                - ![](https://i.imgur.com/4rqjONB.png)
                - 把6 bits input變成4 bits output
                - 頭尾2 bits查row，中間4 bits查col
            - 抵擋 differential cryptanalysis
            - 抵擋 linear cryptanalysis
        - 4.Permutation $P$
            - ![](https://i.imgur.com/Jlwx1WE.png)
            - 32 bits再查表後Output
            - 五個回合後，就有雪崩效應，y和所有64bit xi有關
    - Key 的處理
        - 64bits key 首先透過PC-1變成56 bits
            - ![](https://i.imgur.com/L1CojbG.png)
            - **所以key就是56 bits，不太安全**
            - 每個byte的最後一個bit，用來parity check
            - byte中的8個bit，XOR起來為零
        - 重複16回合，把56 bits分成兩半C和D，獨立操作
            - i=1, 2, 9, 16：左移1 bit
            - 其他回合：左移2 bits
        - 把56bits經過PC-2變成當回合的key，48 bits.
            - ![](https://i.imgur.com/XC1ZaDg.png)
        - **注意到$C_0=C_{16},D_0=D_{16}$**
        - **每回合的key，都只是k的某一種排列**
    - 解密Decryption
        - $R_{i-1}=L_i$
        - $L_{i-1}=R_i\oplus f(L_i,k_i)$
        - Key的處理只要把左移換成右移即可
    - Security of DES
        - Key space = $2^{56}$ is small
        - Analytical Attacks：基本上是不可行
        - Exhaustive key search：現代電腦蠻容易可以破解
        - 2-DES：基本上安全性沒什麼進步
        - 3-DES：大約112位元複雜度。
            - $y=DES_{k3}DES_{k2}^{-1}DES_{k1}(x)$
            - k1=k2=k3時，可以涵蓋一般DES
            - 常用形式為，k1=k3≠k2
### Ch4 AES
- AES
    - Block size為 128 bits
    - key size為 128/192/256 bits
    - 在$GF_2(2^8)$中，XOR等於是做加法。
        - 1997 NIST決定要選出新block cipher
        - 1998 15 candidates
        - 1999 5 finalist
            - Rijndael、Serpent、Twofish、RC6、Mars
    - **Byte Oriented，軟體、硬體Efficient**
- ![](https://i.imgur.com/OatfJX9.png)
- Galois Field
    - 兩元素相乘可以透過查表兩次
        - $A\times B=g^a\times g^b=g^{a+b}$
        - 先查對數表得到$a、b$，在查指數表
    - 使用$m(x)=x^8+x^4+x^3+x+1$
        - $\alpha+1$是generator
            - $(\alpha+1)^{15}\ne1，(\alpha+1)^{51}\ne1，(\alpha+1)^{85}\ne1$
            - $(\alpha+1)^{255}=1$
    - 根據以上知道指對數表要以$\alpha+1$為基準
        - 指數表中第三格表示$(\alpha+1)^3=\alpha^3+\alpha^2+\alpha+1$，因此為15
        - 對數表中第五格表示$\alpha+1$幾次方可以得到$\alpha^2+1$，因此為2
- 演算法
    - 1.Byte substitution
        - ![](https://i.imgur.com/3YkGW3G.png)
        - 查的是同一張表
        - AES中唯一非線性
            - $f(A+B)\ne f(A)+f(B)$
            - 出現在找反元素之中
        - 建立此表的方式為
            - ![](https://i.imgur.com/6yRuLNP.png)
            - ![](https://i.imgur.com/sUkbTOx.png)
            - 對每一個元素，先去找他在$GF_{256}$的反元素，再透過一個Affine Transformation
                - ![](https://i.imgur.com/HzAnPwD.png)
                - 定義$0^{-1}=0$
    - 2.Shift Row
        - ![](https://i.imgur.com/8TIb8Au.png)
        - 線性運算，打亂column之間關係
            - 否則變成4個32bits column獨立加密
    - 3.Mix Column
        - ![](https://i.imgur.com/zeubTAI.png)
        - 每一個column當成$GF_{2^4}$的多項式，先乘以c(x)，再Module $x^4+1$
        - $b_3x^3+b_2x^2+b_1x+b_0=(a_3x^3+a_2x^2+a_1x+a_0)(3x^3+x^2+x+2)$
        - 整理結果如下
        - ![](https://i.imgur.com/eSavIro.png)
    - 4.Add Round Key
        - 和 key 做XOR
- Key Schedule
    - 每一回合最後一個運算一定是Add Round Key，否則在做白工
    - ![](https://i.imgur.com/4t7QNzh.png)
    - ![](https://i.imgur.com/bxnMCy6.png)
    - The round coefficient RC 
        - ![](https://i.imgur.com/E7U0z8q.png)
- 解密Decryption
    - Mix Column
        - ![](https://i.imgur.com/QUZsWfZ.png)
        - [Hamming Weight](https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F) 很大，一定要做乘法，
            - 比加密沒效率，這是AES缺點
    - Key schedule
        - 實務上，加密和解密都先把所有key產生好
        - 最後把反著順序使用key
- 實務
    - Security
        - 暴力攻擊：128bits以上的key，不可能被攻擊
        - 分析攻擊：目前沒有線性攻擊或插分攻擊
        - 旁通道攻擊：
            - 可能可以破AES
            - 要看如何implement，和演算法本身無關
### Ch5 Block
- Goal
    - 使用者認證(authenticity)，是否來自對方
    - 完整性(integrity)，傳送過程是否有被修改
- ECB 電子密碼本 Electronic Code Book
    - ![](https://i.imgur.com/G8iiXl8.png)
    - 每一個block獨立被加解密
        - $y=e_k(x)$
        - $x=e_k^-1(y)$
    - 基本上任何情況下，都不要用ECB mode。
    - 優點：
        - 容易平行化
        - 不用block synchronization
    - 缺點：
        - 攻擊者可以操作block順序、重送兩次等
        - 如果明文一樣，密文就會一樣。Substitution Attack。
        - 如果一個位元錯誤，一個block都會出錯。
- CBC 密碼塊連結 Cipher Block Chaining
    - ![](https://i.imgur.com/MMjDIak.png)
        - $y_i=e_k(x_i\oplus y_{i-1})$
        - $x_i=e_k^{-1}(y_i)\oplus y_{i-1}$
    - IV 是公開的每次不同的值。
        - 或是也可以IV = nounce $\oplus$ k，然後傳送nounce。
        - IV 不需要藏起來，可以跟密文一起傳送
    - 優點：
        - 可推廣到一次加密 m 個block
    - 缺點：
        - 如果一個位元錯誤，一個block+一個位元都會出錯
        - 加密不行平行化，解密可以平行化
- OFB 輸出反饋 Output Feedback mode
    - ![](https://i.imgur.com/klQxeSV.png)
    - 可視為，用 IV 產生stream cipher的key stream
    - 優點：
        - 兩方可以事先產生key，適合大量及時加密。
        - 如果一個位元錯誤，只有一個block都會出錯。
    - 缺點：
        - 完全沒有用到AES解密運算。
        - 兩方需要對齊。
- CFB 密文反饋 Cipher Feedback mode
    - ![](https://i.imgur.com/XYZpLNY.png)
    - key stream 除了跟 IV 有關，也跟明文有關
    - 優點：
        - 自同步(self synchronization)
        - 出錯後一段時間，仍會自動對齊
    - 缺點：
        - 加密不行平行化，解密可以平行化。
- CTR 計數器模式
    - ![](https://i.imgur.com/gj3wCbo.png)
    - 明文依序和加密後的IV做XOR。
    - 優點：
        - 可以抵擋攻擊者交換block
        - **加密和解密都非常容易平行化。**
- GCM Galois計數器模式 $GF_{2^{128}}$
    - ![](https://i.imgur.com/2dJGh0A.png)
    - 除了一般的CTR，還多紀錄了T，用來認證身分
    - 優點
        - Message Authentication
        - Message Integrity
    - 缺點
        - 複雜
- 可能需要padding，因此密文可能比明文長。
- 暴力攻擊(Exhaustive Key Search)
    - $DES_{k_i}(x_1)=y_1$
    - 實際上只有一把key是對的，但有多把key都會滿足上方等式：false positive result
    - Example：
        - block size ： 64bits
        - key size ： 80 bits
        - 平均有$2^{16}=65536$把key可以滿足$DES_{k_i}(x_1)=y_1$
        - false key期望值為$2^{k-tn}$，所以只要2組(明文,密文)，就會被攻擊，$2^{80-2*64}\sim 0$
- 增加Block Cipher安全性
    - Double Encryption
        - ![](https://i.imgur.com/LCH6Y4y.png)
        - 一般暴力搜尋法：要搜尋$2^k2^k=2^{2k}$ operation
    - Meet-in-the-Middle Attack
        - ![](https://i.imgur.com/JeCMuWS.png)
        - 用空間換取時間，大約需要$2^k+2^k=2^{k+1}$ operation：
            - 暴力搜尋明文用 $2^k$ 種 key 加密成 z，並儲存起來
            - 暴力搜尋密文用 $2^k$ 種 key 解密，看看有沒有和以上表格發生碰撞
        - 因此Double Encryption，安全性跟一般encryption沒有差多少
        - **DES用前8回合、後8回合，不會被meet in the middle攻擊**
            - 因為前8回合、後8回合都一樣要用到 56 bit 的key
    - Triple Encryption
        - ![](https://i.imgur.com/6XwEV66.png)
        - 用meet in the middle，大約需要$2^k+2^{2k}=2^{2k}$ operation
    - Key Whitening
        - ![](https://i.imgur.com/BC8XSXs.png)
        - $key=(k_1,k,k_2)~~~y=e_k(x\oplus k_1)\oplus k_2$
        - 可以抵擋暴力攻擊，但無法抵擋線性攻擊跟差分攻擊
### Ch6 Public Key
- 對稱式密碼系統
    - ![](https://i.imgur.com/MCu1tex.png)
    - Key Distribution Problem
    - Number of keys ： n個人，要有 $\frac{n^2-n}{2}$ 把keys
    - 因為雙方有相同key，訊息在雙方之間可以耍賴
- 公鑰密碼系統
    - ![](https://i.imgur.com/ji3XbC5.png)
    - 很不自然，1976年才被提出。(密碼學發展已2000多年)
    - Key generation：通常都是先產生私鑰，再產生公鑰。
    - 解決了key distribution問題
        - key authentication，公鑰可能會被攻擊者掉包
    - 功用：
        - 1.用來傳送AES或DES的key，解決key distribution問題
            - **因為非對稱式密碼系統慢1000倍以上**
        - 2.不可否認性和數位簽章
        - 3.身分認證
        - 4.加解密內容(很少用)
    - ![](https://i.imgur.com/N9Xm1tU.png)
        - 1.公鑰密碼系統傳送key，再用對稱式密碼系統傳送data
        - 2.注意到 hybrid system 安全性，取決於最弱的 key space
- 常見公鑰密碼系統演算法
    - 目標是找到單向函數 one way function $f()$
        - 質因數分解 (RSA...)
            - $n=pq$
        - 離散對數問題 (Diffie-Hellman, Elgamal, DSA, …)
            - $a^x=y~mod~m$
        - 橢圓曲線 (ECDH, ECDSA)
            - generization of 離散對數問題，更短的key達到一樣安全性
    - 安全性|RSA, DL|ECC|附註
      -|-|-|-
      64bit|700bit|128bit|short term(數小時)
      80bit|1024bit|160bit|medium term
      128bit|3072bit|256bit|long term(量子電腦)
      256bit|15360bit|512bit|long term
- **數論工具**
    - Euclidean Algorithm
    - Extended Euclidean Algorithm
    - Euler’s Phi Function
    - Fermat’s Little Theorem
        - $a^{p-2}$為乘法反元素，不怕時間攻擊
    - Euler’s Theorem
### Ch7 RSA
- Ron Rivest、Adi Shamir、Leonard Adleman
- RSA演算法
    - 公鑰：$(n,e)$，私鑰：d
    - 加密：$y=x^e$ mod n
    - 解密：$x=y^d$ mod n
- Key 的產生
    - 1.選定大質數 p, q，算 $n=p\times q$
    - 2.$\phi(n)=(p-1)(q-1)$
    - 3.選定 $e$ 和 $\phi(n)$ 互質
    - 4.計算 $d$ 使 $d\times e=1$ mod $\phi(n)$，**可換成 LCM(p-1,q-1)**
    - 5.『 公鑰：$(n,e)$，私鑰：d 』
- Proof of $x^{ed}=x$ mod $n$ **( LCM(p-1,q-1) )**
    - 我們知道 $ed=1+k\phi(n)$
    - gcd(x,p)=1或p ， gcd(x,q)=1或q ， 因此
        - $x^{ed}\equiv x$ mod $p$
        - $x^{ed}\equiv x$ mod $q$
    - By 中國剩餘定理，$x^{ed}\equiv x$ mod $pq$
- 加速 $x^e$ mod n 過程(都是 t bits)：
    - 1.平方求冪 double and add
        - ![](https://i.imgur.com/BNk7nNB.png)
        - ![](https://i.imgur.com/IvfcRAn.png)
    - 2.挑選合適的e
        - ![](https://i.imgur.com/OVlSIE0.png)
    - 3.中國剩餘定理CRT
        - 不行apply在加密，因為 p,q 是private的
        - 目標：$y=30^{20}~mod~77$
        - Step1：
            - $y_7=30~mod~7^{20~mod~6}=2^2=4 ~~ mod~7$
            - $y_{11}=30~mod~11^{20~mod~10}=8^0=1 ~~ mod~11$
        - Step2：
            - $y=a_1M_1x_1+a_2M_2x_2$
            - $=4\cdot 11\cdot 2+1\cdot 7\cdot 8$
            - $=88+56=67$ mod 77
        - **4倍快**
            - $aaaa^{bbbb}$ mod cccc
            - $aa^{bb}$ mod cc + $aa^{bb}$ mod cc
- 如何找大質數
    - 質數定理 prime number theorem
        - 小於等於 N 的質數約有 N/logN 個
        - 全宇宙原子數約有 $2^{266}$， 512 bits 的 prime numbers 約有 $2^{503}$
        -  小於等於 N 的隨機數，是質數的機率約為 1/logN
    - 費馬質數判定 Fermat’s Test
        - $a^{N-1}\ne 1$ mod N
            - 則 N 不是質數
            - a 是witness
        - Carmichael Numbers
            - $a^{560}=1$ mod 561
    - 米勒拉賓質數判定 Miller-Rabin Test
        - 演算法
            - $N-1=2^km$, a任意從 { 2,..., N-2} 挑
            - 依序檢查有無 $a^{im}\ne\pm1$ 但 $a^{2im}=1$
        - 成功機率有 3/4
        - 如果存在 $x\ne\pm1$ 且 $x^2=1$ mod n，則 n 不是質數
    - AKS 演算法 in 多項式時間
        - 次數很高且係數很大，實務上不被使用
        - $(x-a)^N=x^N-a$ mod N for gcd(a,N)=1 $\leftrightarrow$ N 是質數
            - 費馬小定理的推廣
    - 質因數分解
        - 要分解 N $\rightarrow$ 找 $x^2=y^2$ mod N $\rightarrow$ $(x-y)(x+y)=0$ mod N
        - 如何找 $x,~y$
            - Continued Fraction
            - Quadratic Sieve
            - Number Field Sieve
### Ch8 離散對數問題
- Diffie–Hellman Key Exchange
    - 1.事先決定 ： 質數 $p$, 任意數 $\alpha$
    - 2.兩人各選一個數字 ： a, b
    - 3.兩人互相傳遞 ： $\alpha^a$, $\alpha^b$ mod p
    - 4.兩人得到key ： $\alpha^{ab}$ mod p
- 離散對數問題DLP
    - 兩個元素 $\alpha,~\beta$，很難找到 $x$ 使得 $\alpha^x=\beta$
        - 給定 ${Z_p}^*$
        - 給定 循環群 $G$
        - 給定 Galois field
        - 給定 Hyperelliptic curves or algebraic varieties
    - 離散對數攻擊
        - 1.Brute-Force Search
        - 2.Shanks’ Baby-Step-Giant-Step Method
            - 解 $5^x=219$ mod 307
            - ![](https://i.imgur.com/NfqKkTk.png)
            - $O(\sqrt n)$時間，$O(\sqrt n)$空間
        - 3.Pollard’s Rho ($\rho$) Method
            - $O(\sqrt n)$時間，$O(1)$空間
        - 4.Pohlig-Hellman Method
            - group order可以質因數分解的話，可用CRT解
        - 5.The Index Calculus Method
            - **Non-generic Algorithm**，只可以在 $Z_p^*$ 操作
- Security 
    - DHP $\le$ DLP
    - RSA $\le$ 質因數分解
- The ElGamal Encryption Scheme
    - 1.Bob 決定： ($p,~\alpha,~\beta=\alpha^d$)
    - 2.Alice 傳遞密文及key：($y=x\times\alpha^{di},~k_E=\alpha^i$) 
    - 3.Bob 解密： $x=y\times\alpha^{-di}$
### Ch9 ECC 橢圓曲線密碼學
- 橢圓曲線
    - $y^2=x^3+ax+b$
    - 1.加法運算、Double運算
    - 2.$\theta$表示單位元素，不在橢圓曲線上
    - 3.公式解
        - $s=切線或割線斜率$
        - $x_3=s^2-x_1-x_2$
        - $y_3=s(x_1-x_3)-y_1$
    - Hasse’s Theorem:$\#E=O(p)$
        - mod p下的橢圓曲線的整數點，滿足： $p+1-2\sqrt{p}\le \#E\le p+1+2\sqrt{p}$
    - ECDLP：橢圓曲線版本的離散對數問題
- ECDH
    - 1.事先決定 ： 橢圓曲線 E，基礎點 P
    - 2.兩人各選一個數字 ： a, b
    - 3.兩人互相傳遞 ： aP, bP
    - 4.兩人得到key ： abP=($x_{ab},y_{ab}$)
- Security
    - 目前已知最快演算法只可以在$\sqrt{n}$解出，比RSA強
        - Baby-Step Giant-Step
        - Pollard-Rho method

### Ch10 Signature 數位簽章
- ![](https://i.imgur.com/0tfH224.png)
- Security Services
    - 1.Confidentiality
    - 2.Integrity
    - 3.Message Authentication
    - 4.Non-repudiation
    - 5.Identification/entity authentication
    - 6.Access control
    - 7.Availability
    - 8.Auditing
    - 9.Physical security
    - 10.Anonymity
- RSA：少數加解密跟簽驗章用相同架構的演算法
    - 簽章
        - $s=x^d$
    - 公布
        - (x,s)
    - 驗章
        - 確認是否$x=s^e$
- 攻擊：
    - Existential Forgery，可以用padding來解決
- DSA、ECDSA：
    - 產生key
        - 選1024bit p
        - 選160bit q，可以整除p-1
        - 找出size 為q的子群，$\alpha為生成元$
        - 任意選一個d，0 < d < q
        - $\beta = \alpha^d$ mod p
        - **$k_{pub}$ = (p, q, α, β) , $k_{pr}$ = d**
    - 簽章
        - 1.任意選一個$K_E$，0 < $K_E$ < q
        - 2.計算 $r=\alpha^{K_E}$ mod p mod q
        - 3.計算 $s=(SHA(x)+dr)K_E^{-1}$ mod q
    - 公布
        - **$(x,r,s)$, $k_{pub}$ = (p, q, α, β)**
    - 驗章
        - 1.計算 $w=s^{-1}$ mod q
        - 2.計算 $u_1=w\times SHA(x)$ mod q
        - 3.計算 $u_2=w\times r$ mod q
        - 4.計算 $v=\alpha^{u_1}\times\beta^{u_2}$ mod p mod q
        - 5.確認是否 $v=r$
### Ch11 Hash 雜湊函數
- 把任意長度的字串，對應到固定長度的字串的one way function。
- Avalanche 雪崩效應：input很小改變，output很大改變。
- ![](https://i.imgur.com/IoELCwS.png)
- 演算法
    - MD4 ： 不安全
    - MD5 ： 不安全
    - SHA1 ： 不安全

