传统加密技术

目录索引

置换密码

又叫换位密码，根据一定的规则重新排列明文。
这里密钥是置换关系，表示 $i \rightarrow j$ 的位置映射关系
特点：保持明文所有字符不变

通俗而言，也就是把明文顺序打乱，实现混淆内容的目的

列置换密码

将明文遵照密钥的规则按列换位并且按列读出序列得到密文

举个例子：
明文 $P=Beijing2008OlympicGames$
密钥 $\sigma=\left( \begin{array}{ccc} 1 & 4 & 3 \end{array} \right) \left( \begin{array}{cc} 5 & 6 \end{array} \right)$
密文 $C=i0mme2yaJ0peBglGnoci8is$
解密密钥 $\sigma^{-1}=\left( \begin{array}{ccc} 1 & 3 & 4 \end{array} \right) \left( \begin{array}{cc} 5 & 6 \end{array} \right)$
$[P]_{4 \times 6}=\begin{bmatrix} B & e & i & j & i & n \\ g & 2 & 0 & 0 & 8 & O \\ l & y & m & p & i & c \\ G & a & m & e & s \end{bmatrix} \overset{\sigma}{\Rightarrow} [C]_{4 \times 6} = \begin{bmatrix} i & e & J & B & n & i \\ 0 & 2 & 0 & g & O & 8 \\ m & y & p & l & c & i \\ m & a & e & G & & s\end{bmatrix}$

周期置换密码

将明文 $P$ 按固定长度 $m$ 分组，然后对每组按 $1,2,⋯,m$ 的某个置换重排位置得到密文

举个例子：
明文 $P=State Key Laboratory of Networking and Switching$
密钥 $\sigma = \left( \begin{array}{ccccc} 1 & 5 & 6 & 2 & 3 \end{array} \right)$
可知每一组有6个数字，即 $(StateK)(eyLabo)(ratory)(ofNetw)(orking)(andSwi)(tching)$
使用密钥交换可得到 $(aKttSe)(Loyaeb)(tyaorr)(Nwfeot)(kgrion)(dinSaw)(hgcitn)$
即密文为 $C=aKttSeLoyaebtyaorrNwfeotkgriondinSawhgcitn$

栅栏技术

按照对角线顺序写出明文，而后按照行的顺序读出密文

多次置换密码

多次使用置换密码，可以进一步混乱字符间的规律，更难以被分析

代换密码

将明文中的一个符号由其他符号替代

单表代换密码

也即只有一个代换表，每个字符总是会被替换成同一个固定的字符
如果代换表中有 $n$ 个代换关系，那么最终密钥空间达到 $n!$

单表代换密码，可以使用统计分析法攻击

凯撒密码

凯撒密码是最简单的单表代换密码
代换关系是按照字母表顺序明文字母后面第三个字母，比如 $A$ 对应的密文是 $D$
在程序里可以简单地使用（下面分别是 C 和 Python 的相关函数）

void encrypt(char *plantext, char *ciphertext) {
    for (int i = 0; i < strlen(plantext); ++i) {
        if (plantext[i] >= 'a' && plantext[i] <= 'z')
            ciphertext[i] = ((plantext[i] - 'a' + 3) % 26) + 'A';
        else
            ciphertext[i] = plantext[i];
    }
}

def Caesar(plaintext: str):
    def encrypto(char: str):
        if char >= 'a' and char <= 'z':
            return chr(((ord(char) - ord('a') + 3) % 26) + ord('a'))
        elif char >= 'A' and char <= 'Z':
            return chr(((ord(char) - ord('A') + 3) % 26) + ord('A'))
        return char
    return "".join(map(encrypto, plaintext))

playfair密码

将明文的双字母音节作为一个单元转换为密文的双字母音节
也即是一个双字符的单表替换
根据密钥生成一个二维矩阵，并根据明文双字符在二维矩阵的位置关系进行替换

举个例子：
密钥为 $S=monarchy$
那么可以得到一个矩阵
$\begin{bmatrix} M & O & N & A & R \\ C & H & Y & B & D \\ E & F & G & I/J & K \\ L & P & Q & S & T \\ U & V & W & X & Z \end{bmatrix}$

将明文分割成字母对，并按照以下规则替换：

如果两个字母相同，则在其中增加一个填充字符
如果两个字母在同一行，则两个字母都由它们右面的数据替换
如果两个字母在同一列，则两个字母都由它们下面的数据替换
其余情况下，使用该字母所在行以及另一个字母所在列对应的字母替换

尽管只有 $26$ 个字母，但有 $26 \times 26=676$ 个字母对，因此识别单个字母较为困难
虽然单字母的频率分析很难起效，但是双字母频率分析仍然可用

不过该加密算法，仍然存在一些问题。当明文为奇数时需要补入一个特定字母、当连续两个字母相同时也需要在中间插入该字符。由于这种情况存在，所以要还原明文时，很难判断遇到这个插入字符时，确定它是本来就在明文中的，还是插入的。

多表代换密码

轮流使用多个代换表的代换密码体制，由于有多个代换表，因此每个字符可能会被替换成不同的字符

维吉尼亚密码(Vigenere)

和凯撒密码很像，可以理解为偏移量是循环可变的凯撒密码
首先给定密钥——一个整数数组，代表第 $i$ 个字符的偏移量
当明文长度超过密钥长度时，则循环使用密钥

希尔密码(Hill Cipher)

有明文空间 $P$ ，密文空间 $C$ ，密钥空间 $K=(k_{ij} )_{n \times n},det⁡(k \ne 0), (det⁡(k),26)=1$ ，即满足 $Z_{26}$ 上 $det⁡(k)$ 和 $26$ 互素，且 $K$ 是非奇异矩阵（需要保证有逆矩阵用于解密）
$[c]_{1 \times n}=([p]_{1×n}×[k]_{n×n}) \pmod {26}$

简单而言就是用一个矩阵作为密钥，加密就是做一次矩阵乘法

当矩阵很大时，很难通过频率分析破解，因为数据足够混乱。但是由于这是一个数学计算，因此使用选择明文攻击求出解密矩阵（对于 $m \times m$ 的密钥，有 $m$ 个已知明密文对时）

举例：
明文 $P=cyber$
密钥 $k=\begin{bmatrix} 10 & 5 & 12 & 0 & 0 \\ 3 & 14 & 21 & 0 & 0 \\ 8 & 9 & 11 & 0 & 0 \\ 0 & 0 & 0 & 11 & 7 \\ 0 & 0 & 0 & 3 & 7 \end{bmatrix}$
$c = \left( \begin{array}{ccccc} 2 & 24 & 1 & 4 & 17 \end{array} \right) \begin{bmatrix} 10 & 5 & 12 & 0 & 0 \\ 3 & 14 & 21 & 0 & 0 \\ 8 & 9 & 11 & 0 & 0 \\ 0 & 0 & 0 & 11 & 7 \\ 0 & 0 & 0 & 3 & 7 \end{bmatrix} = \begin{bmatrix} 100 \\ 355 \\ 539 \\ 95 \\ 151 \end{bmatrix}^T \bmod 26 = \begin{bmatrix} 22 \\ 17 \\ 19 \\ 17 \\ 21 \end{bmatrix}^T \Leftrightarrow WRRTRV$

维尔姆密码(Vernam)

将英文字母编码为 5 比特二元数字（共能表示 $32$ 个符号），称为五单元波多电码，选择随机二元数字序列作为密钥，以 $k=k_1,k_2,\cdots,k_i \in [0,1]$
使用异或进行加密
$c_i = m_i \oplus k_i \pmod 2$

恩格玛机(Enigma)

恩格玛机是一种转轮密码机，通过转动齿轮将一个字母转换为另一字母
共有一个输入端，一个接线板（每天更新一次的单表代换），三个转子扰频器（多表代换），以及反射器。实现按下一个键后其他某个键亮起
每一次通信都有单独的通信密码，需要根据通信密码设定转子

转轮密码机是近代密码发展史的里程碑事件，揭示了实用密码设备必备的四要素：安全、性能、成本、易用

一次一密

使用与消息一样长且不重复的随机密钥来加密信息，且密钥只对一个消息进行加解密，之后丢弃不用。该方案不可攻破
其安全性取决于密钥的随机性，如果密钥字符是真正随机的，那么构成密文的字符流也是真正随机的，攻击者无法进行攻击。但是仍然存在一些难点：

产生大规模的随机密钥较为困难
密钥分配与保护困难

传统密码分析技术

统计分析法

根据单字母、双字母、三字母在不同类型文章中出现的概率，来推测出单表代换密码每个符号的含义

使用后面的代码可以统计出哈利波特第一部英文版各个字母出现的概率（可以将analysis_size设置为 2 或者 3 来分析双字符、三字符），其中前五的字母为

t 27993 8.36%
a 25887 7.73%
o 25809 7.70%
n 21337 6.37%
r 20990 6.27%

比如要分析凯撒密码，可以先找到相同领域的明文进行分析作为字典，再对密文进行分析，这时按照频率排序基本上可以映射出对应关系

analysis_size = 1
m = [{"total": 0, "dict": {}}for i in range(analysis_size+1)]


def add(s: str):
    size = len(s)
    for c in s:
        if c not in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ":
            return
    m[size]["dict"][s] = m[size]["dict"].get(s, 0) + 1
    m[size]["total"] += 1


if __name__ == "__main__":
    with open("hp1.txt", "r") as f:
        line = f.read()
        size = len(line)
        for i in range(size):
            for size in range(analysis_size):
                if i >= size:
                    add(line[i-size:i+1])

    for t in m:
        for k, v in sorted(t["dict"].items(), key=lambda x: x[1]):
            print("%5s %5d %5.2f%%" % (k, v, v/t["total"]*100))

重合指数法

对于有意义的文本，每个字符出现的概率不同，能够恰好找到两个等同字母的概率远大于随机文本。重合指数为：
$IC=\sum^n_{i=1}p^2_i \approx \sum^n_{i=1} \frac{x_i(x_i-1)}{L(L-1)}$

明密文对分析法

当有比密钥长度多的明文-密文对时，可以分析出希尔密码的密钥
$[c]_{m \times m}=([p]_{m \times m} \times [k]_{m \times m} ) \bmod 26 \Rightarrow [k]_{m \times m}=([p]_{m \times m}^{−1}×[c]_{m \times m}) \bmod 26$

《密码编码学与网络安全》——传统加密技术