# 資訊安全(密碼學)
:::success
:::spoiler 目錄
[TOC]
:::
| 內 | | | 外 | $\leftarrow$ |
|:---- |------ | ---------------------- |:-------- |:------ |
| 數論 | 密碼學 | 資安技術 | 資安應用 | $\leftarrow$攻擊 |
| | | 加解密、數位簽章、確認 | | $\leftarrow$ |
- 古典密碼學與現代密碼學的分歧點在計算機的發明
- ==攻擊模式==
- 竊聽
- 修改
- 偽裝
- 中斷
- [阻斷式服務攻擊](https://reurl.cc/5Oq6Qn)(Denial-of-Service attack/DoS)
Distributed Denial-of-Service/DDos
- 主動式(active)
- 被動式(passtive)
- 資訊安全[Shamir大師](https://zh.wikipedia.org/zh-tw/%E9%98%BF%E8%BF%AA%C2%B7%E8%90%A8%E8%8E%AB%E5%B0%94)十大建議
- 結論：安全-便利-成本要保持平衡
- 密碼術
- 加密(密碼學)
- 解密(破密學)
- 隱藏學(Steganography)與密碼學(Cryptography)
- 密碼學：加密前後大小不變
- 隱藏學：隱藏後變大
例如：圖片、影片、聲音(多媒體)、大量文字
- 安全服務總類
- 機密性(**C**onfidentiality)
- 完整性(**I**ntegrity)
不被竊取修改
- 確認性(**A**uthentication)
- 重要程度：IT C>I>A，OT A>I>C
:::spoiler
IT(Information Technology)
OT(Operation Technology)
:::
- 不可否認性(Non-repudiation)
類似交易收據，數位簽章
:::spoiler
數位簽章：屬於電子簽章的一種。
數位簽章有運用到密碼學
:::
- 存取控制(Access Control)
- 可使用性(Availability)
- 保密時效性：經過加密後，使用某種破解法仍有一定長度時間的保密性
## 古典密碼學(Classical Cryptography)
- ==[Kerckhoffs's principle](https://reurl.cc/QZ3zqZ)==
- Hacker已知演算法和密文，但不知道Key，
若解不出key或明文，則密碼安全。
- 演算法公開，目的是讓人檢視
- ==破密方法==
1. Ciphertext-Only Attack
2. Known-Plaintext Attack
3. Chosen-Ciphertext Attack
4. Chosen-Plaintext Attack
5. Chosen-Text Attack 我不知道這是什麼
- 密碼系統的分類
- 金鑰數目
- 對稱密碼系統(Symmetric Cryptosystem)
- 非對稱密碼系統(Asymmetric Cryptosystem)
- ==古典技術==
- 代換法
- 凱薩加密
- 單一字母加密
- 多種字母加密
- 換位法
- 籬笆加密
- playfair 波雷費加密
- 視覺密碼
- 黑白視覺密碼技術
- 現代技術
## 對稱密碼系統(Symmetric Cryptosystem)
:::success
- **DES (Data Encryption Standard)**
- **AES (Advanced Encryption Standard)**
:::
:::warning
- 相較於非對稱式
- 優點
- 較快速
- 使用足夠大的密碼將難以破解
- 缺點
- 金鑰分配及管理問題
- 數位簽章問題
- 無法提供不可否認性
:::
### DES(Data Encryption Standard)/DEA(Data Encryption Algorithm)
- 屬於一種區塊加密法 (Block Cipher)
- 每次加解密區塊大小為 64 Bits，超過分割，不足補0
- 金鑰 64 Bits，有效長度為 56 Bits，8 Bits 為錯誤更正。
- 1Byte = 8 Bits
- 目前已不是安全的加密方式，因為 56 Bits 金鑰相對過短。
- Substitution-box(S盒) 作為模糊金鑰與密文之間之關係。
- 將輸入位元 m 轉匯成輸出位元 n
- S盒通常是固定的（例如DES和AES加密演算法）
- 也有一些加密演算法的S盒是基於金鑰動態生成的
#### $\color{red}{\text{DES加密過程}}$
- **金鑰產生**
- 先做初始金鑰排列(KP)
- Key 為 56 Bits(限定)
- 選定金鑰(7個字元)，以8個位元編碼
- 以每7個位元分組後，加入1位[奇同位檢查碼]/(56+8)
- 金鑰排列 (KP/Key Permutation)，64 變回 56，排列表是固定的。
- 再產生各階段金鑰
- 拆成兩個部分($K_{L0}$、$K_{R0}$)，左右兩遍各28
- 使用左移位數表，每階段左旋不同位數
- 壓縮排列(CP)，56 變為 48，壓縮表是固定的。
- 各階段都類似
- **加密過程(64 Bits)**
- 明文 IP(初始排列)，使用初始排列表(固定)。
- 分成左右兩組
- 做運算
$L_j=R_{j-1}$
$R_j=L_{j-1} \oplus f(R_{j-1},K_j)$
- $\oplus$ 互斥或
:::info
- $f()$ 費斯妥函數
- **EP**(擴增排列) 32 變 48，使用擴增排列表
- 引入先前產生的子金鑰，依不同的回合做 XOR 運算
- S-box
- 48 Bits 以每 6 Bits 分成8個區塊
- Example: $...011\ {\color{red}{1}}0101{\color{red}{1}}\ 100 ...$
- 最左最右兩邊 Bits 作為列索引，$\color{red}{11}$
- 或者說與其他區塊相鄰的 2 個 bits
- 剩下的為行索引 $0101$
- 使用對應的 8 個 S-box 做置換為 4 Bits 輸出
- P-box，最後得到的 32 Bits 為輸出再以 P-box 置換，擴張為 64Bits
:::
- 重複16次
- EP、S-box、P-box，皆可以滿足 混淆(confusion) and 擴散(diffusion)
#### 2DES and 3DES
- Double DES(2DES)
- 預期$2^{112}$
- 實際$2^{57}$
- 明文$\rightarrow$中間值$\rightarrow$密文
- 假設攻擊者有一對明文密文對，他窮舉所有的k2把密文解密成中間值。於是他會有 $2^{56}$個中間值
- 接著他窮舉每一個k1得到$2^{56}$個中間值，然後跟剛才得到的中間值做比對，就得到k1和k2
- 沒有更安全
- Triple DES(3DES)
- 安全
- 共有以下四種類型。
規則如右：$E$(加密)、$D$(解密)、(幾把不同金鑰)
- $EEE3$
- $EDE3$
- $EEE2$
- $EDE2$
- 任意舉例
$\text{密文}=E_{K_3}(D_{K_2}(E_{K_1}(\text{明文})))$
屬於$EDE3$。
$\text{密文}=E_{K_2}(E_{K_2}(E_{K_1}(\text{明文})))$
屬於$EEE2$。
- 解密反之。
#### ==四種對稱式金鑰密碼系統加密模式==
:::spoiler 縮寫
- IV 初始向量
:::
- ECB Mode (Electronic Code Book Mode)
- CBC Mode (Cipher Block Chaining Mode)
- CFB Mode (Cipher Feedback Mode)
- OFB Mode (Output Feedback Mode)
:::success
| ECB | CBC | CFB、OFB |
| -------- | -------- | -------- |
| 可平行處理 | 相同明文可以產生不同密文 | 加密區塊可變動 |
:::
:::danger
| ECB | CBC | CFB、OFB |
|:---------------------------- | ----------------------- | -------------- |
| 相同明文產生相同密文，內容可被剪貼 | 不能平行處理，沒有剪貼問題 | 加密區塊可變動 |
| | 有錯誤擴散的問題(Chain) | 有錯誤擴散的問題 |
:::
:::success
:::spoiler 混淆(confusion)與擴散(diffusion)
Claude Elwood Shannon 在1940年代提出的實用密碼所需的必要條件
- Confusion
- 使 **密文** 和對稱式加密方法中 **金鑰** 的關係複雜化
- 掩蓋明文與密文之間的關係
- 可以降低使用密文冗餘度和統計模式破解的可能性
- 最容易的方法是「代替」
- Diffusion
- 使 **明文** 和 **密文** 的關係變得更複雜，明文中任何一點小更動都會引發 **Avalanche effect** (崩塌效應)。
- 產生擴散最簡單的方法是換位（置換）。
:::
### AED(Advanced Encryption Standard) or Rijndael加密法
- AES 是一種區塊加密
- Block Cipher(區塊加密器)設計原則
- 迷惑性:
- 明文金鑰位元 擴散性
- 實現 規則性
- 運算 簡單性
- 加密與解密 相似性
- 安全性高於3DES，且有更高效率
- 區塊大小固定為128Bits
- 根據不同的金鑰長度可寫作AES-128、AES-192、AES-256
- round(回合)，根據金鑰長度，AES會決定不同的round次數，有
| Round | Key size(Bits) |
|:----- | -------------- |
| 10 | 128 |
| 14 | 192 |
| 16 | 256 |
- 雖然Key長度有128、192、256三種，但是 round key 只有一種長度，4 words /16 bytes /128 Bits，目的是為了能在各round進行矩陣運算。
- AES加密過程要在一個$4\times 4$的byte(位元組)矩陣上進行，此矩陣又稱作state。
#### AES加密過程
- 先看這個吧，簡易流程
[圖片來源](https://ithelp.ithome.com.tw/articles/10234844)
- 在加密之前，資料要先進行預先處理
- 將資料每8 bits一組，將資料分成byte
- 將bytes依序排成矩陣，******以16進位表示******
- round key是很重要的，在全部開始之前，我們要有第一把round key，所以要先做第一次AddRoundKey。
:::info
==加密四步驟==
- AddRoundKey
- 將原矩陣與回合金鑰形成的矩陣對應的byte做XOR($\oplus$)運算，得到新的矩陣
- [SubBytes](https://ie.u-ryukyu.ac.jp/~wada/design04/spec_e.html)
- 利用S-box進行轉換
- 此S-box與DES的不同
- 可以用矩陣乘法表示
${\displaystyle {\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}}$
- 也可以用快速查表(需使用16進位)
[iThelp](https://ithelp.ithome.com.tw/articles/10267406)
- ShiftRows
- 不說了上圖
[source](https://comp38411.jtang.dev/docs/conventional-cryptography/advanced-encryption-standard/)
- MixColumns
- [**Finite Field**](#Finite_Field)
- 將 ShiftRows 得來的矩陣與一個**固定**的矩陣做運算
- 
- 固定矩陣為 $\begin{bmatrix}
2&3&1&1\\
1&2&3&1\\
1&1&2&3\\
3&1&1&2\\
\end{bmatrix}$
- 這個固定的矩陣是由${a(x)=(3x^{3}+x^{2}+x+2)} \pmod {x^4+1}$而來
- 每一列都視為一個多項式 $b(x)$
- 新的 $s'$ columns 由 $a(x)\otimes b(x) \pmod {x^4+1}$ 得出
- 固定的矩陣是簡化運算的結果(可見[wiki](https://en.wikipedia.org/wiki/Rijndael_MixColumns))
:::
- 金鑰怎麼產生的?
:::info
產生金鑰
- 擴充金鑰(Extended Key)和回合金鑰Round Key是不同東西，回合金鑰才是加密用的金鑰。
- RotWord
左循環一個bit
- SubWord
S-box，同SubBytes
- Rcon
- $rcon_i=[ rc_i\ 00_{16}\ 00_{16}\ 00_{16}]$
- $rc_{i}={\begin{cases}1&{\text{if }}i=1\\
2\cdot rc_{i-1}&{\text{if }}i>1{\text{ and }}rc_{i-1}<80_{16}\\
(2\cdot rc_{i-1})\oplus {\text{11B}}_{16}&
{\text{if }}i>1{\text{ and }}rc_{i-1}\geq 80_{16}\end{cases}}$
11B$_{16}$=0x11B
- 快速查表
| round(i) | $rc_i$ $_{(16)}$ |
|:-------- |:---------------- |
| 1 | 01 |
| 2 | 02 |
| 3 | 04 |
| 4 | 08 |
| 5 | 10 |
| 6 | 20 |
| 7 | 40 |
| 8 | 80 |
| 9 | 1B |
| 10 | 36 |
- ${W_{i}={\begin{cases}
K_{i}&{\text{if }}i<N\\
W_{i-N}\oplus \operatorname {SubWord}(\operatorname {RotWord} (W_{i-1}))\oplus rcon_{i/N}&
{\text{if }}i\geq N{\text{ and }}i\equiv 0{\pmod {N}}\\
W_{i-N}\oplus \operatorname {SubWord} (W_{i-1})&
{\text{if }}i\geq N{\text{, }}N>6{\text{, and }}i\equiv 4{\pmod {N}}\\
W_{i-N}\oplus W_{i-1}&{\text{otherwise.}}\\
\end{cases}}}$[wiki](https://en.wikipedia.org/wiki/AES_key_schedule)
- 擴充金鑰($W$)
- 金鑰長度($N$)(Words)(4、6、8)
- 原金鑰($K$)
- Round($R$)
- R會比回合數+1，因為AES最前的步驟會先做一次混合。
- $i=0;\ i\le 4R-1;\ i++$
- 因為擴充金鑰(W)每次剛好會產生32bits，但round key長度為128bits，所以要$\times 4$
:::
## 非對稱密碼系統(Asymmetric Cryptosystem)
- 對稱密碼系統(Symmetric Cryptosystem)
:::info
- 功能
- 保護機密資訊
- 鑑定收送方之身份
- 確保資訊完整性
:::
:::success
:::spoiler 優點
- 較快速 $1/1000$
- 金鑰長度短 $1/30$
- 計算能力弱的機器也可運算
- 使用足夠大的密碼將難以破解
:::
:::warning
:::spoiler 缺點
- 金鑰分配及管理問題
- 若與多人秘密通訊，需保存的金鑰數目太多(KMP)
- 數位簽章問題
- 無法提供不可否認性
:::
- 非對稱密碼系統(Asymmetric Cryptosystem)
:::info
- 功能
- 保護機密資訊
- 鑑定收送方之身份
- 確保資訊完整性
- 數位簽章
:::
:::success
:::spoiler 優點
- 簡化金鑰管理(KDP)
- 公開鑰匙可以公開分送
- 提供私密性、驗證與不可否認性等服務
:::
:::warning
:::spoiler 缺點
- 效率較差
- 金鑰長度長
- 計算能力弱的機器運算吃力
:::
- 優點缺點是相對的，實務上兩者都會使用，相輔相成，無法互相取代
:::success
| | 對稱 | 非對稱 |
| --------------------- | ---- | ------ |
| **其他名稱** | 秘密金鑰加密法 | 公開金鑰加密法 |
| **加解密key是否相同** | 相同 | 不同 |
| **key是否公開** | 不可公開 | 公鑰公開，私鑰不公開 |
| **key保管問題** | 若有多個使用者將有多把金鑰 | 每個使用者只須保管好自己的金鑰 |
| **速度** | 快 | 慢 |
| **應用** | 常用於加密較長的資料。例如:email | 常用於加密較短的資料、數位簽章 |
:::
- 衍生問題：[公開金鑰管理問題](#公開金鑰管理方法)。怎麼確認公開金鑰正確$\rightarrow$==憑證(網路身分證)==
- 再衍生問題：憑證信任中心...，區塊練去中心化，以個人衍生信任。
### 電子簽章與數位簽章
- 電子簽章
依附於電子文件，用以辨識確認電子文件簽屬人身分、資格、文件真偽
- 數位簽章
加密演算法，以簽署人私鑰簽章(加密)，公鑰得以驗證
- 電子簽章包含數位簽章
- 目前只有數位簽章
---
- 加密與簽章順序...
- 先簽章後加密
通常
- 先加密後簽章
少用
不好，會暴露身分、驗證時不知道內容為何
- 非對稱密碼系統有兩個部分
- 加密
- 簽章
- 公鑰加密、驗證
- 私鑰解密、簽章
- 「公鑰」可以驗證「私鑰」簽名的檔案，「私鑰」可以解開「公鑰」加密的檔案。
- DH公開金鑰分配系統
- 不是公開金鑰==密碼==系統
- 
- [wiki](https://reurl.cc/7M17kd)
- $a,b$ 是隨機的 $a<p$ and $b<p$
### RSA Cryptosystem
- **確定式**的公開金鑰加密法，相同明文產生相同密文
- 一種區塊加密
- 密文不膨脹
- 基於大數質因數分解難題
#### RSA加密演算法
- 產生金鑰(公鑰與私鑰)
:::info
1. 選取兩個prime，$p,q$，這兩個數通常非常大
2. 利用歐拉公式求得${r=\phi (N)=\phi (p)\times \phi (q)=(p-1)(q-1)}$
3. 選擇一個小於 $r$ 的整數 $e$，使 $e$ 與 $r$ 互質。並求得 $e$ 關於 $r$ 的模反元素，
$d=e^{-1}\bmod r$ 即 ${ed\equiv 1{\pmod {r}}}$（模反元素存在，若且唯若 $e$ 與 $r$ 互質）
4. 銷毀 $p,q$
5. 得到(KU)公鑰$(N,e)$與(KR)私鑰$(N,d)$
:::
- 加解密
:::info
- 加密
- 將明文 $M$ 轉換成長度$m$，$(m<N)$
- $C=m^e \bmod N$
- 解密
- 密文 $C$
- $m=C^d \bmod N$
:::
- >$C^d=m^{ed}\bmod N$
>由先前得知，$ed \equiv 1 \pmod r$，也就是$ed=kr+1=k\phi(N)+1$
>根據歐拉定理，當$\gcd(m,N)=1$ $m^{ed}=m^{1+k\phi (N)}=m\cdot m^{k\phi (N)}
>=m\left(m^{\phi (N)}\right)^{k} \equiv m(1)^{k}\equiv m{\pmod {N}}$
>當$\gcd(m,N)\neq1$，看不懂
>解密流程原理說明
- 簽章：$M=19$
$S= M^d \bmod n = 19^{77} \bmod 119=66 \bmod 119$
私鑰簽章
- 驗證：
$M ?= S^e \bmod n = (66 )^5 \bmod 119=19$
公鑰驗證
### [Hash Function](https://reurl.cc/9R27va)
- 也稱作雜湊演算法
- 給定一個明文輸入，經過Hash function後得到固定長度的Hash value
- 常見的 Hash Function
- MD2,MD5,SHA-128,SHA-256
- SHA-128 SHA-256
- SHA-256比較安全
- 雜湊值可視為明文的摘要(Digest)
- Hash function 會將明文轉為固定長度，使資料量縮小，格式固定
- 將 Hash value 以私鑰加密後，可達到==資料完整性及不可否認性==
- 碰撞/衝突(Collision)：當相同的明文輸入得到相同的密文稱為碰撞。
- 好或不好，不一定
- 數字摘要：利用碰撞特性，檢查內文是否被竄改過。
- **One way Hash function** ==單向==雜湊函數
1. 產生的 Hash value 長度都固定
2. Hash value 可由軟體或硬體計算出
3. 計算是==單向==的，也就是說找任意的 hash value 去計算出明文是不可能的
4. 對於一個訊息 $M_1$，在計算上是無法找出另一個訊息 $M_2 (\neq M_1)$，使得 $H(M_1) = H(M_2)$。也就是說，給定一個雜湊值$(H(M_1))$，須無法找出另一個訊息$(M_2)$，使其所產生的雜湊值相同。
5. 就兩訊息 $M_1$、$M_2$ 而言，若他們的雜湊值相等，亦即 $H(M_1) = H(M_2)$，則 $M_1$ 與 $M_2$ 兩訊息也一定相等$(M_1=M_2)$；
同理，若 $H(M_1)\neq H(M_2)$，則 $M_1\neq M_2$。也就是說，給定一個明文與雜湊值，須保證無法找出另一個訊息來產生同樣的雜湊值。
- 符合1~4為 weak Hash function
- 符合1~5為 Strong Hash function
### ElGamal Cryptosystem
- **機率式**的公開金鑰加密法
- 相同明文會有不同密文
- 參入亂數加密會讓密文膨脹
- 不參亂數相同明文會有相同密文
- DLP(discrete logarithem problem)
#### ElGamal加密演算法
- 參數
:::info
- 系統參數
- $p:$ 大質數
- $g:$ ==原根(primitive root)==$\pmod p$
- 使用者B之秘密金鑰: $x_B$，從 $\{1,2,3...p-1\}$ 挑出
- 使用者B之公開金鑰 : $y_B=g^{x_B} \bmod p$
:::
- 加解密
:::info
- 明文 $M$
- 任取亂數 $k,1<k<p-1$
- 計算密文對$(C_1,C_2)$
- $C_1=g^k \bmod p$
- $C_2=M\times {y_B}^{k}\bmod p$
:::
:::info
- 明文 $M= C_2\times({C_1}^{x_B})^{-1}\bmod p$
$M= M\times {y_b}^{k}\times(g^{k\times x_B})^{-1}\bmod p$
$M= M\times g^{k\times x_B} \times(g^{k\times x_B})^{-1}\bmod p$
:::
- 公鑰加密，私鑰解密
- 數位簽章，明文 $M$ hash function: $h(M)$
- 任取亂數 $k,1<k<p-1,\gcd(k,p-1)=1$
- $r=g^k \bmod p$
- $h(M)=x_B\times r+k\times s \bmod (p-1)$
- $(r,s)$ 用於數位簽章
- $g^{h(M)} ?={y_B}^r\times r^s \bmod p$
- [證明](http://itchen.class.kmu.edu.tw/Crypto/Slides/Reference/Chap07%BC%C6%A6%EC%C3%B1%B3%B9%A7%DE%B3N.pdf)
#### DSS數位簽章系統
- 採用**DSA**（Digital Signature Algorithm）
- DSS(Digital Signature Standard)
- 由 ElGamal 改良而來
- ==只能用來簽章==
- 參數
:::info
- $p$: 大質數(約1024bits)
- $q,q|p-1$: 大質數(約160bits)降低簽章長度
- $g:g=\alpha ^{(p-1)/q}\bmod p, 1\leq\alpha\leq(p-1)$
- 使用者B之秘密金鑰: $x_B$，從 $\{1,2,3...p-1\}$ 挑出
- 使用者B之公開金鑰 : $y_B=g^{x_B} \bmod p$
:::
- 簽章
:::info
- 任取亂數 $k,1<k<q$
- $r=g^k \bmod p$
- $s=k^{-1}(h(M)+x_B\times r) \bmod q$
- $(r,s)$ 用於數位簽章
:::
- 驗證
:::info
- $t=s^{-1} \bmod q$
- 檢查 $r ?=g^{h(M)t}\times {y_B}^{rt} \bmod p$
:::
:::success
:::spoiler DSS優缺點
- 對 DSS 的正面評價：
1. 利用 DSA 所產生的數位簽章長度較短。
2. 在簽署過程中，如對 r 採用預處理程序，可減少簽署時間。
3. 金鑰產生速度相當快。
4. 經過政府的確認，可保證一定程度的安全性。
- 對 DSS 的負面評價：
1. 因為 DSA 與 RSA 並不相容，業界多已接受 RSA，兩套標準勢必造成困擾。
2. DSA 可能侵犯 Schnorr 簽署方法的專利權。
3. 在驗證過程中，若 ==s=0==，將造成除零錯誤。此一情況在標準文件中並未提及。其解決方法為在簽署時若發現 s=0，則另選一個 k 重新簽署。
4. ==DSS 的驗證程序比 RSA 約慢了 100 倍。==
5. ==DSA 之安全並不全基於離散對數==，是否可能影響其安全性值得研究。
6. DSA 採用了與 ElGamal 類似的技術，然而卻==未採用 ElGamal 原根的機制==，這個作法是否會影響其安全性，值得研究。
7. k 值的產生過程對 DSA 的安全性有極大的影響。
8. 有人懷疑美國政府公佈此一標準是否有其它的動機。換言之，美國政府是否已知 DSA 潛在的漏洞，以便於執法。**????**
:::
#### 比較表
### Elliptic Curve Cryotosystem(ECC)
- 橢圓曲線密碼系統
:::info
- 基於離散對數問題
- 金鑰長度比 RSA 短很多
- 相同的金鑰長度計算大致相同
- 在相似的安全性下，ECC提供較好的運算優勢
:::
- 其方程式為：$y^2=x^3+ax+b$
- $x,y,a,b$ 為實數
- 為在 finite field 下的平面曲線，而非實數域
- $(E,+)$。點的集合，在加法下視為一個 abelian group [(交換群)](#群_環_體)。
:::warning
1. 封閉性
2. 交換性
3. **單位元素：** 尋找並確定橢圓曲線上的零元素（通常被稱為無窮遠點），它應該是加法操作的恆等元素。
4. **逆元素：** 確保每個點都有其相對應的加法逆元素。對於每個點 $(P)$，都存在一個點 $(-P)$，使得 $(P + (-P) = O)$。
- 在橢圓曲線上，一點反相點的x座標會和該點相同，而y座標會為該點座標的負值：
${\begin{aligned}
(x,y)+(-(x,y))&={\mathcal {O}}\\
(x,y)+(x,-y)&={\mathcal {O}}\\
(x,-y)&=-(x,y)\end{aligned}}$
5. 結合性
:::
- 
- P+P 切線
[wiki](https://reurl.cc/DoaKlQ)
- ==注意$P+Q+R=0$，所以$P+Q=-R$==
- 在計算的時候$x_R$為正確值，$y_R$要加上$-$號
- 接下來會有一些我們要在意的地方
:::info
- Slope
- The sum of $P+Q$
- Finite field
- Prime
- Binary
:::
- Slope and $P+Q$
- ==斜率==有兩種算法
- 點斜式：$s={y_Q-y_P \over x_Q-x_P}\text{ ,if }P\neq Q$
- 取導數：由 $y^2=x^3+ax+b$ 得 $s={3x^2+a \over 2y}\text{ ,if }P=Q$
- 計算斜率是為了求得$R(x,y)$
:::success
- 通式：$\left\{
\begin{array}{c}
x_R=s^2-x_P-x_Q\\
{\color{red}{-}y_R}=y_P+s(x_R-x_P)
\end{array}
\right.$
:::
- :::spoiler 證明
> 方程式:$y^2=x^3+ax+b$
> 直線方程式:$y=sx+d \Rightarrow y^2$
> 方程式的3的根:$y^2=(x-x_P)(x-x_Q)(x-x_R)$
> 帶入之後便可得 $s^2$ 與 $x_R$ 關係
:::
- Finite field
- $E_P(a,b): y^2=x^3+ax+b \bmod p$
- 意思是以上的運算都要在$\bmod p$下運算
#### 分享公鑰方式
1. 決定 $E_q(a,b)$
2. 選定 $G(x_1,y_1)$ 大 $n,nG = O$
3. 選定雙方私鑰$n_A,n_B$ 且 $n_A,n_B<n$
4. 計算雙方公鑰$P_\alpha=n_\alpha G$
5. 分享方式$K=n_An_BG$
#### 加解密
1. 沿用分享公鑰參數
2. 加密 $P_m : C_m=\{kG, P_m+kP_B\}, k$ is random
3. 解密 $C_m$, to compute: $P_m+kP_B–n_B(kG) = P_m+k(n_BG)–n_B(kG) = P_m$
> 有沒有快速計算$kP_B$的方式?
#### 數位簽章
- $s=(n_B\times r+e)\times k^{-1} \bmod n, k$ is random and $r= x_P$
- $(r, s)$ is the signature of the message M
- 核對 $(r, s)$ and $M$:
- Compute $e=h(M)$
- Compute $P' =(x_P’, y_P’)=e\times s^{-1}\times G+r\times s^{-1} \times P_B$
- If $r=x_P’$, the signature is correct.
### 混合式加密
- AES加密RSA分配金鑰
- 快速+沒有金鑰分配的問題
- 1byte = 8bits
- 加密次數：1次RSA大約等於1000AES
## 數論(Number Theory)
- **mod m 同餘**是整數集合中一個**等價關係**
- 同餘(Congruence)
- 整數特性
- Closure(封閉性)
- Commutative laws（交換性）
- Associative laws（結合性）
- Distributive law（分配性）
- Cancellation law（消去性）：對整數$a、b、c$若$a*c=b*c$ 且 $c≠0$，則$a=b$
:::warning
- Identity elements（單位元素）：對整數 $a$ 滿足 $a+0=a$ 且 $a*1=a$
- 當其他元素與單位元素結合後，不會改變那些元素
- $0$ 是加法單位元素
- $1$ 是乘法單位元素
- Additive inverse（加法反元素）：對整數$a$，若 $a+x=0$,則 $x$ 稱為 $a$ 的加法反元素
- 當元素與某元素結合後，變成單位元素，則稱某元素為該元素的反元素
- 整數系底下沒有乘法反元素
:::
### 群_環_體
- Group $(G,\circ)$
- $\text{G: a set, } \circ\text{: 某二元運算}$
:::info
1. Closability: $∀ a, b ∈ G, a × b ∈ G$
2. Associativity: $∀ a, b, c ∈ G, (a × b) × c = a ×(b × c) ∈ G$
3. Identity: $∀ a ∈ G, a × e =e × a= a$
4. Inversability: $∀ a ∈ G, ∃ a^{-1} ∈ G, a× a^{-1} = a^{-1} ×a= e$
5. 交換群(commutative group) or 阿貝爾群(abelian group): 符合交換律
:::
- Ring $(R, +, \times)$
:::info
1. $(R,+)$ 為==交換群==
- 也就是說，環要先滿足群
2. 封閉性：乘法之封閉性
3. 結合性：乘法之結合律
4. 乘法之單位元素：存在 $1 ∈ R$，使得對任意 $a ∈ R，a×1 = 1×a = a$
5. 分配性： $∀a, b, c ∈R, (a+b)×c = a×c + b×c$
6. 如果運算 $×$ 是可交換的，我們說 $(R,+,×)$ 是交換環(commutative ring)
:::
- Field $(F,+,\times)$
:::info
1. $(F,+,×)$ 為==交換環==
2. 除了 0 以外的元素均存在==乘法反元素==
:::
### 歐幾里得演算法(Euclid Algorithm)
- 又稱作輾轉相除法
- 兩個整數的最大公因數為所有能整除這兩個整數之最大整數
- $\gcd(10, 25)=5$
- $\gcd(a, 0)=a$
- $\gcd(a, b) = \gcd(b, r)$, 其中 $r$ 是 $a$ 除以 $b$ 的餘數
- 由上述寫作算式後
- 舉例來說$\gcd(1071, 462)$
1. $1071=2\times{\color{red}{462}}+{\color{blue}{147}}$
2. ${\color{red}{462}}=3\times{\color{blue}{147}}+{\color{green}{21}}$
3. ${\color{blue}{147}}=7\times{\color{green}{21}}+0$
- 歐幾里得演算法的想法
- $1071=2\times(3\times(7\times{\color{red}{21}})+{\color{red}{21}})+7\times{\color{red}{21}}$
- $462=3\times(7\times{\color{red}{21}})+{\color{red}{21}}{\times1}$
- 一直把大數字縮小為小數字相乘
- 貝祖等式
- $ax+by=\gcd(a,b)$
- 找到GCD的同時，也找到能滿足
$ax+by=\gcd(a,b)$ 的 $(x,y)\text{，where }x,y\in \mathbf{Z}，x,y \neq0$
- [延伸歐幾里得演算法](https://reurl.cc/q0qKoE)
- 可以用來找兩個數的乘法反元素
- 乘法反元素：2 是 $8\pmod{15}$的乘法反元素
- $(2\times8)\bmod15=1$
- [計算機](https://mrraybox.blogspot.com/2015/03/blog-post.html)
### 模運算
- $\mathbf Z$ = Set of all integers = $\{…, -2, -1, 0, 1, 2, …\}$
- $\mathbf Z_n$ = Set of all non-negative integers less than n= $\{0, 1, 2, …, n-1\}$
- 同餘(Congruence)
#### Finite_Field
- 若一個體[Field](#群、環、體)$F$，其元素無限多個，稱Infinite Field(無限體)
- 若有限個，稱Finite Field（有限體）
- Galois Field$\text{ (GF)}$
:::success
- Galois(蓋洛瓦)證明如果一個體為有限體，其中p為質數、n為正整數，則其元素個數為$p^n$
- Galois Fields(蓋洛瓦體) $\text{GF}(p^n)$是一個有限體，內含$p^n$個元素
:::
- 在Galois Fields $\text{GF}(2^n)$底下
- 沒有+-號區別，加減運算都等於$\text{xor }\oplus$
- $\otimes$ 先相乘再取mod
:::success
- $(x^5+ x^2+ x)\otimes (x^7+ x^4+ x^3+ x^2+ x)=$?
- $\Rightarrow(x^5+ x^2+ x)\times
(x^7\oplus x^4\oplus x^3\oplus x^2\oplus x)$
- $\Rightarrow(00100110) \times$
$[(10000000)\oplus(00010000)\oplus(00001000)\oplus(00000100)\oplus(00000010)]$
- 提前列好$(00100110) \times$各數的表就好
:::
### [Euler Totient Function](https://reurl.cc/4WMqXV) $\phi(n)$
- $\mathbf{Z_n}^*=\{x | x∈\mathbf{Z_n} , x>0\text{ and }\gcd(x, n)=1\}$:
Reduced Set of Residue
也就是與n互質且小於n的所有正整數集合
:::success
- $\phi(n)$ : Euler Totient Function
- $\phi(n) =|\mathbf{Z_n}^*|$：表$\mathbf{Z_n}^*$內的正整數個數
- 若n為質數(prime)，則$\phi(n) = n-1$
- $n=11,\phi(11) = 11-1=10$
- 若$n=p\times q$ 為合成數(composite number)
- $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}$為n的標準分解式
- $\phi(n)=p_{1}^{k_{1}-1}p_{2}^{k_{2}-1}
\cdots p_{r}^{k_{r}-1}(p_{1}-1)(p_{2}-1)\cdots (p_{r}-1)$
- $n=10, \phi(10) = (2-1)\times(5-1)=4$
- $n=1024, \phi(1024) = 2^{10-1}*(2-1)=512$
:::
- [計算機](https://www.dcode.fr/euler-totient)
- ==Fermat's Little Theorem==: 若$p$為質數且$a\in \mathbf{Z_p}^*$，
則$a^{p-1}\equiv1 \mod p$
- 或$a^p\equiv a\mod p$
- 其逆定理不成立
- ==Euler Theorem:==
- 若$\gcd(a, n)=1$，則$a^{\phi(n)}\equiv 1\mod n$
- [計算機](https://www.omnicalculator.com/math/power-modulo)
- 快速指數運算
:::warning
- 沒看懂
- $5^{157}={{({{({{({{{{5^2}^2}^2}-5})^2}-5})^2}-5})^2}^2}-5$
- 邊mod邊運算
:::
利用$(157)_{10}=(10011101)_2$
將$5^{157}=5^{2^7}\times 5^{2^4}\times 5^{2^3}\times 5^{2^2}\times 5^{2^0}$
$=5^{128}\times 5^{16}\times 5^8\times 5^4\times 5^1$
再做mod運算
### [中國餘數定理](http://itchen.class.kmu.edu.tw/Crypto/Web/discrete/CRT2.html)
> 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？
> [name=《孫子算經》]
> 三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五便得知
> [name=《算法統宗》]
- 也就是說各先找到$N_1=\begin{cases}1\pmod 3 \\0\pmod 5 \\0\pmod 7 \\ \end{cases}\text{ 5和7的倍數}
,N_2=\begin{cases}0\pmod 3 \\1\pmod 5 \\0\pmod 7 \\ \end{cases}
,N_3=\begin{cases}0\pmod 3 \\0\pmod 5 \\1\pmod 7 \\ \end{cases}$
- 找到各自的==乘法反元素==
- 在按照描述所說，三三數之==剩二==，五五數之==剩三==，七七數之==剩二==
- $N=2\times N_1+3\times N_2+2\times N_3$
- $N_{min}=N\bmod(3\times5\times7)$
:::success
- ==標準做法==
- $N=R_1\times N_1\times {\color{red}{M_1}}
+R_2\times N_2\times {\color{red}{M_2}}
+R_3\times N_3\times {\color{red}{M_3}}$
- R是餘數，M是乘法反元素
- 一定要算乘法反元素，不然算不出最小值
- $N=\begin{cases}-1\pmod 3\text{ 這裡的-1可以看成2} \\1\pmod 5 \\5\pmod 7 \\ \end{cases}$
- $x = 5 \times15\times1+2\times35\times {\color{red}{(-1)}}+1 \times21\times 1$
$x = 75 - 70 + 21$
$x = 26$
- $N_{min}=26$ 正確
:::danger
- $N_{min}=166$ 錯誤
:::
- [計算機](https://nonagon.org/ExLibris/chinese-remainder-theorem-calculator)
### Primality Testing
- 機率式：**Miller-Rabin Algorithm**
- TEST (n) is prime:
:::success
1. Find integers $k, q$, and $k > 0, q$ odd, so that $(n–1)=2^kq$
2. Select a random integer $a, 1<a<n–1$
3. `if` $a^q\bmod n = 1$ then `return (“inconclusive")`;
$(q=n-1)$ ${\color{YellowGreen}{\text{(by Fermat's Little Theorem 成立，n有可能是質數)}}}$
4. `for j = 0 to k – 1`
- do`if` $( a^{{2^j}q} \bmod n = n-1)$
$(a^{{2^j}q}=n-1)$
${\color{YellowGreen}{\text{(by Fermat's Little Theorem 成立，n有可能是質數)}}}$
- then `return(“inconclusive")`
5. `return (“composite”)`
${\color{YellowGreen}{\text{(by Fermat Little Theorem 不成立，n必為合數)}}}$
### ==總結==
- $a^b \bmod n = (a\bmod n)^b \bmod n$
- $a^b \bmod n = a^{b \bmod\phi(n)}$
- $a^b \bmod n =$ (中國餘數定理 CRT)
- 將一個大的指數拆成由已知的多個mod運算表示
- 
- 快速指數運算
## 資安應用系統(Information Security Application System)
- PGP(Pretty Good Privacy)
1. 認證
2. 保密性
3. 壓縮
4. 電子郵件相容性
5. 細分
- 壓縮服務
- 壓縮時機
1. 簽章後壓縮，原因有二：
- 對未壓縮的明文簽章，則未來只需==儲存==未壓縮明文及數位簽章，即可驗證數位簽章的正確性
- 考量未來不同壓縮軟體的發展，因為數位簽章與明文可能要==保留很多年==
2. 加密前壓縮
- 原因：可降低明文的冗贅，使得密碼分析變得較困難
- E-mail相容性
- 對欲傳送的郵件而言，若使用PGP，則郵件會先被編碼8bit的stream
- 因==一些電子郵件系統只允許傳送ASCII 字元==，故PGP可提供轉換服務，將8bit stream轉成printable ASCII字元
- 因radix 64的使用，將使得==訊息擴增33%==
### 公開金鑰管理方法
- A怎知Public key真的是B的Public key，而非C偽冒B放上去的，或是C破解系統而將B的Public key竄改成C的Public key？
- 公開金鑰管理問題的可能解決方法
1. 直接從B那裡拿公開金鑰$PK_B$
- 太麻煩，不切實際
2. B透過Email傳送公開金鑰$PK$給A，A產生B公開金鑰$PK_B$的雜湊值，並用電話與B確認雜湊值是否正確
- 仍有可能被仿冒
3. 透過A與B都信任的第三者D來取得公開金鑰$PK_B$ ，則D用自己的私鑰對B的公開金鑰$PK_B$簽章，則A可驗證D的數位簽章是否正確，若正確，則A得到B的公開金鑰$PK_B$
- 去中心化 $\rightarrow$ 信任的第三方
4. 透過一個公開金鑰信任中心(Certificate Authority, CA)取得B的公開金鑰$PK_B$，X.509
- 信任中心，透過憑證
- ==PGP(公開金鑰管理中心)==
- 從你==本身==去確認那些key合法有效的
- 
- 信任保證
- 灰底：全信任
- 半灰底：半信任
- 合法存取
- 全信任保證
- 兩個半信任保證
Sign in with Wallet
Connect another wallet