Crypto 101 是 Laurens Van Houtven (lvh) 编写的一本关于密码学的开源电子书。

这本书适合各种水平程序员入门密码学。本书内容源自作者在 PyCon 2013 的同名演讲。

XOR

异或（Exclusive or, 简称 XOR）是一种位运算符，当两个比特不同时，返回 1。相同比特，返回 0。可以把异或看作可编程的反相器（programmable inverter）。

通常在数学中，使用 \(\oplus\) 表示异或运算符。

\[0 \oplus 0 = 0 \quad 1 \oplus 0 = 1 \quad 0 \oplus 1 = 1 \quad 1 \oplus 1 = 0\]

通常使用 \(P_i\) 表示明文（plaintext），\(k_i\) 表示密钥（key），\(C_i\) 表示密文（ciphertext）。其中的 \(i\) 表示索引。

\[P_i \oplus k_i = C_i\]

异或运算拥有以下几个数学特性：

  1. 结合律：\(a \oplus (b \oplus c) = (a \oplus b) \oplus c\)
  2. 交换律：\(a \oplus b = b \oplus a \)
  3. 任意比特与自身进行异或，结果始终为 0：\( a \oplus a = 0 \)
  4. 任意比特和 0 进行异或，结果不变：\( a \oplus 0 = a \)

利用这些特性，可以容易推导出 \( a \oplus b \oplus a = b \) 。如果把公式中的 \(a\) 当做密钥，\(b\) 当做明文，那么 \(a \oplus b\) 相当于将明文加密，而 \(a \oplus b \oplus a\) 则相当于对密文解密。

在 Python 和 JavaScript 中，使用 ^ 表示异或运算符。

6 ^ 5 //=> 3

// 相当于
0b110 ^ 0b101 = 0b011

一次性密码本

一次性密码本（One-Time Pad, OTP）是一种加密方式，明文和密钥的比特长度相同，密钥位数完全随机且只能使用一次。这是一种在理论上堪称完美的加密方式。

但是 OTP 的缺点在于密钥的管理和分发。

分块加密

分块加密（block cipher）是一种处理固定长度信息的加密算法。

加密函数 \(E\) 使用密钥 \(k\)，将明文 \(P\) 转换为密文 \(C\)：

\[C = E(k, P)\]

明文和密文的比特长度相同，也可以说它俩具有相同的块大小（block size）。

使用相同的密钥 \(k\) 和解密程序 \(D\)，可以把密文解密为原始明文。

\[P = D(k, C)\]

由于解密和加密使用同样的密钥，因此这种加密模式也被称作对称密钥加密（symmetric-key encryption）或密钥加密（secret-key encryption）。

将来你会见到更多的加密模式，比如公钥加密算法（public-key encryption），它的加密和解密使用的密钥是不同的。这类加密模式也被称作非对称密钥加密（asymmetric-key encryption）。

分块加密是基于密钥的排列置换（keyed-permutation）。也就是说，密钥一旦确定，相同的明文总是会映射为相同的密文。如果密钥改变，输出的密文也会随之改变。

目前常用是分块加密标准是 AES（Advanced Encryption Standard，即高级加密标准）。AES 经过层层选拔，在众多加密算法中脱颖而出，2001 年成为美国国家标准与技术研究所（National Institute of Standards and Technology，简称 NIST）的推荐加密标准。

在成为 NIST 标准之前，AES 的原名叫 Rijndael，这个名称源自它的两位作者名称，比利时的密码学家 Vincent Rijmen 和 Joan Daemen。

原始 Rijndael 算法定义了一系列分块加密算法，块大小和密钥大小可以是 128 比特到 256 比特范围的任意 32 的倍数。成为 AES 后，通过标准化限定了参数长度，块大小固定为 128 比特，而密钥大小只有 128，192 和 256 比特三个标准。密钥越长，加密轮数越多，安全强度也高，但带来的运算开销也就越大。

AES 之前的加密标准是 DES（Data Encryption Standard，即数据加密标准），这是 NIST 1977 年颁布的加密标准，也是最早的广泛使用的分块加密算法之一。

DES 的密钥长度只有 56 比特（DES 算法中密钥占据了 64 比特的长度，但其中 8 比特是奇偶校验位，所以有效的密钥长度只有 56 比特），使用现代计算机硬件，DES 可以在一天内被暴力破解。因此，普遍认为 DES 已不再具有安全性，不应该在新的系统中使用它。

为了延长 DES 算法的寿命，发挥 DES 配套硬件的余热（毕竟花钱买的硬件，扔了确实心疼），人们发明了 3DES 算法。

3DES 就是用 DES 算法把消息处理三遍。第一遍用于加密，第二遍解密，第三遍再加密。

\[C = E_{DES}(k_1, D_{DES}(k_2, E_{DES}(k_3, p)))\]

如果三次的密钥完全一样，即 \(k_1 = k_2 = k_3\)，第二遍的解密抵消了第一遍的加密，3DES 的效果仅仅是第三遍的加密，这和 DES 的效果完全一样，可以实现与旧硬件的兼容性。

如果三次密钥不一样，就能实现更好的安全强度。

尽管 3DES 比 DES 相对安全，但不建议在新系统中使用它。因为它的安全强度不如 AES，但消耗的计算资源要远大于 AES。

据说，3DES 依然是金融领域的主力军。因为金融领域是技术相对保守的行业，数据安全大于技术升级。除非密码学有重大突破，证明 3DES 已完全不可靠，否则 3DES 应该还会持续存在很多年。

分块加密存在一些问题。首先，消息长度有限，比如 AES 消息长度限定为 128 比特。如果想处理更长的消息，或者没有固定长度的消息，需要采用其他的加密技术，比如数据流加密（stream cipher）。

另外，如果密钥丢失，加密将失去意义。如何在不安全的信道上传输密钥，也是一个需要解决的问题。这个问题将通过密钥交换协议（key exchange protocol）解决。

流加密

和分块加密一样，流加密（stream cipher）也是一种对称密钥加密算法，用于处理长度不固定的比特流。

流加密的实现有两种方式，一种是基于已有的分块加密，另一种是从头设计的流加密算法。

ECB mode

一个简单的实现方法，是把输入流切成多个固定长度的块，然后对每个块进行分块加密。这种实现模式叫做电子密码本模式（Electronic Code Book Mode，简称 ECB 模式）。

ECB 模式有一个关键弱点，它会保留明文中的模式。如果明文中有重复的块，会生成对应的重复的密文块，攻击者有可能从密文中猜测出明文大致内容。

ECB 模式虽然简单且易于实现，但是因为有严重的安全问题，通常不推荐在实际应用中使用。

CBC mode

除了 ECB 模式，还有其他的操作模式（mode of operations），可以将块加密配置为流加密。

密码块链模式（cipher block chaining，简称 CBC mode）是一种常见的配置，明文块与上一个密文块进行异或运算，然后在进行分块加密。

第一个明文块与谁搭档？手动创建一个随机数 IV（initialization vectors，初始化向量）。IV 应当是不可预测的，最好是密码学上的加密。

iv 无需保密，可以伴随密文一同发送。但要保证它的不可预测性和唯一性。

如果 iv 使用不当，会造成安全漏洞。比如在 TLS 1.0 中，CBC 模式使用了隐式的 iv，即 iv 来自上一个密文的最后一个块，这种做法导致 iv 具有可预测性，容易遭受 BEAST 攻击，被攻击者利用以恢复部分明文。

为了解决这些问题，TLS 1.1 引入了显式的 iv，从而增强安全性。

填充

如果明文的比特长度不是分块的整数倍时，最后一个块将不满足分块加密的长度要求。

常见的填充方式有以下几种：

  1. 用零填充（或者其他固定的字节常量），缺点是如果原本明文同样以零结尾，就无法区分填充字节的长度和原本明文的长度。
  2. PKCS#5/PKCS#7 填充，使用需要填充的字节数当做填充内容。比如，一个分块长度为 8 个字节，目前明文仅有 12 34 56，还差 5 个字节，那么填充后的明文块是 12 34 56 05 05 05 05 05。

原生的流加密算法

最常用的流加密算法类型是同步流加密（synchronous stream cipher）。它的基本操作是，基于对称密钥生成一串长长的伪随机比特流。这个比特流叫做密钥流（keystream），和明文异或，输出密文。解密过程和加密过程完全一样。

RC4 是著名的原生流加密算法。RC4 的全称是 Rivest Cipher 4，由 Ron Rivest 于 1987 年设计。

RC4 最初是 RSA Security 网络安全公司的商业机密，1994 年其源代码被匿名发布到互联网，由于它运行速度快且易于实现，迅速获得广泛流行。但 RSA 始终没有承认 RC4 算法的真实性。因此，RC4 也常被称作 ARCFOUR 或 ARC4，即 alleged RC4（所谓的 RC4）。

RC4 由于安全问题，已不建议在新应用中使用。

Salsa20 是一种更新的流加密算法，由 Daniel J. Bernstein（丹尼尔·伯恩斯坦） 于 2005 年设计。Salsa20 有两个变体 Salsa20/12 和 Salsa20/8，算法相同，只不过加密轮数不同，原版是 20 次，变体分别是 12 次和 8 次。

ChaCha 是 Salsa20 算法的改进版本，同样由 Daniel 设计，2008 年提出。ChaCha 的速度更快，加密强度更高。

Salsa20 和 ChaCha 是目前流加密算法的佼佼者。

密钥交换协议

密钥交换协议（key exchange protocols）要解决的问题，是一个貌似不可能完成的任务：如何在一个不安全的信道上，交换一个秘密的值。该信道上的所有信息都会被窃听。

密钥交换协议要保证，即使窃听者能够获取所有的信道交换信息，依然无法破解秘密的值。这个交换协议的名字是 Diffie-Hellman，它的作者是 Whitfield Diffie 和 Martin Hellman。该协议也常简称 DH 协议。

DH 协议有许多实现方式。比如离散对数（discrete logarithms）。在下面方程式中，\(y\) 等于 \(g\) 的 \(x\) 次方对 \(p\) 取模的结果。

\[y \equiv g^x \pmod p\]

若 \(g\) 和 \(p\) 已知，通过 \(x\) 求 \(y\) 不难，但是根据 \(y\) 求 \(x\) 却不易。

当 \(p\) 是一个大质数，且 \(g\) 是它的一个原根（primitive root）时，计算 \(x\) 尤其困难。

原根是数论的一个概念，我数学不好，先不深究了。

举个例子，比如张三和李四要确定一个相同的密钥。

张三生成一个秘密的 \(x_1\)，计算得到 \(y_1\)，把 \(y_1\) 发给李四。

\[y_1 \equiv g^{x_1} \pmod p\]

同样的，李四生成一个秘密的 \(x_2\)，计算得到 \(y_2\)，把 \(y_2\) 发给张三：

\[y_2 \equiv g^{x_2} \pmod p\]

张三使用本地的 \(x_1\) 和 \(y_2\) 计算得到一个密钥：

\[k_1 = y_2^{x_1} \pmod p\]

李四使用本地的 \(x_2\) 和 \(y_1\) 计算得到一个密钥：

\[k_2 = y_1^{x_2} \pmod p\]

\(k_1\) 和 \(k_2\) 的值相等，都是 \(g^{x_1 x_2} \pmod p\)。

椭圆曲线离散对数的安全强度更高。