密碼學和信息安全在如今的互聯網行業當中非常重要，相關的理論知識和算法也在計算機系統的方方面面都被用到。雖然我們不一定會從事安全相關的工作，但對密碼學以及信息安全的基本知識和概念有所了解還是很有必要的。

日拱一卒，歡迎大家打卡一起學習。

這節課上我們會關注安全和密碼學相關的概念，這些概念和之前介紹的一些工具也有關聯。比如git當中用到的hash函數或者是SSH當中密鑰生成函數或者是對稱/非對稱密碼體系。

本節課不能作為計算機系統安全以及密碼學的替代。沒有從事訓練，不要輕易從事安全相關的工作，也不要修改或創造加密相關算法。

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

熵

熵用來衡量混亂程度，這是一個非常有用的概念，在很多領域當中都有廣泛應用。比如當我們決定密碼強度的時候。

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

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

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

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

hash函數

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

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

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

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

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

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

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

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

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

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

應用

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

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

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

密鑰生成函數

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

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

應用

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

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

對稱加密

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

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

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

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

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

AES是現在常用的一種對稱加密算法。

應用

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

非對稱加密

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

非對稱加密提供以下幾個函數來實現加密/解密和簽名/驗證(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)

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

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

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

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

應用

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

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

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

密鑰分發

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

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

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

案例分析

密鑰管理

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

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

兩步驗證

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

全盤加密

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

私密消息

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

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

SSH

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

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

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

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

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

資源

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

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

練習

熵

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

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

哪一個密碼更強？

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

密碼hash函數從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或者hexdump對比源文件和加密的文件，再用 openssl aes-256-cbc -d -in {加密文件名} -out {解密文件名} 命令解密剛剛加密的文件。最后使用cmp命令確認源文件和解密后的文件內容相同。

非對稱加密

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

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

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

使用git commit -S命令簽名一個Git提交，并使用git show --show-signature命令驗證這個提交的簽名。或者，使用git tag -s命令簽名一個Git標簽，并使用git tag -v命令驗證標簽的簽名。