密碼學(xué)和信息安全在如今的互聯(lián)網(wǎng)行業(yè)當(dāng)中非常重要，相關(guān)的理論知識和算法也在計算機(jī)系統(tǒng)的方方面面都被用到。雖然我們不一定會從事安全相關(guān)的工作，但對密碼學(xué)以及信息安全的基本知識和概念有所了解還是很有必要的。

日拱一卒，歡迎大家打卡一起學(xué)習(xí)。

這節(jié)課上我們會關(guān)注安全和密碼學(xué)相關(guān)的概念，這些概念和之前介紹的一些工具也有關(guān)聯(lián)。比如git當(dāng)中用到的hash函數(shù)或者是SSH當(dāng)中密鑰生成函數(shù)或者是對稱/非對稱密碼體系。

本節(jié)課不能作為計算機(jī)系統(tǒng)安全以及密碼學(xué)的替代。沒有從事訓(xùn)練，不要輕易從事安全相關(guān)的工作，也不要修改或創(chuàng)造加密相關(guān)算法。

這節(jié)課是對基礎(chǔ)密碼學(xué)概念的一個非正式的介紹。這節(jié)課上我們不會教你如何設(shè)計安全系統(tǒng)或者是加密協(xié)議，但我們希望能夠讓你對頻繁使用的程序以及協(xié)議有一個總體上的了解。

熵

熵用來衡量混亂程度，這是一個非常有用的概念，在很多領(lǐng)域當(dāng)中都有廣泛應(yīng)用。比如當(dāng)我們決定密碼強(qiáng)度的時候。

上圖是關(guān)于密碼強(qiáng)度的漫畫，漫畫當(dāng)中說"correcthorsebatterystaple"比"Tr0ub4dor&3"這樣的密碼更加安全，但是它是怎么定義安全程度的呢？

在計算機(jī)領(lǐng)域當(dāng)中，熵的計算單位是bit，當(dāng)均勻地從一系列值當(dāng)中隨機(jī)選擇時，它的熵等于log_2(可能性總數(shù))。拋一枚均勻的硬幣的熵是1 bit，一個六面骰子的熵大約是2.58 bit。

你可以認(rèn)為黑客們知道密碼的模型（最短長度、最長長度、包含的字符種類等），但不知道密碼是如何被隨機(jī)選擇的（比如通過骰子）。

多少bit的熵才足夠呢？這取決于你的威脅模型。對于在線窮舉的猜測，漫畫告訴我們大約40bit的熵就足夠了。而對于離線的枚舉，一般需要更強(qiáng)的密碼（比如80bit或更多）。

hash函數(shù)

密碼hash函數(shù)可以將任意大小的數(shù)據(jù)映射成一個固定大小的輸出，并且還有一些特殊的屬性。一個hash函數(shù)的定義大體如下：

hash(value:array)->vector(N對于該函數(shù)固定)

SHA1是一個很好的例子，它被用在Git當(dāng)中。它可以將任意長度的輸入轉(zhuǎn)化成160bit的輸出（可以被表示成長度40的十六進(jìn)制數(shù)）。我們可以使用sha1sum命令來使用SHA1函數(shù)：

$printf'hello'|sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$printf'hello'|sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$printf'Hello'|sha1sum
f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0

從更高維度來說，hash函數(shù)擁有不可逆性并且結(jié)果看上去非常隨機(jī)。想要從hash之后的結(jié)果倒推出輸入非常困難，幾乎不可能完成。一個hash函數(shù)擁有如下特性：

確定性：同樣的輸入得到同樣的輸出

不可逆性：對于hash(m) = h，很難通過h倒推得到m

很難目標(biāo)碰撞：對于輸入m_1很難找到另外一個輸入m_2使得它們hash之后的結(jié)果一樣

碰撞抵抗：很難找到一組m_1, m_2使得hash(m_1) = hash(m_2)（這比上一條要求更高）

注意：雖然SHA-1對于某些用途還在使用，但它已經(jīng)不再被認(rèn)為是一個很強(qiáng)的密碼hash函數(shù)了。你可以參考密碼hash函數(shù)的生命周期這篇文章(https://valerieaurora.org/hash.html)。另外，推薦特定的hash函數(shù)并非是本節(jié)課的重點(diǎn)，如果你想要使用它，最好先系統(tǒng)學(xué)習(xí)密碼學(xué)和信息安全。

應(yīng)用

git，用作內(nèi)容尋址存儲。hash函數(shù)是一個非常廣的概念（并非只有密碼hash函數(shù)），為什么git選擇了密碼hash函數(shù)呢？

文件信息摘要：我們通常在一些鏡像網(wǎng)站下載一些軟件，比如Linux ISO文件。對于非官方來源下載的軟件，我們希望它和官網(wǎng)一樣，沒有被篡改。所以通常官方渠道除了會提供下載文件之外，還會提供文件的hash值。我們可以對比下載的文件的hash值和官方提供的hash值是否一致來判斷文件是否被篡改過

承諾機(jī)制（commitment schemes）：假設(shè)你希望commit一個特定的值，但希望之后再同步它。比如玩猜數(shù)游戲，為了保證公平我需要先提供給你目標(biāo)數(shù)的hash值。這樣可以確保目標(biāo)值不被篡改，但又不會泄漏具體的結(jié)果。當(dāng)玩家做出猜測之后，將玩家猜測的結(jié)果hash之后和提供的hash值比對來驗(yàn)證玩家是否猜測正確

密鑰生成函數(shù)

密鑰生成函數(shù)（key derivation functions KDFs）是一個和密碼hash函數(shù)近似的概念，它用在許多場景，比如生成固定長度的輸出結(jié)果，用作一些密碼學(xué)算法當(dāng)中充當(dāng)密鑰。通常KDF生成函數(shù)比較緩慢，這是為了抵抗暴力破解攻擊。

運(yùn)行緩慢可以讓暴力窮舉枚舉的破解方法消耗更多的時間。

應(yīng)用

從密碼生成可以在其他加密算法中使用的密鑰，比如對稱加密算法（見下）。

存儲登錄憑證時不可直接存儲明文密碼。正確的方法是針對每個用戶隨機(jī)生成一個鹽 salt = random()， 并存儲鹽，以及密鑰生成函數(shù)對連接了鹽的明文密碼生成的哈希值KDF(password + salt)。在驗(yàn)證登錄請求時，使用輸入的密碼連接存儲的鹽重新計算哈希值KDF(input + salt)，并與存儲的哈希值對比。

對稱加密

關(guān)于密碼學(xué)，你可能首先想到的就是隱藏消息內(nèi)容。對稱加密通過以下幾個方法來完成這個功能：

keygen() -> key  (this function is randomized)

encrypt(plaintext: array, key) -> array  (the ciphertext)
decrypt(ciphertext: array, key) -> array  (the plaintext)

加密算法encrypt生成密文（ciphertext），在沒有key的情況下，我們很難將密文破譯。

解密函數(shù)要確保正確解密需要保證：decypt(entrypt(m, k), k) = m

AES是現(xiàn)在常用的一種對稱加密算法。

應(yīng)用

在一個不被信任的云服務(wù)器上存儲文件，可以和KDFs結(jié)合起來，這樣你就可以使用密碼加密文件。生成密鑰：key = KDF(passphrase)，接著存儲encrpy(file, key)

非對稱加密

非對稱的意思是會使用兩個功能不同的密鑰。一個是私鑰，不對外公開。一個是公鑰，可以被公開分享，并且不會影響安全性（不像對稱加密不能分享密鑰）。

非對稱加密提供以下幾個函數(shù)來實(shí)現(xiàn)加密/解密和簽名/驗(yàn)證(sign/verify)：

keygen() -> (public key, private key)  (this function is randomized)

encrypt(plaintext: array, public key) -> array  (the ciphertext)
decrypt(ciphertext: array, private key) -> array  (the plaintext)

sign(message: array, private key) -> array  (the signature)
verify(message: array, signature: array, public key) -> bool  (whether or not the signature is valid)

加密/解密函數(shù)和對稱加密當(dāng)中類似。密文可以使用公鑰進(jìn)行加密，得到密文（ciphertext），在沒有私鑰的情況下，很難得到原文（plaintext）。

解密函數(shù)保證decrypt(encrypt(m, public_key), private_key) = m

對稱加密和非對稱加密可以類比于機(jī)械鎖，對稱加密系統(tǒng)就像是門鎖：只要有鑰匙就可以進(jìn)行開鎖和上鎖。非對稱加密就像是一個可以取下的掛鎖，你可以把一個打開的掛鎖給別人（公鑰）上鎖，并保留鑰匙（私鑰）。其他人可以上鎖，但只有私鑰才能開鎖。

簽名/驗(yàn)證函數(shù)和書面簽名有相似的屬性——很難被偽造。不論消息是什么，在沒有私鑰的情況下，很難生產(chǎn)可以使得verify(message, signature, public_key)返回True的簽名。當(dāng)然，在私鑰和公鑰對應(yīng)時，verify會返回True，即verify(message, signature, public_key)=true

應(yīng)用

PGP電子郵件加密：用戶可以將所使用的公鑰在線發(fā)布，比如：PGP密鑰服務(wù)器或 Keybase。任何人都可以向他們發(fā)送加密的電子郵件。

聊天加密：像 Signal 和 Keybase 使用非對稱密鑰來建立私密聊天。

軟件簽名：Git 支持用戶對提交(commit)和標(biāo)簽(tag)進(jìn)行GPG簽名。任何人都可以使用軟件開發(fā)者公布的簽名公鑰驗(yàn)證下載的已簽名軟件。

密鑰分發(fā)

非對稱加密非常好用，但是也有一個巨大的挑戰(zhàn)，就是如何將公鑰分發(fā)/對應(yīng)現(xiàn)實(shí)世界的實(shí)體。關(guān)于這個問題有很多解決方案。信號（signal）使用一種簡單的方法：在第一次使用的時候信任它，同時支持用戶面對面、線下交換公鑰。

PGP的策略不同，它使用信任網(wǎng)絡(luò)。keybase主要通過另外一種叫做社交證明（social proof）和一些其他的設(shè)計。

每個模型都有它的特點(diǎn)，我們更傾向于keybase的模式。

案例分析

密鑰管理

每個人都有必要使用密碼管理器比如keepassxc，pass，1password等。密碼管理器可以讓我們不同的網(wǎng)站使用不同的、隨機(jī)且高熵的密碼，并且會將所有的密碼使用對稱加密的方式來存儲起來。

使用密碼管理器可以讓你不需要重復(fù)使用密碼，并且可以使用高熵密碼，最重要的是你只需要記住一個密碼就可以盡可能避免密碼泄漏、被撞庫等隱患。

兩步驗(yàn)證

兩步驗(yàn)證（2FA）要求用戶使用密碼以及另外一個身份驗(yàn)證器來消除密碼泄漏以及釣魚攻擊的風(fēng)險。

全盤加密

對筆記本電腦的硬盤進(jìn)行全盤加密是防止因設(shè)備丟失而信息泄露的簡單且有效方法。Linux的cryptsetup + LUKS， Windows的BitLocker，或者macOS的FileVault都使用一個由密碼保護(hù)的對稱密鑰來加密盤上的所有信息。

私密消息

使用singal或keybase可以保證端到端的通信安全。

但這需要使用聯(lián)系人的公鑰，要確保安全的話，需要在線下方式驗(yàn)證singal或者keybase的公鑰。

SSH

我們在之前的一堂課討論了SSH和SSH密鑰的使用。讓我們從密碼學(xué)的角度來分析一下它們。

當(dāng)你運(yùn)行ssh-keygen時，它會生成一個非對稱加密的密鑰對，public_key和private_key。這是隨機(jī)生成的，通常會使用操作系統(tǒng)提供的熵（從硬件事件上獲取）。公鑰可以被分發(fā)出去，私鑰需要加密保存在磁盤上。

ssh-keygen程序會提示用戶輸入一個密碼，并將它輸入密鑰生成函數(shù)來生成密鑰。這會被對稱加密算法進(jìn)行加密。

在使用的時候，當(dāng)服務(wù)器知道了客戶端的公鑰之后（存儲在.ssh/authorized_keys文件中），嘗試鏈接的客戶端可以使用非對稱加密簽名來驗(yàn)證客戶的身份。

簡單來說，服務(wù)器選擇一個隨機(jī)數(shù)發(fā)送給客戶。客戶使用私鑰進(jìn)行簽名之后再發(fā)送給服務(wù)器，服務(wù)器隨后使用存儲的公鑰來驗(yàn)證簽名。這種方式可以很方便地驗(yàn)證客戶是否持有對應(yīng)的私鑰，如果驗(yàn)證通過的話，那么允許客戶登錄訪問。

資源

去年的筆記，更多地聚焦在計算機(jī)使用者的安全和隱私上：https://missing.csail.mit.edu/2019/security/

這篇文章解答了對于不同的應(yīng)用應(yīng)該使用什么加密算法的問題：https://latacora.micro.blog/2018/04/03/cryptographic-right-answers.html

練習(xí)

熵

假設(shè)一個密碼是從四個小寫的單詞拼接組成，每個單詞都是從一個含有10萬單詞的字典中隨機(jī)選擇，且每個單詞選中的概率相同。一個符合這樣構(gòu)造的例子是correcthorsebatterystaple。這個密碼有多少比特的熵？

假設(shè)另一個密碼是用八個隨機(jī)的大小寫字母或數(shù)字組成。一個符合這樣構(gòu)造的例子是rg8Ql34g。這個密碼又有多少比特的熵？

哪一個密碼更強(qiáng)？

假設(shè)一個攻擊者每秒可以嘗試1萬個密碼，這個攻擊者需要多久可以分別破解上述兩個密碼？

密碼hash函數(shù)從Debian鏡像站下載一個光盤映像（比如這個來自阿根廷鏡像站的映像：http://debian.xfree.com.ar/debian-cd/10.2.0/amd64/iso-cd/debian-10.2.0-amd64-netinst.iso）。使用sha256sum命令對比下載映像的哈希值和官方Debian站公布的哈希值。如果你下載了上面的映像，官方公布的哈希值可以參考這個文件：https://cdimage.debian.org/debian-cd/current/amd64/iso-cd/SHA256SUMS。

對稱加密使用 OpenSSL的AES模式加密一個文件: openssl aes-256-cbc -salt -in {源文件名} -out {加密文件名}。使用cat或者h(yuǎn)exdump對比源文件和加密的文件，再用 openssl aes-256-cbc -d -in {加密文件名} -out {解密文件名} 命令解密剛剛加密的文件。最后使用cmp命令確認(rèn)源文件和解密后的文件內(nèi)容相同。

非對稱加密

在你自己的電腦上使用更安全的ED25519算法生成一組SSH 密鑰對。為了確保私鑰不使用時的安全，一定使用密碼加密你的私鑰。

配置GPG：https://www.digitalocean.com/community/tutorials/how-to-use-gpg-to-encrypt-and-sign-messages。

給Anish發(fā)送一封加密的電子郵件（Anish的公鑰：https://keybase.io/anish）。

使用git commit -S命令簽名一個Git提交，并使用git show --show-signature命令驗(yàn)證這個提交的簽名。或者，使用git tag -s命令簽名一個Git標(biāo)簽，并使用git tag -v命令驗(yàn)證標(biāo)簽的簽名。