# Crypto II by nynapig

:::danger
請愛惜共筆，勿進行惡意刪減
:::

:::info
下午的課程開始前請先在自己的電腦上下載 netcat，或是使用 OS 課程使用的虛擬機
:::

## 古典 vs 現代
- 古典密碼學
- 以**置換法**為基礎
- 應用於軍事和情報領域
- 現代密碼學
- 建立在數學、和通信科學
- 應用領域廣泛
- 二戰過後電腦發展迅速，開始改加密二進制形式的密碼
- 以語言學為基礎的加密技術因此失效
- 電腦強大的運算能力讓大部分的古典密碼**不再安全**
- 計算機與電子學的發展能實作更複雜的密碼系統
- 以語言學為基礎的破密術因此失效

## 訊息安全三要點 CIA

- **C**onfidentiality 機密性
- 防止未授權的揭露
- ex. 竊聽違反機密性
- **I**ntegrity 完整性
- 防止未授權的更改, 最少要能知道被竄改
- Ex：修改他人訊息違反完整性
- **A**vailability 可用性
- 確保訊息即時且可靠的被使用
- EX : 拒絕被訪問違反可用性

> 所有的加密都是能被破解的，並不存在無法破解的加密系統
> 所謂的安全的加密是指破解所需的成本(時間, 電腦硬體等)遠大於可被接受的範圍(例如要算1000年才能破解, 那就是安全的)

## Introduction
- 明文 pt
- 能直接讀的訊息
- 要保護的目標
- 密文 ct
- 加密後的產物
- 用來傳送
- 金鑰 key
- 要來加/解密的關鍵
- 分為公鑰、私鑰
- 私鑰需要保護好
- 演算法
- 須公開
- 用來加/解密的方法
### XOR 互斥或
- 0 XOR 0 = 0
- 0 XOR 1 = 1
- 1 XOR 0 = 1
- 1 XOR 1 = 0

### Min Lab
- 1 xor 0 = 1
- 1 xor 1 = 0
- (1 xor 1) xor 0 = 0
- (0 xor 1) xor 1 = 0
- (0 xor 1) xor (1 xor 1) = 1
- (0 xor 0) xor (1 xor 1) xor (0 xor 1) = 1

### 模運算 (取餘數)
- 常寫成 mod
- ${\equiv}$ 同於符號，餘數運算中的等於
- Ex:
- 8 ${\equiv}$ 2 mod 3, 8/3 = 2餘2
- 10 ${\equiv}$ 4 mod 6, 10 /6 = 1餘4
- 11 ${\equiv}$ 1 mod 2, 11/2 = 5餘1
### Min Lab
- 5 ${\equiv}$ x mod 3
- 12 ${\equiv}$ x mod 5
- 112 ${\equiv}$ x mod 7
- 99 ${\equiv}$ x mod 3
- 87 ${\equiv}$ x mod 11
- 78 ${\equiv}$ x mod 999

:::spoiler 解答
2,2,1,0,10,78
:::

## 對稱式加密

### 共同金鑰
- 加/解密使用同一把金鑰(key)
- 明文(pt) --> key ， 加密演算法 ---> 密文(ct)
- 密文(ct) --> key ， 解密演算法 ---> 明文(pt)

### 區塊加密
- 常用於一直訊息長度的情況
- 將明文分成一塊一塊等長的模組分別加密
- 長度不足通常會 padding 到足夠長度

### 串流加密
- 全部的明文/密文和 key 做加/解密
- 實踐中資料痛常是一個為( bit )並用互斥或 ( xor ) 操作加密

### DES 資料加密系統
#### Background
- 使用DEA
- Data Encryption Algorithm 資料加密演算法
- 1974 年 NBS ( 國家標準局，現在的NIST )向公眾徵集可以滿足嚴格設計標準的加密演算法，最終由 IBM 的演算法獲選
- DES在1976年11月被定為美國國家標準
- 優點
- 速度快
- 可加密大批資料
- 安全性高


#### f-Function
- DES主要加密函式四步驟：
- 1. Expansion E
- 2. XOR with round key
- 3. S-box substitution
- 4. Permutation

##### Expansion Function E
- 能夠增加更多組合性，提高破解難度
:::spoiler ex
exp_d =[32,1,2,3,4,5,6,7,8,9,8,9,10,11,12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,22,23,24,25,24,25,26,27,28,29,28,29,39,31,32,1]
for i in (0,48)
out_array[i]=inp_array[exp_d[i]-1]
##i:0~47
:::

##### XOR with round key
- 把 round key (48 bits) 和 擴展函式 E 的 out_array( 48 bits ) 做 XOE 的運算

##### S-box substitution
- 由八張替換表組成
- 對於每張表有 6 bits 的 input 和 4 bits 的 output

##### Permutation
- 和擴展函式 E 類似的矩陣轉換
- 轉換的方式一樣只是沒有擴展
- 32 bits 的輸入，32 bits 的輸出
:::spoiler per
per = [ 16, 7, 20, 21, 29, 12, 28, 17,
1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14,32, 27, 3, 9,
19, 13, 30, 6, 22, 11, 4, 25 ]
:::
#### Key Schedule
1. 把 64 bits 的 key 經過一個轉換矩陣 PC-1
2. 分成左右兩邊，再透過位移矩陣做左位移
左位移: 101 --> 011
3. 左右合併後再用 PC-2 轉換一次，得到 k1
4. 重複 2、3 直到有16把key

#### 使用模式
- Electronic Code Book mod (ECB)
- 
- Cipher Block Chaining mode (CBC)
- 
- Output Feedback mod (OFB)
- 
- Cipher Feedback mode (CFB)
- 
- Counter mode (CTR)
- 

#### ECB vs CBC
- 在加密時，ECB會保留明文的部分特徵
- 但 CBC 付出的代價是更長的加 / 解密時間
- 無法同時進行加 / 解密

[CyberChef](https://gchq.github.io/CyberChef/)

### DES面臨的問題

- 56 bits 的金鑰隨著運算能力加強，被暴力破解的可能越來越高
> 世界上沒有暴力不能解決的問題
> 如果有
> 就更暴力
> [name=nynapig]
- DES 的運作原理過於神奇，無法解釋的神奇
- S boxs 讓人懷疑背後是否有後門的存在
- 當時的徵選是非公開的
- 只有 NBS 和 IBM 參與，並沒有其他單位監督
> 黑箱

#### 如何解決？

- 對於過短的金鑰：
- 3DES：做三層的DES來達到加長金鑰的效果
- 重新生一個新的演算法啊
- 對於是否有後門：
- 重新生一個新的演算法啊
> 論為什麼要有弟弟妹妹
> 因為原本的不行了 所以要有新的，~~重練新號~~
> [name=nynapig]
- 結論：
- 與其修改不如砍掉重練
- 2002 年 5 月 26 日 AES 取代 DES 成為聯邦標準

## 非對稱式加密
### 對稱式加密的難題
- 舉個栗子 (chestnut)：
- 小明要送訊息給小美，他把明文 (pt) 用 key加密成密文 (ct) 後傳給小美，但小美不知道 key，所以小明又把 key 傳給小美，這樣小美就能解密了~
> 小明把key傳給小美???然後key就被攔截了@@
> ![Uploading file..._6jj6qwk0v]()

- 金鑰分為公鑰和私鑰
- ![Uploading file..._rnthb4h3r]()
### RSA 加密演算法

#### Background
- RSA 由在 1977 年由以下三位提出
- 羅納德·李維斯特（Ron **R**ivest）
- 阿迪·薩莫爾（Adi **S**hamir）
- 倫納德·阿德曼（Leonard **A**dleman）
- RSA 就是他們三人姓氏開頭字母拼在一起組成的

#### 演算法
- step1 : 選超大質數p、q(大小和安全等級相關)
- step2 : 計算模數 n = p*q
- step3 : 計算歐拉函數 $\varphi$(n) = (p-1) * (q-1)ˋ4ˋ4
- step4 : 選擇公鑰 e(1<e<$\varphi$(n)))互質
- e 常用65537
- step5 : 計算私鑰 d，滿足e * d ≡ 1(mod $\varphi$(n))

歐拉函數：小於這個數字且與這個數字互質的正整數數量，例如：φ(5) = 4
所有質數 n 的歐拉函數值 φ(n) = n - 1，因為比它小的正整數與該質數均互質
歐拉函數為積性函數，亦即若a, b互質時，滿足 φ(ab) = φ(a) * φ(b)

### 安全性
> 很難暴力拆解質因數
> 因為你不夠暴力
> [name=nynapig]
- 基於超大數值因數分解的數學難題

### problem
- 計算速度緩慢
- 在 2048 ~ 4096 bits 的模數下做運算要快有點難
- 低於 2058 bits 的 RSA 已有被破解紀錄
- 量子電腦的開發
- 讓 RSA 和運用超大質因數分解的加密演算法碰到瓶頸
- 補充：[秀爾演算法](https://zh.m.wikipedia.org/zh-tw/%E7%A7%80%E7%88%BE%E6%BC%94%E7%AE%97%E6%B3%95)

#### python 小教室

1. 使用別人寫好的 code:
- `from Crypto.Util.number import *`
2. 直接宣告變數：
- `英文變數名 = 變數值`
- ex. `n = 69420`

:::spoiler Template:

from Crypto.Util.number import *
n = XX
p = XX
q = XX
e = XX
c = XX
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
pt = pow(c, d, n)
print(long_to_bytes(pt).decode())

:::

## Diffie–Hellman key exchange

### Background
- 由 Whitfield Diffie 和 Martin Hellman 於 1976 年提出
- 被認為是最早的公鑰演算法
- 用於交換對稱式加密的 key 而不是用於加密
- 後續衍伸出很多加密方法
### 演算法
- 假設Alice跟Bob兩人共用n, g兩數(公開), n是很大的質數, g 是 p 的 原根

原根：a, m 互質，若使得 a^d = 1 (mod m) 的最小正整數 d = φ(m) 時，此時的 a 為模 m 的原根

- 兩人各選一個數a, b(非公開)其中a,b < p
- 各別計算A(g^a mod p)和B( g^b mod p)傳送給對方
- 計算共同key, B^a mod p 和 A^b mod p 其結果會相同
- 用共同key進行對稱式加密

### 安全性
- 基於離散對數(Discrete logarithm)的數學難題
- 結合同餘運算和原根的一種對數運算(聽起來很邪門)
- 和質因數分解一樣，目前並沒有已知的快速算法
- 補充：[大步小步算法](https://zh.wikipedia.org/wiki/%E5%A4%A7%E6%AD%A5%E5%B0%8F%E6%AD%A5%E7%AE%97%E6%B3%95)，時間複雜度O($\sqrt m$)，m 為要拿來 mod 的數字

## 雜湊／哈希函數 Hashing function
- **非加密!!!**
- 主要將不規則長度訊息的輸入，演算成固定長度雜湊的輸出
- 須盡量符合 3 條件：
- 不可逆
- 抗碰撞
- 雪崩效應
- 常見應用
- 保護資料庫內的密碼
- 數位簽章
- 資料完整性的驗證
- 資料快速查詢
- 常見雜湊
- MD4
- MD5
- SHA-1
- SHA-256
- SHA-512

## 數位簽章 digital signature
- 為何需要數位簽章
- 人們常常會透過簽名的方式來驗證身分等等,但在網路的世界中無法透過紙本簽名的方式,使用公鑰演算法來驗證身分的數位簽章就被發明出來了, 往往有兩種運算, 一個用於簽名，另一個用於驗證
- 常見功能
- 保障訊息傳輸的完整性
- 網路上的身分驗證
- 防止契約抵賴的問題
- 簽章的合法性
1.表示同意
2.數位資料
3.加密技術
4.憑證機構
5.憑證效力
### 非對稱式簽章
- RSA 簽章演算法
- 將訊息經過雜湊函數計算後，再經過 RSA 加密
- 可得到數位簽章的簽署碼
- 接收端將此數位簽章碼解密後（公開鑰匙）
- 再與接收到的訊息所計算出的雜湊值比較
- 簽章：明文 + 私鑰 = 簽名
- 驗章：明文 + 簽名 + 公鑰 = 正確/錯誤
- 如何驗證公鑰的正確性
- 使用有公信力的第三方憑證機構來做公鑰驗證
> 很難偽造
- 第三方憑證機構（Certificate Authority，簡稱CA）
- CA透過數位簽章的方式認證公鑰持有者的身分

---
###### tags: `Enlightened` `NISRA` `2022`

<style>
.navbar-brand:before {
content: ' NISRA × ';
padding-left: 1.7em;
background-image: url(https://i.imgur.com/ue2XHqP.png);
background-repeat: no-repeat;
background-size: contain;
}
.navbar-brand > .fa-file-text {
padding-left: 0.1em;
display: none;
}
</style>