目錄
一、Hash算法與數字摘要
1、定義及特性
2、常見算法
3、數字摘要
二、加解密算法
1、對稱加密算法
2、非對稱加密算法
3、混合加密機制
三、消息認證碼與數字簽名
1、消息認證碼
2、數字簽名
四、數字證書
五、PKI體系
六、默克爾樹結構
七、布隆過濾器
1、基于Hash的快速查找
2、更高效的布隆過濾器
資訊安全的核心要素：機密性、完整性、可認證性、不可抵賴性
一、Hash算法與數字摘要
1、定義及特性
Hash算法又可稱為指紋（fingerprint）算法或摘要（digest）算法，可以将任意長度的二進制明文串映射為較短的二進制串（Hash值），該二進制串通常是固定長度的。
一個優秀的Hash算法有以下特點：
- 正向快速：算法能在有限時間和有限資源内計算得到Hash值。
- 逆向困難：對于給定的Hash值，在有限時間内幾乎不可能逆推出原文。
- 輸入敏感：原始輸入資訊發生任何變化，新産生的Hash值應該發生很大的變化。
- 避免碰撞：很難找到兩個内容不同的明文，使得它們的Hash值一樣，即發生碰撞。
2、常見算法
國際上：
- MD（Message Digest）系列算法，主要包括MD4與MD5算法，目前安全性無法滿足商業需求。
- SHA（Secure Hash Algorithm）系列算法，主要包括SHA-1（安全性不足）與SHA-2（包括SHA-224、SHA-256、SHA-384、SHA-512）。
國内：
- SM3密碼雜湊算法，可滿足商業需求。
3、數字摘要
數字摘要是對原始資料内容進行Hash運算，擷取唯一的摘要值。利用Hash函數抗碰撞性的特點，數字摘要可以檢測内容是否被篡改。
例如下載下傳檔案時，有些網站會一并提供相應的數字摘要值，使用者在本地自行計算摘要值并與其比較，以判斷檔案是否被篡改。
二、加解密算法
從設計理念和應用場景上可以分為：對稱加密（symmetric cryptography），又稱密鑰加密（common-key cryptography）與非對稱加密（asymmetric cryptography），又稱公鑰加密（public-key cryptography）。
1、對稱加密算法
加解密過程使用的密鑰是相同的。優點是加解密效率高（速度快、不占空間）、加密強度高；缺點是參與方需要提前持有密鑰，是以密鑰的分發是個問題，常借助非對稱加密算法或Diffie-Hellman協商協定來實作。
對稱密碼從實作原理上可以分為兩種：分組密碼和序列密碼。前者将明文切分為定長資料塊作為基本加密機關，應用最為廣泛。後者則每次隻對一個位元組或字元進行加密處理，且密碼不斷變化，隻用在一些特定領域（如數字媒介的加密）。
分組對稱加密代表算法包括：
- DES（Data Encryption Standard）：将 64 位明文加密為 64 位的密文。其密鑰長度為 64 位（包括 8 位校驗碼），現在已經很容易被暴力破解。
- 3DES：三重 DES 操作：加密 --> 解密 --> 加密，處理過程和加密強度優于 DES，但現在也被認為不夠安全。
- AES（Advanced Encryption Standard）：用于替代DES，分組長度為 128、192、256 位三種。AES 的優勢在于處理速度快，整個過程可以數學化描述，目前尚未有有效的破解手段。
- IDEA （International Data Encryption Algorithm）：設計類似于 3DES，密鑰長度增加到 128 位，具有更好的加密強度。
序列加密，又稱流加密。Shannon（資訊論創始人）首次證明，要實作絕對安全的完善保密性（Perfect Secrecy），可以通過“一次性密碼本”的對稱加密處理。即通信雙方每次使用跟明文等長的随機密鑰串對明文進行加密處理。序列密碼采用了類似的思想，每次通過僞随機數生成器來生成僞随機密鑰串。代表算法包括 RC4 等。
2、非對稱加密算法
非對稱加密是現代密碼學的偉大發明，它有效解決了對稱加密需要安全分發密鑰的問題。非對稱加密中，加密密鑰和解密密鑰是不同的，分别被稱為公鑰（Public Key）和私鑰（Private Key）。私鑰一般通過随機數算法生成，公鑰可以根據私鑰生成。其中，公鑰一般是公開的，他人可擷取的；私鑰則是個人持有并且要嚴密保護，不能被他人擷取。
非對稱加密算法優點是公私鑰分開，無需安全通道來分發密鑰。缺點是處理速度（特别是生成密鑰和解密過程）往往比較慢，一般比對稱加解密算法慢 2~3 個數量級；同時加密強度也往往不如對稱加密。
非對稱加密算法的安全性往往基于數學問題，包括大數質因子分解、離散對數、橢圓曲線等經典數學難題。
代表算法包括：
- RSA：算法利用了對大數進行質因子分解困難的特性，但目前還沒有數學證明兩者難度等價，或許存在未知算法可以繞過大數分解而進行解密。
- ElGamal：利用了模運算下求離散對數困難的特性，比 RSA 産生密鑰更快。被應用在 PGP 等安全工具中。
- 橢圓曲線算法（Elliptic Curve Cryptography，ECC）：應用最廣也是強度最高的系列算法，基于對橢圓曲線上特定點進行特殊乘法逆運算（求離散對數）難以計算的特性。一般被認為具備較高的安全性，但加解密過程比較費時。
- SM2（ShangMi 2）：中國國家商用密碼系列算法标準，同樣基于橢圓曲線算法，一般認為其安全強度優于 RSA 系列算法。
非對稱加密算法适用于簽名場景或密鑰協商過程，但不适于大量資料的加解密。除了 SM2 之外，大部分算法的簽名速度要比驗簽速度慢（1~2個數量級）。
RSA 類算法被認為已經很難抵禦現代計算裝置的破解，一般推薦商用場景下密鑰至少為 2048 位。如果采用安全強度更高的橢圓曲線算法，256 位密鑰即可滿足絕大部分安全需求。
3、混合加密機制
混合加密機制同時結合了對稱加密和非對稱加密的優點。
該機制的主要過程為：先用非對稱加密（計算複雜度較高）協商出一個臨時的對稱加密密鑰（或稱會話密鑰），然後雙方再通過對稱加密算法（計算複雜度較低）對所傳遞的大量資料進行快速的加密處理。
典型的應用案例是網站中使用越來越普遍的通信協定 —— 安全超文本傳輸協定（Hyper Text Transfer Protocol Secure，HTTPS）。
三、消息認證碼與數字簽名
消息認證碼和數字簽名技術都可以通過對消息的摘要進行加密，可以防止消息被篡改和認證身份。
1、消息認證碼
消息認證碼（Hash-based Message Authentication Code，HMAC），利用對稱加密，對消息完整性（Integrity）進行保護。
基本過程為對某個消息，利用提前共享的對稱密鑰和 Hash 算法進行處理，得到 HMAC 值。該 HMAC 值持有方可以向對方證明自己擁有某個對稱密鑰，并且確定所傳輸消息内容未被篡改。
典型的 HMAC 生成算法包括 K，H，M 三個參數。K 為提前共享的對稱密鑰，H 為提前商定的 Hash 算法（如 SHA-256），M 為要傳輸的消息内容。三個參數缺失了任何一個，都無法得到正确的 HMAC 值。
消息認證碼可以用于簡單證明身份的場景。如 Alice、Bob 提前共享了 K 和 H。Alice 需要知曉對方是否為 Bob，可發送一段消息 M 給 Bob。Bob 收到 M 後計算其 HMAC 值并傳回給 Alice，Alice 檢驗收到 HMAC 值的正确性可以驗證對方是否真是 Bob。因為如果消息被篡改，或者對方并不是Bob（所持密鑰不為K），則發送給Alice的HMAC值與自己計算得出的HMAC值不相同。
消息認證碼的主要問題是需要提前共享密鑰，并且當密鑰可能被多方同時擁有（甚至洩露）的場景下，無法追蹤消息的真實來源。如果采用非對稱加密算法，則能有效的解決這個問題，即數字簽名。
2、數字簽名
數字簽名既可以證明某數字内容的完整性，又可以确認其來源（即不可抵賴，Non-Repudiation）。
一個典型的場景是，Alice 通過信道發給 Bob 一個檔案，Bob 如何獲知所收到的檔案即為 Alice 發出的原始版本？
Alice 可以先對檔案内容進行摘要，然後用自己的私鑰對摘要進行加密（簽名），之後同時将檔案和簽名都發給 Bob。Bob 收到檔案和簽名後，用 Alice 的公鑰來解密簽名，得到數字摘要，與對檔案進行摘要後的結果進行比對。如果一緻，說明該檔案确實是 Alice 發過來的（因為别人無法擁有 Alice 的私鑰），并且檔案内容沒有被修改過（摘要結果一緻）。
理論上所有的非對稱加密算法都可以用來實作數字簽名，實踐中常用算法包括 DSA（Digital Signature Algorithm，基于 ElGamal 算法）和安全強度更高的 ECSDA（Elliptic Curve Digital Signature Algorithm，基于橢圓曲線算法）等。
除普通的數字簽名應用場景外，針對一些特定的安全需求，産生了一些特殊數字簽名技術，包括盲簽名、多重簽名、群簽名、環簽名等。
四、數字證書
對于非對稱加密算法和數字簽名來說，很重要的步驟就是公鑰的分發。理論上任何人都可以擷取到公開的公鑰。然而這個公鑰檔案有沒有可能是僞造的呢？傳輸過程中有沒有可能被篡改呢？一旦公鑰自身出了問題，則整個建立在其上的的安全性将不複成立。
數字證書機制正是為了解決這個問題，它就像日常生活中的證書一樣，可以確定所記錄資訊的合法性。比如證明某個公鑰是某個實體（個人或組織）擁有，并且確定任何篡改都能被檢測出來，進而實作對使用者公鑰的安全分發。
根據所保護公鑰的用途，數字證書可以分為加密數字證書（Encryption Certificate）和簽名驗證數字證書（Signature Certificate）。前者往往用于保護用于加密用途的公鑰；後者則保護用于簽名用途的公鑰。兩種類型的公鑰也可以同時放在同一證書中。
一般情況下，證書需要由證書認證機構（Certification Authority，CA）來進行簽發和背書。權威的商業證書認證機構包括 DigiCert、GlobalSign、VeriSign 等。使用者也可以自行搭建本地 CA 系統，在私有網絡中進行使用。
五、PKI體系
公鑰可以通過證書機制來進行保護，但證書的生成、分發、撤銷等步驟并未涉及。
實際上，要實作安全地管理、分發證書需要遵循 PKI（Public Key Infrastructure）體系。該體系解決了證書生命周期相關的認證和管理問題。
需要注意，PKI 是建立在公私鑰基礎上實作安全可靠傳遞消息和身份确認的一個通用架構，并不代表某個特定的密碼學技術和流程。實作了 PKI 規範的平台可以安全可靠地管理網絡中使用者的密鑰和證書。目前包括多個具體實作和規範，知名的有 RSA 公司的 PKCS（Public Key Cryptography Standards）标準和 OpenSSL 等開源工具。
六、默克爾樹結構
默克爾樹（又叫哈希樹）是一種典型的二叉樹結構，由一個根節點、一組中間節點和一組葉節點組成，如下圖所示。默克爾樹最早由 Merkle Ralf 在 1980 年提出，曾廣泛用于檔案系統和 P2P 系統中。
其主要特點為：
- 最下面的葉節點包含存儲資料或其哈希值。
- 非葉子節點（包括中間節點和根節點）都是它的兩個孩子節點内容的哈希值。
進一步地，默克爾樹可以推廣到多叉樹的情形，此時非葉子節點的内容為它所有的孩子節點的内容的哈希值。
默克爾樹逐層記錄哈希值的特點，讓它具有了一些獨特的性質。例如，底層資料的任何變動，都會傳遞到其父節點，一層層沿着路徑一直到樹根。這意味樹根的值實際上代表了對底層所有資料的“數字摘要”。
默克爾樹的典型應用場景包括：
- 證明某個集合中存在或不存在某個元素
- 快速比較大量資料
- 快速定位修改
- 零知識證明
七、布隆過濾器
布隆過濾器是一種基于 Hash 的高效查找結構，能夠快速（常數時間内）回答“某個元素是否在一個集合内”的問題。該結構因為其高效性，被大量應用到網絡和安全領域，例如資訊檢索（BigTable 和 HBase）、垃圾郵件規則、注冊管理等。
1、基于Hash的快速查找
Hash 可以将任意内容映射到一個固定長度的字元串，而且不同内容映射到相同串的機率很低。是以，這就構成了一個很好的“内容 -> 索引”的生成關系。
如果給定一個内容和存儲數組，通過構造 Hash 函數，讓映射後的 Hash 值總不超過數組的大小，則可以實作快速的基于内容的查找。例如，内容 “hello world” 的 Hash 值如果是 “100”，則存放到數組的第 100 個單元上去。如果需要快速查找任意内容，如 “hello world” 字元串是否在存儲系統中，隻需要将其在常數時間内計算 Hash 值，并用 Hash 值檢視系統中對應元素即可。該系統“完美地”實作了常數時間内的查找。
然而，令人遺憾的是，當映射後的值限制在一定範圍（如總數組的大小）内時，會發現 Hash 沖突的機率會變高，而且範圍越小，沖突機率越大。很多時候，存儲系統的大小又不能無限擴充，這就造成算法效率的下降。為了提高空間使用率，後來人們基于 Hash 算法的思想設計出了布隆過濾器結構。
2、更高效的布隆過濾器
布隆過濾器采用了多個 Hash 函數來提高空間使用率。
對同一個給定輸入來說，多個 Hash 函數計算出多個位址，分别在位串的這些位址上标記為 1。進行查找時，進行同樣的計算過程，并檢視對應元素，如果都為 1，則說明較大機率是存在該輸入。
布隆過濾器相對單個 Hash 算法查找，大大提高了空間使用率，可以使用較少的空間來表示較大集合的存在關系。
實際上，無論是 Hash，還是布隆過濾器，基本思想是一緻的，都是基于内容的編址。Hash 函數存在沖突，布隆過濾器也存在沖突。這就造成了兩種方法都存在着誤報（False Positive）的情況，但絕對不會漏報（False Negative）。
布隆過濾器在應用中誤報率往往很低，例如，在使用 7 個不同 Hash 函數的情況下，記錄 100 萬個資料，采用 2 MB 大小的位串，整體的誤判率将低于 1%。而傳統的 Hash 查找算法的誤報率将接近 10%。
