# 加密演算法介紹

###### tags: `讀書會`

## 概述

今天要介紹的是加密演算法的應用，主要會介紹下面四種演算法

- 對稱
- 非對稱
- Hash function
- KDF

加密的目的不外乎以下幾種：

- `機密性（confidentiality)`——在傳輸數據的時候，不希望竊聽者能夠知道消息的內容。或者保護某些敏感資料如密碼。
- `身份認證（Authentication）`——相當於簽名。收信者希望**能確證該訊息是特定的某個人發出的**，其他人**不能冒充**，例如數位簽名
- `完整性（Integrity）`——這意味著收信者能夠證實自己得到的數據是完完整整、沒有**經第三方改動過**的。
- `不可抵賴性（Non-repudiation）`——防止發信方抵賴自己創建過、發送過某條消息。

## 對稱式加密


Symmetric-key algorithm

圖：原文使用密鑰經過演算法加密成密文，密文通過同一把密鑰可解密成原文
加密解密 使用同一把私鑰 (key),因此稱為對稱加密

這個保護過程的原理是，只要密鑰（有時候也叫「口令」，password）沒有暴露、只被得到授權的人所知，那麼原始數據就不會暴露給其他人。只有知道密鑰的人才能解密密文。這個思路，我們叫「私鑰」

- 優點：運算快
- 缺點：是要求雙方取得相同的密鑰

以下介紹兩種對稱加密演算法
### DES

<details>
<summary>緣由</summary>

1970 年代，IBM 發現他們的客戶需要某種形式的加密手段，所以他們成立了一個密碼學小組，由Horst-Feistel 領頭。他們設計出了一種加密算法叫「Lucifer」。Lucifer 最終被美國國家標準局（現在叫做國家技術與標準局，NIST）接受，因此叫做「DES（數據加密標準）」。
</details>

1997 年以後，DES 被窮舉式搜索攻擊攻破。DES 的主要問題在於加密密鑰的位數太小。隨著電腦運算力的增加，通過暴力窮舉所有可能的密鑰組合來破解密文慢慢變成了一種可行的辦法。

**三重 DES** —— 使用 112位或者 168位的密鑰連續三次使用 DES算法。最終這個算法會比其它有類似強度的算法慢得多，而且，因為電腦還是強大到了能破解這個算法

之所以介紹 DES 是因為他算是第一個正式出現的對稱加密演算法，但以現今來說這一方法已經過時了。

### AES ✅

1997 年，NIST 再次徵求新的加密算法提案，最終收到了 50 份提案。2020 年，NIST 接受了「Rijndael」算法，並命名為「AES」，高級加密標準。

高級加密標準（AES）支持三種密鑰大小，128 位的、192 位的和 256 位的，而數據則按 128 位為一個組。

<details>
<summary>AES 加密</summary>

1. 把明文按照128bit拆分成若干個明文塊。
2. 按照選擇的填充方式來填充最後一個明文塊。
3. 每一個明文塊利用AES加密器和密鑰，加密成密文塊。
各種Key長度對應的輪數如下：
- AES128：10輪
- AES192：12輪
- AES256：14輪
5. 拼接所有的密文塊，成為最終的密文結果。

簡單來說就是以 16 個 byte 為單位 (一個 4x4矩陣) 進行一連串的字節替換、混淆、加密等等

https://www.gushiciku.cn/dc_hk/103291404

AES 有五種加密模式：CBC、ECB、CTR、OCF、CFB
</details>

AES算是廣泛使用的對稱加密演算法

## 非對稱加密


對稱加密的缺點是要求雙方必須取得相同的密鑰

而非對稱加密 (Asymmetric cryptography) 也稱公開金鑰密碼學（Public-key cryptography）
其核心為一組公私鑰，公鑰加密，並用對應的私鑰才解密。

對稱金鑰加密牽涉到金鑰管理的問題，尤其是**金鑰交換**，它需要通訊雙方在通訊之前先透過另一個安全的管道交換共享的金鑰，才可以安全地把密文透過不安全的管道傳送；對稱金鑰一旦被竊，其所作的加密將即時失效；而在網際網路，如果通訊雙方分隔異地而素未謀面，則對稱加密事先所需要的「安全管道」變得不可行；非對稱加密則容許加密公鑰隨便散布，解密的私鑰不發往任何使用者，只在單方保管；如此，即使公鑰在網上被截獲，如果沒有與其匹配的私鑰，也無法解密，極為適合在網際網路上使用。

另一方面，公鑰解密的特性可以形成**數位簽章**，使數據和檔案受到保護並可信賴；如果公鑰透過數位憑證認證機構簽授成為電子憑證，更可作為數位身分的認證，這都是對稱金鑰加密無法實現的。

不過，公鑰加密在在**計算上相當複雜**，**效能欠佳、遠遠不比對稱加密**；因此，在一般實際情況下，往往**通過公鑰加密來隨機建立臨時的對稱秘鑰，亦即對話鍵，然後才通過對稱加密來傳輸大量、主體的資料**。

### RSA

https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

https://ithelp.ithome.com.tw/articles/10250721

(用公鑰反推私鑰 -> 質因數分解)

> 對極大整數做因數分解的難度決定了 RSA 演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 演算法愈可靠。假如有人找到一種快速因數分解的演算法的話，那麼用 RSA 加密的訊息的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的 RSA 鑰匙才可能被強力方式破解。到目前為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。**只要其鑰匙的長度足夠長，用RSA加密的訊息實際上是不能被破解的**。

到目前為止，世界上還沒有任何可靠的攻擊RSA演算法的方式可以破解 1024bit 的金鑰。
因此現今只金鑰長度超過1024bit，即是安全的，但因為 768 bits 被破解威脅到 1024bit 的金鑰
建議至少使用 2048 bit 的金鑰

## Hash function 雜湊函式

MD5, SHA-1, SHA-256...

1. Hash算法是把任意長度的輸入數據經過算法壓縮，輸出一個**尺寸小了很多**的**固定長度**的數據，即hash值。hash值也稱為輸入數據的數字指紋（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函數具備以下的性質：
2. 給定輸入數據，很容易計算出它的hash值 (**快**)；
3. 反過來，給定hash值，倒推出輸入數據則很難，計算上不可行。這就是哈希函數的**單向性**，在技術上稱為抗原像攻擊性；
4. 想要找出能夠產生同樣的hash值的兩個不同的輸入數據，（這種情況稱為碰撞，Collision），這很難，計算上不可行，在技術上稱為**抗碰撞**攻擊性；
5. hash值不表達任何關於輸入數據的信息。

應用場景

- 保護資料 (單向，只能做比對，無法得知原本數據)
- **確保傳遞真實的資訊，未經竄改 (integrity)**
- 雜湊表: 使用雜湊表能夠快速的按照關鍵字尋找資料記錄
- 語音辨識: 匹配 mp3 檔案

Integrity

- 信息/資料 -> 加密(信息)
- 信息 -> Hash -> 加密(Hash)

使用 hash 來比對可以快速判斷資料正確性

## 三種加密比較

| 加密演算法 | 優點 | 缺點 |應用場景|
| -------- | -------- | -------- | --|
| 對稱加密 | Text | Text |d|
| 非對稱加密 | Text | Text |d|
| 雜湊函式 (Hash) | Text | Text |d|

## https 中的三種加密演算法應用

1. client 發起 http 請求，和伺服器協商支援的TLS版本，和支援的[密碼套件](https://zh.wikipedia.org/wiki/%E5%AF%86%E7%A0%81%E5%A5%97%E4%BB%B6)(後續需要用到的各種加密演算法)
2. 伺服器將自己的信息以數位證書的形式返回 client (證書內含有公鑰、網站地址、頒發機構、日期等)
3. client 驗證證書合法性 (數位憑證認證機構 Certificate Authority，縮寫為CA）
4. 瀏覽器產生一個隨機的對稱密鑰 (session key)，並用公鑰加密 (and mac) 送往伺服器
5. 伺服器使用私鑰加密取得 session key，後續內容便使用對稱加密進行傳送。

https 過程中也有使用 hash 來確保傳遞真實的資訊，沒有被竄改或遺失，例如在傳遞數位證書、和對稱密鑰 (session key)時。

### support

支援的 對稱/非對稱 加密方法，會隨著版本而更新

https://zh.wikipedia.org/wiki/%E5%82%B3%E8%BC%B8%E5%B1%A4%E5%AE%89%E5%85%A8%E6%80%A7%E5%8D%94%E5%AE%9A#TLS_1.3

## How to save password in db

- Hash
- Salt

Hash function 設計將大量內容**快速**轉成**較短的** hash -> 適合用來確保完整性 (integrity)

而現今用 hash function 來當作 hash password 的方法已經不太合適

## Key derivation functions (KDF)

金鑰衍生函式
使用偽隨機函式從諸如**主金鑰**或**密碼**的秘密值中衍生出一個或多個金鑰
金鑰延伸/強化

為了對抗線下的**窮舉攻擊**，KDFs 通常故意被設計成**緩慢執行**

KDF 最重要的是有 **迭代因子**

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

- PRF 是一個偽隨機函式，可以簡單的理解為 Hash 函式。
- Password 表示口令 。
- Salt 表示鹽值，一個隨機數。
- c 表示迭代次數。
- dkLen 表示最後輸出的金鑰長度。

如果 c 的數值越大，那麼運算速度就越慢，增加了時間複雜度，攻擊者破解的成功率就會下降。

可以不斷加大來應對日益強大的電腦運算效能。

比較: Md5 0.1s, PBKDF2 16s

PBKDF2、**bcrypt**、scrypt

https://www.npmjs.com/package/bcrypt

## references

- https://www.blocktempo.com/understanding-cryptography-from-math-to-physics/
- https://jackterrylau.pixnet.net/blog/post/222379223-2017-05-05-https-%E4%BA%A4%E6%8F%9B%E8%A8%8A%E6%81%AF%E5%8E%9F%E7%90%86
- https://read01.com/zh-tw/7Pj4g8.html#.YVVjbTHP1PY
- https://missing-semester-zh-hant.github.io/2020/security/