古典密码

参考《现代密码学（第5版）》（杨波编著）

一.古典密码

​ 古典密码的加密是将明文的每一个字母 ，代换为字母表中的另一个字母，代换前首先将明文字母用等价的十进制数字代替，再以代替后的十进制数字进行运算，字母与十进制数字的对应关系如表所示。

字母	a	b	c	d	e	f	g	h	i	j	k	l	m
数字	0	1	2	3	4	5	6	7	8	9	10	11	12

字母	n	o	p	q	r	s	t	u	v	w	x	y	z
数字	13	14	15	16	17	18	19	20	21	22	23	24	25

​ 根据代换是，每个字母逐个进行还是对多个字母同时进行，古典密码又分为单表代换密码和多表代码密码。

1. 单表代换密码

1.1 恺撒（Caesar）密码

​ 加密代换和解密代换分别为： \[ \begin{align*} c &= E_3(m) \equiv m + 3 \pmod{26}, & 0 \leq m \leq 25 \\ m &= D_3(c) \equiv c - 3 \pmod{26}, & 0 \leq c \leq 25 \end{align*} \] 其中 3 是加解密所用的密钥 - 加密时，每个字母向后移3位（循环移位：x→a，y→b，z→c） - 解密时，每个字母向前移3位（循环移位）

1.2 移位变换

​ 加密代换和解密代换分别为： \[ \begin{align*} c &= E_k(m) \equiv m + k \pmod{26}, & 0 \leq m, k \leq 25 \\ m &= D_k(c) \equiv c - k \pmod{26}, & 0 \leq c, k \leq 25 \end{align*} \]

1.3 仿射变换

​ 加密代换和解密代换分别为： \[ \begin{align*} c &= E_{a,b}(m) \equiv am + b \pmod{26} \\ m &= D_{a,b}(c) \equiv a^{-1}(c - b) \pmod{26} \end{align*} \] 其中

• $ a, b $ 是密钥，满足 $ 0 a, b $ 且 $ (a, 26) = 1 $
• $ (a, 26) = 1 $ 表示 $ a $ 和 26 互素，所以 \(a\) 的取值集合为 \(\{1,3,5,7,9,11,15,17,19,21,23,25\}\)
• $ a^{-1} $ 表示 $ a $ 的模逆元，即 $ a^{-1} a $

计算：

​ 下面以 \(E_{5,8}(m) \equiv 5m + 8 \pmod{26}\) 函数为例，加密字符串 AFFINE CIPHER，采用 \(26\) 字母表：

明文	A	F	F	I	N	E	C	I	P	H	E	R
x	0	5	5	8	13	4	2	8	15	7	4	17
\(y=5x+8\)	8	33	33	48	73	28	18	48	83	43	28	93
\(y\mod26\)	8	7	7	22	21	2	18	22	5	17	2	15
密文	I	H	H	W	V	C	S	W	F	R	C	P

​ 其对应的加密结果是 IHHWVCSWFRCP。

​ 对于解密过程，正常解密者具有 \(a\) 与 \(b\) ，可以计算得到 \(a^{-1}\) 为 21，所以其解密函数是\(D_{5,8}(x)=21(x-8)\pmod {26}\) ，解密如下

密文	I	H	H	W	V	C	S	W	F	R	C	P
\(y\)	8	7	7	22	21	2	18	22	5	17	2	15
\(x=21(y-8)\)	0	-21	-21	294	273	-126	210	294	-63	189	-126	147
\(x\mod26\)	0	5	5	8	13	4	2	8	15	7	4	17
明文	A	F	F	I	N	E	C	I	P	H	E	R

可以看出其特点在于只有 26 个英文字母。

破解

1. 首先，我们可以看到的是，仿射密码对于任意两个不同的字母，其最后得到的密文必然不一样，所以其也具有最通用的特点。当密文长度足够长时，我们可以使用 频率分析 的方法来解决。其次，我们可以考虑如何攻击该密码。可以看出当\(a=1\) 时，仿射加密是凯撒加密。

2. 而一般来说，我们利用仿射密码时，其字符集都用的是字母表，一般只有26个字母，而不大于26的与26互素的个数一共有 \(12\) 个，如果是字母表，模数划定了范围为26，

\[ \phi(26)=\phi(2) \times \phi(13) = 12 \]

​ 算上b的偏移可能，一共有可能的密钥空间大小也就是，如果我们知道其中任意一个参数，那我们便可以很容易地快速枚举另外一个参数得到答案。 \[ 12 \times 26 = 312 \]

3. 我们还有另外一种解密方式，我们只需要知道两个加密后的字母 \(y_1,y_2\) 即可进行解密。那么我们还可以知道

\[ y_1=(ax_1+b)\pmod{26} \\ y_2=(ax_2+b)\pmod{26} \]

​ 两式相减，可得 \[ y_1-y_2=a(x_1-x_2)\pmod{26} \]

​ 这里 \(y_1,y_2\) 已知，如果我们知道密文对应的两个不一样的字符 \(x_1\) 与 \(x_2\) ，那么我们就可以很容易得到 \(a\) ，进而就可以得到 \(b\) 了。

2.多表代换密码

1.1 Hill密码

加密

将明文 $ M $ 分为由 $ n $ 个字母构成的分组 $ M_1, M_2, , M_j $，对每个分组 $ M_i $ 的加密为： \[ C_i \equiv A M_i + B \pmod{N}, \quad i = 1, 2, \cdots, j \]

其中

• 密钥为 \((A, B)\)：
  • $ A $ 是 $ n n $ 的可逆矩阵，满足 $ (|A|, N) = 1 \(（\) |A| $ 表示 $ A $ 的行列式）
  • $ B = (B_1, B_2, ..., B_n)^{T} $
  • 向量形式：$ C = (C_1, C_2, ..., C_n)^{T} \(，\) M_i = (m_1, m_2, ..., m_n)^{T} $

---

解密

对密文分组 $ C_i $ 的解密为： \[ M_i \equiv A^{-1}(C_i - B) \pmod{N}, \quad i = 1, 2, \cdots, j \]

关键条件

1. 可逆矩阵：$ A $ 必须是 $ n n $ 的可逆矩阵
2. 行列式约束：$ (|A|, N) = 1 $（保证 $ A $ 在模 $ N $ 下可逆）
3. 向量维度：$ B $ 和 $ C_i $ 均为 $ n $ 维列向量