密碼學(xué)在信息技術(shù)領(lǐng)域的重要地位無需多言，如果沒有現(xiàn)代密碼學(xué)的研究成果，人類社會根本無法進(jìn)入信息時代。
密碼學(xué)領(lǐng)域十分繁雜，本文將介紹密碼學(xué)跟區(qū)塊鏈相關(guān)的基礎(chǔ)知識。
hash 算法
定義
hash （哈?；蛏⒘校┧惴ㄊ切畔⒓夹g(shù)領(lǐng)域非常基礎(chǔ)也非常重要的技術(shù)。它能任意長度的二進(jìn)制值（明文）映射為較短的固定長度的二進(jìn)制值（hash 值），并且不同的明文很難映射為相同的 hash 值。
例如計算一段話“hello blockchain world, this is yeasy@github”的 md5 hash 值為89242549883a2ef85dc81b90fb606046 。
$ echo "hello blockchain world, this is yeasy@github"|md5
89242549883a2ef85dc81b90fb606046
這意味著我們只要對某文件進(jìn)行 md5 hash 計算，得到結(jié)果為
89242549883a2ef85dc81b90fb606046 ，這就說明文件內(nèi)容極大概率上就是 “hello blockchainworld, this is yeasy@github”?？梢?，hash 的核心思想十分類似于基于內(nèi)容的編址或命名。
注：md5 是一個經(jīng)典的 hash 算法，其和 SHA-1 算法都已被 證明 安全性不足應(yīng)用于商業(yè)場景。
一個優(yōu)秀的 hash 算法，將能實現(xiàn)：
正向快速：給定明文和
hash算法，在有限時間和有限資源內(nèi)能計算出 hash 值。逆向困難：給定（若干）
hash值，在有限時間內(nèi)很難（基本不可能）逆推出明文。輸入敏感：原始輸入信息修改一點信息，產(chǎn)生的
hash值看起來應(yīng)該都有很大不同。沖突避免：很難找到兩段內(nèi)容不同的明文，使得它們的
hash值一致（發(fā)生沖突）。
沖突避免有時候又被稱為“抗碰撞性”。如果給定一個明文前提下，無法找到碰撞的另一個明文，稱為“抗弱碰撞性”；如果無法找到任意兩個明文，發(fā)生碰撞，則稱算法具有“抗強(qiáng)碰撞性”。
流行的算法
目前流行的 hash 算法包括 MD5（已被證明不夠安全）和 SHA-1，兩者均以 MD4 為基礎(chǔ)設(shè)計的。
MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計的，MD 是 Message Digest的縮寫。其輸出為 128 位。MD4 并不足夠安全。
MD5（RFC 1321）是 Rivest 于1991年對 MD4 的改進(jìn)版本。它對輸入仍以 512 位分組，其輸出是 128 位。MD5 比 MD4 復(fù)雜，并且計算速度要慢一點，但更安全一些。MD5 并不足夠安全。
SHA1 （Secure Hash Algorithm）是由 NIST NSA 設(shè)計，它的輸出為長度 160 位的 hash值，因此抗窮舉性更好。SHA-1 設(shè)計時基于和 MD4 相同原理,并且模仿了該算法。
為了提高安全性，NIST NSA 還設(shè)計出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（統(tǒng)稱為 SHA-2），跟 SHA-1 算法原理類似。
性能
一般的，hash 算法都是算力敏感型，意味著計算資源是瓶頸，主頻越高的 CPU 進(jìn)行 hash 的速度也越快。
也有一些 hash 算法不是算力敏感的，例如 scrypt，需要大量的內(nèi)存資源，節(jié)點不能通過簡單的增加更多 CPU 來獲得 hash 性能的提升。
數(shù)字摘要
顧名思義，數(shù)字摘要是對數(shù)字內(nèi)容進(jìn)行 hash 運(yùn)算，獲取唯一的摘要值來指代原始數(shù)字內(nèi)容。
數(shù)字摘要是解決確保內(nèi)容沒被篡改過的問題（利用 hash 函數(shù)的抗碰撞性特點）。
數(shù)字摘要是 hash 算法最重要的一個用途。
在網(wǎng)絡(luò)上下載軟件或文件時，往往同時會提供一個數(shù)字摘要值，用戶下載下來原始文件可以自行進(jìn)行計算，并同提供的摘要值進(jìn)行比對，以確保內(nèi)容沒有被修改過。
加密算法
公鑰私鑰體系
現(xiàn)代加密算法的典型組件包括：加解密算法、公鑰、私鑰。
加密過程中，通過加密算法和公鑰，對明文進(jìn)行加密，獲得密文。
解密過程中，通過解密算法和私鑰，對密文進(jìn)行解密，獲得明文。
根據(jù)公鑰和私鑰是否相同，算法可以分為對稱加密和非對稱加密。兩種模式適用于不同的需求，恰好形成互補(bǔ)，很多時候也可以組合使用，形成組合機(jī)制。
對稱加密
顧名思義，公鑰和私鑰是相同的。
優(yōu)點是加解密速度快，空間占用小，保密強(qiáng)度高。
缺點是參與多方都需要持有密鑰，一旦有人泄露則安全性被破壞；另外如何其它分發(fā)密鑰也是個問題。
代表算法包括 DES、3DES、AES、IDEA 等。
適用于大量數(shù)據(jù)的加解密，不能用于簽名場景。
非對稱加密
顧名思義，公鑰和私鑰是不同的。
公鑰一般是公開的，人人可獲取的，私鑰一般是個人自己持有，不能被他人獲取。
優(yōu)點是公私鑰分開，容易管理，并且容易完成密鑰分發(fā)。
缺點是加解密速度慢。
代表算法包括：RSA、ElGamal、橢圓曲線系列算法。
一般適用于簽名場景或密鑰協(xié)商，不適于大量數(shù)據(jù)的加解密。
組合機(jī)制
即先用計算復(fù)雜度高的非對稱加密協(xié)商一個臨時的對稱加密密鑰（會話密鑰），然后雙方再通過對稱加密對傳遞的大量數(shù)據(jù)進(jìn)行加解密處理。
數(shù)字簽名和數(shù)字證書
數(shù)字簽名
類似在紙質(zhì)合同上簽名確認(rèn)合同內(nèi)容，數(shù)字簽名用于證實某數(shù)字內(nèi)容的完整性和來源。
A 發(fā)給 B 一個文件。A 先對文件進(jìn)行摘要，然后用自己的私鑰進(jìn)行加密，將文件和加密串都發(fā)給 B。B 收到后文件和加密串，用 A 的公鑰來解密加密串，得到原始的數(shù)字摘要，跟對文件進(jìn)行摘要后的結(jié)果進(jìn)行比對。如果一致，說明該文件確實是 A 發(fā)過來的，并且文件內(nèi)容沒有被修改過。
多重簽名
n 個持有人中，收集到至少 m 個（n ）的簽名，即認(rèn)為合法，這種簽名被稱為多重簽名。
其中，n 是提供的公鑰個數(shù)，m 是需要匹配公鑰的最少的簽名個數(shù)。
群簽名
在一個群簽名方案中，一個群體中的任意一個成員可以以匿名的方式代表整個群體對消息進(jìn)行簽名。與其他數(shù)字簽名一樣，群簽名是可以公開驗證的，且可以只用單個群公鑰來驗證。
環(huán)簽名
環(huán)簽名由 Rivest,shamir 和 Tauman 三位密碼學(xué)家在 2001 年首次提出。環(huán)簽名屬于一種簡化的群簽名。
簽名者首先選定一個臨時的簽名者集合,集合中包括簽名者自身。然后簽名者利用自己的私鑰和簽名集合中其他人的公鑰就可以獨(dú)立的產(chǎn)生簽名,而無需他人的幫助。簽名者集合中的其他成員可能并不知道自己被包含在其中。
數(shù)字證書
數(shù)字證書用來證明某個公鑰是誰的。
對于數(shù)字簽名應(yīng)用來說，很重要的一點就是公鑰的分發(fā)。一旦公鑰被人替換，則整個安全體系將被破壞掉。
怎么確保一個公鑰確實是某個人的原始公鑰？
這就需要數(shù)字證書機(jī)制。
顧名思義，數(shù)字證書就是像一個證書一樣，證明信息和合法性。由證書認(rèn)證機(jī)構(gòu)（Certification Authority，CA）來簽發(fā)。
數(shù)字證書內(nèi)容可能包括版本、序列號、簽名算法類型、簽發(fā)者信息、有效期、被簽發(fā)人、簽發(fā)的公開密鑰、CA 數(shù)字簽名、其它信息等等。
其中，最重要的包括 簽發(fā)的公開密鑰 、 CA 數(shù)字簽名 兩個信息。因此，只要通過這個證書就能證明某個公鑰是合法的，因為帶有 CA 的數(shù)字簽名。
更進(jìn)一步地，怎么證明 CA 的簽名合法不合法呢？
類似的，CA 的數(shù)字簽名合法不合法也是通過 CA 的證書來證明的。主流操作系統(tǒng)和瀏覽器里面會提前預(yù)置一些 CA 的證書（承認(rèn)這些是合法的證書），然后所有基于他們認(rèn)證的簽名都會自然被認(rèn)為合法。
后面介紹的 PKI 體系提供了一套完整的證書管理的框架。
PKI 體系
PKI （Public Key Infrastructure）體系不代表某一種技術(shù)，而是綜合多種密碼學(xué)手段來實現(xiàn)安全可靠傳遞消息和身份確認(rèn)的一個框架和規(guī)范。
一般情況下，包括如下組件：
CA（Certification Authority）：負(fù)責(zé)證書的頒發(fā)和作廢，接收來自 RA 的請求；RA（Registration Authority）：對用戶身份進(jìn)行驗證，校驗數(shù)據(jù)合法性，負(fù)責(zé)登記，審核過了就發(fā)給 CA；證書數(shù)據(jù)庫：存放證書，一般采用 LDAP 目錄服務(wù)，標(biāo)準(zhǔn)格式采用 X.500 系列。
CA 是最核心的組件，主要完成對公鑰的管理。從之前章節(jié)內(nèi)容中，我們介紹過，密鑰有兩種類型：用于簽名和用于加解密，對應(yīng)稱為 簽名密鑰對 和 加密密鑰對 。
用戶基于 PKI 體系要申請一個證書，一般可以由 CA 來生成證書和私鑰，也可以自己生成公鑰和私鑰，然后由 CA 來對公鑰進(jìn)行簽發(fā)。
Merkle 樹
默克爾樹（又叫哈希樹）是一種二叉樹，由一個根節(jié)點、一組中間節(jié)點和一組葉節(jié)點組成。
最下面的葉節(jié)點包含存儲數(shù)據(jù)或其哈希值，每個中間節(jié)點是它的兩個孩子節(jié)點內(nèi)容的哈希值，根節(jié)點也是由它的兩個子節(jié)點內(nèi)容的哈希值組成。
進(jìn)一步的，默克爾樹可以推廣到多叉樹的情形。
默克爾樹的特點是，底層數(shù)據(jù)的任何變動，都會傳遞到其父親節(jié)點，一直到樹根。
默克爾樹的典型應(yīng)用場景包括：
快速比較大量數(shù)據(jù)：當(dāng)兩個默克爾樹根相同時，則意味著所代表的數(shù)據(jù)必然相同。
快速定位修改：例如上例中，如果 D1 中數(shù)據(jù)被修改，會影響到 N1，N4 和 Root。因此，沿著 Root --> N4 --> N1，可以快速定位到發(fā)生改變的 D1；
零知識證明：例如如何證明某個數(shù)據(jù)（D0……D3）中包括給定內(nèi)容 D0，很簡單，構(gòu)造一個默克爾樹，公布 N0，N1，N4，Root，D0 擁有者可以很容易檢測 D0 存在，但不知道其它內(nèi)容。
同態(tài)加密
定義
同態(tài)加密（Homomorphic Encryption）是一種特殊的加密方法，允許對密文進(jìn)行處理得到仍然是加密的結(jié)果，即對密文直接進(jìn)行處理，跟對明文進(jìn)行處理再加密，得到的結(jié)果相同。從代數(shù)的角度講，即同態(tài)性。
如果定義一個運(yùn)算符 $$\triangle{}$$，對加密算法 E 和 解密算法 D，滿足：
$$ E(X\triangle{}Y) = E(X)\triangle{} E(Y) $$ 則意味著對于該運(yùn)算滿足同態(tài)性。
同態(tài)性在代數(shù)上包括：加法同態(tài)、乘法同態(tài)、減法同態(tài)和除法同態(tài)。同時滿足加法同態(tài)和乘法同態(tài)，則意味著是 代數(shù)同態(tài) ，即 全同態(tài) 。同時滿足四種同態(tài)性，則被稱為 算數(shù)同態(tài) 。
歷史
同態(tài)加密的問題最早是由 Ron Rivest、Leonard Adleman 和 Michael L. Dertouzos 在 1978年提出，但 第一個“全同態(tài)”的算法 到 2009 年才被克雷格·金特里（Craig Gentry）證明。
僅滿足加法同態(tài)的算法包括 Paillier 和 Benaloh 算法；僅滿足乘法同態(tài)的算法包括 RSA 和ElGamal 算法。
同態(tài)加密在云時代的意義十分重大。目前，從安全角度講，用戶還不敢將敏感信息直接放到第三方云上進(jìn)行處理。如果有了比較實用的同態(tài)加密技術(shù)，則大家就可以放心的使用各種云
服務(wù)了。
遺憾的是，目前已知的同態(tài)加密技術(shù)需要消耗大量的計算時間，還遠(yuǎn)達(dá)不到實用的水平。
函數(shù)加密
與同態(tài)加密相關(guān)的一個問題是函數(shù)加密。
同態(tài)加密保護(hù)的是數(shù)據(jù)本身，而函數(shù)加密顧名思義保護(hù)的是處理函數(shù)本身，即讓第三方看不到處理過程的前提下，對數(shù)據(jù)進(jìn)行處理。
該問題已被證明是不存在對多個通用函數(shù)的任意多 key 的方案，目前僅能做到對某個特定函數(shù)的一個 key 的方案。
其它問題
零知識證明（zero knowledge validation）
證明者在不向驗證者提供任何有用的信息的前提下，使驗證者相信某個論斷是正確的。
例如，A 向 B 證明自己有一個物品，但 B 無法拿到這個物品，無法用 A 的證明去向別人證明自己也擁有這個物品。
原文：區(qū)塊鏈技術(shù)指南
作者：yeasy
