加解密（Encryption）& 哈希（Hash）演算法----入門指引

一、Encryption演算法和Hash演算法的區別

• 資訊理論角度：
• Encryption是可逆的，沒有信息熵的改變
• Hash是不可逆的，Hash一般會導致信息熵減小
• 應用角度：
• Encryption常被用來做基於密鑰的數據加解密（AES、RSA、ECC）
• Hash主要被用來做數字簽名、數據校驗（CRC、SHA、MD5）
• 小白角度：
• Encryption就是帶密碼的保險箱
• Hash就是榨汁機，有去無回

二、加解密演算法分為對稱（Symmetric）、非對稱（Asymmetry）兩大類

• 對稱（Symmetric）加密

  n對稱加密是最古老的一種加密方式，從最古老的基於查表替換的「凱撒密碼」到現代的AES等演算法，都是這種類型。其核心特點在於加密、解密的密鑰是一樣的（或可以互相通過演算法變換的）。這種演算法很容易理解，就是一把鑰匙既能加鎖也能開鎖。幾種常見的對稱加密演算法：

• 凱撒密碼
• 例如把一本小說里的 a 替換成 b 、b 替換成 c、c 替換成 d，或者根據一個映射表進行替換。詳細資料參見 https://zh.wikipedia.org/zh-cn/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC 。 這種加密方式比較小兒科，根據詞頻統計就可以輕易破解，常見於小學生傳紙條，中學生信息學奧賽。
• AES（Advanced Encryption Standard）
• 這個演算法久經考驗，運算速度在對稱加密中能排到前三，參見Crypto++官方的測試 http://www.cryptopp.com/benchmarks.html ，廣泛應用於各種加密軟體、硬體，常用的block大小有128bytes、256bytes。
• https://zh.wikipedia.org/zh/%E9%AB%98%E7%BA%A7%E5%8A%A0%E5%AF%86%E6%A0%87%E5%87%86
• SM1、SM4
• SM4是國產加密演算法，block大小為128bytes，演算法是開源的。SM1現在是有硬體實現。
• 關於SM這個名字，我親身請教過北京市保密局的專家&領導，「SM是算密或者商密的簡稱。」
• DES、3DES、Blowfish、RC4等
• 對稱加密的演算法非常之多，一般使用中用AES就基本夠用了。
• 非對稱（Asymmetry）加密
  n非對稱加密演算法，就是加密、解密的密鑰分為兩組，並且互相不能反推。這種演算法在現實中很難有什麼事物可以類比。大致就是通過某種演算法可以生成一個密鑰對k1、k2，用k1加密之後的密文只能用k2解密，反之亦然。
  n非對稱加密演算法從原理上講常用的有兩種：
• 基於因數分解的演算法
• RSA、DSA是此類演算法中的代表，Linux系統的SSH就是基於這兩種演算法進行文件key auth。前幾年一般建議RSA至少要達到1024位密鑰才能保證抵禦暴力破解，但由於GPU和超級計算機的算力提升，現在密鑰長度建議2048位了。
• 橢圓曲線演算法（ECC）
• 這裡說的ECC不是伺服器內存上用到的Error-Correcting Code（奇偶校驗），而是Elliptic Curve Cryptography。內在原理其實我這種搬磚的程序猿不懂，大致是基於解決橢圓曲線離散對數問題的一種演算法-_-|||。但我知道的是這個演算法可以用1/6的密鑰長度達到比RSA更高的強度。代表演算法有ECC、SM2等。
• 非對稱加密演算法非常酷，但它有一個致命的缺點：慢。RSA加密的速度大致是AES的1/30左右。所以我們不可能在所有場合都採用這類加密演算法。我們的程序猿前輩們就創造了SSL、TLS等加密體系：

三、加密體系

說到要給大家理清幾個概念：

TLS的前身是SSL，HTTP + TLS = HTTPS

TLS協議允許C/S模型的應用程序跨網路通訊，旨在防止竊聽和篡改的方式進行溝通。 TLS協議的優勢在於它是與應用層協議獨立無關的。高層的應用層協議（例如：HTTP、FTP、Telnet等等）能透明的建立於TLS協議之上。TLS協議在應用層協議通信之前就已經完成加密演算法、通信密鑰的協商以及伺服器認證工作。在此之後應用層協議所傳送的數據都會被加密，從而保證通信的私密性。

TLS協議是可選的，所以如果需要使用就必須配置客戶端和伺服器，有兩種主要方式實現這一目標：一個是使用統一的TLS協議埠號（例如：用於HTTPS的埠443）；另一個是客戶端請求伺服器連接到TLS時使用特定的協議機制 （例如：郵件、新聞協議和STARTTLS)。一旦客戶端和伺服器都同意使用TLS協議，他們通過使用一個握手過程協商出一個有狀態的連接以傳輸數據[1]。通過握手，客戶端和伺服器協商各種參數用於建立安全連接：

1. 當客戶端連接到支持TLS協議的伺服器要求建立安全連接並列出了受支持的密碼組合（加密密碼演算法和加密哈希函數），握手開始。

2. 伺服器從該列表中決定加密和散列函數，並通知客戶端。

3. 伺服器發回其數字證書，此證書通常包含伺服器的名稱、受信任的證書頒發機構（CA）和伺服器的公鑰。

4. 客戶端確認其頒發的證書的有效性。

5. 為了生成會話密鑰用於安全連接，客戶端使用伺服器的公鑰加密隨機生成的密鑰，並將其發送到伺服器，只有伺服器才能使用自己的私鑰解密。

6. 利用隨機數，雙方生成用於加密和解密的對稱密鑰。

7. 這就是 TLS 協議的握手，握手完畢後的連接是安全的，直到連接（被）關閉。如果上述任何一個步驟失敗，TLS 握手過程就會失敗，並且斷開所有的連接。

以上小節摘自：https://zh.wikipedia.org/zh-cn/%E5%82%B3%E8%BC%B8%E5%B1%A4%E5%AE%89%E5%85%A8%E5%8D%94%E8%AD%B0

四、塊（Block）加密 & 流（Stream）加密

世界上的數據分為兩種：Block and Stream —— auxten

• Block
• 塊很容易理解，數據就在那裡，無論你讀或者不讀。塊的一個顯著特徵就是支持「隨機讀寫」，你可以對數據Block正向讀、倒著讀、跳著讀、躺著讀。磁碟和內存都是這類數據。大多數加密演算法對Block的支持是原生的，也就是說Block是大多數加密演算法的加密、解密最小單元。
• Stream
• 流就像水管一樣，打開水龍頭，來什麼你就收什麼。流的一個顯著特徵就是不支持「隨機讀寫」。由於解密的過程會對之前的數據有依賴，對流進行加密難度係數要比塊加密要高。流的一個典型場景就是網路數據傳輸，如：HTTPS、SSH等協議。

五、鹽的重要性

之前在這篇文章中提到過，如果單純的把文件按塊去加密，即使採用最強壯的演算法也會存在一個很明顯的漏洞，這裡不再贅述，參見：用已知加密演算法AES加密文本123，得到密文xxx，問能否根據密文、加密演算法、原文本123直接推導出密鑰是什麼？ - auxten 的回答

六、暴力破解（Brute-force）

• 原理就是窮舉密鑰去嘗試解密，由於GPU的算力提升，量子計算機的興起，很多演算法變得不堪一擊。

七、哈希（Hash）

哈希演算法在很多地方也被叫做摘要演算法、散列演算法。簡單來說就像是給數據錄指紋。常用來做數據校驗、數據簽名。常見演算法有MD5、SHA、CRC等。

維基百科中英文版的這篇文章寫得比較全面https://en.wikipedia.org/wiki/Hash_function

我就補充一點，關於哈希函數的選用：

工作中發現，很多人對哈希函數的了解僅限於MD5。例如，在做資料庫的分庫分表的時候，可能需要對hostname做一次哈希再去取模，這裡採用MD5就顯得過於浪費CPU。要知道MD5平均會將每個Byte進行6.8次運算代入。

如果只是需要利用哈希的離散型，完全可以採用更輕的哈希演算法，例如fnv hash，對內存是順序訪問，對CPU cache友好，效率比MD5高出很多。具體參見chongo大神的這篇文章：FNV Hash