Security and Cryptography¶

约 2287 个字 9 行代码预计阅读时间 8 分钟

本次lecture主要介绍了一些安全方面的基础知识，进行一些简单但是实用的说明。

熵(ENTROPY)¶

熵是一个系统的不确定性的度量。在密码学中，熵是一个密码系统的随机性的度量。熵越高，密码系统越难破解。

熵的单位是比特(bit)。其大小等于\(\log_2 (n)\),其中\(n\)是密码系统的可能状态数。

比如说投掷一个骰子，那么熵就是\(\log_2 6 = 2.58\) bit。

还有一个信息熵的概念，是一个信源的平均信息量。信息熵越高，信息量越大。

定义为\(H(X) = -\sum_{i=1}^n p(x_i) \log_2 p(x_i)\)，其中\(p(x_i)\)是信源输出\(x_i\)的概率。亦即\(\log_2 p_i\)的期望。

散列函数¶

密码散列函数(Cryptographic Hash Function)是一种将任意长度的输入数据映射为固定长度的输出数据的函数。

其大致的规范如下

hash(value: array<byte>) -> vector<byte, N>  (N对于该函数固定)

SHA-1 是 Git 中使用的一种散列函数，它可以将任意大小的输入映射为一个 160 比特（可被 40 位十六进制数表示）的输出。可以使用sha1sum命令来计算文件的sha1值。

例如：

$ printf "hello" | sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d  -

如果使用echo "hello",会发现结果居然不一样，这是因为echo会在输出后加上一个换行符。

抽象地讲，散列函数可以被认为是一个不可逆，而且看上去随机的函数，其具有以下的特点

确定性：对于不变的输入永远有相同的输出
不可逆性：\(hash(i)=o\),几乎不可能只通过\(o\)来找到\(i\)
目标碰撞抵抗性：对于给定的输入，找到一个不同的输入，使得他们的hash值相同，是困难的
碰撞抵抗性：即使不要求输入给定，任意寻找两个不同的输入，使得他们的hash值相同，也是困难的（这一性质强于目标碰撞抵抗性）

应用¶

Git中的内容寻址存储
文件的信息摘要：可以用来验证文件的正确性，例如下载镜像文件时，可以通过计算这个文件的hash值，与官网上的hash值进行比对，来验证文件的完整性以及正确性。
承诺机制：假设我希望承诺一个值，但之后再透露它—— 比如在没有一个可信的、双方可见的硬币的情况下在我的脑海中公平的“扔一次硬币”。我可以选择一个值 \(r = random()\),并和你分享它的哈希值 \(h = sha256(r)\)。这时你可以开始猜硬币的正反：我们一致同意偶数 \(r\) 代表正面，奇数 \(r\) 代表反面。你猜完了以后，我告诉你值 \(r\) 的内容，得出胜负。同时你可以使用 \(sha256(r)\) 来检查我分享的哈希值 \(h\) 以确认我没有作弊。否则我总是可以随意更改\(r\)的值，来达到作弊的目的。

密钥生成函数¶

密钥生成函数(Key Derivation Function)是一种将输入映射为密钥的函数.被应用于包括生成固定长度，可以使用在其它密码算法中的密钥等方面。为了对抗穷举法goon估计，密钥生成函数通常会比较慢

存贮密码时，不应该存储明文密码，而是存储其hash值。这样即使数据库泄露，也不会泄露用户的密码。但是攻击者们已经拥有了一个庞大的数据库来对应hash值和明文密码（彩虹表），而大多数用户在不同的网站上使用相同的密码，所以攻击者可以通过这个数据库来破解用户的密码。

为了对抗这个问题，可以使用salt。salt是一个随机的字符串，它被添加到密码中，然后再进行hash。这样即使用户使用相同的密码，由于salt不同，hash值也会不同。这样即使攻击者拥有了一个庞大的数据库，也无法通过hash值来破解密码。即salt=random();KDF(password+salt)。在验证登录请求时，使用输入的密码连接存储的盐重新计算哈希值 KDF(input + salt)，并与存储的哈希值对比。

对称加密¶

对称加密是一种加密方式，加密和解密使用相同的密钥。对称加密的优点是速度快，缺点是密钥的分发和管理。

其基本过程如下：

通过密钥生成函数生成密钥\(key\)
使用\(key\)对明文(plaintext,p)进行加密，得到密文(ciphertext,c),即p=en(key,p)
使用\(key\)对密文进行解密，得到明文，即p=de(key,c)

很难在没有key的情况下破解密文，明文通过key加密再解密后必须和原明文一致（correctness）。

AES算法是目前常用的一种对称加密系统

非对称加密¶

非对称加密的“非对称”代表在其环境中，使用两个具有不同功能的密钥：一个是私钥(private key)，不向外公布；另一个是公钥(public key)，公布公钥不像公布对称加密的共享密钥那样可能影响加密体系的安全性。非对称加密使用以下几个方法来实现加密/解密(encrypt/decrypt)，以及签名/验证(sign/verify)：

keygen() -> (public key, private key)  (这是一个随机方法)

encrypt(plaintext: array<byte>, public key) -> array<byte>  (输出密文)
decrypt(ciphertext: array<byte>, private key) -> array<byte>  (输出明文)

sign(message: array<byte>, private key) -> array<byte>  (生成签名)
verify(message: array<byte>, signature: array<byte>, public key) -> bool  (验证签名是否是由和这个公钥相关的私钥生成的)

非对称的加密/解密方法和对称的加密/解密方法有类似的特征。信息在非对称加密中使用公钥加密，且输出的密文很难在不知道私钥的情况下得出明文。解密方法 decrypt() 有明显的正确性。给定密文及私钥，解密方法一定会输出明文： decrypt(encrypt(m, public key), private key) = m。

Note

对称加密好比一道防盗门，只有一把钥匙，只要是有钥匙的人都可以进出，而非对称加密好比是一把锁和钥匙，任何得到这把锁的人都可以锁上，但只有持有钥匙的人才能打开。

非对称加密的应用¶

PGP 电子邮件加密：用户可以将所使用的公钥在线发布，比如：PGP 密钥服务器或 Keybase。任何人都可以向他们发送加密的电子邮件。
聊天加密：像 Signal 和 Keybase 使用非对称密钥来建立私密聊天。
软件签名：Git 支持用户对提交(commit)和标签(tag)进行 GPG 签名。任何人都可以使用软件开发者公布的签名公钥验证下载的已签名软件。

密钥分发¶

非对称加密面对的主要挑战是，如何分发公钥并对应现实世界中存在的人或组织。

Signal 的信任模型是，信任用户第一次使用时给出的身份(trust on first use)，同时支持用户线下(out-of-band)、面对面交换公钥（Signal 里的 safety number）。

PGP 使用的是信任网络。简单来说，如果我想加入一个信任网络，则必须让已经在信任网络中的成员对我进行线下验证，比如对比证件。验证无误后，信任网络的成员使用私钥对我的公钥进行签名。这样我就成为了信任网络的一部分。只要我使用签名过的公钥所对应的私钥就可以证明“我是我”。

Keybase 主要使用社交网络证明 (social proof)，和一些别的精巧设计。Keybase 会在你的社交网络中寻找你的朋友，看他们是否已经验证了他们的公钥。如果你的朋友已经验证了他们的公钥，那么你就可以信任他们的公钥。Keybase 也支持用户验证自己的公钥，比如通过在自己的网站上发布验证信息。

密码管理器¶

密码管理器会帮助你对每个网站生成随机且复杂（表现为高熵）的密码，并使用你指定的主密码配合密钥生成函数来对称加密它们。

你只需要记住一个复杂的主密码，密码管理器就可以生成很多复杂度高且不会重复使用的密码。密码管理器通过这种方式降低密码被猜出的可能，并减少网站信息泄露后对其他网站密码的威胁。

例如，1Password 和 LastPass 是两个常用的密码管理器。

2FA¶

2FA 是两步验证(two-factor authentication)的缩写。2FA 通常是指在输入密码之后，还需要提供第二个验证因素，比如手机上的一个应用程序生成的一次性密码，或者通过短信发送的一次性密码。来消除密码泄露或者钓鱼攻击（钓鱼攻击指的是一种通过伪装成可信来源（如银行、社交平台、企业等）来诱骗用户泄露敏感信息）的风险。