密码学 1：古典密码与密码攻击

古典密码与早期人类的发展密切相关，在许多著名的古代战争中，都可以看见古典密码的身影。古典密码都是对称的加密模型，即符合下面的工作流程：

Message ---[Enc(m, Ke)]---> Ciphertext ---[Dec(C, Ke)]---> Message
                ^                              ^
                |           Transferred        |
         Encryption Key     publicly      The same key

古典密码可以分为两类：

代换密码：将明文中的每个字符代换成另一个字符，代换后的各个字符位置不变。
置换密码：将明文中的各字符置换，改变它们的位置，但不改变字符本身。

单字母单表密码（Monoalphabetic Cipher）

单字母即每次只对一个字母加密，一个密文字母只对应一个明文；单表即用于代换的关系表只有一张，明文密文一一映射。

加法密码：凯撒密码

凯撒密码又称为「移位密码」，据说被凯撒大帝用于军事信息的加密。它将明文字母表进行循环移位后，得到的新字母表作为密文字母表，并与原明文字母一一对应。例如，当 \(k=3\) 时，将字母表左移 3 位，得到：

明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

这个 \(k\) 就是密钥，双方只要事先约定好 \(k\) 就可以进行有效通信。引入「密钥空间」的概念，即所有可能的密钥的集合，显然此种密码的密钥空间 \(\mathcal{K}=\{k|k\in\Z_{26}\}\)，密钥空间的大小为 \(|\mathcal{K}|=26\)。

用数学的方式写出加解密过程即：

\[\left\{ \begin{aligned} & C=\mathrm{Enc}(m, k)\equiv m+k \ (\mathrm{mod}\ 26) \\ & m = \mathrm{Dec}(C, k)\equiv C-k\ (\mathrm{mod}\ 26) \end{aligned} \right.\]

如果把 26 个字母看成数字，这种变换其实就是在原值之上加上一个数，使用求余运算是为了「回滚」。因此这种加密方法又称为加法密码。

乘法密码：仿射密码

将凯撒密码的简单加法变成 \(ax+b\) 的线性变换，得到下面的加密方法称为仿射密码：

\[\left\{ \begin{aligned} & C=\mathrm{Enc}(m, a, b)\equiv am+b\ (\mathrm{mod}\ 26) \\ & m=\mathrm{Dec}(C, a, b)\equiv a^{-1}(C-b)\ (\mathrm{mod}\ 26) \end{aligned} \right.\]

其中，\(a\) 和 \(b\) 共同组成密钥，满足 \(a\) 和 26 互质，且 \(a^{-1}\) 是 \(a\) 在 \(\Z_{26}\) 中的乘法逆元（即 \(a_{-1}, a\in\Z_{26}\) 且 \(a\cdot a^{-1}=1\)。

为什么要互质？如果不互质则无乘法逆。

凯撒密码即是 \(a\) 取 1 的特殊情况。与凯撒密码相比，此方法一定程度上扩大了密钥空间，使密文的统计特性与密钥取值之间变得复杂。

密钥空间 \(\mathcal{K}=\{(a, b)\in\Z_{26}\times\Z_{26}, \mathrm{gcd}(a, 26)=1\}\)。

混合密码

随机混合字母表密码：随机生成明文与密文的对应关系，密钥空间很大（\(26!>4\times10^{26}\)）。分发密码不方便。
关键词混合字母表密码：使用一个关键词构造对应关系。

单字母多表密码（Polyalphabetic Cipher）

这种方法使用复杂的多个对应表进行代换，使得明文和密文不再是一一映射的对应关系，密文的统计规律变得难以寻找。

周期多表代换：维吉尼亚密码

维吉尼亚密码可以看成多次凯撒密码的组合。对于给定的明文 VIGENERE 和密钥 CAFE，先重复密钥到和明文一样的长度：

明文：VIGENERE
密钥：CAFECAFE

然后用下面的表格写出密文：

即，密钥和明文的交叉处即为密文。解密同理。

其加解密过程可以写成：

\[\left\{ \begin{aligned} & C_i\equiv m_i+k_{i\ \mathrm{mod}\ l}\ (\mathrm{mod}\ 26) \\ & m_i\equiv C_i-k_{i\ \mathrm{mod}\ l}\ (\mathrm{mod}\ 26) \\ \end{aligned} \right.\]

其中 \(l\) 是密钥的长度。

周期密码代换：ENIGMA 密码机

二战期间纳粹德国所使用的转子机械加解密机器。机器的关键部分是数个转子和一个接线盘，通过这样的方式构造出了千变万化的明文密文对应关系。

无限多表代换：一次一密

一次一密加密方法是被证明「完美安全」的加密方法，其即是将与明文等长的密钥与明文相异或来取得密文，或反之。一次一密的密钥不能重复使用。密钥在每次传输前随机产生。

多字母代换密码（Multiple Letter Cipher）

普莱菲尔密码

首先选择一个单词作为密钥，填充密钥阵。如，使用 monarchy。字母 i 和字母 j 视为一个字母。

加密规则如下：

如果两个字母相同，中间加一个 x。
如果两个字母在同一行，各以右方字符替代。
如果两个字母在同一列，各以下方字符替代。
对于每个字母，该字母所在行为密文所在行，另一字母所在列为密文所在列。如：
- 对于 hs，h 所在行、s 所在列是 h 的密文，为 B；s 所在行，h 所在列为 s 的明文，为 P。
- 同理，ea 的密文是 IM 或 JM。

密码攻击

攻击类型的划分由攻击者可获取的信息量决定。所有攻击都认为攻击者知道加密类型（加密算法），而根据攻击者得到的其他信息，可以分为如下类型：

唯密文攻击（Ciphertext-Only Attack）：攻击者仅有截获的部分密文。
已知密文攻击（Known Plaintext Attack）：攻击者有截获部分密文，另外还已知一个或多个明文—密文对。
选择明文攻击（Chosen Plaintext Attack）：KPA，但是攻击者已知的明文—密文对中，明文是攻击者指定的。
选择密文攻击（Chosen Ciphertext Attack）：KPA，但是攻击者已知的明文—密文对中，密文是攻击者指定的。

计算机技术学习札记