# Cryptography and network security - NOTE

## Lecture 2 Basic Number Theory

### 2.1 整數算術
* 整數集合，標記為𝑍: 從負無窮大到正無窮大的所有整數
* 三種作用在整數集合上的二元運算
>
* 整數的除法演算法
>
>---
>讓負餘數變正的方法: 
>---
>整除符號: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)
>
>---
>ex: 試求2740 和1760 的最大公因數
>解法：我們得到gcd(2740,1760) =20
>
* 歐幾里德延伸演算法
>同時計算出gcd(𝑎,𝑏)以及𝑠和𝑡的值
>
>
>ex: 給定𝑎=161和𝑏=28，求出gcd(𝑎,𝑏)以及𝑠和𝑡的值
>解法：我們得到gcd(161,28)=7，𝑠=−1和𝑡=6
>

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

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

### 2.2 模數算術

* 負數
>ex: -18 mod 14 => r = -4 => r = 10
>ex: -7 mod 10 => r = -7 => r = 3
* 餘數集合：Zn
>模𝑛之最小餘數集合
>

* 剩餘類(Residue Class)
> [𝑎] 或 [a]n => 模𝑛之下所有餘數為𝑎的整數集合
> 

* Zn中的二元運算
>

* 同餘(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
>
* 集合
>當需要加法反元素時，我們使用集合Z~n~
>當需要乘法反元素時，我們使用集合Z~n*~ (跟n互質的)

### 2.3 矩陣

* 行列式(determinant)
>det(𝐴)
>
>只有方陣有行列式
>
* 反矩陣(Inverse Matrix)
>乘法反矩陣只在方陣有定義
>
* 餘數矩陣(Residual Matrix)
>所有元素皆定義在𝑍𝑛中的矩陣
>gcd(det(𝐴),𝑛) = 1，則該餘數矩陣具有乘法反矩陣

### 2.4 線性同餘
* 單變數線性方程式
>𝑎𝑥 ≡ 𝑏 (mod 𝑛) 可能為無解或是有限個數的解
>若 𝑑 = gcd⁡(𝑎,𝑛) 整除 𝑏，則存在 𝑑 個解
> • 如果𝑑∤𝑏，則無解。
> • 如果𝑑|𝑏，則有𝑑個解。
>
>
>---
>
>
>---
>
>ex: 解出方程式 14x ≡ 12(mod 18) => 
>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: 看作業內容比較快
>
>
>---
>
>
>---
>特別的:中國餘數定理
>

## Lecture 3 Classical Encryption Techniques

### Symmetric Encryption
>對稱式金鑰(Symmetric Key)：以同一把金鑰來加密或解密
>
>

### Techniques of Classical Ciphers

* Substitution Techniques
* Monoalphabetic Cipher(單字母加密)
>明文用小寫字體，密文則用大寫字體
>
>加法加密法(Additive Cipher)
> => 此加密法有時稱為位移加密法(Shift Cipher)
> => 凱撒加密法(Caesar Cipher)

* Caesar Cipher
>其明文、密文和金鑰都是Z~26~中的整數
> 𝑓(𝑎) = (𝑎+𝑘) mod n
> 𝑎 =該字在字集中原先位置；𝑘=移動的位置；𝑛=此字集的大小
>
>
>加密用加法
>
>解密用減法
>

* Multiplicative Cipher(乘法加密法)
>明文和密文都是𝑍~26~的整數；金鑰為一個𝑍~26∗~的整數
>
>

* Affine Cipher(仿射加密法)
>加密:
>
>解密:
>

* Monoalphabetic Substitution Cipher(單字母取代加密法)
>

* Polyalphabetic Ciphers(多字母加密法)
>明文裡的一個字元和密文裡的一個字元之間的關係是一對多

* Autokey Cipher(自動金鑰加密法)
>往右平移並加起來 mod 26
>

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

* Transposition Ciphers(換位加密法)
>改變符號的位置

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

* 有金鑰的換位加密法(Transposition Ciphers with Key)
* 行換位加密法(Columnar Transposition Cipher)
>橫著進去 換個排列順序 豎著出來
>
>解密的話:
>站著進去 躺著出來
>
>key可以用矩陣表示
>

### 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)等三個常用的代數結構

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

* 交換群（Commutative Group)(Abelian Group):
* 交換性(Commutative)：對於集合𝐺 中所有的元素𝑎和𝑏，皆滿足等式a•𝑏 =𝑏•a

:::info
群的概念:
ex: G=<𝑍𝑛,+> 是一個交換群
ex: G=<𝑍𝑛∗,×> 也是
:::
* 排列群（Permutation Group）
>所有排列方式的集合
>可合成（Compositional）的

* 這張表是排列群的運算方法
>
* 然後這是他的總表(就是各種組合出的結果)
>

* 子群
* 
* 循環子群（Cyclic Subgroup）
>乘冪的意思是重複對這個元素引用群運算
>a^𝑛^ → 𝑎 • 𝑎 •⋯• 𝑎（𝑛次）
>像作業題目:
>
>

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

* 群 𝑮=<𝒁~10∗~,×> 為一個含兩個生成子**𝑔=3和𝑔=7**的循環群
>

* 元素的階(Order)
>這個元素所生成之循環群的基數(Cardinality)，也就是其元素的個數
>𝑟𝑎𝑛𝑘(G)=1 if and only if 𝐺 是一個循環群
>
* Lagrange 定理
>假設有一群𝐺，𝐻為其子群(𝐻⊆𝐺)，令𝐺和𝐻的秩分別為|𝐺|和|𝐻|。根據Lagrange 定理，**|𝐻|會整除|𝐺|**

* 在群𝐺=<𝑍~6~,+>中，個別元素的階(Order)為：𝑜𝑟𝑑(0) = 1，𝑜𝑟𝑑(1) = 6，𝑜𝑟𝑑(2) = 3，𝑜𝑟𝑑(3) = 2，𝑜𝑟𝑑(4) = 3，𝑜𝑟𝑑(5) = 6
>
* 在群𝐺=<𝑍~10∗~,×>中，個別元素的階為：𝑜𝑟𝑑(1) = 1，𝑜𝑟𝑑(3) = 4，𝑜𝑟𝑑(7) = 4，𝑜𝑟𝑑(9) = 2
>

* 環（Ring）
一個集合和兩種二元運算所構成的代數結構，記作 R = <{…}, •, □>

* 體（Field）
F = <{…}, •, □ >
為一交換環

* 有限體（Finite Field）
* 元素個數為𝑝^n^
* **蓋洛瓦體𝐺𝐹(𝑝^𝑛^) 是一個有限體，內含有限𝑝^𝑛^個元素，亦稱為其Order**

* G𝐹\(𝑝)體
* ex: GF(2) ,集合為{0, 1}
>
* ex: GF(5) ,集合為Z~5~
>
:::info
總之
:::

### 4.2 𝐺𝐹(2^𝑛^)體
* 多項式

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

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

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

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

* 𝑮𝑭(2^8^) 下 (𝑥^5^+𝑥^2^+𝑥)⨂(𝑥^7^+𝑥^4^+𝑥^3^+𝑥^2^+𝑥)的結果，不可分解多項式為(𝑥^8^+𝑥^4^+𝑥^3^+𝑥+1)
>

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

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

## Lecture 5 Modern Symmetric-Key Encryption
### 現代區塊加密法
𝑛位元的明文區塊或解密一個𝑛位元的密文區塊
>適用於區塊加密的資料（一整段）
>範例：電子郵件、檔案傳輸
* 全大小金鑰加密法
>

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

* 線性破密分析(Linear Cryptanalysis)
>1993 年由日本密碼學家 Mitsuru Matsui 所提出，此分析使用已知明文攻擊
>
* 線性相近
>在一些現代區塊加密法中，可能發生的情況是某些S-box 並不是完全非線性，而是藉由一些線性函數機率式地近似於非線性
>
## Lecture 6 Data Encryption Standard
### 6.1 簡介
**資料加密標準（Data Encryption Standard, DES）**
是一個對稱式鑰區塊加密法，由美國國家標準技術局（National Institute of Standards and Technology, NIST）發表
* DES 是一個區塊加密法
>
### 6.2 DES 的結構
* DES 的一般結構
* 初始排列&最終列表
>
>
>---
>
>找出初始排列的輸出結果:
>***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*
:::danger
DES 的有效加密金鑰長度僅為 56 位元
其餘 8 位元會被用於奇偶校驗
:::
### 6.3 DES 分析
* 特性
* 崩塌影響（Avalanche Effect）
>* 意指在明文（或金鑰）少數位元的一個小改變會造成在密文中的重大改變
* 完整性影響（Completeness Effect）
>* 意指密文的每一個位元需要由明文的許多位元來決定
>* DES 的 S-box 與 P-box 會產生**混淆**與**擴散**，具有非常強的完整性影響
* DES 的弱點
* S-box 的弱點
>兩個特定選擇的輸入可得到相同的輸出
* P-box 的弱點
>初始排列與最終排列的運算對於安全性並無幫助
* 加密金鑰的弱點
>存在弱金鑰，使得加密和解密具有相同的效果
* 弱金鑰
>弱金鑰來加密一個區塊內容兩次
>
* EX: 隨機挑選到一把弱金鑰或一把半弱金鑰的機率為何？
>DES 的金鑰範圍大小為 2^56^，上述所有的金鑰數目為 16（即為 4 + 12）
>因此，挑選到其中一把金鑰的機率為 2.2 ×10^−16^，這幾乎是不可能的
* 金鑰補數（Key Complement）
>可以經由每一位元反向（將 0 改變為 1，或將 1 改變為 0）來得到
:::info
金鑰補數是否會簡化密碼分析的工作呢？
答案是肯定的。攻擊者可以僅使用一半的可能金鑰（2^55^）來執行暴力攻擊法
### 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）的的**已知明文攻擊**
>

* Triple DES
>
* 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
>
>商業應用程式 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 總共定義了三個版本
>十、十二 和十四個回合
* 區塊與狀態之間的轉換
>
>
>---
>
>把文字填進去的方法
>
>
>---
>
>每個回合的結構
>

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

### 7.3 金鑰擴展（Key Expansion）
* 金鑰擴展分析
>回合金鑰之間的關係是**非線性**的
>加入回合常數的步驟也確保了每個回合金鑰都不會和上一個相同
### 7.4 加密法
解密演算法則稱為反向加密法 (Inverse Cipher)
* 改變金鑰擴展演算法
### 7.5 金鑰擴展與加密的範例
### 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 是否為質數？
>
* EX: 301 是否為質數？
>
* 尤拉 phi 函數（Euler’s phi function，𝜙(𝑛)）
>尤拉 totient 函數（Euler’s totient function）
* 𝜙(1) = 1
* 𝜙(𝑝) = 𝑝 − 1，若 𝑝 是一個質數
* 𝜙(𝑚 × 𝑛) = 𝜙(𝑚) × 𝜙(𝑛)，若正整數 𝑚 和 𝑛 互質
>
* 𝜙(𝑝^𝑒^) = 𝑝^𝑒^ − 𝑝^𝑒−1^，若 𝑝 是質數且 𝑒 為正整數
>
* 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
>

* 乘法反元素
a^−1^ mod 𝑝 = 𝑎^𝑝−2^ mod 𝑝
* 模數是質數
>不使用歐幾里德延伸演算法
* a^−1^ mod 𝑛 ≡ 𝑎^𝜙(𝑛)−1^ mod 𝑛
* 尤拉定理
>令正整數𝑛與底數𝑎互質
* a^𝜙(𝑛)^ ≡ 1 (mod 𝑛)
* a^𝑘×𝜙(𝑛)+1^ ≡ 𝑎 (mod 𝑛)

* 莫仙尼（Mersenne）質數
* 可能是質數，也可能不是((蛤?
* M~𝑝~ =2^𝑝^−1
* 費馬（Fermat）質數
* 有可能是質數，也可能不是
* 

### 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 有可能會成立。
* 平方根測試法
>
* Miller-Rabin 測試法
>𝑛−1=𝑚×2^k^
>測試法需要從步驟0執行到步驟𝑘−1
* 561 能否通過Miller-Rabin 測試法？
>

### 9.3 因數分解（Factorization）
最小公倍數 x 最大公因數 = a x b
* 費馬分解法(Fermat Factorization Method)
> 𝑛 = 𝑥^2^−𝑦^2^ = 𝑎×𝑏，其中 𝑎=(𝑥+𝑦) 和 𝑏=(𝑥−𝑦)

### 9.4 中國餘數定理（Chinese Remainder Theorem, CRT）

### 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

### 9.6 指數運算與對數運算
* 快速指數運算
>平方暨乘演算法(Square-and-Multiply Method)
>
* 複雜度
>多項式成長

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

:::info
:bulb:
**對稱式金鑰**密碼技術是基於**分享的祕密**，
**非對稱式金鑰**密碼技術是基於**個人的祕密**。
在**對稱式金鑰**密碼學中，符號被重新排列與取代；
在**非對稱式金鑰**密碼學中，數字被操作處理。
:::
* 非對稱式金鑰
>
>非對稱式金鑰密碼學將明文（Plaintext）與密文（Ciphertext）當成**整數**
* 一把為*私密金鑰*（Private Key）
* 一把為*公開金鑰*（Public Key
* 公開金鑰基本概念
* 對稱式密碼系統有金鑰的管理問題
>例如要與𝑁個人做秘密通訊，那麼就必須握有𝑁把秘密金鑰
* 為了改善對稱式密碼系統問題，於是便有公開金鑰密碼系統（Public-Key Cryptosystems）的產生
>只需要1把私密金鑰跟1把公開金鑰
* 單向暗門函數
>給一個𝑦以及一個暗門（Trapdoor，祕密）
>則𝑥可以很容易計算出來 ((蛤??
* Diffie-Hellman
>A用自己的私鑰x~a~去解B給他的公鑰加密的𝑔^𝑥𝑏^ mod p
> 𝐾 =(𝑔^𝑥𝑏^)^𝑥𝑎^ mod p
* 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:
解密也可直接用: **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小很多的金鑰大小