计算机技术学习札记

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

2022 年 9 月 8 日

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

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

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

Vigenere​

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

其加解密过程可以写成：

$$ \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 密码机 #

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

Screenshot_20220909_152142​

无限多表代换：一次一密 #

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

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

普莱菲尔密码 #

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

Screenshot_20221122_113414​

加密规则如下：

  • 如果两个字母相同，中间加一个 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，但是攻击者已知的明文—密文对中，密文是攻击者指定的。