计算机技术学习札记

密码学 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

  • 如果两个字母在同一行,各以右方字符替代。

  • 如果两个字母在同一列,各以下方字符替代。

  • 对于每个字母,该字母所在行为密文所在行,另一字母所在列为密文所在列。如:

    • 对于 hsh 所在行、s 所在列是 h 的密文,为 Bs 所在行,h 所在列为 s 的明文,为 P

    • 同理,ea 的密文是 IMJM

密码攻击

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

  • 唯密文攻击(Ciphertext-Only Attack):攻击者仅有截获的部分密文。

  • 已知密文攻击(Known Plaintext Attack):攻击者有截获部分密文,另外还已知一个或多个明文—密文对。

  • 选择明文攻击(Chosen Plaintext Attack):KPA,但是攻击者已知的明文—密文对中,明文是攻击者指定的。

  • 选择密文攻击(Chosen Ciphertext Attack):KPA,但是攻击者已知的明文—密文对中,密文是攻击者指定的。