Enigma密码机密码分析中的统计分析(保护Ultra中的情报源)

机器算法验证 假设检验 优化 参考
2022-03-30 14:02:42

在第二次世界大战期间,英国人正在对德国 Enigma 密码机和随后的信号情报进行密码分析。

其中一个问题是关于保护情报来源,例如参见http://en.m.wikipedia.org/wiki/Ultra#Safeguarding_of_sources

在最近一部关于Enigma密码破解的电影《模仿游戏》中,艾伦·图灵的角色指的是使用“统计分析”来保护源头。在说什么分析?

警告:以下是电影剧透。

STEWART MENZIES [军情六处特工]

……你为什么要告诉我这个?

艾伦·图灵

我们需要你的帮助才能让海军部知道这一点。军队。英国皇家空军。没有人知道我们破解了 Enigma,甚至 Denniston [负责密码分析的皇家海军军官] 也不知道。

斯图尔特·孟席斯

谁正在让你被解雇。

琼·克拉克 [密码分析师]

你会照顾好它的。

艾伦·图灵

当我们开发一个系统来确定要采取多少情报时。阻止哪些攻击,让哪些攻击通过。统计分析。赢得战争所需的最少行动次数,但在德国人起疑之前我们能够采取的最多行动。

斯图尔特·孟席斯

你会把这一切都交给统计数据吗?

对数学?

艾伦·图灵

正确的。

2个回答

在说什么分析?

该剧本由格雷厄姆·摩尔根据安德鲁·霍奇斯的一本书编写。

我们有一个戏剧性的(可能是虚构的)对话,图灵可能有过,或者可能有过一次模糊的喜欢,或者他可能从来没有真正有过,但它的戏剧性目的是传达一些原本不太容易或不太容易的东西可观察传达。如果不问他,猜测编剧的想法可能很困难。

我们可能会做出猜测,但最终它们可能仅此而已。

以下内容很清楚:

  • 如果他们对截获的每一个信号采取行动,很快就会清楚,对此的解释是代码可以被破坏,在这一点上,所有能够做到这一点的未来价值都将丢失。

  • 如果他们从不使用知识做任何事情,他们当然会学到很多东西,并且不太可能被发现,但他们无法从中获得运营收益。

  • 如果他们谨慎地利用信息,只在最重要的时候采取行动,他们或许能够获得丰厚的回报。

  • 他们使用信息的次数越多,他们发送的“信号”就越多,他们可以解码这些信息。

那么,在一个非常明确的意义上,使用 Enigma 的人有一个统计问题(又一个任务失败了——也许是因为敌人准备充分;我们牢不可破的密码被破解了吗?)。

如果它没有被破坏,那么更改代码将是一个困难、昂贵(甚至有些冒险,因为一个全新的、仓促构建的系统与一个经过验证的真正安全的系统相比可能会以意想不到的方式易受攻击)过程——你真的如果您不需要,希望避免更改它。另一方面,如果它已被破坏,您确实需要使用新代码。

因此,Enigma 用户将试图从盟军的行动中获取微弱而嘈杂的信号——我们甚至可以将其框定为假设检验——他们“知道”的内容是否超出了偶然性所能解释的范围?(或者作为一个决策理论问题,通过在相关动作的数据存在的情况下最小化更改代码和保留代码这两个不同动作的损失函数)

用现代术语来说,博弈论*会建议对于盟友来说有一个最佳的混合策略——对于使用特定信息的任何给定水平的利益,都有一个相应的概率你应该使用该信息(实际上,有一些情况您可能能够伪造一个看似合理的机制,您知道通过该机制不涉及代码破坏——但如果你开始这样做,你也会冒着被发现欺骗的风险——甚至更多的人知道这样的事情很大的风险;在上面的交流中提到了这种“知道的人越多”的风险)

*(图灵可能有也可能没有任何正式的背景,但其中一些想法可能对他来说很清楚)

所以图灵是对的——考虑到他们可以破坏消息(至少非常频繁),他们将拥有非常具体的重要信息流,这将带来巨大的好处。但是,如何最好地使用这些信息以避免*传达代码可以被破坏的信息?概率(/统计)方法实际上是一种非常聪明的策略,因为它允许您在给定的信息使用水平下尽可能难以检测到信号。

事实上,你“挑选”的次数越多,就越容易发现自己知道,因为无论你用来选择什么基础,都可能会被偶尔将正确的虚假信息输入通信系统的人利用,以期抓住你(如果似乎倾向于对特定类型的信息采取行动,你可以专注于那些......并迅速揭示它们是)。[相比之下,精心定制的概率方法使得对这种策略的每一种反应都相当嘈杂。所以你需要观察更长时间才能真正确信代码被破坏了。]

* “避免”是指他们可以从中获得尽可能多的总收益

由于在这类问题中您缺乏数据,因此您必须在统计模型中包含外部知识。在模型中包含先验信息是贝叶斯模型的一个关键特征许多消息来源(例如这里这里)引用了某种贝叶斯分析在二战期间用于不同目的,例如破解谜团、猎杀 U 艇等。实际上,即使在今天,贝叶斯估计也用于类似的目的(例如对于搜索和救援,请参见此处此处)。

请注意,第一次使用计算机来破解 Enigma,现在计算机也是基于模拟的贝叶斯估计方法的关键部分。