日拱一卒，麻省理工教你信息安全和密码学

密码学和信息安全在如今的互联网行业当中非常重要，相关的理论知识和算法也在计算机系统的方方面面都被用到。虽然我们不一定会从事安全相关的工作，但对密码学以及信息安全的基本知识和概念有所了解还是很有必要的。

日拱一卒，欢迎大家打卡一起学习。

这节课上我们会关注安全和密码学相关的概念，这些概念和之前介绍的一些工具也有关联。比如git当中用到的hash函数或者是SSH当中密钥生成函数或者是对称/非对称密码体系。

本节课不能作为计算机系统安全以及密码学的替代。没有从事训练，不要轻易从事安全相关的工作，也不要修改或创造加密相关算法。

这节课是对基础密码学概念的一个非正式的介绍。这节课上我们不会教你如何设计安全系统或者是加密协议，但我们希望能够让你对频繁使用的程序以及协议有一个总体上的了解。

熵

熵用来衡量混乱程度，这是一个非常有用的概念，在很多领域当中都有广泛应用。比如当我们决定密码强度的时候。

上图是关于密码强度的漫画，漫画当中说"correcthorsebatterystaple"比"Tr0ub4dor&3"这样的密码更加安全，但是它是怎么定义安全程度的呢？

在计算机领域当中，熵的计算单位是bit，当均匀地从一系列值当中随机选择时，它的熵等于log_2(可能性总数)。抛一枚均匀的硬币的熵是1 bit，一个六面骰子的熵大约是2.58 bit。

你可以认为黑客们知道密码的模型（最短长度、最长长度、包含的字符种类等），但不知道密码是如何被随机选择的（比如通过骰子）。

多少bit的熵才足够呢？这取决于你的威胁模型。对于在线穷举的猜测，漫画告诉我们大约40bit的熵就足够了。而对于离线的枚举，一般需要更强的密码（比如80bit或更多）。

hash函数

密码hash函数可以将任意大小的数据映射成一个固定大小的输出，并且还有一些特殊的属性。一个hash函数的定义大体如下：

hash(value: array<byte>) -> vector<byte, N>  (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<byte>, key) -> array<byte>  (the ciphertext)
decrypt(ciphertext: array<byte>, key) -> array<byte>  (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)