常见古典密码观赏

前言

所谓“密码”，并不是单指在应用、网页中注册账号时靠自己习惯设置的一个字符串，而是一种用来混淆的技术。使用密码的人希望把可以正常识别的信息转化成无法识别的信息，并且有可行的方案将这样的信息重新破解为原来的可识别的信息。

例如，如果我提前告诉你，如果我抬手了，你就过来打掩护。这其实就是一种加密。再例如盲文也是一种密码，它把正常的英文字母加密成点阵的形式（更容易通过触摸识别），视力障碍者通过记住的盲文字母和英文字母的对应表就可以“对表”解密。

古典密码是密码学里的一个类型，大部分密码的加密方式都比较清晰易懂。现代已经很少使用了（很多密码都可以暴力破解，但是这是基于使用计算机的，如果放在古代可以视为是比较强的密码了）。但是因为很有意思，这里就来观赏一下。部分密码的解密可能需要一定计算机科学或数学基础。

古典密码大致可以分为替换式密码和移项式密码，或是这两种的结合。前者的主要原理是把每个字母用其它字符代替；后者的主要原理是把字母按照一定的规则打乱顺序。

需要被加密的文本称为『明文』，加密后的文本称为『密文』。有时将明文和密文的相互转换需要第三文本作为媒介，称为『密钥』。为了方便，记 $n$ 为明/密文字符串长度。

密文不一定可以能被准确的还原成明文（相同密钥的不同明文对应相同密文）。这样的密码称为哈希（Hash）。

查表类

查表类密码一般把信息按照固定表格加密成其他字符。是一种替换式密码。

例如，福尔摩斯探案集里有一个经典的密码，即跳舞的小人。每个小人对应一个英文字母。如果小人的手上带有棋子，就表示这个字母是本单词的最后一个字母。

再例如猪圈密码，对照表如下：

例如明文 thisisasimplesentence 的加密结果为：

可以对照查表来试一试。

常见的查表密码还有：火星文、摩斯电码、夏多密码、盲文、培根密码等等。

查表密码纯查表没有什么意思，套路基本一致，观赏趣味性低，这里不进行展开。

替换式密码

凯撒密码

最经典的无非是凯撒密码，网剧《超少年密码》的导演自认为知道这个非常厉害就拍了个神秘爽文片。其实会没什么大不了的，因为它最经典也最简单。

凯撒密码加密的方式就是把明文的每个字母按照其在字母表中的顺序向后循环移动固定的数目得到的密文。例如下图就是位移 $13$ 位的对应表：

例如明文 THE MISSION AT LA 用上面的方式加密可以得到 GUR ZVFFVBA NG YN。

解密的方式，通常是因为循环位移只有 $26$ 种情况，暴力枚举位移表然后从密文倒推明文破解。

凯撒密码有一个基于密钥的衍生版，密钥和明文一样长，密钥的每一位字母转化成数字（一般按字母表顺序），每一个数字分别代表明文对应的这一位字母需要位移多少位。例如明文 sauusbva，密钥 guangtou，可以得出每一位的偏移量 $6,20,0,13,6,19,14,20$ 得到密文 yuuhyuju。

基于密钥的凯撒密码一般必须知道对应的密钥是什么，否则将会有 $26^n$ 种对应方式，除非密文很短，否则无法在合理时间内用计算机得到结果。

简单替换密码

简单替换密码则是将每个字母双射成另外的字母。是凯撒密码的严格加强版。也就是确定一个长度为 $26$ 的密钥，第 $i$ 个字母表示明文字母表中第 $i$ 个字母对应密文的什么字母。

一种特殊的简单替换密码，是将第一个字母 a 和最后一个字母 z 对应，第二个字母 b 和倒数第二个字母 y 对应……依次类推。

还有一种特殊的简单替换密码为 QWE 密码，也就是用 QWERT… 分别代替 ABCDEF…，这里的 QWERT… 其实是电脑键盘上的字母顺序。

如果是一般的简单替换密码，其密钥的个数是 $26!$，同样无法使用暴力的方式枚举密钥破解，一般将会采用词频分析。也就是提取出现频率很高的字母组合来猜测其对应的字母。

维吉尼亚密码

维吉尼亚密码使用一系列的凯撒密码组成一个密码表来实现明文和密文转换。

加密时，将密钥循环填充到和明文长度一样。例如明文为 copy the tech，密钥为 cry：

明文	c	o	p	y	t	h	e	t	e	c	h
密钥	c	r	y	c	r	y	c	r	y	c	r

然后查表得到密文，以前两个字符为例：

这样的密码破解的关键在于密钥是循环重复的。如果知道了密钥的长度，它就是一个对应表交叉使用的凯撒密码，然后对于每个凯撒密码分别破解。

仿射密码

仿射密码就是人造映射。通常，采用一个多项式函数 $F(x)$ 来实现替换。也就是把明文对应的数字 $x$ 代入一个公式求出结果数字再对应回字符。

一种常见的仿射密码就是一次函数 $F(x) = (ax+b)\bmod m$。其中 $a,m$ 互质（否则无法解密），$m$ 是字符集大小。显然它的解密函数为 $G(y) = a^{-1}(y-b)\bmod m$。

举个例子，加密明文 affine cipher，设置加密函数 $F(x) = (5x+8)\bmod 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
$F(x)$	8	7	7	22	21	2	18	22	5	17	2	15
密文	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
$G(y)$	0	5	5	8	13	4	2	8	15	7	4	17
明文	a	f	f	i	n	e	c	i	p	h	e	r

仿射密码的破解有两种方案，一种是暴力枚举：如果字符集小（例如字母表大小 $m=26$），$a$ 的取值只会有 $\varphi(m)$ 这么大（以字母表为例子则为 $\varphi(26)=12$）。就算算上 $b$ 的可能，总的可能函数大小为：

$m\varphi(m)$

用字母表的例子就是 $12\times 26=312$。暴力破解是没有什么问题的。

当然对于这种密码，如果已知部分明文和密文的对应，攻击会变得很简单。仍然考虑字母表的例子。假设已知两个明文字母 $x_1,x_2$ 和对应的密文字母 $y_1,y_2(y_1\neq y_2)$，则：

$y_1-y_2 \equiv a(x_1-x_2) \pmod{26}$

于是能很容易求出 $a$，进一步得到 $b$。

使用一次函数仿射密码时，将加密串再次加密任意次都无法改变密码强度（即使使用了不同的 $a,b$），结果都会是 $F(x) = (ax+b)\bmod m$ 的形式。

棋盘密码

棋盘密码一般将给定的明文加密成两两组合的数字或字母。例如经典的一战中被德军使用的 ADFGX 密码，就用到了它（当然它其实是棋盘密码和列位移密码的组合）。

这样的密码将字母表的 $26$ 个字母按照某种方式去掉一个（常见的方案是把 i,j 两个字母在加密时视为同一个字母），然后用某种方式排列到一个 $5\times 5$ 的棋盘上得到密码表，例如：

	A	D	F	G	X
A	b	o	c	w	v
D	z	d	s	h	r
F	l	a	k	n	g
G	q	x	t	e	u
X	i/j	m	p	y	f

然后，将每个明文字母（表格里的小写字母）按照其对应的行列对应的字母（表格里的大写字母）加密。例如明文 fight 将会被加密为密文 XXXAFXDGGF。

棋盘密码的暴力破解是 $25!$ 的。以古典密码学的标准，这是一个强密码。通常需要大量的信息传输量，才能被破解。法国密码局通过截获了大量密码信息，通过密文相同的开头（这通常表示其使用了同一个棋盘加密）对 ADFGX 密码进行破译。

键盘密码

以手机键盘密码和电脑键盘密码为例子，手机键盘密码的加密方式来自九键输入法：

用两位数字来表示一个字母，其中第一个数字表示这个字母在九键键盘上对应的哪个数字，第二个数字表示这个数字代表的字母里的第几个。例如 come 会被加密成 23636132。

这个密码只要能被识别出是手机键盘密码，就能简单破译。识别也是简单的：密文由纯数字组成，且第奇数个数字 $>1$，第偶数个数字 $<5$。

电脑键盘密码通过每个字母在键盘上的坐标加密，或者用一个字母在键盘上周围的字母来加密，例如 w 加密成 qasde。

当然还有一种比较抽象的电脑键盘密码，也就是在键盘上“绘画”，例如 2wsxdr4gbhu7，在键盘上描画一下可以得到一个 W 的样子。这个密码很民间，大家当个乐子看看。

云影密码

云影密码通过用相同数字的和的形式来加密。一般使用 $2$ 的幂的数和，也被称为 01248 密码，使用 $0,1,2,4,8$ 五种数字，其中 $0$ 是分隔符，其他数字用加法的形式表示出一个数，然后再用这个数表示字母。

这类密码的特点是只含有 $0,1,2,4,8$ 五种。识别不困难。

例如破译密码 8842101220480224404014224202480122。按照 $0$ 分隔得到：

内容	数字和	字母
88421	$8+8+4+2+1=23$	W
122	$1+2+2=5$	E
48	$4+8=12$	L
2244	$2+2+4+4=12$	L
4	$4$	D
142242	$1+4+2+2+4+2=15$	O
248	$2+4+8=14$	N
122	$1+2+2=5$	E

恩尼格码

恩尼格码是二战时期的纳粹德国使用的高级机械加密系统。恩尼格码可以将相同的字符转化为不同的字符。这个密码为了实现，通常需要物理设备的辅助，也就是恩尼格码机。

其原理是设置若干个转子，每个转子有 $26$ 格。每次加密一个字母，第一个转子转动一格，当第一个转子转动完一圈时，第二个转子就会转动一格……以此类推。不同的转子组合会让一个字符被加密成不同的字符。

使用密码机打字按下一个字母时，电流通过转子决定到达哪个灯泡，这个灯泡将会亮起。把每个灯泡对应成一个字母，就得到了明文和密文的相互转换。

后来这个机器被进行了加强：将字母两两配对，每次按下一个字母时，实际电流传输的信号是另一个字母的。但是就算没这个加强，总共可能的方案也达到了 $26^n$ 种（$n$ 是转子数）。当时德军配备了五种接线不同的转子，每次选择三个转子并调整起始位置接入。这样算总的方案就是 $\binom{5}{3}26^3=1054560$ 种。

如果算上加强则会有 $>10^{18}$ 种方案，即使使用现在大家家里的电脑去暴力解决也需要 $300$ 年以上，因此希特勒认为这个密码是最强的，不可能被破解。这也是古典密码学的巅峰。

然而再优秀的作品也会有瑕疵。在这个网站模拟恩尼格码，随意配置一套密码机，在明文里输入一堆的 a：

你会发现加密的密文中，bcde…z 这些字母都有，唯独没有出现 a。

也就是说因为转子会严格改变每个字母对应接线的字母，因此一个密文字母对应的明文字母一定不可能就是它本身。

先猜测一个可能出现的词，比如 Heil Hitler（希特勒万岁），然后枚举把它任意的位置上进行比对。若有一样的的字母则说明这个词和这个位置不匹配。如果找到了一套对应的字母，则可以用推理的方法排查所有的对应可能。

人力操作是复杂的，英国数学家图灵专门设计了一台机器用来破译恩尼格码。

移项式密码

栅栏密码

栅栏密码把要加密的明文分成若干个字母一组，然后把每组的第一个字连起来，形成一段无规律的话，如果有不成一组的部分可以不管或者添加特殊字符。这里给出一个例子。明文为 stop attack this city，取 $3$ 个一组得到 sto，pat，tac，kth，isc，ity，然后把每组的第一、二、三个字母分别连起来，最后再拼起来得到 sptkiitaatstotchcy。

解密时可以暴力枚举分组的长度破译。

曲路密码

曲路密码的密钥不是一个字符串（当然可以用字符串的形式表现），而是一个网格上的行走路线。加密时按照句子正常的字母顺序将字母填入一个表格，然后根据密钥代表的路线重新走一边网格，按顺序记录写下的字母得到密文。

例如 The quick brown fox jumps over the lazy dog 可以变成：

然后用一个约定的曲路行动：

得到密文 gesfcinphodtmwuqouryzejrehbxvalookT。

由于网格的行列，曲路的样式都不确定，而且曲路的个数可能很多，暴力破译是很困难的。当然如果确定了曲路的样式，暴力破译还是比较轻松的。

列位移密码

列位移密码的原理是把明文写在一个网格中，然后用一个和列数相同长度的密钥进行加密，然后根据密钥的对每一列重排序。例如：

按照密钥 howareu 加密，将其在字母表中出现的先后顺序编号：

然后按照编号顺序把每一列的字母从上到下写下来得到 qouryinphoTkoolhbxvauwmtdcfsegerjez。

假设列的个数是 $m$，如果 $m$ 很小，暴力枚举 $m!$ 种列的排序方案是可行的。

前面提到一战时德国使用的 ADFGX 密码，就是棋盘密码和列位移密码的组合。

base64

base64 的加密原理将原文每个字符的 ASCII 码值记下来写成一个二进制串（需要保证每个数二进制位数相同，不同的用零补齐）。然后把这个二进制串按顺序写到一个矩阵里（矩阵的列数和原来的二进制位数不相同），再对矩阵每一行的二进制数反过来得到一个字符。

听起来比较厉害，其实举一个例子就有了：

解密时可以考虑枚举密钥矩阵的列数实现。