BrokenEnigma-WriteUp


BrokenEnigma WriteUp

什么是Enigma

恩尼格玛密码机 - Wikipedia

不太严格地来讲,Enigma加密系统可以视作一个权值近似随机的凯撒密码双向算子。 这使得频率分析对其无效。 当然,它也有弱点,也就是后来的已知明文攻击

Enigma的设计初衷是通过其3个转子(德国海军版为4个),每个转子将一个字符映射到另一个字符,且每次对单个字符加密或解密后,映射关系都会变化,带来庞大的密钥空间,使得密码分析人员难以通过暴力方式进行破译。

加密过程分析

这里省略电路和显示部分

转子

转子组成了恩尼格玛密码机的核心部分。一系列由弹簧承载的黄铜管脚呈环形排列于其中一面,而另一面相对应的则是圆形的金属触点。管脚与触点代表的是字母表上的全部字母,典型的排列就是A-Z(以下的介绍全部假设转子为这种排列方式)。当两个转子的位置相邻时,其中一个的管脚就会接触另外一个的金属触点,这就形成了一个通路。在转子内部,有26条金属线将一面的管脚与另一面的触点连接起来,这些金属线的排列方式在每个转子内都有所不同。当被放进恩尼格玛密码机后,一个转子可以有26种排列方法。

此时,我们可以认为转子是一个对于A-Z空间内字符的双射

这也是其能同时加解密的重要基础。

转动

为了避免产生简单(并且容易破译)的加密信息,有些转子在操作员连续按下同一个键时也会转动。这就保证了每次按键得到的结果都不一样,也就会产生很难破译的复式密码。

在德国防卫军的恩尼格玛密码机中,每个转子都有一个可调节的带缺口的外环。5个最基本的转子(I-V)各有一个缺口,而附加的转子VI、VII和VIII各有两个缺口。在转子转动到某一点时,第二个转子的防倒转爪正好位于它的缺口之内,这就使第二个转子在下一次按键后也会转动。当防倒转爪位于缺口之外时,它就只会沿着另一个转子外环的光滑边缘滑动。在所有转子都只有一个缺口的系统中,第一个转子每转26次就会使第二个转子转动一次,同样的,第二个转子每转动26次就会使第三个转子转动一次。第三个转子转动的同时第二个转子也会转动。

这里较难理解,可以想象一下水表示数器或者体育记分牌的原理。

当拥有三个转子,并且第一和第二个转子的外环各有一个缺口时,一台恩尼格玛密码机就会拥有\(26×25×26 = 16,900\)个组合(不是\(26 X 26 X 26\)。因为第二个转子会与第三个转子一起转动,这里很难向大家解释,就暂且这么认为吧)。在德国军队的实际使用中,为了安全,每条信息的长度都被限制在几百个字母以内,所以在同一条信息中输入同样的字母产生同样的密码的几率是很小的。

当按下一个键后,转子会在电路接通之前转动。

之前!

反射器

恩尼格玛密码机的最后一个转子之后都有一个反射器,反射器是恩尼格玛密码机与当时其它转子机械之间最显著的区别。它将最后一个转子的其中两个触点连接起来,并将电流沿一个不同的路线导回。这就使加密过程与解密过程变得一致。但是,反射器也使恩尼格玛密码机具有了如下性质:加密后得到的字母与输入的字母永远永远不会相同。这在概念上和密码学上都是一个严重甚至致命的错误,这个错误最终被波兰和英国密码分析人员利用,最终使得Enigma加密系统土崩瓦解。

接线板

接线板上的每条线都会连接一对字母。这些线的作用就是在电流进入转子前改变它的方向。为了解释它的原理,我们把E插口和Q插口连接起来。当操作员按下E键时,电流就会先流到Q插口(相当于按下Q键)再流经转子。接线板上最多可以同时接13条线。

电流会从键盘流经接线板,之后进入转子。接线板上的每个插口内都有两个插孔,当将插头插入时,上插孔(连到键盘)与下插孔(连到转子)之间的连接就会被断开。另外一个插口内的上插孔会与此插口内的下插孔连接起来,而下插孔会与此插口内的上插孔连接起来,这样就完成了两个插口之间的连接。

依然,相当于双射,否则加解密无法结合。

数学描述

恩尼格玛对每个字母的加密过程可以以数学的角度看作为一个组合过程。假设我们有一台德国陆军/空军版3转子恩尼格玛密码机,让P表示接线板的连线,U表示反射器,L、M、R表示左、中、右转子。那么加密后的信息E就可以表示成

\[ E = PRMLU{L^{ - 1}}{M^{ - 1}}{R^{ - 1}}{P^{ - 1}}{E_0} \]

关于此道CTF题目

转子转动的时机出现了错误,在电路接通之后转动了,改写代码即可修复。

源代码可在我的Github上找到

题目背景

我的Fork原项目是一位SE在NASDAQ的获奖项目,但是我尝试了几组输入,发现输出与预期不同,对代码审计后发现代码有误,已PR。截至发文时未Merge。

现实中的Enigma是怎么被攻破的?

自己了解更有意思,如果感兴趣的人足够的话,我可以在周会上浅谈下(笑)。


文章作者: sfc9982
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
  目录