Playfair Cracker

关于playfair密码的破解。

Playfair这个加密呢，之前做题一直有点困扰我。最近找到了一篇关于playfair crack的文章，就想着自己写一下里面的破解算法。原文给出了C语言实现这篇相当于是原文的翻译吧。
这是原文地址：
http://www.practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-playfair/

使用的是Simulated annealing(模拟退火)算法。要求明文长度至少要大于100字符。

//hill-climbing algorithm:
1-生成一个随机的key,作为我们的'parent', 使用这个key对密文进行解密，计算结果的适配度，并保存这个值。
2-微小的改变key,比如随机的交换其中的两个字符。重新进行解密与评估，将评估结果保存。
3-如果修改的密钥适配度要高一些，那么将当前的key作为parent，丢弃之前的parent。
4-回到2， 除非在迭代一千次之后都没有提升。

在简单的单表或者多表替换密码中，我们可以采用爬山算法，每次迭代优化选择我们的key，直到把最优的key选择出来。但是仅仅将这种算法运用与playfair，我们是无法破解他的，爬山算法会进入一个局部最优的情况。所以我们需要让爬山算法偶尔能接收结果下降的改变，也就是我们的SA了。

// Simulated annealing algorithm (hill-climbing enhance):
1-生成一个随机的key,作为我们的'parent', 使用这个key对密文进行解密
2-计算当前密钥解密的出来的数据的适配度，并保存
3-for(TEMP = 10; TEMP >= 0; TEMP -= STEP)
	for(count = 50000; count > 0; count--)
		微小的改变key,比如随机的交换其中的两个字符，获得子密钥child。
		衡量当前子密钥的适配度
		set dF = (子密钥适配度 - 父密钥适配度)
		if dF > 0
			parent = child
		if dF < 0 
			parent = child 在e^(dF/T)的概论下
			
// T是退火算法的温度参数

关于公式$e^{\frac{dF}{T}}$有以下的特点：

变量	$e^{\frac{dF}{T}}$的值
$dF <<0$	$close \quad 0$
$dF \ close \ 0$	$close \quad 1$
$large \ T$	$close \quad 1$
$small \ T$	$close \quad 0$

我们将$e^{\frac{dF}{T}}$作为概论判断依据。如果他很接近1的话，我们基本上就等于接受了parent = child。而如果他很接近0的话，我们也就相当于不改变parent。而对T的修改也同理的。当T很大的时候，整体的幂次数会接近0，那么其值就接近了1，而T很小的时候，其值就会像负方向移动，更加接近0。随者程序的运行我们会不断的降低这个T，那么我们将越来越低可能的接收适配度降低的子密钥。

我们为什么要这么做？还是为了跳出爬山算法的局部最优。爬山算法进入了局部最优那么我们就无法跳出了，添加这种接收损失的途径可以让我们有可能跳出局部最优，而且在我们尝试的次数足够多的时候，我们基本上都能够跳出原来的局部最优解。从而得到一个适配度更好的结果。当我们的温度T将到0之后，就和爬山算法别无二致了。

测量适配度

其实就是判断当前的明文和英文的拟合程度，也就是像不像是英文文本。一个和英文文本很像的明文将会获得一个高的分数，而杂乱无章的随机字符序列将会得到一个低的分数。这里我们使用quadgram statistics作为我们的分析工具。通过分析当前明文的分布和正常的英语是否接近来给出相应的分数。如果明文中有“QKPC”这种基本上看不到的英文序列，基本上就和英文文本说再见了。所以我们可以通过这种方式来评判一个解密密钥的好坏。

Quadgram Statistics

为了本文逻辑的完整性，我把另外一篇文章的内容也搬过来了

原文地址：http://www.practicalcryptography.com/cryptanalysis/text-characterisation/quadgrams/

我们想要来判断一个明文片段是否和给定的语言种类接近，可以对Quadgram(四格图)进行计数，或者对4个字母一组进行计数。

当然，single letter frequencies, bigrams 与 trigrams也是可以用来做这个的。但是Quadgram效果最好。在单词ATTACK中，我们的四格图为：ATTA,TTAC,TACK。

想要用quadgram来判断文本是否和英文接近，我们首先要知道那些quadgram在英文里出现了。要做到这一点，我们需要用大量的文本片段去计算。比如用几本书的内容，统计其中出现的quadgram。然后计算每个quadgram出现的概论。

在战争与和平中，统计出了2500000个quadgram。计算出每一个quadgram出现的概率，然后对他做log处理。

Quadgram	Count	Log Probability
AAAA	1	-6.40018764963
QKPC	0	-9.40018764963
YOUR	1132	-3.34634122278
TION	4694	-2.72864456437
ATTA	359	-3.84509320105

有部分quadgram出现的很频繁，这个quadgram就可以当作我们判断的一个依据。而QKPC这种序列是完全没有出现过，他的可能性是负无穷，表格上并不是，这是因为我们给概率定了一个下界。

为了计算明文碎片整体的可能性，我们需要提取当前明文碎片所有的quadgram，然后将他们的概率相乘。

还是拿ATTACK举例：

$p(ATTACK) = p(ATTA) \times p(TTAC) \times p(TACK) \\ p(ATTA) = \frac{count(ATTA)}{N}$

最后将概率进行log操作。

$log(p(ATTACK)) = log(p(ATTA)) + log(p(TTAC)) + log(p(TACK))$

具体实现很简单的。如果嫌麻烦，可以去原文下载python实现代码。

算法考量

在破解简单替换加密的时候，简单的对父密钥进行修改，并不能让我们破解playfair加密。通过添加其他的交换方式比如行交换、列交换、逆序、左移右移、反转、上下位移等等（这里主要是playfair的key是一个棋盘格式），我们很有可能能够得到正确的key。

我们需要考虑的是我们新引入的变量：起始温度，温度下降阶，以及每阶中的迭代次数。迭代次数越高，我们能得到正确key的可能性就越大，但是耗时会越久。通过降低温度下降阶（每次下降的温度减小），我们能得到正确的key的可能性就越大，但是耗时会越久。而起始温度一般来说和密文的长度有关系。对于一个100字节长度的密文，起始温度在10附近。而对于300字节长的密文，起始温度在20附近。

使用模拟退火算法破解playfair，可以参考这篇论文：“Breaking Short Playfair Ciphers with the Simulated Annealing Algorithm” by Cowan, M. Cryptologia, Vol 32, issue 1, 2008.