---
# System prepended metadata

title: Cryptography and network security - NOTE
tags: [大三下]

---

# Cryptography and network security - NOTE 

## Lecture 2 Basic Number Theory

### 2.1 整數算術
* 整數集合，標記為𝑍: 從負無窮大到正無窮大的所有整數
* 三種作用在整數集合上的二元運算
    >![image](https://hackmd.io/_uploads/HkfjCJFgA.png)
* 整數的除法演算法
    >![image](https://hackmd.io/_uploads/ryeJylFl0.png)
    >---
    >讓負餘數變正的方法: ![image](https://hackmd.io/_uploads/S1CxbxYe0.png)
    >---
    >整除符號:13|78, 7|98, −6|24, 4|44以及11|(−33)
    >不整除:13∤27, 7∤50, −6∤23, 4∤41以及11∤(−32)
    >---
    >整除性質:
    >性質1：若𝑎|1，則𝑎=±1。
    >性質2：若𝑎|𝑏且𝑏|𝑎，則𝑎=±𝑏。
    >性質3：若𝑎|𝑏且𝑏|𝑐，則𝑎|𝑐。
    >性質4：若𝑎|𝑏且𝑎|𝑐，則𝑎|(𝑚×𝑏+𝑛×𝑐)，其中𝑚和𝑛為任意整數。
* 因數(Divisor)
    >除了1以外，任何整數至少有2個因數，1 和它自己（但也可能有更多其他因數）
* 歐幾里德演算法(求gcd)
    >![image](https://hackmd.io/_uploads/rJJVQlYlA.png)
    >---
    >ex: 試求2740 和1760 的最大公因數
    >解法：我們得到gcd(2740,1760) =20
    >![image](https://hackmd.io/_uploads/HkgKExteA.png)
* 歐幾里德延伸演算法
    >同時計算出gcd(𝑎,𝑏)以及𝑠和𝑡的值
    >![image](https://hackmd.io/_uploads/BJ_h4xte0.png)
    >![image](https://hackmd.io/_uploads/rkGTVxKlR.png)
    >ex: 給定𝑎=161和𝑏=28，求出gcd(𝑎,𝑏)以及𝑠和𝑡的值
    >解法：我們得到gcd(161,28)=7，𝑠=−1和𝑡=6
    >![image](https://hackmd.io/_uploads/S1zgSgKlR.png)

* 互質(Relatively Prime)
    >gcd(𝑎,𝑏) = 1時，我們說𝑎和𝑏為互質

* 線性Diophantine方程式
    >雙變數之Diophantine方程式是一種形態為a𝑥+𝑏𝑦=𝑐的線性不定方程式
    >𝑑 = gcd(𝑎,𝑏)
    >特解：
    >x0 = (𝑐/𝑑)𝑠 和 𝑦0 = (𝑐/𝑑)t
    >通解：
    >x = 𝑥0 + 𝑘(𝑏/𝑑) 和 𝑦 = 𝑦0 − 𝑘(𝑎/𝑑)
    >ex:通解會用到特解 => 先解出特解
    >![image](https://hackmd.io/_uploads/rJFG_xYeA.png)

### 2.2 模數算術
![image](https://hackmd.io/_uploads/ry__dlFxA.png)

* 負數
    >ex: -18 mod 14 => r = -4 => r = 10
    >ex: -7 mod 10 => r = -7 => r = 3
* 餘數集合：Zn
    >模𝑛之最小餘數集合
    >![image](https://hackmd.io/_uploads/r1rM5eFxA.png)

* 剩餘類(Residue Class)
    > [𝑎] 或 [a]n => 模𝑛之下所有餘數為𝑎的整數集合
    > ![image](https://hackmd.io/_uploads/SJO29xFgA.png)

* Zn中的二元運算
    >![image](https://hackmd.io/_uploads/ry5mjetx0.png)

* 同餘(Congruence)
    -8 ≡ 12 (mod 10)
    2 ≡ 12 (mod 10)
    >剩餘類(Residue Class): [0] = {...,-5,0,5,...} 模完餘數一樣的放在一起
* 加法反元素(Additive Inverse)
    **a + b ≡ 0 (mod n)**
    模數運算中, 每個整數都有加法反元素 
    >ex: 𝑍~10~中所有互為加法反元素的數對
    >(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), 和 (5, 5)
* 乘法反元素(Multiplicative Inverse)
    **a x b ≡ 1 (mod n)**
    一個整數不一定有乘法反元素
    >ex: 8在Z~10~中的乘法反元素 => 不存在, gcd(10,8) = 2  (要互質才存在)
    >ex: 求Z~10~中所有乘法反元素 => (1,1),(3,7),(9,9)
    >ex: 求Z~11~中所有乘法反元素 => (1,1),(2,6),(3,4),(5,9),(7,8),(10,10)
* 利用歐幾里德延伸演算法來求出乘法反元素
    >ex:12在Z~26~中的乘法反元素: 不存在 因為不互質 gcd(12,26) = 2
    >![image](https://hackmd.io/_uploads/Hyh4Z-tlA.png)
* 集合
    >當需要加法反元素時，我們使用集合Z~n~
    >當需要乘法反元素時，我們使用集合Z~n*~ (跟n互質的)

### 2.3  矩陣
![image](https://hackmd.io/_uploads/S1bP4ZYe0.png)



* 行列式(determinant) 
    >det(𝐴)
    >![image](https://hackmd.io/_uploads/ByFqEbtgC.png)
    >只有方陣有行列式
    >![image](https://hackmd.io/_uploads/H1gNrZYxA.png)
* 反矩陣(Inverse Matrix)
    >乘法反矩陣只在方陣有定義
    >![image](https://hackmd.io/_uploads/SkxIBbtgA.png)
* 餘數矩陣(Residual Matrix)
    >所有元素皆定義在𝑍𝑛中的矩陣
    >gcd(det(𝐴),𝑛) = 1，則該餘數矩陣具有乘法反矩陣

### 2.4 線性同餘
* 單變數線性方程式
    >𝑎𝑥 ≡ 𝑏 (mod 𝑛) 可能為無解或是有限個數的解
    >若 𝑑 = gcd⁡(𝑎,𝑛) 整除 𝑏，則存在 𝑑 個解 
    > • 如果𝑑∤𝑏，則無解。
    > • 如果𝑑|𝑏，則有𝑑個解。
    >![image](https://hackmd.io/_uploads/r1diU-Kx0.png)
    >
    >---
    >![image](https://hackmd.io/_uploads/SyWd-XuA6.png)
    >
    >---
    >
    >ex: 解出方程式 14x ≡ 12(mod 18) => ![image](https://hackmd.io/_uploads/BkssbQdRT.png)
    >ex: 3x+4 ≡ 6(mod 13) => 3x ≡ 2(mod 13) => x ≡ 2*3^-1^(mod 13) ≡ 2*9(mod 13) ≡ 5 => d=gcd(3,13)=1 => 因為d|b ,so 1個解 => 就是5
    >
    >---
    >ex: 看作業內容比較快
    >![image](https://hackmd.io/_uploads/ryXE_btx0.png)
    >
    >---
    >![image](https://hackmd.io/_uploads/HkiV_bteA.png)
    >
    >---
    >特別的:中國餘數定理
    >![image](https://hackmd.io/_uploads/H1WZKZKlA.png)


## Lecture 3 Classical Encryption Techniques

### Symmetric Encryption
>對稱式金鑰(Symmetric Key)：以同一把金鑰來加密或解密
>![image](https://hackmd.io/_uploads/Sk-TtWYx0.png)
>![image](https://hackmd.io/_uploads/rkJRKWtxR.png)

### Techniques of Classical Ciphers
![image](https://hackmd.io/_uploads/H1dbcbFlA.png)

* Substitution Techniques
    * Monoalphabetic Cipher(單字母加密)
        >明文用小寫字體，密文則用大寫字體
        >![image](https://hackmd.io/_uploads/ByucqWKxR.png)
        >加法加密法(Additive Cipher)
        > => 此加密法有時稱為位移加密法(Shift Cipher)
        > => 凱撒加密法(Caesar Cipher)
        
        * Caesar Cipher
            >其明文、密文和金鑰都是Z~26~中的整數
            > 𝑓(𝑎) = (𝑎+𝑘) mod n
            > 𝑎 =該字在字集中原先位置；𝑘=移動的位置；𝑛=此字集的大小
            >![image](https://hackmd.io/_uploads/S1SkobKlR.png)
            >![image](https://hackmd.io/_uploads/SJGT0bYeA.png)
            >加密用加法
            >![image](https://hackmd.io/_uploads/BJcM1MKx0.png)
            >解密用減法
            >![image](https://hackmd.io/_uploads/HkPHJfFeR.png)

        * Multiplicative Cipher(乘法加密法)
            >明文和密文都是𝑍~26~的整數；金鑰為一個𝑍~26∗~的整數
            >![image](https://hackmd.io/_uploads/Sy26JGKl0.png)
            >![image](https://hackmd.io/_uploads/ryZggMKeR.png)


        * Affine Cipher(仿射加密法)
            >加密:
            >![image](https://hackmd.io/_uploads/H1TNlGteA.png)
            >解密:
            >![image](https://hackmd.io/_uploads/Bk3_lfKgC.png)

        * Monoalphabetic Substitution Cipher(單字母取代加密法)
            >![image](https://hackmd.io/_uploads/SJv8-fKxR.png)


    * Polyalphabetic Ciphers(多字母加密法)
        >明文裡的一個字元和密文裡的一個字元之間的關係是一對多
        
        * Autokey Cipher(自動金鑰加密法)
            >往右平移並加起來 mod 26
            >![image](https://hackmd.io/_uploads/HkmEGfKxC.png)

        * Playfair Cipher(普萊費爾密碼)
            >Best-known multiple-letter encryption cipher
        * Vigenère Cipher(維吉尼亞密碼)
            >Vigenère cipher 可視為 𝑚 個加法加密法的組合
            >Caesar cipher 可視為 Vigenère cipher 在 𝑚 = 1 時的特例
            >![image](https://hackmd.io/_uploads/SJ8FXfKlR.png)
        * Hill Cipher(希爾密碼)
            >看作業
        * One-Time Pad(OTP)
            >Shannon的研究表示，每個明文的符號都由一個金鑰範圍隨機挑出的一把金鑰加密
            >**Gilbert Vernam** 在貝爾實驗室所發明的一次性密碼本
            >每個新訊息都需要一個與訊息長度相同的新金鑰
            >![image](https://hackmd.io/_uploads/Hy-THztlC.png)
            >一次性密碼本是唯一具有完美保密性的密碼系統
            >但是有兩個根本困難：
                • 存在製作大量隨機密鑰的實際問題
                • 任何頻繁使用的系統可能需要定期使用數百萬個隨機字符
            
* Transposition Ciphers(換位加密法)
    >改變符號的位置

    * 無金鑰的換位加密法(Transposition Ciphers without Key)
        * 反轉換位加密法
            >就倒過來寫XD
            >![image](https://hackmd.io/_uploads/SJWK8MFxR.png)
        * 鐵軌栅欄加密法(Rail Fence Cipher)
            >交叉寫 然後寫完上排再寫下排
            >![image](https://hackmd.io/_uploads/rJC2UGKlC.png)
        * 使用行數的換位加密法
            >橫著進去 豎著出來
            >可以協議以四行(或隨便幾行)為一個單位
            >![image](https://hackmd.io/_uploads/SkxevMFgA.png)

    * 有金鑰的換位加密法(Transposition Ciphers with Key)
        * 行換位加密法(Columnar Transposition Cipher)
            >橫著進去 換個排列順序 豎著出來
            >![image](https://hackmd.io/_uploads/rJUIwzKxR.png)
            >解密的話:
            >站著進去 躺著出來
            >![image](https://hackmd.io/_uploads/rkkldzKlR.png)
            >key可以用矩陣表示
            >![image](https://hackmd.io/_uploads/SJ8uOztlA.png)


### Block and Stream Ciphers
* Classical Block Cipher(區塊加密法)
    * Playfair Cipher 區塊大小為𝑚 =2，兩個字元一起被加密
    * Hill Cipher 單一金鑰(矩陣)一起加密一個大小為2或更多的明文區塊
* Classical Stream Cipher(串流加密法)
    * 單字母取代加密法
    * Vigenère Cipher 

## Lecture 4 Finite Fields

### 4.1 代數結構(Algebraic Structure)
群(Group)、環(Ring)、體(Field)等三個常用的代數結構
![image](https://hackmd.io/_uploads/BkrSqfFlA.png)

* 群（Group）
    * 封閉性(Closure): 元素𝑎和𝑏，運算𝑎•𝑏的結果也在𝐺中
    * 結合性(Associativity): 等式(a•𝑏)•𝑐=𝑎•(𝑏•𝑐)成立
    * 存在單位元素(Identity Element): 存在集合𝐺中的一個元素𝑒使等式𝑒•𝑎=𝑎•𝑒=𝑎成立
    * 存在反元素(Inverse Element): 存在一個𝐺中的元素𝑏，使得𝑎•𝑏=𝑏•𝑎=𝑒，其中這裡的𝑒是單位元素

* 交換群（Commutative Group)(Abelian Group): 
    * 交換性(Commutative)：對於集合𝐺 中所有的元素𝑎和𝑏，皆滿足等式a•𝑏 =𝑏•a
    
:::info
群的概念:
![image](https://hackmd.io/_uploads/H1lIsZ5gR.png)
ex: G=<𝑍𝑛,+> 是一個交換群
ex: G=<𝑍𝑛∗,×> 也是
:::
* 排列群（Permutation Group）
    >所有排列方式的集合
    >可合成（Compositional）的
    
    * 這張表是排列群的運算方法
        >![image](https://hackmd.io/_uploads/BkNIT-5xR.png)
    * 然後這是他的總表(就是各種組合出的結果)
        >![image](https://hackmd.io/_uploads/ByZyeG5xC.png)

    
* 子群
    * ![image](https://hackmd.io/_uploads/r1sL1M9lR.png)
* 循環子群（Cyclic Subgroup）
    >乘冪的意思是重複對這個元素引用群運算
    >a^𝑛^ → 𝑎 • 𝑎 •⋯• 𝑎（𝑛次）
    >像作業題目:
    >![image](https://hackmd.io/_uploads/ByQnkM9gC.png)
    >![image](https://hackmd.io/_uploads/rJsh1M9xC.png)

* 循環群（Cyclic Group）
    >一個群為本身的循環子群
    >本身能由其單個元素所生成
    >令𝑔為一個循環群𝐺的生成子（Generator），則 𝐺={𝑒,𝑔,𝑔^2^,…,𝑔^𝑛−1^}，其中𝑔^𝑛^=e
    `每個循環群都是Abelian Group，滿足運算的交換性`
    * 群𝑮=<𝒁~6~,+>為一個含兩個生成子**𝑔=1和𝑔=5**的循環群
        >![image](https://hackmd.io/_uploads/BJXVZMqeR.png)

    * 群 𝑮=<𝒁~10∗~,×> 為一個含兩個生成子**𝑔=3和𝑔=7**的循環群
        >![image](https://hackmd.io/_uploads/Hyb8ZG9gA.png)

* 元素的階(Order)
    >這個元素所生成之循環群的基數(Cardinality)，也就是其元素的個數
    >𝑟𝑎𝑛𝑘(G)=1 if and only if 𝐺 是一個循環群
    >![image](https://hackmd.io/_uploads/ryIbGfqg0.png)
* Lagrange 定理
    >假設有一群𝐺，𝐻為其子群(𝐻⊆𝐺)，令𝐺和𝐻的秩分別為|𝐺|和|𝐻|。根據Lagrange 定理，**|𝐻|會整除|𝐺|**
    
    * 在群𝐺=<𝑍~6~,+>中，個別元素的階(Order)為：𝑜𝑟𝑑(0) = 1，𝑜𝑟𝑑(1) = 6，𝑜𝑟𝑑(2) = 3，𝑜𝑟𝑑(3) = 2，𝑜𝑟𝑑(4) = 3，𝑜𝑟𝑑(5) = 6
        >![image](https://hackmd.io/_uploads/BkVlXGqgR.png)
    * 在群𝐺=<𝑍~10∗~,×>中，個別元素的階為：𝑜𝑟𝑑(1) = 1，𝑜𝑟𝑑(3) = 4，𝑜𝑟𝑑(7) = 4，𝑜𝑟𝑑(9) = 2
        >![image](https://hackmd.io/_uploads/Skc-J4neR.png)


* 環（Ring）
    一個集合和兩種二元運算所構成的代數結構，記作 R = <{…}, •, □>
    ![image](https://hackmd.io/_uploads/SkZ5mzqgA.png)

* 體（Field）
    F = <{…}, •, □ >
    為一交換環
    ![image](https://hackmd.io/_uploads/SyPZNf5l0.png)
    
    * 有限體（Finite Field）
        * 元素個數為𝑝^n^
        * **蓋洛瓦體𝐺𝐹(𝑝^𝑛^) 是一個有限體，內含有限𝑝^𝑛^個元素，亦稱為其Order**

    * G𝐹\(𝑝)體
        * ex: GF(2) ,集合為{0, 1}
            >![image](https://hackmd.io/_uploads/Hk7JBMcgR.png)
        * ex: GF(5) ,集合為Z~5~
            >![image](https://hackmd.io/_uploads/ByfVHG9eC.png)
:::info
總之
![image](https://hackmd.io/_uploads/SJ9Drf9x0.png)
:::

### 4.2 𝐺𝐹(2^𝑛^)體
* 多項式
    ![image](https://hackmd.io/_uploads/Sk-FMmceR.png)

:::success
用來表示𝑛位元字組的多項式使用兩個體：
𝐺𝐹(2) 和 𝐺𝐹(2^𝑛^)
:::

* 模多項式（Modulo Polynomial）
    >在這裡被當作質多項式（Prime Polynomial）
    >集合中沒有任何一個多項式可以將之整除
    >**不可分解多項式（Irreducible Polynomial）**
    >**對多項式而言，加法和減法是完全相等的運算**
    * 加法
        * 𝑮𝑭(2^8^)下執行(𝑥^5^+𝑥^2^+𝑥)⊕(𝑥^3^+𝑥^2^+1)
            >![image](https://hackmd.io/_uploads/rkyuV7cg0.png)

            :::warning
            :+1: 速解:
            在𝑮𝑭(2)下的加法相當於XOR運算
            𝑥^5^+𝑥^2^+𝑥相當於00100110，而𝑥^3^+𝑥^2^+1 相當於00001101
            :::

    * 乘法
        * 相乘的結果階數可能會超過𝑛−1，所以必須除以模多項式取其餘式

        * 𝑮𝑭(2^8^) 下 (𝑥^5^+𝑥^2^+𝑥)⨂(𝑥^7^+𝑥^4^+𝑥^3^+𝑥^2^+𝑥)的結果，不可分解多項式為(𝑥^8^+𝑥^4^+𝑥^3^+𝑥+1)
            >![image](https://hackmd.io/_uploads/By7CwXcg0.png)

        * 係數在𝐺𝐹(2)之下的多項式除法
            >![image](https://hackmd.io/_uploads/HksOyN9lR.png)
        * 在𝑮𝑭(2^4^)下，找出多項式(𝑥^2^+1)對模多項式(𝑥^4^+𝑥+1)的乘法反元素。
            >解法：答案為(𝑥^3^+𝑥+1)
            >t~1~-t~2~如果 > 原本題目的r~1~, 要mod r~1~
            >![image](https://hackmd.io/_uploads/SJ4zpcje0.png)
        * 計算在𝑮𝑭(2^8^)下，𝑃1 =(𝑥^5^+𝑥^2^+𝑥)乘以𝑃2 =(𝑥^7^+𝑥^4^+𝑥^3^+𝑥^2^+𝑥)的結果，使用不可分解多項式(𝑥^8^+𝑥^4^+𝑥^3^+𝑥+1)
            >因為是把P~1~拆掉,所以最後撿起P~1~的x階乘數5,2,1
            >![image](https://hackmd.io/_uploads/r17puooxR.png)
        * 令𝑃1=00100110，𝑃2 =10011110，模數為100011011（9個位元）
            >用剛才的數據+8-bit再搞一次
            >位移之後有溢位的要XOR不可分解多項式
            >![image](https://hackmd.io/_uploads/SJr7TjslR.png)

有限體 𝑮𝑭(2^𝑛^) 可以用來定義 𝑛 位元字組的加減乘除等四則運算。
唯一的限制是當除數為零時，結果沒有定義


## Lecture 5 Modern Symmetric-Key Encryption
### 現代區塊加密法
𝑛位元的明文區塊或解密一個𝑛位元的密文區塊
>適用於區塊加密的資料（一整段）
>範例：電子郵件、檔案傳輸
![image](https://hackmd.io/_uploads/ryyMfXsH0.png)
![image](https://hackmd.io/_uploads/S1xBQ7irA.png)
* 全大小金鑰加密法
    >![image](https://hackmd.io/_uploads/BJu28moH0.png)

* P-box
    排列box
    類似於傳統的字元換位加密法，不同之處在於P-box的換位單元是**位元**
    * 三種不同型態的P-box
        >![image](https://hackmd.io/_uploads/ryifKXoHR.png)
    * Compression P-box(壓縮的P-box)
    * Expansion P-box(擴展的P-box)
    * 可逆性
        >![image](https://hackmd.io/_uploads/r1p6jmiB0.png)
        >反轉的方法:
        >![image](https://hackmd.io/_uploads/SkhihmjBA.png)
        :::warning
        :warning: 壓縮和擴展的P-box 是不可逆
        :::
* S-box
    取代box
    可以視為一種小型的取代加密法
    ![image](https://hackmd.io/_uploads/BJOBp7sHA.png)
    * 可逆性
        >可以是可逆的或是不可逆的(??蛤)
        >可逆的S-box 其輸入位元的數量必須與輸出位元的數量相同
* XOR
    封閉性、結合性、交換性、存在單位元素、存在反元素
    * 反向
        >![image](https://hackmd.io/_uploads/BJuv-NiBC.png)
* 循環位移(Circular Shift Operation)
    >![image](https://hackmd.io/_uploads/BkbNNNsHC.png)
* 交換（Swap Operation）
    >k =𝑛/2
    >![image](https://hackmd.io/_uploads/rksTN4jrC.png)
* 分割與整合
* 乘積加密法（Product Cipher）
    >概念是由Shannon提出
    * 擴散（Diffusion）
        >擴散隱藏密文和明文之間的關係
    * 混淆（Confusion）
        >混淆隱藏密文和金鑰之間的關係
* 回合
    ![image](https://hackmd.io/_uploads/Hk_OPVjSA.png)
* 現代區塊加密法都是乘積加密
    但分成2種:
    Feistel 加密法、非Feistel 加密法
* Feistel 加密法
    >自我可逆、可逆和不可逆的
    * EX: 明文和密文的長度各是4 位元，金鑰長度是 3 位元，假設此函數取*金鑰*的第一和第三位元，將此二位元解釋成十進位的數字，再將該數字平方，以二進位的 4 位元表示結果。如果原始的明文是0111，而金鑰是101，請顯示加密和解密的結果。
        >此函數取出第一和第三位元，得到二進位的 11 或十進位的3，平方的結果是9，以二進位表示則是1001
        >![image](https://hackmd.io/_uploads/Bk3U-SsrA.png)
* 非Feistel 加密(Non-Feistel Cipher)
    >只使用可逆的組成元件
* 區塊加密法的攻擊
    * 差異破密分析(Differential Cryptanalysis)
        > Eli Biham 和Adi Shamir 提出差異破密分析（Differential Cryptanalysis）的想法，這是一種選擇明文攻擊
        > 假設有一加密法只由一個XOR運算組成
        > 在不知道金鑰的情況之下，Eve 可以容易地找出明文差異與密文差異之間的關係
        > ![image](https://hackmd.io/_uploads/r1zBmBsHC.png)
        > 基於區塊加密法中S-box的不平均差異分布表

    * 線性破密分析(Linear Cryptanalysis)
        >1993 年由日本密碼學家 Mitsuru Matsui 所提出，此分析使用已知明文攻擊
        >![image](https://hackmd.io/_uploads/rJ2-OBjrC.png)
    * 線性相近
        >在一些現代區塊加密法中，可能發生的情況是某些S-box 並不是完全非線性，而是藉由一些線性函數機率式地近似於非線性
        >![image](https://hackmd.io/_uploads/BkjS9riH0.png)
## Lecture 6 Data Encryption Standard
### 6.1 簡介
**資料加密標準（Data Encryption Standard, DES）**
是一個對稱式鑰區塊加密法，由美國國家標準技術局（National Institute of Standards and Technology, NIST）發表
* DES 是一個區塊加密法
    >![image](https://hackmd.io/_uploads/SyVg2riHC.png)
### 6.2 DES 的結構
* DES 的一般結構
    ![image](https://hackmd.io/_uploads/HkdM3SiBA.png)
* 初始排列&最終列表
    >![image](https://hackmd.io/_uploads/Bygsa-hBA.png)
    >
    >---
    >
    >找出初始排列的輸出結果:
    >***0x0002 0000 0000 0001***
    >輸入僅有兩個為 1 的位元（第 15 個位元及第 64 個位元）
    >輸入的第 15 個位元將變為輸出的第 63 個位元；
    >輸入的第 64 個位元將變為輸出的第 25 個位元
    >tip: 從左邊數第幾個位元
    >***0x0000 0080 0000 0002***
    >
    >---
    >
    >找出最終排列之輸出，以證明初始與最終排列互為反向
    >***0x0000 0080 0000 0002***
    >只有第 25 個位元及第 63 個位元為 1
    >輸入的第 25 個位元將變為輸出的第 64 個位元，
    >而輸入的第 63 個位元將變為輸出的第 15 個位元
    >***0x0002 0000 0000 0001***
    >
    :::info
    :bulb:初始排列與最終排列皆為標準的 P-box 且互為反向
    :::
* S-box
    * EX:  若 S-box 的輸入為 100011，其輸出為何？
        >若將第 1 位元及第 6 位元寫在一起，以二進位表示為11，以十進位表示為3
        剩下的位元為 0001，以十進位表示為 1
        我們查表（S-box）的第 3 列與第 1 行，結果為 12（十進位）
        以二進位表示為 1100。因此若輸入為 100011，*則輸出為 1100*
        ![image](https://hackmd.io/_uploads/SkCvQMnHA.png)
:::danger
DES 的有效加密金鑰長度僅為 56 位元
其餘 8 位元會被用於奇偶校驗
:::
### 6.3 DES 分析
* 特性
    * 崩塌影響（Avalanche Effect）
        >* 意指在明文（或金鑰）少數位元的一個小改變會造成在密文中的重大改變
    * 完整性影響（Completeness Effect）
        >* 意指密文的每一個位元需要由明文的許多位元來決定
        >* DES 的 S-box 與 P-box 會產生**混淆**與**擴散**，具有非常強的完整性影響
* DES 的弱點
    * S-box 的弱點
        >兩個特定選擇的輸入可得到相同的輸出
    * P-box 的弱點
        >初始排列與最終排列的運算對於安全性並無幫助
    * 加密金鑰的弱點
        >存在弱金鑰，使得加密和解密具有相同的效果
* 弱金鑰
    >弱金鑰來加密一個區塊內容兩次
    >![image](https://hackmd.io/_uploads/HyjQCGhHR.png)
    * EX: 隨機挑選到一把弱金鑰或一把半弱金鑰的機率為何？
        >DES 的金鑰範圍大小為 2^56^，上述所有的金鑰數目為 16（即為 4 + 12）
        >因此，挑選到其中一把金鑰的機率為 2.2 ×10^−16^，這幾乎是不可能的
* 金鑰補數（Key Complement）
    >可以經由每一位元反向（將 0 改變為 1，或將 1 改變為 0）來得到
    :::info
    金鑰補數是否會簡化密碼分析的工作呢？
    答案是肯定的。攻擊者可以僅使用一半的可能金鑰（2^55^）來執行暴力攻擊法
    ![image](https://hackmd.io/_uploads/r1Rh1Q2BC.png)
### 6.4 DES 安全性
* 暴力攻擊法 (Brute-Force Attack)
    >* 1977 年，Diffie 和 Hellman 提出了一部造價約兩千萬美元的破解器，
    >可以在一天內找到一個 DES 金鑰，但並無公開的實作
* 差異破密分析 (Differential Cryptanalysis)
    >* DES 的設計者已知關於這類的攻擊，
    >並且設計 S-box 及選擇使用十六個回合，
    >使得 DES 特別能夠抵抗這類的攻擊
* 線性破密分析 (Linear Cryptanalysis)
    >* 在 1994 年由 Kaliski 和Robshaw 所提
    >* 設法得到 S-box 輸入與輸出的某幾個位元之間的線性關係式
    >，以統計的方法找出最可能的子金鑰
    >* S-box 幾乎不能抵抗線性破密分析，
    >目前已證明使用 2^43^ 對已知明文便可破解 DES
### 6.5 多重 DES
    >對 DES 主要的批評是金鑰長度
    >DES 並非一個群，這表示我們可以使用 Double DES（2DES）
    >或者 Triple DES（3DES）來增加金鑰長度
* Double DES
    >中間相遇攻擊（Meet-in-the-Middle Attack）的的**已知明文攻擊**
    >![image](https://hackmd.io/_uploads/ryy4NX2HR.png)

* Triple DES
    >![image](https://hackmd.io/_uploads/S1-XNX2SA.png)
    * Triple DES 的金鑰選取
        >1. 金鑰選擇一: K~1~、K~2~ 及 K~3~皆獨立選取，又稱 3TDEA，強度最高
        >2. 金鑰選擇二: 僅 K~1~ 和 K~2~ 是獨立選取，而 K~3~ = K~1~，又稱 2TDEA，安全性稍低
        >3. 金鑰選擇三: 三個金鑰均相等（K~1~ = K~2~ = K~3~），安全性等同於 DES
    ![image](https://hackmd.io/_uploads/SyynNX2HA.png)
    >![image](https://hackmd.io/_uploads/ByObSX3HC.png)
    >商業應用程式 PGP（Pretty Good Privacy）協定
## Lecture 7 Advanced Encryption Standard
### 7.1 簡介
    >* 簡單說就是因為電腦變太強，
    >DES不夠安全了，
    >* 美國國家標準技術局（NIST）徵求下一代的加密標準
    >進階加密標準（Advanced Encryption Standard，AES）
    >是 NIST 於2001 年 12 月所發布的對稱式區塊加密法
* 歷史
    >2000 年 10 月舉行第三次 AES 候選研討會
    >Joan Daemen 和 Vincent Rijment 所設計的 Rijndael 演算法
    >在 2001 年 12 月，AES 正式發表於《聯邦公報》，稱為 FIPS 197
* AES
    >非 Feistel 架構
    * AES 總共定義了三個版本
        >十、十二 和十四個回合
        * 區塊與狀態之間的轉換
            >![image](https://hackmd.io/_uploads/rykPiX3BC.png)
            >
            >---
            >
            >把文字填進去的方法
            >![image](https://hackmd.io/_uploads/HJzso73r0.png)
            >
            >---
            >
            >每個回合的結構
            >![image](https://hackmd.io/_uploads/rkHpj7nH0.png)

### 7.2 轉換
取代(SubBytes)、排列 (ShiftRow)、混合 (MixColumn) 以及加入金鑰(AddRoundKey)
* SubBytes
    >AES 使用兩個可逆的轉換
    * 使用 GF(2^8^) 體的轉換
        >不可分解多項式:
        >***x^8^ + x^4^ + x^3^ + x + 1***
* ShiftRows
    >![image](https://hackmd.io/_uploads/S1qiR7hSR.png)
    >
    >---
    >
    >InvShiftRows 轉換可產生原始的狀態:
    >![image](https://hackmd.io/_uploads/r17GyV3H0.png)
* MixColumns
    >![image](https://hackmd.io/_uploads/ByI8y4hS0.png)
    >`InvMixColumns 的轉換程序基本上和 MixColumns 一樣`
* AddRoundKey
    >一次處理一行
    >AddRoundKey 使用矩陣加法
    >:::info
    >AddRoundKey 轉換為自己的反向
    >:::

### 7.3 金鑰擴展（Key Expansion）
* 金鑰擴展分析
    >回合金鑰之間的關係是**非線性**的
    >加入回合常數的步驟也確保了每個回合金鑰都不會和上一個相同
### 7.4 加密法
解密演算法則稱為反向加密法 (Inverse Cipher)
* 改變金鑰擴展演算法
### 7.5 金鑰擴展與加密的範例
![image](https://hackmd.io/_uploads/ByhdPV3BA.png)
### 7.6 AES 安全性分析
* 安全性
    >目前尚未發現其中有任何一種方法可以破壞 AES 的安全性
* SubBytes
    >提供了加密法非線性的變換能力
* ShiftRow 與 MixColumns
    >提供了擴散性：每個 input byte 都會對 output byte 造成影響
* AddRoundKey
    >AES 沒有弱金鑰

## Lecture 9 Mathematics of Asymmetric-Key Encryption
### 9.1 質數
* 質數的個數
    * 𝜋(𝑛): 小於或等於某個實數 𝑛 的質數個數
* 質數的檢查
    * 給定一個數值 𝑛，如何判定 𝑛 是否為質數？
        >逐一測試所有小於 𝑛^1/2^ 質數是否可以整除 n
    * EX: 97 是否為質數？
        >![image](https://hackmd.io/_uploads/BkLUxDnSC.png)
    * EX: 301 是否為質數？
        >![image](https://hackmd.io/_uploads/Sy2_xw3S0.png)
* 尤拉 phi 函數（Euler’s phi function，𝜙(𝑛)）
    >尤拉 totient 函數（Euler’s totient function）
    *  𝜙(1) = 1
    *  𝜙(𝑝) = 𝑝 − 1，若 𝑝 是一個質數
    *  𝜙(𝑚 × 𝑛) = 𝜙(𝑚) × 𝜙(𝑛)，若正整數 𝑚 和 𝑛 互質
        >![image](https://hackmd.io/_uploads/SypAQv3SA.png)
    *  𝜙(𝑝^𝑒^) = 𝑝^𝑒^ − 𝑝^𝑒−1^，若 𝑝 是質數且 𝑒 為正整數
        >![image](https://hackmd.io/_uploads/Sk_kNv3S0.png)
    * EX: 𝜙(13) 的值為何？
        >由於 13 是質數，𝜙(13) = (13 − 1) = 12
    * EX: 在 Z^14*^ 中有多少個元素？
        >𝜙(14) = 𝜙(7) × 𝜙(2) = 6 × 1 = 6
        >1、3、5、9、11 和 13
        >`1、3、5、9、11 和 13`
* 費馬小定理
    * 令質數 𝑝 與底數 𝑎 互質
        * 第一種版本
            >𝑎^𝑝−1^ ≡ 1 (mod 𝑝)
            * EX: 計算 6^10^ mod 11
                >我們可得 6^10^ mod 11 = 1
        * 第二種版本
            >𝑎^𝑝^ ≡ 𝑎 (mod 𝑝)
            * 3^12^ mod 11
                >![image](https://hackmd.io/_uploads/rJNstw3B0.png)

* 乘法反元素
    a^−1^ mod 𝑝 = 𝑎^𝑝−2^ mod 𝑝
    * 模數是質數
        >不使用歐幾里德延伸演算法
    * a^−1^ mod 𝑛 ≡ 𝑎^𝜙(𝑛)−1^ mod 𝑛
* 尤拉定理
    >令正整數𝑛與底數𝑎互質
    * a^𝜙(𝑛)^ ≡ 1 (mod 𝑛)
    * a^𝑘×𝜙(𝑛)+1^ ≡ 𝑎 (mod 𝑛)
    ![image](https://hackmd.io/_uploads/HkKWHgyLR.png)

* 莫仙尼（Mersenne）質數
    * 可能是質數，也可能不是((蛤?
    * M~𝑝~ =2^𝑝^−1
* 費馬（Fermat）質數
    * 有可能是質數，也可能不是
    * ![image](https://hackmd.io/_uploads/HJZNhe1LR.png)


### 9.2 質數測試法
* 整除性測試法
    >整除性測試法的位元運算複雜度是以指數成長的
    * 假設𝑛有200 個位元。對𝑛執行整除性測試法演算法需要多少次位元運算？
        >此演算法需要2^100^次位元運算
* AKS測試法
    >Agrawal–Kayal–Saxena
    *  假設𝑛有200 個位元。對𝑛執行AKS 演算法需要多少次位元運算？
        >(log~2~200)^12^
* 費馬測試法
    * 若𝑛是質數，則𝑎^𝑛−1^ ≡ 1 mod n
        >若𝑛是質數，𝑎^𝑛−1^ mod 𝑛 ≡ 1 一定會成立。
        >若𝑛是合成數，𝑎^𝑛−1^ mod 𝑛 ≡ 1 有可能會成立。
* 平方根測試法
    >![image](https://hackmd.io/_uploads/B1Obm-yIR.png)
* Miller-Rabin 測試法
    >𝑛−1=𝑚×2^k^
    >測試法需要從步驟0執行到步驟𝑘−1
    * 561 能否通過Miller-Rabin 測試法？
        >![image](https://hackmd.io/_uploads/H1Ax6GJUC.png)

### 9.3 因數分解（Factorization）
最小公倍數 x 最大公因數 = a x b
![image](https://hackmd.io/_uploads/ry-ARG1IR.png)
* 費馬分解法(Fermat Factorization Method)
    > 𝑛 = 𝑥^2^−𝑦^2^ = 𝑎×𝑏，其中 𝑎=(𝑥+𝑦) 和 𝑏=(𝑥−𝑦)

### 9.4 中國餘數定理（Chinese Remainder Theorem, CRT）
![image](https://hackmd.io/_uploads/S15OrQ1LR.png)

### 9.5 二次同餘（Quadratic Congruence）
𝑎~2~𝑥^2^+𝑎~1~𝑥+𝑎~0~ ≡ 0(mod 𝑛)的方程式
形式為𝑥^2^ ≡ 𝑎(mod 𝑛)的方程式
* 二次剩餘與非二次剩餘
    * 二次剩餘（Quadratic Residue，QR）
        >在方程式𝑥^2^ ≡ 𝑎(mod 𝑝)中，如果此方程式有兩個解
    * 非二次剩餘（Quadratic Nonresidue，NQR）
        >如果此方程式無解
* 尤拉準則
    * 𝑎^(𝑝−1)/2^ ≡ 1(mod 𝑝)
        >二次剩餘QR
    * 𝑎^(𝑝−1)/2^ ≡ −1(mod 𝑝)
        >非二次剩餘NQR
    ![image](https://hackmd.io/_uploads/r1zMpQ1IC.png)
    
### 9.6 指數運算與對數運算
* 快速指數運算
    >平方暨乘演算法(Square-and-Multiply Method)
    >![image](https://hackmd.io/_uploads/SkyJdEkIR.png)
* 複雜度
    >多項式成長

## Lecture 10 Asymmetric-Key Encryption
### 10.1 簡介

:::info
:bulb: 
**對稱式金鑰**密碼技術是基於**分享的祕密**，
**非對稱式金鑰**密碼技術是基於**個人的祕密**。
在**對稱式金鑰**密碼學中，符號被重新排列與取代；
在**非對稱式金鑰**密碼學中，數字被操作處理。
:::
* 非對稱式金鑰
    >![image](https://hackmd.io/_uploads/r1YOY4yLA.png)
    >非對稱式金鑰密碼學將明文（Plaintext）與密文（Ciphertext）當成**整數**
    * 一把為*私密金鑰*（Private Key）
    * 一把為*公開金鑰*（Public Key
* 公開金鑰基本概念
    * 對稱式密碼系統有金鑰的管理問題
        >例如要與𝑁個人做秘密通訊，那麼就必須握有𝑁把秘密金鑰
    * 為了改善對稱式密碼系統問題，於是便有公開金鑰密碼系統（Public-Key Cryptosystems）的產生
        >只需要1把私密金鑰跟1把公開金鑰
* 單向暗門函數
    >給一個𝑦以及一個暗門（Trapdoor，祕密）
    >則𝑥可以很容易計算出來 ((蛤??
* Diffie-Hellman
    >A用自己的私鑰x~a~去解B給他的公鑰加密的𝑔^𝑥𝑏^ mod p
    > 𝐾 =(𝑔^𝑥𝑏^)^𝑥𝑎^ mod p
    ![image](https://hackmd.io/_uploads/rJEpBSyU0.png)
    * Man-in-the-Middle Attack(中間人攻擊)
        >假裝自己是對方
    * Possible Solutions
        * 前置共享密鑰（Pre-shared Secret）
            >來交換訊息加密
        * 傳送共享數值、名稱、前置共享密鑰的雜湊值
### 10.2 RSA 密碼系統
**R**ivest、**S**hamir、**A**dleman（RSA）

:::success
公開金鑰密碼系統作為資料加密的方式，可達到資料加密及數位簽章的功能
:::


* RSA Encryption
    >使用對方公開金鑰（Public Key）將明文加密
* RSA Decryption
    >使用自己的私密金鑰（Private Key）才能將密文解出
* 𝜙(𝑛) =(𝑝−1)(𝑞−1)
    >𝜙(𝑛)Euler’s totient 函數，其意為與 𝑛 互質之個數
    >(𝑒,𝑛)即為Bob的*公開金鑰*
* Bob 選 1 個數𝑑，滿足 𝑒∙𝑑 mod 𝜙(𝑛) = 1
    >𝑑 即為Bob 的解密金鑰（亦稱私密金鑰）
:::info
:bulb:
加密法為C=P^𝑒^ mod 𝑛
解密法為P=C^𝑑^ mod 𝑛
:::

`RSA之安全性取決於質因數分解之困難度`
如果知悉公開參數𝑛的兩個質因數(𝑝,𝑞)
則𝜙(𝑛)的值將無秘密可言

總之: 如果可以有效率地執行因數分解，則RSA密碼系統毫無安全性可言

* Public-Key Cryptosystems 之特性
    1. 可還原性：𝐷(𝑑,𝐸(𝑒,P)) = P
    
    2. 金鑰產生容易：𝑑和𝑒很容易求得
    3. 單向暗門：若公開(𝑒,𝑛)，別人很難從(𝑒,𝑛)去求得𝑑，即只有自己知道如何解以𝑒加的密
    4. 可驗證性：𝐷(𝑒,𝐸(𝑑,P)) = P
    
### 10.3 Rabin 密碼系統
將𝑒及𝑑固定的RSA密碼系統
是C≡P^2^(mod 𝑛)，而解密是P≡C^1/2^(mod 𝑛)
:::info
Rabin 密碼系統是非確定式的：
解密得到四個同樣都可能的明文
:::

公開金鑰：𝑛
私密金鑰：𝑝、q

*  本系統之安全性可證明等於分解因數，但存在選擇密文攻擊法
    >破解者可解因數 n，系統可被破解

### 10.4 ElGamal 密碼系統（ElGamalCryptosystem）
Taher ElGamal
基於解**離散對數**問題
複雜度是多項式型態的
* EX:
    ![image](https://hackmd.io/_uploads/B1o8021IA.png)
    ![image](https://hackmd.io/_uploads/S1QDRn18A.png)
    解密也可直接用: **P=\[C2×C1^𝑝−1−𝑑^\] mod p**
* 安全性
    1. 𝑝必須至少 300 位數字，
    2. 對每一次加密，𝑟都必須採用一個全新的數值
* 橢圓曲線密碼學（Elliptic Curve Cryptography，ECC）
    >Neal Koblitz 與 Victor Miller 各自提出的
    >Pros: 
    >* 可以使用比RSA演算法還要小的金鑰長度
    >* 用於計算效能相對較差的輕量級裝置上
    * 𝑦^2^=𝑥^3^+𝑎𝑥+b
* 有限體和離散對數
    * 橢圓曲線是連續的，容易被推算，因此，並不適合用於加密
* Security of Elliptic Curve Cryptography
    * ECC的安全性是基於解橢圓曲線離散對數的難題
    * John Pollard所提的Pollard’s rho演算法
    * 可以使用比RSA小很多的金鑰大小