哪些算法最可靠地解决替换密码？

Question

我正在研究一个问题，这个问题可以简化为对用已知语言编写的冗长的单字母替换密文的密码分析。这个问题很容易用频率分析和单词模式手工解决，就像辛科夫的《基本密码分析》中描述的那样。我很难找到一个理论上有效的算法： Joux的《算法密码分析》甚至没有涵盖这种基本的替换，我从盖恩斯的《密码分析：密码及其解决方案的研究》中一无所获（我还应该看到什么其他资源？）。

有些方法是显而易见的。确定每个替换顺序，然后利用已经知道的，只有在过程中没有出错的情况下才有效。使用元启发式优化——例如，重新分配字母，直到找到的有效单词数量最大化——使得很难判断搜索何时结束。也许测试变化的动态编程方法是最好的。或者，这个问题的答案包含其他可能幼稚的方法。

解决这类问题的首选算法是什么？

Answer 1

本文描述了一种求解谐音替换密码的算法，其中长度为26（a-z）的字母是其特例。这里提供了它们的C参考实现。

算法背后的基本思想（爬山使用二进制频率，以避免不得不破译一次以上）来自这篇论文，并且（由第一篇论文的作者）被描述为解决单字母替代密码的最快已知算法。

Answer 2

如果我们（不切实际地）假设给定语言中的每个字母都以某种已知的概率独立于附近的字母出现，那么精确的最大似然估计可以相当有效地找到。这是你对这个模型的最好期望。

假设信息中有n个字母，字母表中有k个字母。

基本思想是，我们以某种方式为每个k^2可能的字母对计算出一个数字分数，然后在两个字母表上寻找最大权重的二分完美匹配——也就是说，我们选择字母对的方式是，一个字母表中的每个字母都与另一个字母中的一个字母配对，并且所选字母对的分数之和最大化。主要有两个问题：（1）如何定义给定配对的分数；（2） 一旦我们决定了个人的分数，如何解决寻找对的最高和子集的一般问题。

将编码字母x与源字母y配对的分数应该是log（p（y）^freq（x）），其中p（y）是语言中字母y的已知概率，freq（x）是字母x在编码输入中出现的次数。为什么？因为在忽略附近字符影响的源语言的这种简单模型下，生成任何给定n个字符的源语言字符串的概率等于其中出现的字母的概率的乘积，你也可以将其计算为p（y）^freq（y）在源字母表中所有字母y上的乘积。因此，为了计算生成该字符串的概率，假设每个x都是“真正的”y（其他都不是y），我们将freq（y）改为freq（x）。如果我们接下来取日志，我们得到的是源字母表中所有字母y的log（p（y）^freq（x））之和——这个和正是最大二部完全匹配算法将最大化的。

有算法在O（V^2E）时间内解决密切相关的最大权重二部匹配问题，这里相当于O（k^4）时间。这个版本的问题看起来是最大化所有选择对的总和，同时遵守约束，即没有项目与另一组中的两个或更多其他项目匹配，但不要求每个项目都与其他项目匹配。幸运的是，我们可以把这个算法变成一个算法，通过向每个分数添加大量的M来非常简单地解决我们想要解决的“完美”变化：直观地说，这导致算法试图添加尽可能多的边（因为即使省略单个边也有很大的成本，使得这样的解决方案比包含全套k边的“愚蠢”解决方案糟糕得多），同时仍然迫使算法在所有k边解决方案中选择最好的（因为所有这些解决方案都包括来自添加权重的相同kM贡献）。