文本解密,基于字母频率的方法(关于成本函数的问题)

Question

我想基于频率分析来破译文本.编程不是问题,但存在一些数学上的困难.

(不用担心,不是为了黑客攻击,我想要去Zodiac 340密码,但问题只是解释http://zodiackillerciphers.com/wiki/images/7/7d/340-cipher-hi -resolution.jpg,而不是关于密码的其他问题.)

我把它分解为5个与成本函数相关的简短问题,以显示我的努力,简短的答案很好,任何帮助赞赏.我的问题是成本函数中的值的差异非常小.

特定

1. 包含任意数量符号的文本,从现在开始称为密码.密码是英文的.密码中的每个符号仅代表一个字母,但一个字母可以通过几个符号表示.我们不知道是否有任何空格(但是必须由成本函数评估的字符串将以空格分隔并且只有字母AZ).
2. 字母频率分析(AZ和空格):单字母,字母对和字母三元组.4000个最常用的英文单词或"all"单词使用sowpods拼字游戏字典.

有关频率分析的问题:

1. 最好只检查最常用的单词或使用sowpods的所有单词(可能删除不在4000个最常用单词中的2个和3个字母单词)？
2. 对于字母对和三元组:最好是将它们的频率存储在全部,还是以P(A | B)的形式存储(A的概率跟随B)和P(C | AB)的三元组？

概念

如果不感兴趣,请跳过.我不想在这里详细介绍,有几种方法可以使用.粗略草图:

1. 生成(半)随机解决方案
2. 基于成本函数的解决方案的局部优化
3. 重新开始并转移一些获得的知识
4. 停滞一段时间之后,在本地优化之前在固定位置引入空格尝试相同的事情(如果消息没有空格)
5. 比较2个检索到的解决方案并返回更好的解决方案

成本函数

成本函数如何？一般可以表达为:

w1 * letterCost + w2 * pairCost + w3 * tripletCost + w4 * wordCost

并且所有轮动的总和是一个:

w1 + w2 + w3 + w4 = 1

关于成本函数的问题

3. 现在用简单的频率忽略单词(w4 = 0)你可以计算频率并取平方差(这就是我现在正在做的事情).我想知道的是:w1 = w2 = w3或w1 = 27*w2 = 27*27*w3更合理吗？

4. 如何处理条件概率？

5. 你如何结合关于单词的知识？只计算有多少真正的英语单词,可能按它们的长度加权,还是有更聪明的方法？

Answer 1

在我看来，你的问题源于过于笼统的概念。如果你不精确的算法，就不可能计算成本函数。我可以提出一种方法来实现您概念的精确第二点：

1. 计算随机的期望值（例如：如果您有 100 000 个字母，则随机三元组应出现 5 次）
2. 令n为密文中的字母数。然后为每个字母增加 Letter[y]、Pair[y][y+1]、Triplet[y][y+1][y+2] 的值
3. 如果某些数据的出现次数明显大于1中计算的值，则尝试判断您与答案的接近程度。

不过，第三点和“判断”是非常笼统的，但基于此我可以给你几个答案：

关于成本函数的问题

1. 最好只使用最常见的单词，因为它可以为您提供有关随机结果偏差的信息。保留所有话语不会给你带来任何利润。
2. 频率是我的建议。我找不到保持条件概率的任何用法。

成本函数

在我的例子中，算法的成本是 O( n ) + const （对于长单词，你可以考虑使用哈希表）+“判断”。问题依然存在，因为很多事情取决于“判断”将如何解决。

3. 我不知道你为什么选择这样计算成本函数，但对我来说 w1 = 27 * w2 = 27 * 27 * w3 听起来更合理，因为它不太可能比长单词的平均出现次数多。
4. 在我的解决方案中，使用条件概率没有必要也没有优势。
5. 这个问题是另一个大问题，在我看来与“生成（半）随机解决方案”有很多共同点。假设您猜到了字母“t”、“h”、“e”、“y”、……。您的算法应该检测单词“the”、“them”、“they”，但完全漏掉单词“and”、“work”、“no”、“will”。您可以使用单词的特征，例如“the”是常见前缀，“will”中的3个和4个字母相同等等。这使解决方案变得复杂，但应该会给出更好的结果。