文|李偉志

hash 算法

定義

hash （哈鲜χ＃或散列）算法是信息技術(shù)領(lǐng)域非郴房基礎(chǔ)也非常重要的技術(shù)。它能任意長度的二進制值（明文）映射為較短的固定長度的二進制值（hash 值）宝冕，并且不同的明文很難映射為相同的 hash 值张遭。

例如計算一段話“hello blockchain world, this is yeasy@github”的 md5 hash 值為 89242549883a2ef85dc81b90fb606046。

$ echo “hello blockchain world, this is yeasy@github”|md5

89242549883a2ef85dc81b90fb606046

這意味著我們只要對某文件進行 md5 hash 計算猬仁，得到結(jié)果為 89242549883a2ef85dc81b90fb606046帝璧，這就說明文件內(nèi)容極大概率上就是 “hello blockchain world, 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ā)生碰撞扶歪，則稱算法具有“抗強碰撞性”。

流行的算法

目前流行的 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 的改進版本画切。它對輸入仍以 512 位分組竣稽，其輸出是 128 位。MD5 比 MD4 復雜，并且計算速度要慢一點毫别，但更安全一些娃弓。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 進行 hash 的速度也越快庐完。

也有一些 hash 算法不是算力敏感的，例如 scrypt徘熔，需要大量的內(nèi)存資源门躯，節(jié)點不能通過簡單的增加更多 CPU 來獲得 hash 性能的提升。

數(shù)字摘要

顧名思義酷师，數(shù)字摘要是對數(shù)字內(nèi)容進行 hash 運算讶凉，獲取唯一的摘要值來指代原始數(shù)字內(nèi)容。

數(shù)字摘要是解決確保內(nèi)容沒被篡改過的問題（利用 hash 函數(shù)的抗碰撞性特點）窒升。

數(shù)字摘要是 hash 算法最重要的一個用途。

在網(wǎng)絡(luò)上下載軟件或文件時慕匠，往往同時會提供一個數(shù)字摘要值饱须，用戶下載下來原始文件可以自行進行計算，并同提供的摘要值進行比對台谊，以確保內(nèi)容沒有被修改過蓉媳。

加密算法

公鑰私鑰體系

現(xiàn)代加密算法的典型組件包括：加解密算法、公鑰锅铅、私鑰酪呻。

加密過程中，通過加密算法和公鑰盐须，對明文進行加密玩荠，獲得密文。

解密過程中，通過解密算法和私鑰阶冈，對密文進行解密闷尿，獲得明文。

根據(jù)公鑰和私鑰是否相同女坑，算法可以分為對稱加密和非對稱加密填具。兩種模式適用于不同的需求，恰好形成互補匆骗，很多時候也可以組合使用劳景，形成組合機制。

對稱加密

顧名思義碉就，公鑰和私鑰是相同的盟广。

優(yōu)點是加解密速度快，空間占用小铝噩，保密強度高衡蚂。

缺點是參與多方都需要持有密鑰，一旦有人泄露則安全性被破壞骏庸；另外如何其它分發(fā)密鑰也是個問題毛甲。

代表算法包括 DES、3DES具被、AES玻募、IDEA 等。

適用于大量數(shù)據(jù)的加解密一姿，不能用于簽名場景七咧。

非對稱加密

顧名思義茫负，公鑰和私鑰是不同的剂娄。

公鑰一般是公開的，人人可獲取的六荒，私鑰一般是個人自己持有蛉顽，不能被他人獲取蝗砾。

優(yōu)點是公私鑰分開，容易管理携冤，并且容易完成密鑰分發(fā)悼粮。

缺點是加解密速度慢。

代表算法包括：RSA曾棕、ElGamal扣猫、橢圓曲線系列算法。

一般適用于簽名場景或密鑰協(xié)商翘地，不適于大量數(shù)據(jù)的加解密申尤。

組合機制

即先用計算復雜度高的非對稱加密協(xié)商一個臨時的對稱加密密鑰（會話密鑰）癌幕，然后雙方再通過對稱加密對傳遞的大量數(shù)據(jù)進行加解密處理。

數(shù)字簽名和數(shù)字證書

數(shù)字簽名

類似在紙質(zhì)合同上簽名確認合同內(nèi)容瀑凝，數(shù)字簽名用于證實某數(shù)字內(nèi)容的完整性和來源序芦。

A 發(fā)給 B 一個文件。A 先對文件進行摘要粤咪，然后用自己的私鑰進行加密谚中，將文件和加密串都發(fā)給 B。B 收到后文件和加密串寥枝，用 A 的公鑰來解密加密串宪塔，得到原始的數(shù)字摘要，跟對文件進行摘要后的結(jié)果進行比對囊拜。如果一致某筐，說明該文件確實是 A 發(fā)過來的，并且文件內(nèi)容沒有被修改過冠跷。

多重簽名

n 個持有人中南誊，收集到至少 m 個（

n≥m≥1n≥m≥1

）的簽名，即認為合法蜜托，這種簽名被稱為多重簽名抄囚。

其中，n 是提供的公鑰個數(shù)橄务，m 是需要匹配公鑰的最少的簽名個數(shù)幔托，

群簽名

環(huán)簽名

環(huán)簽名由 Rivest,shamir 和 Tauman 三位密碼學家在 2001 年首次提出。環(huán)簽名屬于一種簡化的群簽名蜂挪。

簽名者首先選定一個臨時的簽名者集合,集合中包括簽名者自身重挑。然后簽名者利用自己的私鑰和簽名集合中其他人的公鑰就可以獨立的產(chǎn)生簽名,而無需他人的幫助。簽名者集合中的其他成員可能并不知道自己被包含在其中棠涮。

數(shù)字證書

數(shù)字證書用來證明某個公鑰是誰的谬哀。

對于數(shù)字簽名應(yīng)用來說，很重要的一點就是公鑰的分發(fā)严肪。一旦公鑰被人替換史煎，則整個安全體系將被破壞掉。

怎么確保一個公鑰確實是某個人的原始公鑰诬垂？

這就需要數(shù)字證書機制劲室。

顧名思義伦仍，數(shù)字證書就是像一個證書一樣结窘，證明信息和合法性。由證書認證機構(gòu)（Certification Authority充蓝，CA）來簽發(fā)隧枫。

數(shù)字證書內(nèi)容可能包括版本喉磁、序列號、簽名算法類型官脓、簽發(fā)者信息协怒、有效期、被簽發(fā)人卑笨、簽發(fā)的公開密鑰孕暇、CA 數(shù)字簽名、其它信息等等赤兴。

其中妖滔，最重要的包括 簽發(fā)的公開密鑰、CA 數(shù)字簽名 兩個信息桶良。因此座舍，只要通過這個證書就能證明某個公鑰是合法的，因為帶有 CA 的數(shù)字簽名陨帆。

更進一步地曲秉，怎么證明 CA 的簽名合法不合法呢？

類似的疲牵，CA 的數(shù)字簽名合法不合法也是通過 CA 的證書來證明的承二。主流操作系統(tǒng)和瀏覽器里面會提前預置一些 CA 的證書（承認這些是合法的證書），然后所有基于他們認證的簽名都會自然被認為合法瑰步。

后面章節(jié)將介紹的 PKI 體系提供了一套完整的證書管理的框架矢洲。

PKI 體系

PKI （Public Key Infrastructure）體系不代表某一種技術(shù)，而是綜合多種密碼學手段來實現(xiàn)安全可靠傳遞消息和身份確認的一個框架和規(guī)范缩焦。

一般情況下读虏，包括如下組件：

CA（Certification Authority）：負責證書的頒發(fā)和作廢，接收來自 RA 的請求袁滥；

RA（Registration Authority）：對用戶身份進行驗證盖桥，校驗數(shù)據(jù)合法性，負責登記题翻，審核過了就發(fā)給 CA揩徊；

證書數(shù)據(jù)庫：存放證書，一般采用 LDAP 目錄服務(wù)嵌赠，標準格式采用 X.500 系列塑荒。

CA 是最核心的組件，主要完成對公鑰的管理姜挺。從之前章節(jié)內(nèi)容中齿税，我們介紹過，密鑰有兩種類型：用于簽名和用于加解密炊豪，對應(yīng)稱為 簽名密鑰對 和 加密密鑰對凌箕。

用戶基于 PKI 體系要申請一個證書拧篮，一般可以由 CA 來生成證書和私鑰，也可以自己生成公鑰和私鑰牵舱，然后由 CA 來對公鑰進行簽發(fā)串绩。

默克爾樹（又叫哈希樹）是一種二叉樹，由一個根節(jié)點芜壁、一組中間節(jié)點和一組葉節(jié)點組成礁凡。最下面的葉節(jié)點包含存儲數(shù)據(jù)或其哈希值，每個中間節(jié)點是它的兩個孩子節(jié)點內(nèi)容的哈希值慧妄，根節(jié)點也是由它的兩個子節(jié)點內(nèi)容的哈希值組成把篓。

進一步的，默克爾樹可以推廣到多叉樹的情形腰涧。

默克爾樹的特點是韧掩，底層數(shù)據(jù)的任何變動，都會傳遞到其父親節(jié)點窖铡，一直到樹根疗锐。

默克爾樹的典型應(yīng)用場景包括：

快速比較大量數(shù)據(jù)：當兩個默克爾樹根相同時，則意味著所代表的數(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）是一種特殊的加密方法，允許對密文進行處理得到仍然是加密的結(jié)果今穿，即對密文直接進行處理缤灵，跟對明文進行處理再加密，得到的結(jié)果相同荣赶。從代數(shù)的角度講凤价，即同態(tài)性。

如果定義一個運算符

△△

拔创，對加密算法 E 和 解密算法 D利诺，滿足：

$$ E(X\triangle{}Y) = E(X)\triangle{} E(Y)

$$ 則意味著對于該運算滿足同態(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)加密在云時代的意義十分重大唯竹。目前，從安全角度講苦丁，用戶還不敢將敏感信息直接放到第三方云上進行處理浸颓。如果有了比較實用的同態(tài)加密技術(shù)，則大家就可以放心的使用各種云服務(wù)了旺拉。

遺憾的是产上，目前已知的同態(tài)加密技術(shù)需要消耗大量的計算時間，還遠達不到實用的水平蛾狗。

函數(shù)加密

與同態(tài)加密相關(guān)的一個問題是函數(shù)加密蒂秘。

同態(tài)加密保護的是數(shù)據(jù)本身，而函數(shù)加密顧名思義保護的是處理函數(shù)本身淘太，即讓第三方看不到處理過程的前提下姻僧，對數(shù)據(jù)進行處理。

該問題已被證明是不存在對多個通用函數(shù)的任意多 key 的方案蒲牧，目前僅能做到對某個特定函數(shù)的一個 key 的方案撇贺。

零知識證明（zero knowledge validation）

證明者在不向驗證者提供任何有用的信息的前提下，使驗證者相信某個論斷是正確的冰抢。

例如松嘶，A 像 B 證明自己有一個物品，但 B 無法拿到這個物品挎扰，無法用 A 的證明去向別人證明自己也擁有這個物品翠订。

作者簡介：李偉志巢音，職場作家、職業(yè)生涯咨詢師尽超。