密码学 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
然后用下面的表格写出密文:
![Vigenere](/assets/Vigenere-20220908150305-duarm2b.png)
即,密钥和明文的交叉处即为密文。解密同理。
其加解密过程可以写成:
\[\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](/assets/Screenshot_20220909_152142-20220909152213-3e48tcn.png)
无限多表代换:一次一密
一次一密加密方法是被证明「完美安全」的加密方法,其即是将与明文等长的密钥与明文相异或来取得密文,或反之。一次一密的密钥不能重复使用。密钥在每次传输前随机产生。
多字母代换密码(Multiple Letter Cipher)
普莱菲尔密码
首先选择一个单词作为密钥,填充密钥阵。如,使用 monarchy
。字母 i
和字母 j
视为一个字母。
![Screenshot_20221122_113414](/assets/Screenshot_20221122_113414-20221122113434-rhi86ig.png)
加密规则如下:
如果两个字母相同,中间加一个
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,但是攻击者已知的明文—密文对中,密文是攻击者指定的。