密码的自动化密码分析

• 源代码 - 13 Kb
• 演示项目，包含一个示例书籍 - 323 Kb

我假设您知道什么是密码电文。一个密码电文破解程序可以被认为是两个程序一起工作。

• 一个生成一系列可能的解决方案
• 一个评估每个解决方案

生成器

do
	generate a random initial permutation
	do
		for each pair of letters in the permutation
			swap the two letters
			evaluate the permutation
			if worse, then swap them back
		end for
	while there was an improvement
	if this was the best solution then save it
until you are bored

评估器

for each subsequence of 4 letters (each 4-gram) in the solution
	add the cost associated with the subsequence
end for

其中与每个 4 个字母子序列相关的成本与它在书籍文本中的频率的倒数成正比。如果频率为零，则分配一些最小的基线频率。这种评估方法是假设每个 4-gram 已经出现了无限次之后的卡方成本的限制点。这种假设是完全错误的，但它使评估线性化，因此速度很快。

评估示例

if the book text is:
"to be or not to be"

and the cryptogram solution for evaluation is:
"...qwe rwzxcrb..." --> "...for nothing..."

then the cost would be:
...
+ cost (for ) = 1/epsilon
+ cost (or n) = 1/1
+ cost (r no) = 1/1
+...

because "for " never occurs in the book text and "or n" and "r no" each appear once.
For real, you would use a *whole book* for the book text.

假设问/答

问：你为什么使用 4-gram 而不是 3 或 5？
答：因为预先计算的 4-gram 成本表适合 4 兆字节的 RAM，这是一个合理数量，期望人们拥有。较低的计数给出较差的结果，而较高的计数需要使用哈希表，这将使代码更加复杂，并且会增加决定哈希表大小的复杂性。我发现使用带有空格的密码电文时，你可以获得高达 6-gram 的改进，而使用没有空格的密码电文时，你可以获得高达 5-gram 的改进。在那之后，我相信书籍文本成为了限制因素，而其他解决问题的办法将更合适。

问：程序可以修改为解决没有单词之间空格的密码电文吗？
答：是的，实际上，代码比解决有空格的密码电文更简单。只需调整过滤文本的函数，不要理会空格即可。类似地，您可以通过在洗牌和字母交换时循环遍历 27 个元素而不是 26 个元素来解决空格像第 27 个字母的密码电文。

问：您是否将这些方法应用于其他古典密码的密码分析？
答：没有。如果你想这样做，请继续 - 这就是这篇文章和代码的目的。

问：你的代码看起来就像我的狗吐出来的东西！我可以建议一些修改吗？
答：是的，请。这实际上是我第一次编写代码，可能会有人看，我很感谢任何建议。不过，不要进行优化，除非它也使代码更小、更简洁，并让我感觉温暖和模糊。

问：我运行了你的示例程序，但它只给出一个错误消息然后退出。怎么回事？
答：该程序在没有要读取的示例文本的情况下是无用的。如果您希望它破解莎士比亚的引言，请从网络上获取一些，并将文件重命名为 "book.txt"，并将其放在与可执行文件相同的目录中。或者，如果您希望它处理法语，请将 "cyrano.txt" 重命名为 "book.txt"，并将其放在同一个文件夹中。

问：如何保存示例程序的输出？
答：首先确保程序已停止（如不再尝试破解密码电文），然后从窗口中剪切并粘贴文本。