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）也是一种对称密钥加密算法，用于处理长度不固定的比特流。

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