資安導論筆記
資安導論筆記
CH01 Introduction
資安三要素 : CIA triad
- 保密性 (Confidentiality)
保護機密資料，防止未授權資料外洩
攻擊方法 :
竊取偷聽社交工程等 - 完整性 (Integrity)
避免資料在不正確的狀態下被竄改揭露，ex 避免釣魚、簽章
攻擊方法 :
竄改釣魚刪除機密檔案等 - 可用性 (Availability)
同時確保資料與系統在任一時刻都是可靠的，ex 避免系統崩潰及資料流失
攻擊方法 :
DOS等
OSI Security Architecture
一個由國際標準組織所制訂的安全作業方法
- 安全攻擊：任何洩漏企業資訊的行為。
- 安全機制：用來偵測或預防安全攻擊，或者能夠復原安全攻擊的機制。
- 安全服務：能夠加強資訊安全的服務，這些服務是由數種安全機制提供。
定義
威脅（Threat）：可能破壞系統安全的情況、能力或行為。 攻擊（Attack）：利用已知的技術，並且有計畫的迴避系統的安全服務。
攻擊種類 Active V.S Passive attack
Active Attack 主動式攻擊
入侵者針對檔案或通訊內容進行偽造或修改
主動式攻擊法 : 偽裝 重播 訊息竄改 服務阻絕DOS
Passive Attack 被動式攻擊
入侵者竊取資訊，或者監控資訊傳輸
被動式攻擊法 : 竊聽 通訊分析
CH02 經典的加密法
名詞定義
Plaintext : 原文
Ciphertext : 密文
Cipher : 加密演算法
Key : 金鑰
encipher(decrypt) : 加密
decipher(encrypt) : 解密
Crytography : 加密學
Crytanalysis : 破譯
Cryptology : 密碼學
對稱式加密 Symmetric Cipher
加解密的 Key 是同一把，並且都為密鑰
條件 :
- 夠強的加密演算法
- 密鑰僅被 Sender / receiver 所知 (Secure channel)
- 加密演算法是公開的
數學上表示 : Y = E(K, X) X = D(K, Y)
破譯方法
- Cryptanalytic Attack 分析明文、常見文法解密後的結果來解析加密演算法
- Brute-force Attack 暴力解
名詞定義
Unconditional security : 不管給多久的時間、多少的運算能，都不可能被破解 Computational security : 在有限算力下不能被破解
古典加密法
凱薩加密法 Caesar Cipher
為 Shift 加密法的一種，以 Key 作為位移位元數，往下移動位元
破譯僅需嘗試 26 種組合
ex :
原文 abcdez
Key 3
密文 defghc
破解方法 :
- 暴力解，因英文字母僅有 26 個，所以平均嘗試 13 次即可得到原文
- 字頻分析，分析英文常見字母的位元差，去做反位移
Monoalphabetic Cipher
凱薩加密法進階版本，讓每個字母都做一個一對一的映射，A 對應到 C，B 對應到 Z 等，而不是位移共同的長度。
破譯難度提升至 26! 種組合
ex :
原文 ABCDEFGHIJKLMNOPQRSTUVWXYZ
金鑰 DKVQFIBJWPESCXHTMYAUOLRGZN
密文 DKVQFIBJWPESCXHTMYAUOLRGZN
破解方法 :
- 字頻分析，分析英文常見字母的位元差，去做反位移
Playfair Cipher
- 做一個5*5的表格
- 依序將 Key 填入，重複的字母跳過。因為字母有26個，通常將
I / J視為同一個字。 - 填完Key的字母後，將沒出現過的字母依序填完。
- 開始加密，將明文兩個兩個字一組，如果
- 兩個字母出現在同一
Row，轉換為右邊一格的字母。 - 兩個字母出現在同一
Column，轉換為下面一個的字母。 - 其他，則找出另外兩格使該四個字母形成一個矩形。 (第一個字母找同
Row，第二個字母找同Column) - 如果兩個字母一樣、或是最後只剩一個字，插入/補上字母X。
原文 DA RE TO CO ME DO WN IC EB IR D 金鑰 PLAYFAIR 密文 BF IG NQ RS EG RT UQ RD HI RB CZ|P |L|A|Y|F| |—-|-|-|-|-| |I(J)|R|B|C|D| |E |G|H|K|M| |N |O|Q|S|T| |U |V|W|X|Z|
- 兩個字母出現在同一
Vigenère Cipher
類似凱薩加密，將 KEY 重複複製直到等於原文長度，再做相加得到密文
原文 IFEELLIKEPATRICKSAGENIUSANDHESJUSTTROLLING
金鑰 PATRICK
密鑰2 PATRICKPATRICKPATRICKPATRICKPATRICKPATRICK
密文 XFXVTNSZEIRBTSRKLROGXXULRVFRTSCLAVDGOECQPQ
- 特點
如果Key的長度被得知，被破解的可能性會大幅上升。
Autokey Cipher
與 Vigenère Cipher 類似，只是 KEY 後面是將原文放入補充長度
原文 IFEELLIKEPATRICKSAGENIUSANDHESJUSTTROLLING
金鑰 PATRICK
密鑰2 PATRICKIFEELLIKEPATRICKSAGENIUSANDHESJUSTT
密文 XFXVTNSSJTEECQMOHAZVVKEKATHUMMBUFWAVGUFAGZ
Vernam Cipher
與 Vigenère Cipher 類似，只是運算由加法改為 XOR，每個字元依 ABC 順序轉為二進位 5 bits
ex : A -> 0, C -> 2
原文 VERNAM
金鑰 CIPHER
密文 XMGUED
One-Time Pad
與 Vernam 一樣，用跟名文一樣長的密碼本
Rail Fence Cipher
Key 為一個數字，代表著籬笆的 Row 數量，明文隨著籬笆上下移動 ↘↗↘，最後再由左而右，由上而下合起來變成密文。
原文 RAILFENCE
金鑰 3
R F E
A L E C
I N
密文 RFEALECIN
Row Transposition Ciphers
先把明文依據 Key 的長度作為一 Row，依序建成一個二維陣列。之後依據 Key 將每一 Column 取出和為密文
原文 ROWTRANSPOSITIONCIPHER
金鑰 531246
ROWTRA
NSPOSI
TIONCI
PHER
密文 WPOETONROSIHRSCRNTPAII
Product Ciphers
又名 Substitution cipher，KEY 為一 MAPPING 表，將 KEY 作為 Index mapping 位置
原文 PRODUCTCIPHER
金鑰 13 1 5 7 3 4 6 11 9 10 8 12 2
密文 RPUTODCHIPCER
Rotor Machines
大量用於二戰時期的實體式加解密設備，為機械式加密，同為替換位元式加密
CH03 Block Ciphers and the Data Encryption Standard
Stream Cipher vs. Block Cipher
Stream ciphers : 以位元為單位加密，一次一位元，較小且快速。
Block ciphers : 以區塊為單位加密，較為被網路應用所使用。
Sream Ciphers
通常以 XOR 作為運算元，以不同的 S 去與原文做 XOR 來加密，Key 的生成必須為隨機，並分為
非同步 : Key 生成要參考上一個密文
同步 : Key 生成要參考上一個 Key
目前因安全性以及演算法問題比較少用到
Block Ciphers
以固定長度的區塊 (64 bits) 作為單位加密，而目前使用對稱式加密的 Block cipher 加密法多為 ==Feistel Cipher Structure==
Block Cipher 原始要素
- Confusion 困惑
複雜化密文與 Key 之間的關係 - Diffusion 擴散
將原文的元素擴散到整個密文之中，使的統計結構被消除。
一個 bit 的變化可能就使密文有著截然不同的樣式
DES
Block size = 64 bits
Key size = 64bits, 實際使用 56 bits
16次迭代
Feistel cipher 的一種 (對稱式加密結構)
Permutation
將整個陣列依據 Table 裡的 Index 去置換順序
ex :
array = ABCDE
Table = [ 2, 3, 5, 4, 1]
Result = BCEDA
F-Function
輸入 32 bits，先將 32 bit 透過 expansion table 擴展到 48 bits，再來與 subkey 的 48 bits 做 XOR，再來每 6 位元為一組進入 S-Box。
依據位元作為 Index，到陣列中找出對應的值
ex : 010011~(2)~
value = S_Box[01][1001] = 6 = 0110~(2)~
最後將 S-Box 出來的值做 Permutation，得到 32 bits 的結果。
Subkey
將 Key 先做 PC1 (Permutation Choice 1)得到 56 bits 的資料後，分為兩部分 C0 / D0。
C0 / D0 分別做左移並再做一次 PC2 得到 Subkey。
接下來持續左移，再做 PC2，總共 16 次的迭代。
解密
解密步驟幾乎與加密相同，僅 Subkey 須倒過來使用 ex : subkey[15] → subkey[14] … subkey[0]
CH04 Basic Concepts in Number Theory and Finite Fields
Divisors 除數 / 因數
A 如能被 B 整除，則稱 B 為 A 的 Divisor
寫做 B | A
| $𝑎 | 1$ → then $𝑎=±1$ | |
| $𝑎 | 𝑏$ and $𝑏 | 𝑎$ → then $𝑎=±𝑏$ |
Residue 餘數
Greatest Common Divisor (GCD 最大公因數)
A 與 B 有著共同除數 C，而最大的 C 則為 GCD。
如兩數除了 1 無其他除數，則兩數互質 (relatively prime)
- 算法
$gcd(a, b) = gcd(b, a\bmod b)$
Modular Arithmetic 模算數
:::info 餘數必為正 :::
- module operator 模運算
$a \bmod b = c$
$a = b*int + c$ - congruent module 同餘
if $𝑎 \bmod 𝑛 = 𝑏 \bmod 𝑛$
$a ≡ b \bmod n$ - 模運算產生的集合
$Z_n = {0, 1, …, n-1}$
Modular Arithmetic Operations 模運算元
$(a + b) \bmod n = [(a \bmod n) + (b \bmod n)] \bmod n$
$(a - b) \bmod n = [(a \bmod n) - (b \bmod n)] \bmod n$
$(a × b) \bmod n = [(a \bmod n) * (b \bmod n)] \bmod n$
Additive Inverse 加法反元素
對於一個任意數 n，存在加法反元素，其與加法反元素之和在 mod n 下與 0 同餘
$a + b ≡ 0 \bmod n$
$b$ 為 $a$ 的加法反元素
ex : 列出 Zn ,n=10之加法反元素的數對
(0,0)、(1,9)、(2,8)、(3,7)、(4,6)、(5,5)
對於整數 a 來說，-a 為 a 的加法反元素
Multiplicative Inverse 乘法反元素
對於一個任意整數 $a$，不一定存在乘法反元素，$a$ 與其乘法反元素 $b$ 之積在 $\mod n$ 下與 $1$ 同餘 $a * b ≡ 1 \bmod n$
ex : 列出 Zn 之乘法反元素的數對
(1,1)、(2,6)、(3,4)、(5,9)、(7,8)、(10,10)
Extended GCD Algorithm
已知整數 $a$ $b$，extended GCD 可求得其 GCD 的同時找到整數 $x$ $y$（其中一個很可能是負數），使它們滿足 $ax + by = gcd(a, b)$
ex : $a = 100, b = 35$
$100 = 35 × 2 + 30$
$35 = 30 × 1 + 5$
$30 = 100 - 35 × 2$
$5 = 35 - 30 × 1$
$5 = 35 - (100 - 35 × 2)$
$5 = -100 + 35 × 3$
ans $a = -1, b = 3$
數論名詞
Z - 所有整數 ${…-2, -1, 0, 1, 2…}$
Z~n~ - 小於 n 的非負整數 ${0, 1, 2…, n-1}$
Z~n~^^ - 小於 n 的正整數 ${1, 2…, n-1}$
N - 非負整數 ${0, 1, 2…}$
P - 正整數 ${1, 2…}$
Q - 有理數
R - 實數
C - 複數
Q^^, R^^, C^^ - 非負XX
Group
群 $(G, ·)$ 是由一個集合 $G$ 以及一個二元運算元 $·$ 所組成的代數結構，必須符合以下四點
- 封閉性
對於所有 $G$ 中的 $a, b$，運算 $a·b$ 的結果也在 $G$ 中 - 結合率
對於所有 $G$ 中的 $a, b, c$，等式 $(a·b)·c = a· (b·c)$ 成立 - 單位元素
存在 $G$ 中的一個元素 $e$，使得對於所有 $G$ 中的元素 $a$，總有等式 $e·a = a·e = a$ 成立 - 反元素
對於每個 $G$ 中的 $a$，存在 $G$ 中的一個元素 $b$ 使得總有 $a·b = b·a = e$，此處 $e$ 為單位元素
ex :
(Z7, +) = {0, 1, 2, 3, 4, 5, 6}
不符合，因未封閉 (加法會超出 7)
abeliangroup 交換群 : $a．b = b．a$
Cyclic Group 循環群
指能由單個元素 g 透過次方所生成的 Group
ex : $(𝒁_7^*,⊗)$ is Cyclic ($⊗$ 為$\bmod 7$)
${1=3^0, 2=3^2, 3=3^1, 4=3^4, 5=3^5, 6=3^3}$
Ring 環
Ring 環 $(R, +, ×)$ 是一個有著兩個運算元的集合，必須符合以下四點
- $(𝑅,+)$ 必須是 abeliangroup/交換群
- 在 × 下得封閉 $(a × b ∈ R$ for all $a, b ∈ R)$
- 結合率
- 分配率
Field 體
Ring $(𝑅,+,×)$ 中每個 $a ∈ R$ 都有 $a^-1$ (反元素) 則為 Field
ex : Zp p 為質數，是 Field
Finite Fields (Galois)
Finite field 內的元素個數必為質數的次方
通常算完後要再 Mod
標示為 $GF(p^n)$
標示為 $GF(p)$
則運算完後都要 $Mod(p)$
Polynomial Arithmetic
多項式
$f(x) = a_nx^n + a_{n-1}x^{n-1}+ … + a_1x + a_0 = \sum a_ix^i$
$f(x) = x^3 + x^2, g(x) = x^2 + x + 1$
Polynomial Arithmetic with Modulo Coefficients
會變成 polynomial ring
ex : mod 2
$f(x) + g(x) = x^3 + x + 1$
$f(x) × g(x) = x^5 + x^2$
$GF(2^3)$ polynomial :
polynomial 𝑆 in the set are ${0, 1, 𝑥, 𝑥+1, 𝑥^2,𝑥^2+1,𝑥^2+𝑥,𝑥^2+𝑥+1}$
Polynomial Extended GCD
$gcd[a(x), b(x)] = 𝑎(𝑥)𝑣(𝑥)+𝑏(𝑥)𝑤(𝑥)=𝑑(𝑥)$
CH05 AES
Block Size = 128 bits
Key Size = 128 / 192 / 256 bits
Iterative cipher
| Key length | Number of rounds |
|---|---|
| 128 | 10 |
| 192 | 12 |
| 256 | 14 |
AES 加密是在一個 4X4 的矩陣上完成
此矩陣又稱作體（State），其初值為一明文區塊（16 Byte），而依據密鑰的長度來決定 Iteration 的次數，一個 Iteration 包含 4 個步驟 :
- AddRoundKey
與該回合之金鑰做 XOR 運算 - SubBytes
將矩陣內的值組透過 8 bits 的 S-Box 做轉換，S-box 與 $GF(2^8)$ 上的乘法反元素有關。
詳細是這樣避免簡單代數性質的攻擊，S-box結合了乘法反元素及一個可逆的仿射變換矩陣建構而成。 此外在建構S-box時，刻意避開了固定點與反固定點，即以S-box替換位元組的結果會相當於錯排的結果。 -
ShiftRows
每一 Row 都往左循環位移一個偏移量
Row 0 不移動
Row 1 左移 1
Row 2 左移 2
Row 3 左移 3
- MixColumns
每一 Column 透過線性變換互相結合，每一 Column
Subkey
CH06 Block Cipher Operation
- Electronic Code Book mode (ECB)
- Cipher Block Chaining mode (CBC)
- Output Feedback mode (OFB)
- Cipher Feedback mode (CFB)
- Counter mode (CTR)
Electronic Code Book mode
ECB 模式 的運作原理就是將明文切割成多個區塊加密解密，彼此互相不影養
優點 :
中間有 bit error 並不會影響其他區塊
可以平行處理
缺點 :
同個明文都是同個密文
- Substitution Attack
用已知的 $x_i → y_i$ mapping 去推測出其他訊息為何
ex : 攻擊者匯 $1 給受害者，藉以獲得帳戶資訊
Cipher Block Chaining mode
CBC 模式 所有加密區塊都被綁在一起，後面的區塊會參考前面區塊的密文做 XOR
Initialization vector (IV)
用於隨機化加密，可讓同個明文得到不同的密文
- Substitution Attack
當 IV 在多次加密都用同個 IV 的話就可能被入侵
Cipher Feedback mode
CFB模式 可以說是不同順序的CBC模式版本。
在CFB模式，前一個密文區塊會先用加密演算法加密，才與明文區塊做XOR運算
Output Feedback mode
OFB 模式 中，加密演算法的 output 會 ==feedback== 回加密演算法的 input。
如要指定第幾個 block，僅需重複加密 IV n-1 次即可求得。
Counter mode
CTR 模式 中使用了計數器取代傳遞 IV，用 IV + n 與金鑰加密後再與明文做 XOR 產生密文。
可以平行運算或式指定 Block
Exhaustive Key Search
https://fu-sheng-wang.blogspot.com/2017/07/cryptography10-exhaustive-search-attack.html
CH07 Pseudorandom Number Generation and Stream Ciphers
Random Numbers
Pseudorandom Number Generators
PRNGs 使用確定性演算法 deterministic algorithmic 產生亂數，過程似乎是隨機的，但實際上並不是，如果種子為同一個，那後續結果也會完全相同。
- 不是真的亂數
被稱作 pseudorandom numbers
Linear Congruential Generator
線性同餘方法 LOG 用線性方法求得
$𝑋_{𝑛+1}=(𝑎𝑋_𝑛+𝑐)\bmod 𝑚$
Blum Blum Shub Generator
期中考分隔線
CH08 RSA
非對稱式金鑰加密 (Asymmetric Cryptography)
分為公鑰與私鑰
公鑰用來加密，私鑰解密
- 優點
- Key 的傳輸方便許多，畢竟公鑰不需要 Secure channel 就可傳輸簽章，確保了訊息完整性
- 缺點
- 計算量大
實際上的加解密系統會融合非對稱式金鑰以及對稱式，稱為 Hybrid System
主要的訊息由對稱式加密負責，金鑰由非對稱式加密負責。
非對稱式金鑰加密演算法
目標 : One way function
$y = f(x)$ 很好計算，但是 $x = f^{-1}(y)$ 很難計算
方法 :
- 整數因數分解 Factoring integers
RSA - 離散對數 Discrete Logarithm
Diffie-Hellman, Elgamal, DSA
Given $𝑎, 𝑦$ and $𝑚$, find $𝑥$ such that $𝑎^𝑥 = 𝑦 \bmod 𝑚$ -› Exponentiation $𝑎^𝑥$ : easy - 橢圓曲線 Elliptic Curves (EC)
ECDH, ECDSA
金鑰長度與破譯難度的關係
同餘 $a ≡ b (\bmod c)$
如果 $a \bmod c$ == $b \bmod c$
- 加法性質
a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)- 乘法性質
a ≡ b (mod k) ＆ c ≡ d (mod k) <=> ac = bd (mod k)
a ≡ b (mod k) <=> a^n^ ≡ b^n^ (mod k)
a ≡ b (mod k) <=> am ≡ bm (mod k)
費馬小定理
假設 $a$ 為整數， $p$ 為質數，且 $a, p$ 互質 ( $GCD(a, p) = 1$ ) 則 $a^{p-1}≡1(\bmod p)$
歐拉函數 Euler’s Phi Function
$φ(n)$ 小於或等於 $n$ 的正整數中與 $n$ 互質的數目
$p$ 為質數， $φ(p) = p-1$
$φ(𝑚𝑛)=φ(𝑚) φ(𝑛)$ for $𝑚, 𝑛$ 互質
$φ(𝑝^𝑘)=𝑝^{𝑘−1}(𝑝−1)$
歐拉定理 Euler’s Theorem
$m, a$為整數，$m, a$互質
$a^{φ(m)}≡1(\bmod m)$
應用 : 求 $7^{222}$ 的個位數
7 與 10 互質，所以 $7^{φ(10)} \bmod 10 = 1$
$7^{4} \bmod 10 = 1$
所以 $7^{4 * 55 + 2} \bmod 10 = 7^2 \bmod 10 = 9$
中國剩餘定理 CRT
是數論中的一個關於一元線性同餘方程組的定理，說明了==一元線性同餘方程組==有解的準則以及求解方法。
EX1. $x≡4(\bmod 7)$ 且 $x≡3(\bmod 5)$ ，求 $x$
\(x = 4 + 7u\)
Square-and-Multiply
原理：將 $a^{2b}$ 拆成 ${(a^b)}^2$ 然後一直拆下去
用法：假設要算 $3^{13}$
- $13_{10}=1101_2$
- set $Res=1$，從 MSB 到 LSB。先將 $Res = Res^2$
- 如果位元為1，則 $Res=Res×13$
- Loop 4 次後 $Res$ 即為結果
那實際跑一次
- 1： $Res=1$ , $Res=Res^2=1^2=1$ , $Res=Res×3=3$
- 1： $Res=3$ , $Res=Res^2=3^2=9$ , $Res=Res×3=27$
- 0： $Res=27$ , $Res=Res^2=27^2=729$
- 1： $Res=729$ , $Res=Res^2=729^2=531441$ , $Res=Res×3=1594323$
複雜度 : n+1 bits 複雜度為 1.5n
質數測試
費馬質數判定法 Fermat Primality-Test
有一個質數 $p$ 隨機選一個 $a$, $1≦a≦p-1$ 計算 $b≡a^{p-1} (\bmod p)$ 假如 ==$b$ 不為 $1$ 則 $p$ 為合數==，反之則==可能==為質數
Miller-Rabin Primality-Test
假設 $p$ 為一質數，$p-1$ 可表示為 $2^{s}×d$。且 $s$ 為正整數、$d$ 為奇數
則此數如為質數，對於 $2≦a≦p-1$，必符合以下兩條件之一
- $a^d≡1$
- $a^{2^rd}≡-1$
※ $r$ 為滿足 $0≦r≦s-1$ 的整數
此測試做 $n$ 遍，出現錯誤的機率為 $𝑃𝑟𝑜𝑏(error) ≤ 4^{−𝑘}$
AKS
能夠在多項式時間完成質數測試
攻擊方法與反制方法
- Analytical attacks
算出組合出 $n$ 的 $p, q$ - Implementation attacks
透過 RSA 演算法在硬體以及軟體上的實作弱點去針對攻擊
CH10 公開式金鑰加密法
Diffie–Hellman key exchange
https://notes.andywu.tw/2019/%e4%bb%a5%e5%85%ac%e9%96%8b%e7%9a%84%e6%96%b9%e5%bc%8f%e4%ba%a4%e6%8f%9b%e8%b3%87%e8%a8%8a%e7%94%9f%e6%88%90%e5%b0%8d%e7%a8%b1%e5%bc%8f%e9%87%91%e9%91%b0/
Discrete Logarithm Problem (DLP)
給一質數 $p$，一個生成元 $α∈Z∗p$，一個元素 $β∈Z∗p$ ( Z∗p has order n)
求 $x$
滿足 $α^x≡β(\bmod p)$
中間人攻擊 Man in the middle attack
使用 Diffie–Hellman Key Exchange 產生金鑰雖然可以防止第三方監聽，
但如果遇到 ==中間人攻擊== 那就沒輒了
小美若介入了小明與小華的對話
當小明將 $(G^A \bmod P)$ 傳送給小華時把訊息給攔截
並假冒成小明傳送 $(G^C \bmod P)$ 給小華
(C是小美自己產生的隨機數，加上公開的P與G即可產生 $(G^C \bmod P) )$
依樣畫葫蘆，當小華將 $(G^B \bmod P)$ 傳送給小明時把訊息攔截
並假冒成小華傳送 $(G^D \bmod P)$ 給小明
(D是小美自己產生的隨機數，加上公開的P與G即可產生 $(G^D \bmod P) )$
如此一來，小美即成為擁有金鑰的中間人
往後可以神不知鬼不覺的把加密訊息用現有的 $P、G、C、D$ 給解密了
CH11 Hash
- preimage resistance (one way function)
$H(x)=z$
但 $z$ 無法找回 $x$ - Collision resistance
計算上不可能找的到一個 $x_2$ 符合 $H(x_2)=H(x_1)$ 且 $x_1≠x_2$
