我正在研究一个问题，该问题可以归结为用已知语言编写的长篇单字母替换密文的密码分析。这个问题很容易通过使用频率分析和单词模式手动解决，如Sinkov的初等密码分析中所述。我很难找到一个经过理论验证的算法：Joux的算法密码分析甚至没有涵盖如此基本的替换，我也没有从Gaines的Cryptanalysis:a Study of Ciphers and Their Solution中得到任何东西(我还应该看到什么其他资源？(。
有些方法非常明显。按照顺序决定每个替换，然后利用已知的内容，只有在过程中没有出错的情况下才有效。使用元启发式优化——例如，重新分配字母，直到找到的有效单词数量最大化——使得很难判断搜索何时结束。也许测试变体的动态编程方法是最好的。或者，这个问题的答案包含了其他可能天真的方法。
解决这类问题的首选算法是什么？
独立字母模型的精确最大似然估计
如果我们(不切实际地(假设给定语言中的每个字母都以某种已知的概率独立于附近的字母出现，那么可以相当有效地找到确切的最大似然估计。这是你对这个模型所能期望的最好的结果。
假设信息中有n个字母，字母表中有k个字母。
基本思想是，我们以某种方式为k^2个可能的字母对中的每一个得出一个数字分数，然后在两个字母上寻找最大权重的二分完美匹配——也就是说，我们选择字母对的方式是，一个字母表中的每个字母都与另一个字母中的一个字母配对，并且所选字母对的分数之和最大化。主要有两个问题：(1(如何定义给定配对的分数；(2( 一旦我们决定了个人得分，如何解决找到配对的最高和子集的一般问题。
记分对
将编码的字母x与源字母y配对的分数应为log(p(y(^freq(x((，其中p(y(是字母y在该语言中的已知概率，freq(x(是字母x在编码输入中出现的次数。为什么？因为在这个忽略附近字符影响的源语言简单模型下，生成任何给定n个字符的源语言字符串的概率等于其中出现的字母的概率的乘积，也可以计算为源字母表中所有字母y的p(y(^freq(y(的乘积。因此，为了计算生成字符串的概率，假设每个x"真的"是y(其他都不是y(，我们将freq(y(更改为freq(x(。如果我们取log，我们得到的是源字母表中所有字母y上log(p(y(^freq(x((的和，而这个和正是最大二分完全匹配算法将最大化的值。
寻找最佳完美匹配
有一些算法可以在O(V^2E(时间内解决密切相关的最大权重二分匹配问题，这里相当于O(k^4(时间。这个版本的问题寻求最大化所有选择对的总和，同时遵守没有项目与另一集中的两个或多个其他项目匹配的约束，但不要求每个项目都与其他项目匹配。幸运的是，我们可以将该算法转化为一种算法，通过在每个分数上添加一个大数字M，非常简单地解决我们想要解决的"完美"变体：直观地说，这会导致算法尝试添加尽可能多的边(因为即使省略一条边也会有很大的成本，这使得这样的解决方案甚至比包含完整k条边的"愚蠢"解决方案更糟糕(，同时仍然迫使算法在所有k边解中选择最好的(因为所有这些解都包括来自添加的权重的相同kM贡献(。
本文描述了一种求解长度为26(a-z(的字母表为特例的同音替换密码的算法。这里提供了它们在C++中的参考实现。
该算法背后的基本思想(使用有向图频率爬山以避免多次解密(来自本文，并被(第一篇论文的作者(描述为解决单字母替换密码的已知最快算法。