---
title: Crypto
---

# Crypto by Mask
>密碼學到底是簡單還是複雜呢?讓我們繼續看下去

> [簡報連結](https://drive.google.com/file/d/1l07ibtl3uCxONdDdK-blHT9ZxS5AlRpR/view?usp=sharing)
> [課程影片連結](https://youtu.be/UgKfpZGlrm8)

> [課後問卷](https://forms.gle/b4BjUiFM81WVZJiq5)

## Python 複習
- 創建一個副檔名為 py 的檔案 ex:`test.py`
- 寫上 `printf("Hello world")`
- cmd 裡輸入 `py test.py`
- 這樣 cmd 裡就會跑出 `Hello world`

## 密碼學簡介

- 可分為古典密碼學和現代密碼學
- 古典密碼學仰賴創造力與技巧
- 現代密碼學仰賴大量電腦科學、數學等理論
- 密碼學 == 數學

### 名詞簡介

- 加密 Encrypt
- 指將明文經過某種程序轉換成密文,該程序稱為加密
- 解密 Decrypt:
- 指將密文經過某種程序轉換成明文,該程序稱為解密
- 明文 Plaintext:
- 加密前的訊息
- 密文 Cipertext:
- 加密後的訊息
- 演算法 Algorithm
- 解決複查問題的程序
- 密碼學演算法:
- 做與密碼學相關程序(如加密、解密、簽章...)的演算法
- 金鑰 / 密鑰 Key:
- 加解密時所使用的「鑰匙」
- 編碼(encoding):
- 是資訊從一種形式或格式轉換為另一種形式的過程
- 解碼(decoding):
- 編碼的逆過程,即將資料從另一種形式轉換回來

*編碼!=加密*
## ASCII 編碼
ASCII編碼只有0~127，因為要留一個位元給檢查碼
- `0` = 48
- `A` = 65
- `a` = 97

## 摩斯電碼

## Base64 encode
- 用於傳輸資料(如圖片)
- 一個單元 8bit
- Base64 一單元只有6 bits
- 詳細見: [Base64](https://http://s.nisra.net/base64)
- 如果原文不整除3,結尾會出現對應數量的=

ex 

## 古典密碼學

- 豬圈密碼(pigen cipher、共濟會密碼)


- 密碼棒
> ~~多試幾遍就成功了~~
> [name=Mask]

### 替換式

- 單表加密：
- 凱薩加密、阿特巴希密碼
- 多表加密:
- 維吉尼亞密碼、自動密鑰密碼

- 凱撒密碼(單表):
ABC 3 => DEF
DEF -3 => ABC
HELLO 13 => URYYB
URYYB 13 => HELLO
- ROT-13(凱撒裡的特定種)

#### 單表加密攻擊
- 爆破:
- 已知為凱撒密碼,只有26種可能,未知則26!
- [線上爆破](http://theblob.org/rot.cgi)
- 字頻分析:
- 最常出現的字母: e, t, a, o, i
- 最常出現的單字: the, to, of, and
- [自動化分析](https://quipqiup.com/)

#### 多表加密攻擊
- 維吉尼亞密碼
- 
- 加密：
- 密鑰：CSIEC
- 明文：HELLO
- 密文：JWTPQ
- 解密：
- 密鑰：CSIEC
- 密文：JWTPQ
- 明文：HELLO
- 從密文、明文取得密鑰
- 明文：HELLO
- 密文：JWTPQ
- 密鑰：CSIEC

- 卡西斯基試驗 (Kasiski examination)
- 密鑰:ABCDAB CD ABCDA BCD ABCDABCDABCD
- 明文:CRYPTO IS SHORT FOR CRYPTOGRAPHY
- 密文:CSASTP KV SIQUT GQU CSASTPIUAQJB
> 相差 16 位 => 密鑰為 16 的因數
- Index of coincidence
- 已知在英文一段有意義的長文中，隨機取兩字母，相同機率為 0.068
- 已知同樣明文經同樣的密鑰加密後會出來同樣的密文
> C ----- key=B -----> D
- 以重複間隔不斷取密文，其字母重複的機率應該接近 0.068
> `Q`PW`K`AL`V`RX`C`QZ`I`KG`R`BP`F`AE`O`MF`L`...
- 先把密文拆成 n 行(n=1, 2, 3...)，並計算每一行的字元出現次數

### 移位式加密
- I LOVE YOU BOB -> BOB UOY EVOL I
- 字母不變，但透過一些規則重新排序，使得較難辨認原文
- Ex. 密碼棒、柵欄加密、中國式密碼

#### Lab 1
- ASCII + ROT-13

- some tool
- http://theblob.org/rot.cgi
- https://www.asciitohex.com
#### Lab 2
- 維吉尼亞密碼加密

#### 古典密碼學的不足
- 柯克霍夫原則 (Kerckhoffs's principle)
- 即使演算法完全洩漏，只要金鑰沒有洩漏，密文就是安全的
- Claude Shannon:
- "the enemy knows the system."
- Bruce Schneier:
- 任何以隱藏設計作為防護的保安系統必然會失敗

## 現代密碼學
- 不再限於書寫文字
- 基於各種複雜的數學
- 加密簡單破解難
- 對稱式加密 & 非對稱式加密

### XOR

### 對稱式加密
- 加密解密用同一把金鑰

### 區塊加密法/串流加密法
- 區塊加密
- 常用於已知訊息長度的情況
- 將明文分成一塊一塊等長的模組分別加密
- AES DES

- 串流加密
- 常用於需要即時回應,或是訊息長度未定的情況
- 對明文逐 bit 加密
## Advanced Encryption Standard (AES)
- 美國國家標準局 NIST 於 1997 年開始徵選下一代的對稱式加密系統
- 要求實作程式碼必須公開
- 必須無償給所有人使用
- 除安全性外要考慮效能、記憶體使用量、是否易於實作等
- 由全世界所有專家一起研究與評比

- 由比利時密碼學家 Joan Daemen 和Vincent Rijmen 設計的 Rijndael 獲勝
- 金鑰長度(Key sizes):128, 192 or 256 bits
- 加密回合:10、12、14 (與金鑰長度對應)
- 區塊長度(Block sizes):128 bits
- 換而言之,AES 規定一次只能加密 128 bits
- 詳細加密過程請見:
- https://www.youtube.com/watch?v=xtCfKHE4-r8
- http://netzts.in/cryptography-blog-downloads/
- 用途:
- 無線網路協定
- Wi-Fi Protected Access (WPA)
- ZigBee
- 無線網路協定
- Secure Sockets Layer (SSL)
- Transport Layer Security (TLS)
- 其他軟硬體協定
- 攻擊:
- Padding Oracle attack
- 社交工程學

### XOR Cipher

- 攻擊:
- 已知明文與密文時可以直接回推 Key (明文⊕密文 = 金鑰)
- 遇到一長串 Null (0x00) 時會直接寫出 Key,而這在二進制檔案中是很常見的事情
- 如果 Key 長度等於 Plaintext,又 Key 完全隨機且不重用,是被證實無法破解的。

## RSA
- 非對稱式加密
- 由 Rivest、Shamir、Adleman三位教授發展出來
- 運算速度慢,通常用來加密Session key (用來加密會議內容的key)
- 將兩個質數p和q(p!=q)相乘得到N很簡單,但從N推回p、q不簡單,尤其當N很大的時候。
- 製作 Public Key 與 Private Key:
- 1. 選擇 2 個超大相異質數 p, q 並計算 N = pq
- 2. 計算 r = (p-1) × (q-1)
- 3. 選一整數 e 滿足 e < r 且 gcd(e, r) = 1
- 4. 尋一整數 d 滿足 ed ≡ 1 (mod r)
- 5. 銷毀 p 與 q,得 Public Key `e` 與 Private Key `d`
- 加密與解密:

- 1. Bob 要傳訊息給 Alice,訊息依據特定方法轉成整數 m( m < N)
- 2. Alice 將 Public Key (N, e) 交給 Bob
- 3. Bob 運算 c ≡ m^e^ (mod N) 得 c 並交給 Alice (加密)
- 4. Alice 運算 c^d^ ≡ m (mod N) 得 m ,再依約定方法轉回原始內容(解密)

### 歐拉原理
gcd a, N = 1 , a ^φ(N)^ ≡ 1 (mod N)
𝑎 ^𝜑(𝑁+1)^ ≡ a (mod N)
如果 φ N + 1 可以分解成兩數(設e,d)相乘,就可寫成:
a^ed^ % N =a (其中 a < N)
=>a^e^ % N = ct (ct)^d^ % N = a
- 符號們
- pt:Plain text
- ct:Cypher text
- e:Encrypt key
- d:Decrypt key
- (pt)^e^ % N = ct
- (ct)^d^ % N = pt

### Hash (雜湊、哈希)
- 將任意長度的字串轉成固定長度
- 雪崩效應:字串即使只有動一個字,Hash 結果差異很大
- md5(1234) = 81dc9bdb52d04dc20036dbd8313ed055
- md5(1235) = 9996535e07258a7bbfd8b132435c5962
- 無法回推:可以從 X 算出 Hash(X),但無法從 Hash(X) 算出 X
- 抗碰撞:很難找到兩個不同字串 X 與 X’ 符合 Hash(X) = Hash(X’)
- md5, sha256, bcrypt
#### Hash 用處?
- 驗證資料完整性(Data integrity)
- 用不安全通道傳很大的檔案
- 用安全通道傳該檔案的 Hash
- 傳過去後hash對看看

- 在不取得明文的情況下驗證資料正確性
- 儲存使用者密碼的 Hash 在資料庫,確保管理員看不到使用者密碼的明文

### 數位簽章

- 類似於在紙上簽名,證明這份資料是我認可的
- 只有擁有私鑰的人可以簽章,所有人都可以驗證簽章
- 因為訊息很長,所以通常會先將訊息 Hash 過再簽章
- 基於非對稱式加密系統的應用
- 具有不可否認性(Non-repudiation)

### Lab3
Base64 + MD5 hash
### Lab4
RSA
- (pt)^e^ % N = ct
- (ct)^d^ % N = pt

---
###### tags: `Enlightened` `NISRA` `2020`
<style>
.navbar-brand::after { content: " × NISRA"; }
</style>