古典密码算法¶

古典代换密码¶

替换方法：每个字母用其后的第三个字母替换
- 例子：\(A \to D, B \to E, C \to F, \ldots, X \to A, Y \to B, Z \to C\)
一般形式：令 \(P = C = K = \mathbb{Z}_{26}\)，对 \(0 \leq i < 26\)，任意 \(x, y \in \mathbb{Z}_{26}\) 加密函数为

\[ E(x) = (x + i) \bmod 26 \]

解密函数为

\[ D(y) = (y - i) \bmod 26 \]
密钥长度：1（位移量）
密钥空间：25（因为位移 26 会回到原字母）
缺点：字母频率不变，容易被频率分析法破解

替换方法：每个字母用另一个字母替换，但不是简单的位移，每个字母随机映射到另一个字母
一般形式：令 \(P = C = K = \mathbb{Z}_{26}\)，对 \(0 \leq i < 26\)，任意 \(x, y \in \mathbb{Z}_{26}\) 加密函数为

\[ E(x) = (ax + b) \bmod 26 \]

解密函数为

\[ D(y) = a^{-1}(y - b) \bmod 26 \]

其中 \(a, b \in \mathbb{Z}_{26}\)，且 \(\gcd(a, 26) = 1\)
密钥长度：\(26\)
密钥空间：\(26! \approx 2^{88}\)，比凯撒密码更安全
有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面
- 例如，给定密钥字 "JULIUSCAESAR" ，则映射为：
  
  \[ \begin{aligned} Plain: & \mathtt{ABCDEFGHIJKLMNOPQRSTUVWXYZ} \\ Cipher: & \mathtt{JULISCAERTVWXYZBDFGHKMNOPQ} \end{aligned} \]
缺点：字母频率不变，容易被频率分析法破解

替换方法：使用多个单字母代换表，因此一个字母可以被多个字母代换
一般形式：令 \(P = C = K = \mathbb{Z}_{26}\)，设 \(m \in \mathbb{Z}^+\) 为密钥长度，任意 \(x, y \in \mathbb{Z}_{26}\)，\(k = (k_1, k_2, \ldots, k_m) \in \mathbb{Z}_{26}^m\)，加密函数为

\[ E(x_i) = (x_i + k_{(i \bmod m) + 1}) \bmod 26 \]

解密函数为

\[ D(y_i) = (y_i - k_{(i \bmod m) + 1}) \bmod 26 \]
密钥长度：\(m\)
密钥空间：\(26^m\)，比混合单表代换密码更安全
例子：明文 "ATTACKATDAWN" ，密钥 "LEMON" ，加密过程如下：

\[ \begin{aligned} Plain: & \mathtt{A T T A C K A T D A W N} \\ Key: & \mathtt{L E M O N L E M O N L E} \\ Cipher: & \mathtt{L X F O P V E F R N H R} \end{aligned} \]
优点：字母频率被打乱，更难被频率分析法破解
缺点：如果密钥较短，仍然可能被频率分析法破解

思想：按一定规则写出明文，按另一规则读出密文。

替换方法：将明文写在多个“轨道”上，然后按轨道顺序读取密文
例子：明文 "WEAREDISCOVEREDFLEEATONCE" ，轨道数为 3 ，加密过程如下：

\[ \begin{aligned} &\mathtt{W . . . E . . . C . . . R . . . L . . . T . . . E} \\ &\mathtt{. E . R . D . S . O . E . E . F . E . A . O . C .} \\ &\mathtt{. . A . . . I . . . V . . . D . . . E . . . N .} \end{aligned} \]
- 密文为 "WECRLTEERDSOEEFEAOCAIVDEN"

替换方法：以一种形式写下消息，以另一种形式读取消息
例子：以行的形式写下消息，以列的形式读取消息
- 明文 "HELLOTHERE" ，矩阵宽度为 3 ，加密过程如下：
  
  \[ \begin{aligned} &\mathtt{H E L} \\ &\mathtt{L O T} \\ &\mathtt{H E R} \\ &\mathtt{E} \end{aligned} \]
  - 密文为 "HLHEEOELTR"