---
# System prepended metadata

title: Information Security-資訊安全
tags: [資訊安全, 密碼學]

---

# 資訊安全(密碼學)

:::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加密過程

- 先看這個吧，簡易流程
  ![AES流程圖](https://hackmd.io/_uploads/S11t09Hgp.png)[圖片來源](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進位)
    ![查表](https://hackmd.io/_uploads/BkSGK6Bga.png)
    [iThelp](https://ithelp.ithome.com.tw/articles/10267406)
- ShiftRows
  - 不說了上圖
    ![ShiftRows](https://hackmd.io/_uploads/SJGl96re6.png)
    [source](https://comp38411.jtang.dev/docs/conventional-cryptography/advanced-encryption-standard/)
- MixColumns
  - [**Finite Field**](#Finite_Field)
  - 將 ShiftRows 得來的矩陣與一個**固定**的矩陣做運算
    - ![image](https://hackmd.io/_uploads/SJ6CYYwV6.png)
    - 固定矩陣為 $\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公開金鑰分配系統
  - 不是公開金鑰==密碼==系統
  - ![image](https://hackmd.io/_uploads/rJ3CdZXBT.png)
    - [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 潛在的漏洞，以便於執法。**????**
:::

#### 比較表

![比較表](https://hackmd.io/_uploads/rkuryt1L6.png)

### 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. 結合性
    :::
- ![image](https://hackmd.io/_uploads/HkOdkeQ86.png)
  - 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$
![image](https://hackmd.io/_uploads/S1lIxz78T.png)

#### 加解密

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運算表示
  - ![image](https://hackmd.io/_uploads/SJtZijvVa.png)
- 快速指數運算

## 資安應用系統(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合法有效的
  - ![image](https://hackmd.io/_uploads/r1m4oQXU6.png)
    - 信任保證
      - 灰底：全信任
      - 半灰底：半信任
    - 合法存取
      - 全信任保證
      - 兩個半信任保證
