古典密码之单表代换加密

在古典密码学中，我们主要介绍单表替代密码，多表替代密码，以及一些其它比较有意思的密码。值得一提的是，在古典密码学中，设计者主要考虑消息的保密性，使得只有相关密钥的人才可以解密密文获得消息的内容，对于消息的完整性和不可否认性则并没有进行太多的考虑。

在单表替换加密中，所有的加密方式几乎都有一个共性，那就是明密文一一对应。所以说，一般有以下两种方式来进行破解

当密钥空间足够大，而密文长度足够短的情况下，破解较为困难。

凯撒密码（Caesar）加密时会将明文中的 每个字母 都按照其在字母表中的顺序向后（或向前）移动固定数目（循环移动）作为密文。例如，当偏移量是左移 3 的时候（解密时的密钥就是 3）：

使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作，得到原来的明文。例如：

根据偏移量的不同，还存在若干特定的恺撒密码名称：

此外，还有还有一种基于密钥的凯撒密码 Keyed Caesar。其基本原理是 利用一个密钥，将密钥的每一位转换为数字（一般转化为字母表对应顺序的数字），分别以这一数字为密钥加密明文的每一位字母。

这里以 XMan 一期夏令营分享赛宫保鸡丁队 Crypto 100 为例进行介绍。

对于不带密钥的凯撒密码来说，其基本的破解方法有两种方式

其中，第一种方式肯定可以得到明文，而第二种方式则不一定可以得到正确的明文。

而对于基于密钥的凯撒密码来说，一般来说必须知道对应的密钥。

一般我们有如下的工具，其中JPK比较通用。

与凯撒密码类似，区别在于移位密码不仅会处理字母，还会处理数字和特殊字符，常用 ASCII 码表进行移位。其破解方法也是遍历所有的可能性来得到可能的结果。

埃特巴什码（Atbash Cipher）其实可以视为下面要介绍的简单替换密码的特例，它使用字母表中的最后一个字母代表第一个字母，倒数第二个字母代表第二个字母。在罗马字母表中，它是这样出现的：

下面给出一个例子：

可以看出其密钥空间足够短，同时当密文足够长时，仍然可以采用词频分析的方法解决。

简单替换密码（Simple Substitution Cipher）加密时，将每个明文字母替换为与之唯一对应且不同的字母。它与恺撒密码之间的区别是其密码字母表的字母不是简单的移位，而是完全是混乱的，这也使得其破解难度要高于凯撒密码。 比如：

a 对应 p，d 对应 h，以此类推。

而解密时，我们一般是知道了每一个字母的对应规则，才可以正常解密。

由于这种加密方式导致其所有的密钥个数是26!

，所以几乎上不可能使用暴力的解决方式。所以我们 一般采用词频分析。

仿射密码的加密函数是 E(x)=(ax+b)(modm)，其中

解密函数是 D(x)= a^{-1} (x−b)(modm)，其中 a^{-1} 是 a 在 Z_{m} 群的乘法逆元。

下面我们以 E(x)=(5x+8)mod26

函数为例子进行介绍，加密字符串为 AFFINE CIPHER，这里我们直接采用字母表26个字母作为编码系统

其对应的加密结果是 IHHWVCSWFRCP。

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

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

首先，我们可以看到的是，仿射密码对于任意两个不同的字母，其最后得到的密文必然不一样，所以其也具有最通用的特点。当密文长度足够长时，我们可以使用频率分析的方法来解决。

其次，我们可以考虑如何攻击该密码。可以看出当a=1

时，仿射加密是凯撒加密。而一般来说，我们利用仿射密码时，其字符集都用的是字母表，一般只有26个字母，而不大于26的与26互素的个数一共有

ϕ(26)=ϕ(2)×ϕ(13)=12

算上b的偏移可能，一共有可能的密钥空间大小也就是

12×26=312

一般来说，对于该种密码，我们至少得是在已知部分明文的情况下才可以攻击。下面进行简单的分析。

这种密码由两种参数来控制，如果我们知道其中任意一个参数，那我们便可以很容易地快速枚举另外一个参数得到答案。

但是，假设我们已经知道采用的字母集，这里假设为26个字母，我们还有另外一种解密方式，我们只需要知道两个加密后的字母 y_{1} , y_{2}

即可进行解密。那么我们还可以知道

y_{1} =(a x_{1} +b)(mod26)y2=(a x_{2} +b)(mod26)

两式相减，可得

y_{1} − y_{2} =a( x_{1} − x_{2} )(mod26)

这里 y_{1} , y_{2} 已知，如果我们知道密文对应的两个不一样的字符 x_{1} 与 x_{2} ，那么我们就可以很容易得到 a ，进而就可以得到 b 了。

这里我们以TWCTF 2016 的 super_express为例进行介绍。简单看一下给的源码

可以发现，虽然对于 flag 中的每个字母都加密了 n 次，如果我们仔细分析的话，我们可以发现

c_{1} = a_{1} c+ b_{1}

c_{2} = a_{2}c_{1} + b_{2}

= a_{1} a_{2} c+ a_{2} b_{1} + b_{2}

=kc+d

根据第二行的推导，我们可以得到其实 c_{n} 也是这样的形式，可以看成 c_{n} =xc+y ，并且，我们可以知道的是，key 是始终不变化的，所以说，其实这个就是仿射密码。

此外，题目中还给出了密文以及部分部分密文对应的明文，那么我们就很容易利用已知明文攻击的方法来攻击了，利用代码如下

结果如下

本文转载自CTF Wiki