# 密碼學基本概念
內容是我看圖解密碼技術這本書的筆記和回憶，沒有太多深奧的數學，只求有個基本概念XD
以下會是以各章節為區分，記錄各章節的重點，一開始會先試著用記憶中的內容來記錄，然後翻閱書籍看有沒有漏掉或講的地方並特別標註起來
(忘記用 :warning: ，跟自己想像相反的用 :exclamation: )
###### tags: `learning`
## 概論
### 密碼
* Alice and Bob:
通常密碼學的例子會用這兩個人當作傳送訊息、接收訊息的人(八成是因為兩個人的名字開頭是 AB 的關係...)
* 發送者、接收者、竊聽者:
密碼的出現就是防止在通訊過程中被第三方拿到消息因而發明出的一種技術，故一個標準的場景就是發送者傳遞訊息給接收者，而竊聽者試著竊聽兩人的通訊
* 加密與解密:
```flow
st=>start: 明文
op1=>operation: 加密(encrypt)
op3=>operation: 傳送(ciphertext)
op4=>operation: 解密(decrypt)
e=>end: 明文(plaintext)
st->op1->op3->op4->e
```
簡單講就是明文放到加密流程出來後變成密文，密文傳輸給對方，對方再透過解密流程解出密文
* 保證機密性:
密碼學有三大特性，機密性(confidentiality)、一致性、防止否認性，這邊透過加密傳輸解密的過程因為透過密文傳輸，沒有解密手段的人拿到密文一點作用都沒有，故為機密性
* 破譯:
按理來說，沒有解密工具的人應該是無法解密，但很多時候透過其他手段，比如:暴力破解、攻擊加密算法的漏洞......等方式，可以不透過解密手段而得知明文，稱為破譯
### 對稱密碼與公鑰密碼
現今最常用的密碼類型(保證機密性方面)是對稱密碼和公鑰密碼，兩者的簡介如下:
* 對稱密碼:
* 接收端和發送端的金鑰相同
* 加密過程較快
* 確保金鑰傳輸是一大重點
* 金鑰數量為 2^n
* 密文較長
* 公鑰密碼:
* 接收端和發送端金鑰不同，發送端的稱為公鑰，接收端稱為私鑰
* 私鑰解密用且自己保管，公鑰讓想秘密傳輸消息的人加密用
* 加密過程較慢
* 金鑰數量 2*n 個即可
* 密文較短
#### 密碼算法
密碼算法即加解密的步驟
對稱密碼的常用算法為: DES, AES 以及其他變種
公鑰密碼的常用算法為: RSA256, RSA1024 等
#### 密鑰:
密鑰相當於保險箱鑰匙，加密算法需要靠相對的密鑰生成密文，同樣解密也需要密鑰解成明文
#### 對稱密碼與公鑰密碼
* 對稱密碼:
若發送端與接收端的密鑰相同，則稱為對稱密碼(因為兩端相同)，因為密鑰相同的緣故，如何用安全的方式把密鑰給他人就是一大問題
* 公鑰密碼:
反之若兩端密鑰不同則稱之為公鑰密碼，這種密碼類型是公鑰密碼，接收端握有公鑰、私鑰，當他想跟他人通訊則將公鑰散播到網路上，想通訊的人透過公鑰加密自己的明文後發送給接收端，接收端收到消息透過私鑰解密
兩者的詳細介紹會在後面的篇章中提到
* 混合密碼系統:
所謂的混合為公鑰密碼、對稱密碼的結合，比如說用公鑰密碼加密對稱密碼的金鑰A成金鑰B，用對稱密碼加密明文成密文，將密文和金鑰B送出去，接收端透過私鑰將金鑰B解成金鑰A再用金鑰A解密文，如此就可以防範對稱密鑰被他人竊聽的可能性
### 其他密碼技術
上述提過三大特性：機密性、一致性、防止否認性，後兩者一樣可以用密碼相關技術實現
* 單向散列函數(one-way hash function)
* integrity
單向散列函數之所以稱為單向原因是無法通過得出來的結果和分析函數回推原本的內容，且同樣的資料通過單向散列函數得出來會是同樣的結果，如此保證了一致性
通常單向散列函數用於確保資料未遭修改，故很多軟體官方會放出自己的軟體的 hash 值，讓用戶比對看其他下載區的軟體是否有修改過，常見的算法有: md5, sha1 等等
* 消息認證碼(message authentication code):
* integrity
* authentication
消息認證碼則證明了該消息確實為某人所發出的訊息，這麼做是以防有人假冒他人名義發送消息給他人，這種技術的利用其實算是公鑰密碼的反向利用: 用私鑰加密、公鑰解密，因為其他接收者能用公鑰解密代表消息的確是握有私鑰的人發送的
**忘記數字簽名QQ**
* 數字簽名(digital signature):
* 防篡改
* 防偽裝
* 防否認
將現實的簽名應用在資訊領域中，透過對消息加上簽名保證上述特性，而他人可以對簽名進行確認(verify)
* 偽隨機變數產生器
跟密碼的相關性在於有些密鑰的產生跟偽隨機變數產生器有關，比如說 SSL/TLS 的臨時生成的會話密鑰
### 密碼學家的工具箱
:warning:
以下參考書中的圖做個簡介:
* 竊聽:
* 機密性
* 應對
* 公鑰密碼
* 對稱密碼
* 篡改:
* 完整性
* 應對
* hash
* 消息認證碼
* 數字簽名
* 偽裝
* 認證
* 應對
* 消息認證碼
* 數字簽名
* 否認:
* 不可否認性
* 應對
* 數字簽名
* 隱寫術:
隱寫術通常用於將一串消息藏在某個媒介中，比如圖片、音樂等等，知道該怎麼從中提取消息的人就能順利解密，這種藏匿方式變化也相當多種而且有時候無跡可尋，**但一定知道藏匿方式就會被破解**
:warning:
* 數字水印:
指的是將身分信息嵌入消息中，通常用於保護著作財產權
### 密碼與資訊安全常識
1. 不要使用保密的密碼算法
這條常識其實挺違反直覺，很多人覺得要是算法保密則大家就無法通過分析算法進而攻擊，事實上現代密碼學的常用算法都是公開的，原因是就算你公開了算法，不知道密鑰的人即使知道算法也無法解密，而且透過公開算法讓學者專家對你的算法進行檢驗更能確保算法的強度
:exclamation: 密碼的強度無法透過數學證明，只能透過事實證明
:warning:
2. 使用低強度的密碼比不進行任何加密更危險:
用低強度的密碼給人一種錯誤的安全感，導致在處理機密事項的時候大意
3. 任何密碼總有一天會被破解
理論上來說只要有無窮的時間讓攻擊者去窮舉整個密鑰空間，總有一天密碼會被找出來，但防範的重點在於讓攻擊者知道這樣的時間成本不符合效益，讓其知難而退
4. 密碼只是資訊安全的一部分
密碼不是萬靈丹，要是電腦本身就有其他漏洞或後門，攻擊者大可不必去破譯密文，直接入侵電腦竊取解密後的明文即可
## 歷史上的密碼
### 凱撒密碼
* 什麼是凱撒密碼:
聽說是古羅馬的凱撒在戰爭中曾經使用過的加密方法，不過放到現在已經沒用了
* 加密:
* 字母偏移 n 個
* ex:
* right shift 1: apple -> bqqmf
* 解密:
* reverse shift
* 暴力破解:
* 因為字母只有 26 個，把所有可能都偏移一次僅需 26 次，就算不用電腦也可以快速解出
以現代密碼的模型來說，加密解密算法為偏移字母，金鑰則是偏移的 n
### 簡單替換密碼
* 什麼是簡單替換密碼:
* 將字母用其他字母做替換，凱撒加密可以說是簡單替換的一種變形
* 加密:
* 為每個字母選定一個替換字母且不重複，對著明文一一替換
* 解密:
* 從約定好的替換表中將每個字母替換回來
* 密鑰空間:
* 第一種有 26 種可能，第二種有 25 種可能，以此類推，密鑰空間總共有 26!
* 以詞頻分析破解:
* 分析定位出現最多次的字母、pattern ，進而分析單字慢慢找出可能的字母
* 英文中出現比例最高的字母為 e
* 英文中出現比例最高的單字為 the
* 明文越長越容易破解 :exclamation:
* 破譯的速度會越來越快 :exclamation:
### Enigma
* 什麼是 Enigma
* Enigma 是二戰德軍用來加密軍事消息的加密算法，其實作為一個手動調整的機器
:warning: 後面忘了
* Enigma 加密通信
* 接收、傳送兩方都有一台 Enigma
* 兩者需要共同的密鑰
* 將明文輸入 Enigma 生出密文，將密文輸入 Enigma 生出明文，前題是兩者都用相同的密鑰
* Enigma 構造
* 透過每日密碼(密鑰)和轉盤設定 Enigma
* 發送者對著明文按按鍵，代表某個字母的燈泡會亮起來 => 加密
* 接收者對著密文按按鍵，代表某個字母的燈泡會亮起來 => 解密
* Enimga 加密詳細步驟:
1. 設定 Enigma:
* 找當天的每日密碼
* 依據每日密碼接線、調整轉子
2. 加密通信密碼:
* 發送者想一個 3 個字母的通訊密碼並輸入到 Enigma 兩次(輸入兩次可以撿查通訊過程有沒有出錯)
* 得到的就是 Enigma 加密過後的加密後的通訊密碼
3. 重新設定 Enigma:
* 根據原本的通訊密碼再設定 Enigma
4. 加密消息:
* 輸入明文轉成密文
5. 傳送消息
* 將密文和加密過後的通訊密碼發送出去給接收者
由上可知， Enigma 不僅加密通訊內容，連用來加密的密鑰也加密過一次，這種加密方式(加密金鑰)也很常在現代密碼學上使用
* Enigma 解密詳細步驟:
1. 設定 Enigma:
* 找當天的每日密碼
* 依據每日密碼接線、調整轉子
2. 解密通訊密碼:
* 根據收到的消息拆分為通訊密碼和密文
* 把通訊密碼拿去解密得到原本的通訊密碼
3. 重新設定 Enigma:
* 依據通訊密碼設定 Enigma
4. 解密:
* 將密文輸入 Enigma 得到明文
* Enigma 的弱點:
* 通訊密碼固定輸入兩次
破譯者知道這規律會降低破譯難度
* 通訊密碼是人設定的
基本上人設定的一定會有人出現不安全的設定，比如: aaaa, abcd 等等
* 保存每日密碼
要如何安全配送每日密碼並且之後保證不讓人拿到
> 書中還有說什麼第一次設定轉子只會轉一次，看不太懂
## 對稱密碼(共享密碼)
### 文字密碼到位元序列編碼
之前所講的形式皆以文字當作範例，現在的世代用於傳輸的工具卻是電腦，在電腦中任何東西都被視為是位元序列
* 編碼(encoding):
* 將文字以一串特定的位元序列表示，方便電腦作業
* 最早期是用 ascii table 0x20 ~ 0x7f 表示
* 為了包容廣大語言，故後來編碼多採用 unicode ，以兩個 bytes 來表示一個字
* XOR:
* 一種位元運算
* 簡單講就是相異則真，相同則假
* 特性:
* $A \oplus B = C \wedge C \oplus B = A$
* 經過兩次以 B 當運算元的 xor 運算可以反推回 A
* 適合當作加密算法
* 密鑰的選擇應採用**隨機**位元序列，因此隨機這個概念在密碼學中舉足輕重
### 一次性密碼本
利用簡單的 xor 可以做出絕對無法破解的密碼
* 加密:
* 選定跟明文位元序列一樣長的**隨機**位元序列當作密鑰
* 對明文和密鑰做 xor ，所得即為密文
* 解密:
* 將所得密文跟密鑰做 xor 即可得到明文
* 無法被破解: :exclamation:
這裡的無法破解是指即使窮盡密鑰空間也無法得到明文的意思，這是因為窮舉密鑰時得出來的結果會出現其他有意義的語句，而明文指是這些有意義語句的其中一種，不知道密鑰意味著也無法得知**正確的明文**
* 侷限性:
* 密鑰長度太大 (長度跟明文長度一樣...)
* 保存不易 (能保存密鑰也就代表能保存明文，那密鑰就無存在必要)
* 傳輸不易 (傳輸有可能會出錯)
* 密鑰配送不易 :warning:
* 相同的密鑰不能重用 :warning:
* 生成不易 (不能透過偽隨機數生成) :warning:
[題目 - You either know, XOR you don't](https://cryptohack.org/challenges/general/)：
CryptoHack 上的題目，首先題目是一串 hex ，透過已知的部分明文去拼湊出密鑰
原先我以為他的密鑰是不重複的，如同上面的一次性密碼本那種，這樣有個問題就是什麼組合都有可能，所以不可能解得出來，因此密鑰一定是重複的 byte sequence
### DES (Data Encryption standard)
:warning:
美國國家訊息處理標準 (FIPS) 採用的對稱密碼 (FIPS 46-3)
* DES:
* 64bit 明文加密成 64bit 密文
* 每 7 bit 就會設一個校驗 bit ，所以密鑰長度為 56bit
* 64bit 為一個加密單位，所以是一種**分組密碼** (block chipher)
* 若明文長度超過 64bit ，則會再進行 DES 加密 (迭代)，一直到所有的明文都加密過，這種行為稱為 mode
* 現在會被輕易破解
* 只能用來解密以前的密文
* 結構:
* 又稱 Feistel 網路/結構/密碼
* Horst Feistel 設計
* 用於多種密碼算法中
* 加密的步驟稱為 round
* DES 的加密步驟有 16 round
* 加密:
1. 將明文拆分成 64bit 為一組
2. 64bit 的明文再拆成左邊 32bit 右邊 32bit
3. 右邊 32bit 會連同子密鑰輸入進輪函數 f 輸出一串隨機 bit seq A
* 子密鑰的意思代表僅在該輪使用
5. bit seq 會和左邊的 32bit 做 xor
* 到此代表一輪
7. 將左右側 32bit 的結果對調
* 左側為已加密的 32bit 右側為明文 32bit
* 對調是因為右側沒有加密
* 此時為第二輪
* 輪數可以任意增加:
* DES 有 16 輪
* 用圖說明:
* 
* 圖中的 F 代表 round function
* 解密:
1. 將密文拆成 32bit, 32bit
2. 按照加密的子密鑰倒著運算回去，步驟和加密相同
3. 重複輪數
4. 解密成功
* Feistel 網路性質:
* 輪函數可以任意增加
* 輪函數可以非常複雜，即使輸出結果逆向推不回輸入也可以 :question:
* 加密與解密可以用相同的構造實現
* 硬體設計容易
* 眾多密碼算法採用此網路
* AES 除外XDDD
* 差分分析和線性分析 :exclamation:
* 差分分析:
* 改變明文觀察密文的變化
* 按裡來說， 1bit 的改變，密文也應完全不同
* 分析密文改變的偏差獲得破譯明文
* 線性分析:
* 將明文和密文對應的 bit xor 其為零的機率
* 一般來說完全隨機的話機率應該趨近 1/2
* 找到大幅偏離 1/2 的 bit 就能獲得線索
* DES 的破解從 2^56 降低到 2^47 次方
* 上述的分析都屬於**選擇明文攻擊** (chosen plaintext attack)
* 攻擊者必須知道任意明文和加密的結果
* 三重 DES
* 為了增強 DES 密碼強度的算法
* 簡單講: 對明文做三次 DES 加密
* 流程: 加密 -> 解密 -> 加密
* 每次的密鑰可以不同，若三次密鑰皆相同等同於 DES
* 為了向下兼容 DES 的設計
* 圖示: 
* 日本銀行有使用，但處理速度不高，除了有向下兼容 DES 的必要，否則不常使用
### AES (Advanced Encryption Standard) :warning:
因為 DES 應付不了現今的需求，美國標準技術研究所 (National Institude of Standards and Technology) 選拔出來的演算法，獲獎者是 Rijndael 開發的算法
* 選拔過程:
* 提交算法的人必須公開算法，讓世界各地的專家進行檢驗
* 杜絕隱蔽性安全 (security by obscurity)
* 算法必須無償免費提供世界使用
* 除了安全之外還必須符合容易實作、速度要快、密鑰準備速度也要快
* 最後由比利時密碼學家 Joan Daemen 和 Vincent Rijmen 兩個人的 Rijndael 獲選
### Rijndael :warning:
Rijndael 的基本介紹在上面，這邊提供一些規格介紹:
* 規格:
* 分組長度和密鑰長度以 32bit 為單位，從 128 到 256 之間任取
* AES 則規定分組長度必須在 128bit ，密鑰長度則在 128, 192, 256 中選擇
* 加密:
* 由多個 round 構成， round 又分為以下幾個操作:
* SubBytes
* ShiftRows
* MixColoumn
* AddRoundKey
* 不採用 Festiel 架構，而是採用 SPN 結構
* 一輪的步驟:
1. 輸入分為每 16bytes(128bits) 為一組
2. 每個 bytes 經過替換表映射到另一個 bytes (看成是替換密碼即可)
3. 以 4 bytes 的 row 為單位向左 shift (每個 row shift 的位數不同)
4. 將 4bytes 的 column 經過矩陣運算成另一組 4bytes
5. 將輸出的 bytes 和 round key 進行 xor 運算
* Rijndael 會跑個 10~14 round
* 優點:
* 每個 bytes 在每一輪都會被加密，相較 Festiel 右側無法被加密，round time 可以更少
* 3 個步驟可以同時平行運算
* 解密:
* 將每個 round 操作相反操作一次:
1. AddRoundKey (xor 運算，故加解密是相同的)
2. InvMixColimn
3. InvShiftRows
4. InvSubBytes
* 破譯:
* 因為 Rijndael 能全部用數學表示，新的攻擊方法可能因應而生
* 但是目前沒出現過...
* 對稱密碼的選擇:
* DES
* 不妥，已經是可以破解的密碼算法
* 三重 DES
* 除了有必要向下兼容外，不適合使用
* AES
* 最推薦
* 其他候選算法也可以納入考慮 (畢竟也通過了安全性的考驗)
## 分組密碼 :warning:
### 分組密碼的模式
其實這部分忘的差不多了......
* 分組密碼與流密碼:
* 分組密碼(block cipher):
* 僅能處理固定大小的數據
* DES, AES (128bit, 256bit etc..)
* 無須記錄內部狀態
* 流密碼(stream cipher):
* 能連續處理數據
* 一次性密碼本
* 必須記錄狀態
* 模式:
* 超過處理大小的數據時必須多次對數據進行運算
* 比如:
* 分組後進行加密運算後組合起來
* 分組後由前一組的結果結合當前組的結果進行運算
* 諸如此類...
* 明文分組和密文分組:
* 明文分組 = 分組密碼加密中與分組密碼處理大小相同的明文
* 密文分組 = 明文分組出來後的密文
* 主動攻擊者:
* 主動介入接收兩者間的通訊
* 前面的攻擊者僅僅是竊聽而已
### ECB 模式 (Electronic Codebook Block)
* ECB 模式簡介:
* 將明文分組後加密並在最後將所有密文合併
* 圖示: 
* 有可能出現無法恰好分組的情況，此時需要填充 (padding)
* ECB 模式特點:
* 固定的明文得出的密文會相同
* 簡單好實作又可以平行運算
* ECB 的攻擊:
* 因為明文和密文有一對一的關係，很容易觀察出哪些部分是重複的
* :question: 若每個 block 都採用不同的 key 呢？ (懶的打密鑰了 ...)
* 攻擊者可以任意更改密文的話，那解密出來的明文是有意義但跟正確的明文就毫無相關了
### CBC 模式 (Cipher Block Chaining)
* CBC 模式介紹:
* 將前一個加密過後的密文分組跟當前要處理的明文分組做 xor
* 第一塊沒有加密分組，所以需要 IV (initial vector, 就只是一個隨機位元序列而已)
* 圖示:
* CBC 模式特點:
* 彌補 ECB 模式的缺點，就算兩個明文分組一樣，因為 xor 的關係密文也會有所不同
* 無法從中間開始加密，要加密中間的話勢必前面兩個都要加密過
* 出錯的情況:
* 密文出錯但長度不變則會有兩個明文分組受影響 (出錯密文 A 的解密和出錯密文 A 的下一個密文的解密)
* 密文出錯且長度有變則後面所有明文都會受影響
* CBC 模式的攻擊:
* 改變 IV
* 反轉特定的 bit 可以使相對應的明文 bit 反轉
* Padding Oracle Attack (修改 IV + padding + 觀察網站給出的回饋判斷 = 獲得明文相關消息)
* 猜測 IV 的值
* 應用:
* CBC 目前大量運用於 SSL/TLS 中
* 補充:
* CTS (Cipher Text Stealing) 模式:
* 需要 padding 的部分由前一個密文分組來填充
* 用處？ :question:
### CFB (Cipher Feedback) 模式:
* CFB 簡介:
* 將前一塊密文分組再加密後跟下一個明文分組 xor
* 第一塊一樣用 IV 處理
* 圖示:
* 解密時 IV 和前一個密文分組需要加密 :exclamation:
* 因為還原成明文時需要 xor
* 圖示: 
* 明文和密文之間並沒有直接加密 :exclamation:
* CFB 和 stream cipher:
* 相同:
* CFB 和 stream cipher 都是用一串位元序列對明文做 xor
* 相異:
* stream cipher 需要直接產生與明文長度相等的隨機位元序列
* CFB 產生與第一塊明文分組長度相等的隨機位元序列
* CFB 的位元序列是經過計算而得，不具備隨機性，因此不可稱為不可破譯 :exclamation:
* 針對 CFB 的攻擊:
* 重放攻擊:
1. 攔截部分密文分組
2. 下一次的傳輸中替換掉密文分組
3. 解密時替換的密文分組開頭會壞掉 (因為錯誤的密文分組跟正確的密文分組 xor)
4. 後面的密文分組(被替換的)會根據前面的密文分組(被替換的) xor 會是正確的
* 換句話說只有其中一個明文會壞掉，其他的會是被替換過的明文
* 如無其他手段則接收者判斷不出是被惡意操弄還是傳輸出問題
### OFB (output feedback block)
* OFB 模式簡介:
* 加密:
* 由 IV 加密後對明文分組進行 xor
* 跟 CFB 一樣都並非由明文分組直接進行加密
* 換到下一個明文分組前加密後的 IV 會再加密一次
* 每次要 xor 新的明文分組 IV 都會重新加密一次
* 解密:
* 由 IV 加密後對密文分組 xor
* 換到下一個密文分組前加密後的 IV 再加密一次
* 可以實現平行運算，速度很快
* 直接對 IV 進行多次加密後對其他明文分組 xor 即可
* CFB 和 OFB 的差別:
* CFB
* CFB 的 xor 是根據前一塊密文分組的加密而得
* 速度慢 (要等前一塊密文分組加密)
* OFB
* OFB 的 xor 都是根據 IV 加密而來
* 速度快 (可以平行運算)
### CTR (CounTeR) 模式
* CTR 簡介:
* 加密:
1. 將與明文分組長度相同的位元序列 (計數器) 加密後跟明文分組 xor
2. 位元序列 + 1 加密後再與明文分組 xor
* 解密:
* 基本上同上
* 可以平行運算
* 計數器生成方法:
* 計數器組成:
* nonce: 隨機位元序列
* 次數: 接在 nonce 後面，加 1 則加在此之上
* 老實說不太懂為啥不用隨機位元序列直接 + 1 ....
* 錯誤和機密性:
* 錯誤不會被放大:
* 反轉一個 bit 則只有一個明文分組的 bit 被反轉
* 略優於 OFB
* OFB 中若 IV 加密後剛好與加密前相同，key 會變的很單調，而 CTR 不會
* GCM 模式:
* CTR 加上認證功能
### 各模式整理
* EBC:
* 特點:
* 對每個明文分組做加密後串在一起
* 優點:
* 簡單
* 快速 (平行運算)
* 錯誤不會放大
* 缺點:
* 相同明文的密文也會相同
* 刪除、替換密文可以對明文操作
* 重放攻擊
* 備註:
* 不應使用
* CBC:
* 特點:
* IV 當 key 對明文分組 1 加密成密文分組 1
* 密文分組 1 當作 key 對明文分組 2 加密
* 類推
* 不夠長需要 padding
* 優點:
* 相同明文的密文會不同
* 解密可以平行計算
* 可以任意分組解密
* 缺點:
* 錯誤會放大
* 不支持平行計算
* 備註:
* 書中較推薦
* CFB:
* 特點
* 用 IV 加密後跟明文分組 1 xor 得到密文分組 1
* 密文分組 1 在加密後跟明文分組 2 做 xor
* 明文分組跟密文分組間沒有加密關係
* 優點
* 平行運算(解密)
* ~~錯誤不會放大~~ (搞錯XD)
* 可以任意解密
* 不需填充
* 缺點
* IV 加密後跟加密前一樣則退化成 ECB
* 加密無法平行運算
* 錯誤會放大到後面所有的密文分組
* 重放攻擊
* 備註
* OFB:
* 特點:
* 用 IV 加密後跟明文分組 1 xor 得到密文分組 1
* IV 再加密跟明文分組 2 xor 得到密文分組 2
* 類推
* 明文和密文間無直接加密關係
* 優點:
* 平行運算 :question:
* 錯誤不會放大 (除了 IV 錯誤)
* 任意解密
* 不需填充
* 缺點:
* 反轉 bit 能修改明文 bit
* 備註:
* CTR:
* 特點:
* 計數器加密後對明文分組 xor
* 計數器加一後加密再對下一個明文分組 xor
* 類推
* 計數器 = nonce + 次數
* 優點
* 平行計算
* 錯誤不會放大
* 不需填充
* 可以任意解密
* 缺點
* 反轉 bit 能修改明文 bit
* 備註
## 公鑰密碼
### 密鑰配送問題
對稱密碼需要接收雙方都持有相同的 key ，在網路中如何**安全**的傳遞 key 給對方 ？
* 解決方案:
* 事先配送
* 傳輸前就透過其他方式給對方 key
* 多人都要通訊的話 key 數量會很多
* 密鑰分配中心 (Key distribution center) :warning:
* 由某機器管理大家的 key (自己也會保有自己的 key)
* 以下為通訊的場景:
1. 員工 A 需要和員工 B 通訊
2. 中心生成一個通訊 key ，並用 A 的 key 加密
3. 傳送給 A
4. 中心生成一個通訊 key ，並用 B 的 key 加密
5. 傳送給 B
6. A, B 解密後得到這次的通訊 key
7. 雙方用通訊 key 加密解密傳遞的消息
* 中心處理的機制要夠強大
* 要非常小心避免被侵入
* Diffle-Hellman 密鑰交換
* 用可公開的消息傳遞，利用此消息生成 key ，這些消息僅能由接收雙方解出 key ，其他人拿到沒有用
* 公鑰密碼 (public key ，以下簡稱 pub key)
* 用公開的 pub key 加密，用自己的 pri key 解密
### 公鑰密碼
* 公鑰密碼特點:
* 由密鑰對組成 (key pair):
* 解密密鑰
* 加密密鑰
* 兩者不同但同時出現
* 一對一的對應關係
* 加密密鑰給大眾，解密密鑰自己保留
* 解密密鑰也可以用來加密，不過這屬於消息認證的範疇
* 公鑰密碼歷史:
* 概念由 Whitfield 和 Matrin Hellman 提出
* 實際運用始於 RSA 的出現 (?
* 公鑰密碼通信流程:
1. 接收者自己先產生 pub key, pri key
2. 在網路上公開自己的 pub key
3. 傳輸者利用 pub key 給自己的訊息加密
4. 傳送給接收者
5. 接收者用 pri key 解密
* 無法解決的問題: :warning:
* 公鑰是否合法 ？
要是有人宣稱公開密鑰是屬於 A 的但實際屬於 B ，則大家用此密鑰加密被 B 攔截， B 可以偷到本想傳給 A 的消息
### 模運算
$A \equiv B \ mod \ n$ 即 A 餘 n = B 餘 n
* 加法
* 加完後取模即可
* 減法
* $(a-x)mod\ n = b\ and\ (a + y)mod\ n = b$ 代表 $x + y = n$
* 乘法
* 乘完後取模
* 除法
* $(a\times\ b)mod\ n = 1$ 代表 $(1 \div a) mod\ n = b$
* a 和 b 為模運算中的倒數關係
* 若 a 和 n 為互質關係，則 a 在 mod n 內有倒數，反之則否
* 次方:
* 直接乘開取模
* 中間步驟取模後最後再取模，EX:
$7\times7\times7\times7 mod\ n = ((7\times7mod\ n)(7\times7mod\ n))mod\ n$
### RSA
* RSA 簡介:
* 由三個科學家: Ron Rivest, Adi Shamir, Leonard Adleman 發明
* 廣泛運用於公鑰密碼
* 本質是利用大數質因數分解的困難度保證機密性
:warning:
* RSA 加密:
* 公式: 明文^E mod N = 密文
* (E, N) 為公鑰，其生成是經過計算而非亂決定
* RSA 解密:
* 公式: 密文^D mod N = 明文
* (D, N) 為私鑰，其生成是經過計算而非亂決定
* D 和 E 之間有相當的關係
* 生成 key 的方法
1. 生成 N
1. 準備兩質數 p, q
通常透過偽隨機產生器生成固定大小的數，再判斷是否為質數 (費馬小定理之類)
2. N = p*q
2. 生成 L
L 只會在生成 key 的時候出現，使用的時候並不會用到
1. L = lcm((p - 1), (q - 1)) ，其中 lcm 為最小公倍數
3. 生成 E
E 的條件為: 1 < E < L 且 gcd(E, L) = 1
1. 偽隨機產生器生成數 E
2. 用最大公因數判斷 E 是否跟 L 互質 (可用輾轉相除法)
之所以要互質是因為後續要找 mod L 底下跟 E 為倒數的數 D
4. 生成 D
D 的條件為: 1 < D < L 且 E * D mod L = 1
1. 由 E 計算而得
### 對 RSA 的攻擊 :warning:
* 資訊:
* 破譯者已知:
* 密文 (攔截到的)
* E, N (pub key)
* 破譯者未知:
* 明文
* D (pri key)
* p, q, L
* ~~密文逆推明文~~:
* C = P^E mod N
目前沒有找到任何能高效解決離散對數問題的方法
* ~~暴力破解找出 D~~:
* 需要對 2048bit 以上的 D 進行暴力破解非常非常困難
* p, q 為 1024bit 且 N 為 2048bit ， E, D 的長度和 N 差不多
* ~~透過 E, N 求 D~~:
* E*D mod L = 1 ， L 為 (p-1)*(q-1) ，故不知道 p, q 的話求不出 L
**p, q 需要好好保存！**
* ~~對 N 進行質因數分解~~
* 目前沒有好方法，找到的話 RSA 也不用玩了
* ~~推測 p, q~~
* 這部分屬於偽隨機產生器的問題
太爛被猜出來就會被破解
* 中間人攻擊:
* 攻擊者 Eve 有能力竊聽、竄改、讓別人收不到消息的能力
1. Alice 向 Bob 要公鑰
2. Eve 攔截後將公鑰改成自己的公鑰並發送給 Alice
3. Alice 用 Eve 的公鑰加密後傳給 Bob
4. Eve 攔截密文後用自己的私鑰解開
5. Eve 用 Bob 的公鑰加密假消息候傳給 Bob
* 需要透過憑證來解決這類問題
* 選擇密文攻擊 (Chosen Ciphertext Attack):
* 攻擊者能任意發送密文去解密
* 從解密而得的資訊獲得線索 (回傳狀態、回應時間等等)
* 解決方法:
* 確認發送消息的人是經過合法管道而生 = 認證
* 不要提示一堆消息
### 其他公鑰密碼 :warning:
* ElGamal:
* 應用 mod N 下離散對數難解
* 密文會變成明文的兩倍
* Rabin:
* 應用 mod N 下求平方根的困難度
* 橢圓曲線密碼 (Elliptic Curve Cryptography):
* 橢圓曲線上的特定點進行乘法運算
* 運用此乘法運算難以逆推的困難
* 密文長度比 RSA 小
### 公鑰密碼 Q&A :warning:
* 公鑰密碼的機密性:
* Q: 跟對稱密碼比機密性會更高嗎？
* A: 機密性跟 key 長度比較有關，不能這樣比較
* 公鑰密碼與對稱密碼長度比較:
* Q1: AES 256 跟 RSA 1024 相比，機密性會更高嗎？
* A1: 首先演算法不同很難就此比較 :exclamation: ，不過有給出強度相對均衡的參考表:
| 對稱密碼 | 公鑰密碼 |
| -------- | -------- |
| 128 | 3072 |
|192 |7680|
|256|15360|
* 對稱密碼的未來:
* Q: 有了公鑰密碼，對稱密碼會消失嗎？
* A: 不會，公鑰密碼的加密效率太低，目前主要應用是結合對稱密碼和公鑰密碼的混合密碼為主流
* RSA 與質數:
* Q: 質數會不會被用完？
* A: 不會，質數基本上已經被證明為無限個且 512 bit 內的質數有 10^150 次方個，比宇宙的原子數量還多
* 但有可能發生別人的 key pair 跟自己的 key pair 相撞的可能
* RSA 與質因數分解:
* Q: 加密過程中有需要進行質因數分解嗎？
* A: 不需要，只有破譯者想透過 N 反推 p, q 才需要
* Q: RSA 的破譯和大數質因數分解是等價的嗎？
* A: 是，得出 p, q 就可以算出 L ，有了 L 就可以從 D*E mod L = 1 中推出 D ，這樣就得到密鑰了
* RSA 長度
* Q: 要抵禦質因數分解，N 的長度要達到多少 bit ？
* A: 基本上總有一天 N 一定會會被分解，時間長短由資源和有無快速公式而定，以當今的情況來說 2009 年 RSA challenge 被成功分解的記錄是 RSA-768 (這是公開記錄)，目前 1024 可能會被成功分解，但 2048 應該還是安全的 :exclamation:
## 混合密碼系統
### 混合密碼系統
* 對稱密碼與公鑰密碼:
* 對稱密碼特性:
* 需要共通 key
* 處理速度快
* 有配送問題
* 公鑰密碼:
* 沒有配送問題
* 處理速度慢 (大概百分之一)
* 不能抵禦中間人攻擊 :exclamation: (這邊不會提到怎麼抵禦，請看憑證的部分)
* 混合密碼系統:
* 原因:
* 對稱密碼和公鑰密碼的優缺可以互補
* 原理:
* 利用偽隨機產生器生成對稱密碼的 key 用來加解密明文 (快速)
* 利用公鑰密碼加密對稱密碼的 key (保證對稱密鑰的機密性)
* 組合後傳輸出去
某方面來說跟 Engimel 滿像的...
* 加密:
1. Bob 向網路上發出自己的 pub key
2. Alice 想跟 Bob 通訊
3. Alice 拿自己的對稱密鑰加密明文
4. Alice 拿 Bob 的 pub key 加密自己的對稱密鑰
5. Alice 傳送自己被加密過的對稱密鑰和用自己的對稱密鑰加密的明文發送給 Bob
* 解密:
1. Bob 收到被加密過的對稱密鑰和密文
2. Bob 分離被加密過的密鑰和密文
3. Bob 用 pri key 解密得到 Alice 對稱密鑰
4. 用 Alice 的對稱密鑰解密密文得到明文
* 具體例子 :warning:
* SSL/TLS
* PGP 加密軟體
### 怎麼樣才是高強度的混合密碼系統 :warning:
* 偽隨機數生成器
* 用來生成對稱密碼的 key
* 不能被猜到 (密鑰空間不大，一部分被推出來就完了 :exclamation: )
* 對稱密碼
* 對稱密碼要選擇目前可行的算法 (AES)
* 選擇合適的分組模式
* 選擇長度適合的 key
* 公鑰密碼
* 保護好 p,q
* 保護好 pri key
* 選擇長度夠長的 key
原則上來說公鑰密碼 key 強度應該要強於對稱密碼，因為對稱密碼的 key 是臨時生成，被破譯頂多這次被偷聽，公鑰密碼被破譯就是每次通訊都會被破譯
### 密碼技術的組合
* 三重 DES
* 三個對稱密碼算法串在一起
* 混合密碼系統
* 對稱密碼
* 公鑰密碼
* 偽隨機產生器
:warning:
* 數字簽名:
* hash
* 公鑰密碼
* 憑證:
* 數字簽名
* 公鑰密碼
* 偽隨機產生器:
* 對稱密碼
* 公鑰密碼
* hash
## 單向散列函數 (以下簡稱 hash)
### 什麼是 hash
hash 簡單講就是一個無論輸入多大的資料 A 出來都會是一個固定大小的位元序列 B，且此 B 只會從 hash(A) 獲得
* hash 的性質:
* 計算一串資料給出近乎獨一無二<font color="#ff5733">**固定長度**</font>的值的函數
* 任何 1 bit 發生改變，都會使輸出發生劇烈變化 (抗碰撞性)
* 無法從輸出的值推回輸入的值 (單向)
* 類似指紋的概念
* 用以檢查完整性 :exclamation:
* 能快速計算 :exclamation:
* 抗碰撞性:
* 弱抗碰撞:
**給定原文情況下**，找到跟原文具有相同的 Hash 的另一個消息非常困難
* 強抗碰撞:
找到 hash 相同的不同消息是非常困難的
hash 兩者都必須具備
* 術語(換句話說列表): :warning:
* hash function
* message digest function
* hash function
* 雜湊
* message
* pre-image
* output
* message digest
* fingerprint
* integrity
* 一致性
### 實際應用
* 檢查軟體是否被修改:
* 任何 1 bit 以上的修改都會使 hash 發生劇烈變化
* 避免有人偷塞後門
* passwd 加密:
* 對使用者的密碼加密並儲存有效避免伺服器被入侵而被盜走
* 加鹽:
* 因為很多人可能會使用相同的爛密碼，所以通常會在後面加一串隨機數據 (salt) ，如此就算密碼一樣 hash 也會不一樣
* 抵禦字典攻擊 :exclamation:
* 消息認證碼: :warning:
* 對被~~加密過~~對稱 key 和~~加密過的~~消息做 hash
* 避免傳輸過程中被竄改、丟失、偽裝
* SSL/TLS 中應用
* 數字簽名: :warning:
* 單純對消息做數字簽名 :x: (太耗時)
* 對消息的 Hash 做數字簽名 :o:
* 偽隨機數產生器
* 要求: 不能根據過去的隨機數預測未來的隨機數
* hash 的單向性可以滿足
* 一次性密碼:
* 用於 server 對 client 的合法認證
* hash 保證密碼只在通訊中使用一次 :question:
### 具體例子 :warning:
* MD4, MD5:
* MD = message digest
* MD4:
* 產生 128bit 的 hash number
* 已被提出找出 MD4 碰撞的方法
* MD5:
* 產生 128bit 的 hash number
* 強抗碰撞已破
* SHA-1, SHA-256, SHA-384, SHA-512:
* SHA-1
* 160 bit 的 hash
* 除了保持兼容外不應使用
* SHA-2
* SHA-256, SHA-384, SHA-512
* 尚未被攻破
* RIPEMD-160
* 歐盟提出
* 尚有 128, 256, 320 版本
* 除保持兼容外不應使用
* 被 BitCoin 使用
* 因為產生的獨特 hash 最短 [參考](https://bitcoin.stackexchange.com/questions/9202/why-does-bitcoin-use-two-hash-functions-sha-256-and-ripemd-160-to-create-an-ad)
* SHA-3
* 公開選拔
* Keccak 獲勝
* 詳情看下面
### SHA-3 選拔 :warning:
由於 SHA-1 被攻破， NIST 著手選拔下一代的 hash function ，透過公開競爭來實現標準化
* 選拔:
* 總計 64 個算法
* 入選 5 個
* BLAKE
* Grostl
* JH
* Keccak
* Skein
* Keccak :exclamation:
* 跟 SHA-2 結構完全不同
* 結構清晰、易於分析
* 適用於各種設備
* 硬體實現有很高的效能
* 安全邊際大
### Keccak
keccak 基本的性質上面已經提過了，且 keccak 可以生成**任意長度**的 hash 值和**沒有上限的輸入**，但為了兼容 SHA-2 的標準還是規定了幾種標準:
* 有限定長度
* SHA3-224
* SHA3-256
* SHA3-384
* SHA3-512
* 無限定長度:
* SHAKE128
* SHAKE256
#### 海綿結構
* 海綿結構:
* 吸收
1. 以 r bit 為單位進行分組 (不夠則先填充)
2. 將內部狀態的 r bit 跟第一個輸入的分組做 xor
3. xor 的值放入 function f()
4. f() 的輸出跟第二組輸入的分組做 xor
5. xor 的值放入 function f()
6. f() 的輸出跟第三組輸入分組做 xor
7. ...以此類推
f 的作用為將輸入分組進行充分的「攪拌」
* 擠出
1. 將 f 的輸出當作第一輸出分組輸出
2. 將第一輸出分組送入 f()
3. f() 的輸出為第二分組
4. 將第二輸出分組送入 f()
5. 以此類推直到長度滿足
6. 組合所有的輸出分組
* 圖示:
根據描述，先將輸入吸收進 keccak 內部狀態，然後根據此狀態擠出 hash
* 雙工結構:
* 海綿結構的變形
1. 輸入分組經過一次的 f() 後就輸出當做輸出分組1
2. 輸出分組 1 跟輸入分組 2 做 xor 後輸入 f()
3. 以此類推
* 內部狀態:
超級複雜先略過....
#### 對 Keccak 的攻擊
前面提過的算法基本上屬於 MD 結構，針對 SHA-1 的攻擊可能也適用於這些算法，但採用完全不同結構的 Keccak 沒這問題且目前沒有能對 Keccak 攻擊的例子
### 該使用哪種 hash function
* SHA-1
* 除兼容外應避免使用
* SHA-2
* 可以使用
* SHA-3
* 最推薦
### 對 hash 的攻擊:
* 暴力破解
* 透過輸入類似的消息到 hash function (更改內容或更改顏色或更改其他跟消息無關的內容) 以求找到相同的 hash
* 主要是利用冗餘性 ( hash 的過程一定有些被丟棄，找出這部分並修改，即使 hash 過後產生的值也會一樣)
* 生日悖論
* 找到 Hash 相同的消息 (強抗碰撞)
* 利用任意 hash 一致的機率比想像中的高
### hash 無法解決的問題
* 檢查不出偽裝
* 若有人假借他人名義發送消息和 Hash 給接收者，此時 Hash 也沒用
**HASH 僅能提供完整性檢查**
## 消息認證碼
為了解決 single way hash 解決不了的偽裝的問題，發明的一種機制
### 消息認證碼本質、使用、問題
* 消息認證碼
* Message Authentication Code (以下簡稱 MAC)
* 對稱密碼 + hash 來確保該 hash 是經由擁有對稱 key 的人所發
* 消息認證碼的使用步驟:
* Alice
1. Alice 向 Bob 發出一段消息
2. Alice 輸入消息和對稱 key 進 MAC 計算出 MAC 值
3. Alice 將 MAC 值發送給 Bob
* Bob
1. Bob 收到消息
2. Bob 輸入消息和對稱 key 進 MAC 計算 MAC 值
3. Bob 收到 MAC
4. Bob 比對兩者是否一致
* 消息認證碼問題:
* 密鑰配送問題
* 解決方案:
* 密鑰配送中心
* Diffie-Hellman
* 公鑰密碼
### 應用例子
* IPsec
* 通訊協定中的 IP ，用 MAC 檢查憑證和完整性
* SSL/TLS
* 同 IPsec
* SWIFT :warning:
* 銀行和銀行間的通訊
### 實作方式
* single hash 實現
* SHA-2 (?
* HMAC
* 用對稱密碼實現
* 利用 AES 中的 CBC 模式對消息加密，保留最後一個密文分組即可 (用來比對而已)
* 其他實現
* 公鑰密碼
* stream cipher :warning:
### 認證加密
結合對稱密碼和認證
* Encryption then MAC
* 先加密後**針對密文計算 MAC**
* 確保密文的確是本人所發
* Encrypion and MAC
* 明文加密後用明文計算 MAC
* MAC then Encryption
* 計算明文 MAC 後連同明文一同加密
* GCM/GMAC
* 透過 AES 中的 CTR 和反覆進行加法乘法運算的 hash function()
### HMAC
利用 hash 來進行 MAC ，高強度的 hash 都可以使用
* 步驟:
1. 密鑰填充為密鑰'
* 小於分組長度則填充
* 大於分組長度則先對密鑰進行 hash 再拿 hash 當作密鑰'
3. 密鑰'與 ipad 進行 xor 輸出 ipadkey
* ipadkey 為 0x36 的 bit sequenece 反覆計算後得到分組長度的 bit sequence
5. ipadkey 與消息組合
6. 計算 hash 為 hash'
7. 密鑰'與 opad 進行 xor 輸出 opadkey
* opadkey 為 0x5c 的 bit sequenece 反覆計算後得到分組長度的 bit sequence
9. 與 hash'合併
10. 再 hash 一次最終得到 MAC 值
### 對 MAC 的攻擊
* Replay Attack
* 透過截獲發送的 MAC 再重複進行發送
* 解決方法:
* 序號
通訊對象必須記錄最後一個序號
* 時間戳
可能有時間差被拿來利用
* nonce
每次通訊都產生隨機值，通訊數據量也會增大
* 密鑰推測攻擊
* 暴力破解
* 生日攻擊
### MAC 無法解決的問題
* 對第三方證明
* 無法對第三者保證該 MAC 一定由某人所發，因為任何知道密鑰的人都可以發
* 防止否認
* 跟上一點類似，可以向第三者否認說該 MAC 不是自己發的，是對方自己發或是被盜用
## 數字簽名 :warning:
(忘的差不多了...先胡扯瞎寫一通)
### 數字簽名的本質、使用
* 數字簽名:
* MAC 的更進階
* 為了**防止否認**
* 和公鑰密碼息息相關 (事實上就是因為對稱密碼共享金鑰才不能防止否認)
* 步驟:
1. Alice 用簽名密鑰加密消息並發送
2. Bob 或第三者收到用 Alice 發布的驗證密鑰解密
若可以解密則確認該消息是由持有簽名密鑰的人所發 (理應只有 Alice 知道)
把簽名密鑰、驗證密鑰和私鑰、公鑰代入也說的通
### 數字簽名的方法
* 直接對消息簽名
1. Alice 用私鑰對消息進行加密，密文就是數字簽名
2. Alice 發送簽名和消息給 Bob
3. Bob 用公鑰解密簽名
4. 將解密完的簽名和直接發送的消息比對
* 處理速度較慢
* 對消息的 hash 簽名
1. Alice 先將消息 hash 得到 hash A
2. Alice 用私鑰對 hash A 加密得到簽名
3. Alice 將消息連同簽名給 Bob
4. Bob 用公鑰解密簽名得到 hash A
5. Bob 對消息 hash 得到 hash B
6. 比對 A, B 進行驗證
* 處理速度較快
* 有碰撞的風險
* 比較安全
### 數字簽名的疑問
* Q: 密文為何能當作簽名使用？
* A: 基於密鑰對的理論，可以由私鑰加密公鑰解密，而能被公鑰解密則代表該密文一定是擁有私鑰的人發送出去的
* Q: 數字簽名不能保證機密性嗎？
* A: 數字簽名本意是防止否認而非保證機密性，不然能用公鑰解密有何機密性可言？
* Q: 簽名可以隨意複製嗎？
* A: ~~不同的消息簽名也會不同，複製沒有意義~~簽名本身就是給大家看，複製再多也沒用
* Q: 消息內容會不會被任意修改？
* A: 任何人都可以對數字簽名做解密以確認消息內容和發送者，~~不能修改誤導他人~~可以修改，但簽名驗證會失敗
* Q: 簽名會不會被重複利用？
* A: ~~有這種風險，不過可以用抵禦重放攻擊的方式防守~~不同的消息簽名也會不同，重複利用一樣會失敗
* Q: 刪除簽名也無法做廢合同嗎？
* A: ~~只要有發過公鑰到網路上，大家都知道密鑰是誰的話，應該無法做廢吧~~要發表聲明說作廢該合同並附上簽名
* Q: 如何防止否認？
* A: 用只有自己知道的私鑰加密來確定
* Q: 數字簽名能代替簽名媽？
* A: 不太能，單純覺得數字簽名可信而盲目使用一樣很危險 :exclamation:
### 應用例子
* SSL/TLS
* 驗證是否為該使用者/伺服器發出的消息
* 安全公告
* 避免有人偽造身分亂發公告，通常稱為**明文簽名**
* 軟體下載
* 軟體下載通常會附上 hash ，但又怕有人不信該 hash 是作者的，於是加上簽名
* 公鑰證書
* 為了確認所獲得的公鑰是合法的，對公鑰做數字簽名
### 透過 RSA 實現簽名
* 生成簽名
1. 對消息或 hash 用私鑰進行加密成數字簽名
2. 將數字簽名和消息合併
* 認證簽名
1. 收到消息和數字簽名
2. 利用公鑰解開數字簽名成 hash 或
3. 拿消息或 hash 進行比對
### 其他簽名方式 :warning:
* ElGamel
* mod N 下求離散對數的困難
* DSA
* Schnorr + ElGamel
* 僅用於數字簽名
* ECDSA
* 利用橢圓曲線算法
* Rabin
* mod N 下求平方根的困難
* 公鑰密碼或是數字簽名
### 對數字簽名攻擊
~~* replay attack~~
* MITM
* 攻擊者介入通訊雙方，假冒他人發送假的公鑰
* 可以透過其他通訊方式對公鑰進行 hash 確認
* 針對公鑰加密的攻擊
* 誘騙他人對密文進行數字簽名 (==對密文解密)
* 所以對 hash 簽名比較安全一點
* RSA 暴力破解
* 質因數分解
* 針對 hash 的攻擊
* hash 須具備抗碰撞
### 數字簽名無法解決的問題
* 確認公鑰一定由發送者所發
* 進入找可信的第三方的無窮迴圈
* 透過 Public Key Infranstructure (PKI)
不太能算解決，只是信任的源頭歸於 PKI 而已
## 憑證 :warning:
(這也是忘的差不多了...直接看書本寫好了)
### 憑證的基本性質和應用
* 公鑰憑證
* 憑證對使用者的姓名、地址、電話、公鑰等訊息
* 認證機構 (Certification Authority) 會對憑證加上數字簽名
* CA 即能夠認證幫你的憑證背書的機構(無論私人、公家)
* 應用
* 以下場景為 Alice 向 Bob 發送密文且公鑰有憑證
1. Bob 生成 key pair
2. Bob 將 pub key 發送給 CA ，由 CA 進行身分確認後對公鑰加上 CA 自己的數字簽名 (身分確認可以是當面確認、 email 確認等方法)
3. CA 用自己的私鑰對 Bob 的公鑰加上數字簽名
4. Alice 由 CA 獲得 Bob 的公鑰和數字簽名
5. Alice 用 CA 的公鑰驗證數字簽名
6. Alice 用 Bob 的公鑰加密消息給 Bob
7. Bob 用私鑰解密
### PKI
PKI (public Key Infrastructure) ，為了有效使用公鑰而形成的規範、規格的總稱
#### PKI 的要素
* 用戶
* 使用 PKI 註冊公鑰的人
* 生成密鑰對
* CA 中認證公鑰
* 向 CA 申請證書
* 申請作廢證書
* 解密密文
* 對消息加上數字簽名
* 使用已註冊 PKI 公鑰的人
* 將消息加密發給接收者
* 驗證數字簽名
* 認證機構
* 生成密鑰對
* 對密鑰加上數字簽名
* 頒發憑證
* 作廢憑證
* 倉庫
* 儲存憑證的資料庫
#### PKI 的工作
* 生成密鑰對
* CA 生成須透過 RFC7292 將私鑰傳送給使用者
* 註冊憑證
1. 先對申請者進行身分辨識
2. 生成憑證
3. 用自己的私鑰對憑證加上數字簽名
* 做廢憑證和 CRL
* 製作憑證作廢清單 (Certification Revocation List)
* 對 CRL 加上數字簽名
* 使用者一定要確認憑證是否被列在 CRL 上
* 結構
* 因為要確認 CA 是否合法，所以要再找第三方幫 CA 做憑證
* 這樣下去一定沒完沒了，所以會有 root CA ， root CA 會自己對自己做憑證
事實上之所以信任 CA 都是源自於對 root CA 的信任
### 對憑證的攻擊
* 公鑰註冊前攻擊
* 申請公鑰前搶先更改掉申請人的公鑰，變成申請人的個人資料 + 攻擊者的公鑰
* 註冊相似人名攻擊
* 註冊相似人名則使用者選擇公鑰時可能會選錯
* 竊取 CA 的私鑰
* 拿到 CA 私鑰就能亂發憑證
* 偽裝 CA
* 顧名思義，慎選 CA 很重要
* 趁 CRL 生效前進行攻擊
* 被他人入侵
* 先入侵別人的電腦獲取私鑰再發送消息給他人詐騙，即使受害者申請 CRL 但這段時間可能有人誤信消息被騙
* 自行否認
* 自己發送消息後馬上申請作廢憑證，如此可以跟別人說自己被盜用
### Q&A
* Q: 為什麼需要憑證
* A: 為了取得可信的公鑰，需要有可信任的第三方幫忙背書
* Q: 通過自己進行憑證是不是更安全
* A: 違反隱蔽式安全謬論
* Q: 為何要相信憑證機構
* A: 要不要信任某 CA 要靠自己從多方資訊進行整理總結而得
## 密鑰
### 密鑰的基本訊息
* 密鑰 == 巨大的數字
* 通常選擇密鑰會選擇**密鑰空間巨大**的數字以防暴力破解
* 密鑰價值即明文價值
* 因為算法公開，所以有了密文和密鑰等於有了明文，故密鑰的價值相等於明文 (密文的攔截很簡單沒什麼問題)
* 加密算法與密鑰
* 加密算法是公開的
* 輸入不同的密鑰，則就算明文相同密文也會不相同
### 各種不同的密鑰 (當做 review )
* 對稱密碼密鑰
* 接收雙方皆相同
* DES:
* 56bit 剩下 8 bit 為校驗碼
* 三重 DES (DES-EDE3) 有 56*3 bit 的密鑰 (如果三個密鑰皆不同的話)
* AES:
* 有 128, 192, 256 bit 版本
* 公鑰密碼的密鑰:
* 加密用公鑰，解密用私鑰，兩者同時生成(key-pair)
* 常見的如 RSA-1024, RSA-2048 等
* 消息認證碼的密鑰
* 對 hash 或消息用共通的對稱密鑰加密以確保為知曉對稱密碼的人發出
* 防偽裝 :exclamation:
* 數字簽名的密鑰:
* 對 hash 或消息用私鑰加密，讓持有公鑰的人能確認該消息是持有私鑰的人發出
* 目的
* 確保機密性用
* 對稱密碼
* 公鑰密碼
* 認證用
* 消息認證碼
* 數字簽名
* 會話密鑰和主密鑰
* 會話密鑰
* 用於單次通訊生成的密鑰
* 主密鑰 :warning:
* 一直重複利用的稱為主密鑰
### 密鑰的管理
* 生成密碼
* 盡量用~~強隨機性~~針對密碼學上用途的偽隨機產生器
* 或是用 Password 這種單字組成的當作密鑰，不過一般都會將 password 丟進 hash function() 過的 hash 值當作密鑰
* 配送密鑰
* Diffie-Hellman 密鑰交換
* 其他通訊方式 (面交?)
* 事先共享密鑰 :warning:
* 密鑰分配中心 :warning:
* 公鑰密碼
* 更新密鑰 :warning:
* 將這次的密鑰輸入 hash 得到 hash A 當作下次的密鑰
* 因為 hash 是單向，故難以從該次的 hash 反推前面的 hash ，這種安全稱為 backward security
* 保存密鑰 :warning:
* 很難靠人腦記住
* 將密鑰加密後保存成文件放在保險箱，加密密鑰的密鑰稱之為 KEK
* 很多密鑰需要保存的話會先統一加密後保存加密密鑰到保險箱
* 作廢密鑰 :warning:
* 若作廢密鑰被得知，則之前的通訊都會被解開
* 需要動用到密碼軟體和電腦系統對資安的保護 (有夠籠統...)
### Diffie-Hellman 密鑰交換
* Diffie-Hellman 原理和步驟
* 在公開的網路上交換~~加密的消息~~用來計算共同密鑰的消息
* 利用解有限元下的離散對數問題的困難度
* 步驟:
1. Alice 向 Bob 發送質數 P 和 P 的生成元 G (P, G 都不需要保密)
2. Alice 生成 1~P-2 隨機數 A ，這個 A 自己保管，千萬不能讓人知道
3. Bob 生成 1~P-2 隨機數 B ，這個 B 自己保管，千萬不能讓人知道
4. Alice 將 G^A mod P 發送給 Bob
5. Bob 將 G^B mod P 發送給 Alice
6. Alice 用 Bob 的 G^B mod P 計算 A 次方並求 mod P
(G^B mod P) ^ A mod P = G^(B*A) mod P
8. Bob 用 Alice 的 G^A mod P 計算 B 次方並求 mod P
(G^A mod P) ^ B mod P = G^(A*B) mod P
10. 所得即為共享密鑰
:warning:
* 生成元的意義
* P 的生成元的次方和 1~P-1 是一對一對應 (無重複)，基於這個性質才能在 1~P-2 之間隨機選一個數當次方，保證出來的數一定是獨一無二
* 橢圓曲線 Diffie-Hellman 交換
* mod N 下求離散對數 :x:
* 橢圓曲線下求離散對數 :o:
### 基於 password 的密碼 (PBE) :warning:
* PBE 基本性質和加解密
* 使用輸入密碼，而後將密碼送入加密算法成密文，將密文當作密鑰
* 加密:
1. 生成 KEK
1. 偽隨機產生器生成亂數當作 salt
2. 自己想一個 password
3. password + salt 送入 hash 生成 KEK
3. 生成會話密鑰並加密
1. 偽隨機產生器生成亂數當作會話密鑰(以下簡稱 CEK)
2. 用 KEK 加密 CEK
3. 將 KEK 丟棄，保存加密後的CEK + salt 即可 (KEK 可以隨時透過 password 和 salt 組成)
4. 用物理的方式保存加密後的 CEK 和鹽
5. 加密消息
1. 用剛剛的 CEK 加密這次的消息
* 鹽的作用
* 在 password 後面加上隨機值，使出來的密文(或 hash) 密鑰空間更大，防禦字典攻擊
* password 的作用
* 方便記憶，可以隨時透過保存的 salt 生成 KEK 用來解密 CEK
* 透過拉伸改良 PBE
* 將 KEK 輸入 hash ，再將結果輸入 hash ，重複以上行為
* 攻擊者必須作更多的嘗試來找到 password
### 生成安全的密碼
* 使用自己才知道的訊息
* 不能被別人知道
* 自己不會忘記
* 將多個不同的 password 分開使用
* 根據 password 價值來區分
* 千萬不可作局部更改而已
* 有效利用筆記
* 用筆記記下來並小心保存
* 理解其侷限性
* 使用相關工具
* chrome 就會自動生成 password
* 是否該使用工具自己要清楚判斷
## 隨機數
### 使用隨機數的密碼技術
現代密碼中的密鑰部分通常都需要隨機數生成，如:
* 對稱密碼 key
* 公鑰密碼 key pair
* IV (mode 中的 initial vector)
* nonce
* salt
### 性質
**定義何謂隨機數很困難，暫且不表**
隨機數具體可以分為三種層級:
1. 隨機性 (弱)
* 不能有規律，看起來雜亂無章，不存在統計偏差
* 僅符合這條稱為弱隨機 (書中自己取的名字)
3. 不可預測性 (中)
* **已知前面的隨機數情況下**，不能讓人猜到之後的隨機數
* 符合 1, 2 稱為強隨機
5. 不可重複性 (強)
* 出現過的隨機數不能再出現
* 通常很難透過軟體去算出來(電腦內部狀態是有限的)，要結合硬體的一些特性
:warning:
### PRNG
* RNG vs PRNG
* RNG
* 用硬體的一些狀態去生成隨機數 (溫度、電壓、聲音等)
* PRNG
* 用軟體去模擬，因為不是真隨機數，故稱為偽隨機數
* PRNG 結構
* 內部狀態
* 根據 PRNG 的記憶體數值作運算，最後給出隨機數
* 給出後會對記憶體數值作調整對接下來的生成隨機數做準備
* 種子
* 用於內部狀態初始化
* 根據種子能生成不同隨機數，而種子需要保密，如同金鑰一般
### 實作
* 雜亂的方法
* 用雜亂無比的算法
* 週期性太小
* 不理解內容也無法判斷是否具備不可預測性 :exclamation:
* 線性同餘
* 不具備不可預測性 (得知前面的隨機數可以預測到後面的隨機數)
* 通常用於遊戲中隨機性
* 通常的公式:
* R0 = (A*seed + C) mod M
* A, C const 且 A,C < M
* R1 = (A*R0 + C) mod M
* 依此類推
* single way hash
* 用種子初始化計數器
* 計算計數器的 hash
* 計數器 + 1 後 hash 為下一個隨機數
* 依此類推
* 要破解隨機數就必須破解 single way hash
* 密碼生成
* 透過對稱密碼或公鑰密碼生成密文當隨機數
* 採用計數器逐步加 1 的方式送入加密算法生成密文
* ANSI X9.17
* 步驟有點多
1. 初使化內部狀態
2. 用當前時間當做掩碼 (當前時間和密鑰輸入進加密算法後所得的密文在此稱為掩碼)
3. 對內部狀態和掩碼作 xor 得 A
4. 對 A 進行加密得 B 當做隨機數
5. 對 B 與掩碼作 xor 得 C
6. 對 C 加密後當做內部狀態
7. 循環
* 以攻擊面向來看:
* 步驟 2 不知道密鑰推不出掩碼
* 步驟 3~4 要反算隨機數必須破解密碼
* 步驟 5~7 更新內部狀態猜不出下一個隨機數，因為還必須知道掩碼和密鑰
* 其他算法
* 須具備不可預測性的算法
* 使用 library 應挑選專門為資訊安全打造的算法
### 對 PRNG 的攻擊
因為被拿來生成密鑰，故也會成為攻擊的對像
* 對種子攻擊
* 種子的重要性等同密鑰
* 可以使用硬體生成的**真●隨機數**當做種子
* 對隨機數池進行攻擊
* 在某個特定文件中累積之後可能會用到的真隨機數
* 本身除了可以取出當隨機數使用外並無任何意義，但必須加以保護 :exclamation:
## SSL/TLS
我覺得這算滿重要的一部分，認真寫一下
### 什麼是 SSL/TLS
* 一個 layer 負責加密網路通訊
* 最常見的就是 http + ssl/tls = https
* 也可以搭配其他 protocol 如: SMTP, POP3
### 網路通訊常需要加密的問題和解決方案
以刷信用卡為例，主要會遇到三個問題:
1. 如何保護信用卡卡號不會被竊聽
* 機密性
* 對稱密碼解決
* 透過 PRNG 生成密鑰
* 會用到公鑰密碼/Diffie-Hellman 等方式解決配送問題
*
3. 如何防止信用卡卡號不會被竄改
* 完整性
* MAC
* single way hash
5. 如何確認 server 真的是商店的
* 驗證性
* 數字簽名
### SSL TLS 區別
原先都是用 SSL 並且更新了好幾版，1999 將 ssl 標準化為 tls ，直到 SSL3.0 爆出 Poodle 漏洞，後來才決定 tls 內不准用 ssl
TLS 內含的技術:
* AES
* GCM
* CCM
* HMAC-SHA256
* ~~DES~~
### TLS 結構和用途
TLS 具體可以分為兩層:
* record protocol
* 負責加密的部分
* handshake protocol
* handshake
* client 跟 server 協商決定用哪個算法和共同密鑰
* 憑證的認證
* 更換密碼規格
* 通知對方更換密碼方式的協議
* 警告協議
* 出錯時將錯誤告知對方
* 應用數據協議
* TLS 上搭載的數據傳給對方的協議
可以想成 handshake 就是負責加密以外的部分
record protocol 的操作過程:
1. 將消息切割成片段
2. 將片段壓縮 (壓縮算法須與對方協商)
3. 對片段加上消息認證碼 MAC
4. 對片段加上編號 (防止 replay attack)
hash 算法和 MAC 的共通密鑰都要跟對方協商
5. 片段 + MAC 用對稱加密 CBC mode 進行加密成密文
6. 密文 + header = data
* handshake protocol 的操作過程(狗幹長):
1. ClientHello
client 對 server 發送以下訊息
* 可用版本
* 當前時間
* client random number (之後會用到)
* session id (是否要重新建立之前的連線)
* 可用密碼套件清單
* 可用壓縮方式清單
通常這階段是 client 跟 server 說自己支援哪種方案， 彼此再協商這樣
3. ServerHello
server 對 client 發送以下訊息
* 可用版本
* 當前時間
* server random number
* session id
* 使用的密碼套件
* 使用的壓縮方式
告知 client 自己使用的方案
5. Certificate (server -> client)
服務器發送證書和 CA 對服務器的證書清單，客戶端進行認證
7. ServerKeyExchange(s->c)
**以Certificate 不滿足為前題**， server 會用 server key exchange 發送必要消息給 client :question:
9. CerticateRequest(s->c)
有必要確認客戶端的情況下， server 會發送自己看的懂的憑證類型清單和自己認可的 CA 清單，要求 client 傳憑證給自己
11. ServerHelloDone(s->c)
server 前置作業完成
13. Certificate(c->s)
**若 server 有發送 certificate request**，client 會發送憑證給 server
15. ClientKeyExchange(c->s)
* 發送預備主密碼或是 Diffie-Hellman 的公開值，透過解密和計算會得到之後用到的主密鑰的值
* 預備主密碼即 client 的隨機值，之後會拿來當生成主密碼的種子使用，主密碼再生成如對稱密碼的密鑰、 MAC 的密鑰、對稱密碼中的 CBC 模式的 IV
(預備主密碼 -> 主密碼 -> 密鑰)
17. CertificateVerify(c->s)
計算主密碼和 handshake protocol message 的 hash ，向 server 證明自己持有憑證的私鑰
19. ChangeCipherSpec(c->s)
告知 server 準備切換密碼
**這屬於密碼規格變更協議**:exclamation:
21. Finished(c->s)
handshake 結束
23. ChangeCipherSpec(s->c)
告知 client 準備切換密碼
25. Finished(s->c)
handshake 結束
27. SwitchToAppliedDataProtocol
使用應用數據協定和 record protocol 進行通訊
上面的部分步驟很多，我大概區分為:
* 選定密碼套件
* client 提供選項
* server 決定
* 憑證相關
* server
* 發送自己的憑證
* 密鑰交換
* 要求對方憑證
* client
* 發送憑證
* 密鑰交換
* 認證憑證
* 切換密碼協定
* 雙方說好交換後就可以結束了
* 密碼規格變更協議
* 同步 client server 密碼切換
* 加密後還可以更改
* 最開始 handshake 是沒有加密的 :exclamation:
* 警告協議
* 發生錯誤時通知對方
* MAC 出錯
* 壓縮出錯
* handshake 時出現異常
* 應用數據協議
* 傳輸數據用
* 主密碼
* 機密性、認證都靠他
* 預備主密碼 + 客戶端隨機數 + 伺服器端隨機數 = 主密碼 (隨機數相當於加鹽 :exclamation: )
### 針對 SSL/TLS 的攻擊
* 針對各種密碼技術進行攻擊
* OpenSSL heartbleed
* Poodle Attack
* FREAK 攻擊
* 強行使用 RSA Export Suites 這個強度較低的套件
* 對 PRNG 攻擊
* 憑證時間差攻擊
不過 SSL/TLS 某個元件出問題可以透過更換套件的方式立即處理
### 注意事項
* 不要誤解憑證
* 憑證僅能代表該機構經過某 CA 認證，有可能該機構正在從事不法工作
* 加密通訊前的數據都不受保護
* 加密通訊後的數據也不受保護 (指加密的數據到達 server 解密後就不被 ssl/tls 保護)
## 橢圓曲線加密 Elliptic Curve Cryptograph
由於是附錄的關係，所以沒有安排好的段落，下面我就按我自己寫的草稿做個紀錄
* 橢圓曲線加密的性質
* 核心概念
* 利用橢圓曲線在有限域下逆推的困難
* 特性
* 密鑰短，強度夠
* 應用
* Public key cryptogrpah
* digital sign
* key exchange
* 實際例子
* SSL/TLS ECDH(Elliptic Curve Diffie-Hellman)
* SSL/TLS ECDSA
* BitCoin
所謂的橢圓曲線其實是指求橢圓弧長的積分反函數
下面是圖片和運算規則
不過要注意的是上面的例子中是在實數域才會有光滑曲線，而加密中的曲線則是在有限域上
有限域即 {0,1,...,p-1,p} 這些數的範圍內進行加減乘除的運算，換句話說原先在實數域上的 elliptic curve 會變成:
y^2 = (ax^3 + bx^2 + cx + d) mod p
若給定 G 點、 x 點求 xG 較簡單
若給定 xG 求 x 就極為困難，而橢圓曲線就是利用這點達到保護機密性
* 橢圓曲線的非對稱加密
* [來源](https://www.youtube.com/watch?v=0_XmvNu0J40)
* P = k * G
* k 為私鑰，隨機生成
* G 為基準點，大家都知道
* P 為計算後的公鑰，也是一個座標點
* kG 是橢圓曲線的運算而非一般的乘法
* 難逆推 + 容易驗證
* 在有限域中的運算
因為有限域中會把點離散化，所以 P, Q 在有限域中超過範圍還找不到焦點的話就從其對稱點再延伸直到找到交點 R 為止，此 R = P + Q
已知 P 的座標是很難推算出 k 的值，因為可能的走向有很多種
Sign in with Wallet
Connect another wallet