# 密碼學

### **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,  gcd(a, b)=gcd(|a|, |b|),  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}$
- 
- 解法一
- $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$
- 
- **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$
- 
- **多項式的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$
- 
- ${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 公鑰密碼系統
- 
- **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$
- 
- 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)
- 
- 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))
- 
- 
- C. De Canniere, Bart Preneel 設計
- 出於硬體效率而設計的對稱式Stream Cipher
- 3 NonLinear FSR

- [RC4](https://zh.wikipedia.org/wiki/RC4)
- 產生S-box
- 
- 用S-box產生key stram
- 
- 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)$
- 
- 前後的Permutation
- 
- f-Function 的處理
- 1.32bits Expand 成48 bits
- 
- 2.48 bits 和k做XOR
- k來自key的處理
- 3.S-box substitution
- 8個S-box
- 
- 把6 bits input變成4 bits output
- 頭尾2 bits查row，中間4 bits查col
- 抵擋 differential cryptanalysis
- 抵擋 linear cryptanalysis
- 4.Permutation $P$
- 
- 32 bits再查表後Output
- 五個回合後，就有雪崩效應，y和所有64bit xi有關
- Key 的處理
- 64bits key 首先透過PC-1變成56 bits
- 
- **所以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.
- 
- **注意到$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**
- 
- 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
- 
- 查的是同一張表
- AES中唯一非線性
- $f(A+B)\ne f(A)+f(B)$
- 出現在找反元素之中
- 建立此表的方式為
- 
- 
- 對每一個元素，先去找他在$GF_{256}$的反元素，再透過一個Affine Transformation
- 
- 定義$0^{-1}=0$
- 2.Shift Row
- 
- 線性運算，打亂column之間關係
- 否則變成4個32bits column獨立加密
- 3.Mix Column
- 
- 每一個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)$
- 整理結果如下
- 
- 4.Add Round Key
- 和 key 做XOR
- Key Schedule
- 每一回合最後一個運算一定是Add Round Key，否則在做白工
- 
- 
- The round coefficient RC
- 
- 解密Decryption
- Mix Column
- 
- [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
- 
- 每一個block獨立被加解密
- $y=e_k(x)$
- $x=e_k^-1(y)$
- 基本上任何情況下，都不要用ECB mode。
- 優點：
- 容易平行化
- 不用block synchronization
- 缺點：
- 攻擊者可以操作block順序、重送兩次等
- 如果明文一樣，密文就會一樣。Substitution Attack。
- 如果一個位元錯誤，一個block都會出錯。
- CBC 密碼塊連結 Cipher Block Chaining
- 
- $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
- 
- 可視為，用 IV 產生stream cipher的key stream
- 優點：
- 兩方可以事先產生key，適合大量及時加密。
- 如果一個位元錯誤，只有一個block都會出錯。
- 缺點：
- 完全沒有用到AES解密運算。
- 兩方需要對齊。
- CFB 密文反饋 Cipher Feedback mode
- 
- key stream 除了跟 IV 有關，也跟明文有關
- 優點：
- 自同步(self synchronization)
- 出錯後一段時間，仍會自動對齊
- 缺點：
- 加密不行平行化，解密可以平行化。
- CTR 計數器模式
- 
- 明文依序和加密後的IV做XOR。
- 優點：
- 可以抵擋攻擊者交換block
- **加密和解密都非常容易平行化。**
- GCM Galois計數器模式 $GF_{2^{128}}$
- 
- 除了一般的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
- 
- 一般暴力搜尋法：要搜尋$2^k2^k=2^{2k}$ operation
- Meet-in-the-Middle Attack
- 
- 用空間換取時間，大約需要$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
- 
- 用meet in the middle，大約需要$2^k+2^{2k}=2^{2k}$ operation
- Key Whitening
- 
- $key=(k_1,k,k_2)~~~y=e_k(x\oplus k_1)\oplus k_2$
- 可以抵擋暴力攻擊，但無法抵擋線性攻擊跟差分攻擊
### Ch6 Public Key
- 對稱式密碼系統
- 
- Key Distribution Problem
- Number of keys ： n個人，要有 $\frac{n^2-n}{2}$ 把keys
- 因為雙方有相同key，訊息在雙方之間可以耍賴
- 公鑰密碼系統
- 
- 很不自然，1976年才被提出。(密碼學發展已2000多年)
- Key generation：通常都是先產生私鑰，再產生公鑰。
- 解決了key distribution問題
- key authentication，公鑰可能會被攻擊者掉包
- 功用：
- 1.用來傳送AES或DES的key，解決key distribution問題
- **因為非對稱式密碼系統慢1000倍以上**
- 2.不可否認性和數位簽章
- 3.身分認證
- 4.加解密內容(很少用)
- 
- 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
- 
- 
- 2.挑選合適的e
- 
- 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
- 
- $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 數位簽章
- 
- 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很大改變。
- 
- 演算法
- MD4 ： 不安全
- MD5 ： 不安全
- SHA1 ： 不安全