密碼學概念科普（加密演算法、數字簽名、散列函式、HMAC）

密碼散列函式

密碼散列函式 (Cryptographic hash function)，是一個單向函式，輸入訊息，輸出摘要，主要特點是：

• 只能根據訊息計算摘要，很難根據摘要反推訊息
• 改變訊息，摘要一定會跟著改變
• 對于不同的訊息，計算出的摘要幾乎不可能相同

根據散列函式的上述特點，可以應用在保存密碼、資料防篡改和完整性保護、數字簽名等方面，后面介紹其他概念的時候也會提到，

在網上下載檔案時，經常會提供 MD5 值供校驗，因為檔案實際可能是從世界各地的鏡像站下載的，有可能會被篡改，所以下載完成之后計算一下 MD5 看是否一致，就知道是否被篡改了，

一般系統在設計時，都不會直接保存密碼原文，防止密碼泄漏，這時可以使用散列函式保存原始密碼的摘要，根據散列函式的特點，即便摘要泄漏了，也很難反推出密碼是什么，只有正確的輸入了原始密碼，才能計算出完全相同的摘要，

雖然散列函式是單向的，但可以使用彩虹表用空間換時間，就是把常見的組合的摘要都計算出來，這樣拿到一個摘要之后，去比對一下就有可能找到原始資訊，例如可以去搜索引擎上搜索一下 456b7016a916a4b178dd72b947c152b7 這個字串，很容易就能知道他的原文是什么，

為了避免被彩虹表攻擊，可以在計算摘要時，添加一點隨機的東西進去再計算摘要，這個東西叫鹽值 (salt)，由于鹽值足夠長且是隨機的，這樣想通過事先計算的彩虹表去碰撞就會更困難了，例如上面那個字串很容易能搜到是 admin 的 MD5 值，而如果我們給 admin 后面拼接上 P6R8ERaZ，再計算出 adminP6R8ERaZ 的 MD5 值 70a1a6831709d7e7cb6cc35ccdfdbd39，再去搜索這個值就很難找到他的原文了，上面只是個例子，實際應用中，鹽值不是簡單的添加到原始訊息的后面，

常見的散列函式包括 MD5、SHA-1、SHA-2 等，SHA-2 包含 SHA-256/224、SHA-512/384 等，其中 MD5、SHA-1 已經被證明不安全，推薦使用 SHA-2 系列的，

本文的例子中都使用 MD5，是因為 MD5 生成的摘要是 128 位的，更短一點好寫，

MAC/HMAC

上面提到下載檔案時可能會提供檔案的 MD5，供校驗檔案是否被篡改，這樣做有個前提是這個 MD5 本身不會被篡改，例如下載的檔案放在鏡像站，而 MD5 本身是放在 HTTPS 的源網站的，

但很多時候摘要本身也是不能安全傳遞的，這時如果還使用摘要去校驗就失去了意義，因為篡改訊息的人直接把摘要一起篡改了就行了，

這種情況可以使用訊息認證碼 (Message authentication code, MAC)，MAC 是根據一個密鑰，使用一個演算法，把訊息計算成一個摘要，通信的另一方，使用相同的密鑰和演算法，計算出摘要，對比是否一致，可以驗證訊息是否被篡改，

將訊息和 MAC 一起傳遞，如果訊息被篡改了，但中間人沒有密鑰，無法計算出新的 MAC，訊息接收方就能校驗出訊息被篡改了，

實際使用中通常使用的是 HMAC (keyed-hash message authentication code)，也就是使用密碼散列函式，結合一個密鑰，去計算訊息的摘要，

舉個例子，我們可以定義這樣一個 MAC 演算法：原始訊息后面直接拼接密鑰，然后使用 MD5 演算法計算摘要，假設通信雙方約定的密鑰是 secret，當我要發送 Hello World 時，就計算出 Hello Worldsecret 的 MD5 值 (88266e1db8f6446d33071e6b1b14747f) 作為 MAC 一起發送，如果有人截獲了這個訊息刪了一個字母變成了 Hello Worl，他不知道我們約定的密鑰 secret，就沒辦法計算出新的 MAC，接收方收到 Hello Worl 拼接上 secret 計算出的 MAC 是 d5f4677a2612e26c50b55ba257743170，就會發現訊息被篡改了，

OTP

因為大多數用戶設定的密碼強度可能不夠高，又或者可能在不安全的環境登陸過導致密碼已經泄漏了，所以很多網站除了密碼之外還需要其他驗證方式，提高安全性，

這個時候就需要使用一些只有你和網站之間知道的資訊來驗證，而且這個資訊最好是一次性的，避免被人截獲之后可以多次用于驗證，這個就是 OTP (one-time password)，

例如很多網站都會發送短信驗證碼或郵箱驗證碼，這個就屬于一種 OTP，只有網站知道你的手機號和隨機生成的驗證碼是什么，也只有你擁有這個手機號才能收到這個驗證碼，這個驗證碼用一次就會失效，

HOTP

使用短信驗證碼、郵箱驗證碼作為 OTP，還得依賴郵件服務商或者通信運營商等，而且沒辦法離線，

根據前面提到的 HMAC 的概念，我們可以在注冊賬號的時候和網站約定好一個密鑰，這個密鑰只需要在第一次生成的時候傳遞一次，雙方都保存好，以后需要使用 OTP 驗證的時候，我們就都用這個密鑰去計算某個訊息的 HMAC 值，用這個值作為 OTP 去做認證，這就是 HOTP (HMAC-based one-time password)，

使用 HOTP 同樣可以達到驗證的目的，還可以離線，不用依賴短信和郵箱服務器了，

TOTP

使用 HOTP 時，雙方共同用于計算摘要的資訊可以是一個計數器，例如初始時雙方都是加密 1，每用一次就遞增，但是這個計數器可能出現雙方不一致的情況，所以可能還需要調整一下，

我們可以更進一步約定雙方都去計算一個公開的資訊的摘要，這個資訊雙方永遠都會是一致的，會更方便一些，這個資訊還要隨時間變化，否則每次計算出來的摘要是同一個，就不是 OTP 了，既然這樣，那直接把時間作為資訊去計算摘要就好了，這就是 TOTP (Time-based one-time password) 了，

當然我們還要稍微做些變通，如果直接把精確到秒的時間作為資訊去計算摘要，還沒等輸入呢，就已經過期了，所以一般都會有一個余量，比如除以 30 秒并向下取整，這樣每 30 秒內計算出來的結果都是相同的，

HOTP 和 TOTP 都是有公開的標準的，規定了密鑰是怎么編碼的、使用哪種 HASH 函式、有效期是多長時間、生成的數字是幾位的等等，按照這個標準，理論上自己手敲計算器都能計算出相同的 TOTP 值，要備份也很容易，只要把前面說的那個和網站約定的共同的密鑰備份下來就行了，

國外主流網站都支持使用 TOTP 作為二次驗證的手段，Google 和微軟也都有自己的身份認證器應用，因為 TOTP 是一個標準，所以不是一定要用這些應用，更不是每個網站都要安裝一個 APP，可以找一個支持 TOTP 的 APP 統一管理所有網站的就可以了，例如 Keepass，支持所有平臺，還可以管理密碼，

有些銀行的安全介質除了 U 盾外，還有一種長得像一個小計算器一樣的電子密碼器，其實這個東西也算是一個 TOTP 和 HOTP 的應用，這個東西打開之后就會有一個每 30 秒更換一次的 6 位數字，辦理業務時需要把這個數字輸入進去，這就是 TOTP，有些場景還需要把網銀或手機銀行上彈出的幾位數字輸入到電子密碼器中，然后再把密碼器上生成的數字輸入回網銀或手機銀行，這就是 HOTP，這里面的軟體演算法應該和上面說的差不多，做成一個硬體可以防止密鑰泄漏、丟失，

對稱加密演算法

如果想加密一段資訊，最容易想到的方式就是先隨機生成一段足夠長的密鑰，例如 01010101011010101，然后用這個密鑰對明文的每一位做異或操作，就得到了密文，如果這個密鑰足夠隨機，理論上沒有人能根據密文直接還原明文，解密時使用密鑰再對密文做一次異或操作，就得到了明文，這基本上就是流加密的原理了，

這種需要加密和解密雙方具有相同資訊（密鑰）的加密演算法，叫做對稱加密演算法，

流加密就像上面例子一樣，直接對每一位加密，效率高，但需要密鑰和加密的資料一樣長，很難做到，實際應用并不多，

另一種更常用的對稱加密演算法是分組加密演算法，又叫塊加密，就是把明文根據演算法和密鑰長度分成一塊一塊的去加密，

因為明文不太可能總是密鑰長度的整數倍，所以不夠的部分就需要填充，比如全填 0，或者按照其他什么規則填充，這個叫做填充模式，

分組加密處理每組資料有幾種不同的作業模式，最直觀的就是把每一塊獨立加密再拼接起來就行了，這就是 ECB 模式（Electronic codebook，電子密碼本），但這樣的特征很容易被人識別，更安全一點的例如 CBC 模式（Cipher-block chaining，密碼分組鏈接），每一塊都是在上一塊加密的基礎上進行加密的，

另外為了保證相同的明文多次加密的結果不一樣，還要使用一個隨機生成的初始化向量 (IV)，作用就跟鹽值的作用差不多，

使用 OpenSSL 時，可以通過引數設定加密演算法和作業模式，如果不指定默認是 CBC 模式，GPG 默認使用的是定制過的 CFB 模式，不能自己選擇，

常見的對稱加密演算法有 DES、3DES、AES，其中 DES 已經不安全了，3DES 也不完全安全，建議使用 AES，AES 演算法的密鑰長度有 128、192、256 三種，

KDF/PBKDF2

我們在實際使用對稱加密演算法時，自己想的密碼的強度通常是不夠的，

例如 AES 演算法最短的密鑰長度也有 128 位，也就是 16 個位元組，粗略的估計大概是 16 個字符的密碼長度，實際不能這樣比較，因為 128 位的密鑰意味著有 2^128 ≈ 3 * 10^38 種組合的可能，而 16 個字符的密碼，如果只包含字母和數字，大概只有 (26 + 26 + 10)^16 ≈ 5 * 10^28 種組合，就算算上全部 ASCII 可列印字符，也只有 95^16 ≈ 4 * 10^31 種組合，而且實際使用中，一般人不可能真的想到和記住這么復雜的密碼，

所以如果直接使用自己想到的密碼作為密鑰去加密資料，實際暴力破解起來的難度至少會下降幾個數量級，根本達不到 128 位的密鑰強度，

為了解決這個問題，我們可以基于輸入的密碼去派生出一個更加安全的密鑰，這個派生的程序要足夠的慢、足夠的隨機，足夠隨機是為了防止被彩虹表攻擊、足夠的慢是增加暴力破解的難度，

例如本來 1 毫秒就能試一個密碼，如果是 6 位數字的密碼，只需要不到兩分鐘就能破解出來了，而如果這個密鑰派生的程序需要 1 秒，那么同樣是 6 位數字的密碼，也需要大概 69 天才能試出來，

用于派生密鑰的函式叫做 KDF (Key derivation function)，目前常用的是 PBKDF2 (Password-Based Key Derivation Function 2)，通過加入隨機的鹽值，使用 HMAC 演算法，迭代很多輪次，得到最終的密鑰，

GPG 的 s2k (string to key) 系列引數，就是用來控制 KDF 演算法的相關引數，SSH 用的是 bcrypt pbkdf，OpenSSL 可以在命令中指定 pbkdf 演算法和迭代次數，

非對稱加密演算法

根據 GPG 使用指南中的描述，直接使用對稱加密演算法加密，很多時候如何交換密鑰就成了一個問題，而非對稱加密則利用一些數學問題，使雙方可以不需要具有相同的密鑰也能加解密訊息，

非對稱加密演算法一般利用的是離散對數、大數分解、橢圓曲線等數學問題，不管是哪個都超出了我的知識范疇，但這不影響我們理解非對稱加密，

我們可以假設這是一個只會計算乘法、沒人會算除法的世界，那么如果有這樣一對數字 2 和 0.5，就可以把他們分別作為公鑰和私鑰，例如我可以把 2 作為公鑰廣而告之，誰想給我發送數字（例如 5），就把它乘 2 （得到 10）發過來，我收到之后再乘 0.5 就得到了原始數字（5），而如果其他人拿到這個 10，即便知道公鑰是 2，但是因為不會計算除法，所以也無法計算出原始數字，

正是因為非對稱演算法利用了各種數學計算，所以沒有對稱加密演算法那種簡單粗暴的位運算高效，性能大概比對稱加密演算法慢 10 倍以上，

所以一般不會直接使用非對稱加密演算法去加密原始資訊，而是去加密一個短一點的對稱加密密鑰，然后再用這個對稱加密密鑰去加密真正的訊息，當然理論上說，結合分組加密演算法的作業模式，使用非對稱加密演算法直接去加密長一點的原始資訊也是完全可行的，只是慢了點，

非對稱加密演算法的用途很廣泛，除了基本的加密之外，還可以用于數字簽名、密鑰協商等場景，

數字簽名

如果直接使用私鑰加密，同樣也只有公鑰能解密，但因為公鑰已經廣而告之了，這種加密就沒有保密的意義了，但可以證明這個訊息確實是由這個持有這個公鑰對應的私鑰的人發出的，而且沒有被改動過，就像是簽名一樣，所以叫做數字簽名，

同樣的基于性能的考慮，一般不會、也沒必要用私鑰直接加密（簽名）整個訊息，根據前面密碼散列函式的特點，我們只需要先對訊息計算個摘要，再對摘要進行簽名，就可以達到給整個訊息簽名相同的效果了，

這就有點像要給一打檔案蓋章，沒必要一頁一頁的去蓋章，可以在這一打檔案的側面蓋一個章，這樣如果這一打檔案被抽走、添加、替換了一頁，這個印章都不會完整了，

密鑰協商

前面說了出于性能的考慮，我們一般只用非對稱加密演算法加密一個對稱加密密鑰，然后再用這個對稱加密密鑰去真正的加密訊息，這種方式生成的密鑰不夠隨機，只有通信的發送方參與了密鑰的生成，密鑰協商演算法可以使通信的雙方共同參與協商出一個密鑰，

我們同樣可以假設這是一個只會算乘法的世界，然后通信的雙方可以事先約定好一個數字（例如 10），然后雙方都再隨機生成一個誰都不知道的數字（例如雙方分別是 2 和 3），然后雙方都用自己隨機生成的數字乘以約定好的數字發給對方（10 * 2 = 20 和 10 * 3 = 30），雙方收到后再都用收到的數字乘以自己隨機生成的數字 （30 * 2 = 60 和 20 * 3 = 60）就得到了相同的數字（60）作為密鑰，最終生成的這個密鑰雙方都有參與，而其他人就算拿到了中間傳遞的 10、20、30 等資訊，但因為他們都不會計算除法，就沒辦法知道真正的密鑰是什么，

這種密鑰協商演算法可以安全的交換一個密鑰，但沒辦法防止中間人攻擊，所以一般使用時還需要結合數字簽名等使用，

非對稱加密演算法概覽

非對稱加密演算法的種類比較多，而且不像對稱加密演算法中 AES 一枝獨秀，各種演算法都有其使用場景，因此分別簡單介紹一下，

依賴大數分解問題的演算法：

• RSA 演算法是非對稱加密演算法中最主流、使用范圍最廣、兼容性最好的，安全性隨著其密鑰長度的增加而增加，但性能也會隨之急劇下降，

依賴離散對數問題的演算法：

• DSA (Digital Signature Algorithm) 演算法顧名思義，他在設計上就只是用來簽名的，不能用來加密，因為安全問題已經不推薦使用了，
• DH 密鑰協商演算法/協議，可以在通信的雙方之間安全的交換會話密鑰，

依賴橢圓曲線問題的概念：

• ECC（Elliptic Curve Cryptography，橢圓曲線演算法），比 RSA、DSA 等依賴大數分解和離散對數的演算法性能更好，同等安全級別需要的密鑰長度也更短，ECC 是一個泛指，并不是一個具體的演算法，
• ECDSA 是使用橢圓曲線實作的 DSA 演算法的變體，具有比 DSA 演算法更高的安全性和更好的性能，
• EdDSA 和 ECDSA 類似，但使用的是愛德華茲曲線，比 ECDSA 性能和安全性更好，
• ECDH 是使用橢圓曲線實作的 DH 密鑰交換演算法，

ECDSA、EdDSA、ECDH 和 ECC 一樣，都是一種泛指，要結合具體的橢圓曲線實作，

具體的橢圓曲線：

• NIST P-256/P-384/P-512 曲線，
• Curve25519 曲線，性能比 P 系列曲線更好，而且 NIST 的曲線被人懷疑可能會有后門，而 Curve25519 更加公開透明，

具體的橢圓曲線演算法：

• X25519 是使用了 Curve25519 曲線的 ECDH 演算法實作，
• Ed25519 是使用了 Curve25519 曲線和 SHA-512 的 EdDSA 演算法實作，

非對稱加密演算法對比

這么多非對稱加密演算法，拋開與眾不同的 DH 演算法和已經不再推薦使用的 DSA 演算法，其實剩下的主要就是依賴大數分解問題的 RSA 演算法和依賴橢圓曲線問題的 ECC 系列演算法了，

更具體一點，我們可以對比一下 Curve25519 和 3072 位的 RSA 演算法，

在安全方面，Curve25519 的密鑰長度是 256 位，和 3072 位的 RSA 演算法一樣，都大概等同于 128 位的密鑰強度，所以他們從安全性上來講，基本上是相同的，

在性能方面，ECC 演算法所需的密鑰長度更短、計算性能更快，而且隨著對安全級別要求的提升，ECC 的密鑰長度是線性增加的、而 RSA 并不是，例如要實作 256 位的密鑰強度，ECC 只需要 256 位密鑰長度，RSA 演算法則需要 15360 位，所以普遍認為 ECC 將會取代 RSA 演算法，

但這并不意味著 RSA 演算法在現在就已經過時了，RSA 演算法更加久經考驗，適用范圍和兼容性更好，滿足當前安全強度所需的密鑰長度還在可接受范圍內，只是性能差了點，

密鑰強度

密鑰強度是指暴力破解所需的計算復雜度，通常用位來表示，

對于對稱加密演算法來說，密鑰強度比較直接，例如 AES-128 演算法的密鑰強度就是 128 位，因為對稱加密演算法暴力破解的方式就是把所有的密鑰可能都試一遍，沒有更好的方法了，

而非對稱加密演算法暴力破解則可以根據一些數學特性有更高效的破解方法，所以密鑰強度并不等同于其密鑰長度，例如 3072 位的 RSA 演算法和 256 多位的橢圓曲線演算法都大概只有 128 位的密鑰強度，也就是說要破解 3072 位的 RSA 演算法，并不需要計算 2^3072 次，只需要計算 2^128 次就夠了，

具體密鑰強度的對應關系，以及不同演算法推薦使用的密鑰長度可以參考 Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2020)，

標籤：其他

上一篇：空 - 三眼烏鴉

下一篇：返回列表