密码学分析-Enigma机破解

授课老师：张秉晟

bingsheng@

Enigma机介绍与破解密码与加密技术Enigma密码机01PARTONE1.1背景1920年代早期开始被用于商业，也被一些国家的军队与政府采用过，在这些国家中，最著名的是第二次世界大战时的纳粹德国。Enigma密码机的大部分设置都会在一段时间（一般为一天）以后被更换。1932年，波兰密码学家马里安·雷耶夫斯基，杰尔兹·罗佐基和亨里克·佐加尔斯基破译了德军的Enigma机，但随后德军对Enigma机进行了改进。波兰战败后，将研究成果分享给英法，随后英国的图灵和其他专家共同破译了Enigma机。1.2加密原理Enigma密码机的构造01输入端，每次输入一个英文字母。包含26个英文字母的键盘03由快速扰频器、中速扰频器、慢速扰频器组成，进行加密工作。扰频组合02

将1对字母相连接，进行加密工作。线路接线板04保证加密后得到的字母与输入的字母一定不相同。反射器05输出端，在键盘上输入一个英文字母后，灯盘上都会有一个英文字母亮起来，代表明文字母加密后的所对应的密文字母。包含26个英文字母的显示灯的显示灯板1.2加密原理Enigma密码机的加密原理0201Enigma密码机加密是一种多表代换的对称加密算法，逐字母加密。Enigma密码机是对称加密，加解密过程一致，不论加密还是解密。明文空间密文空间密钥P

∈{A}n，A表示字母表{A-Z}C∈{A}nK1,K2，分别表示接线板和三个转子的初始位置1.2加密原理Enigma密码机的加密原理02扰频组合RT反射器0304R-1扰频组合01标有26个英文字母的线路接线板S05S标有26个英文字母的线路接线板加解密算法得到密文C，解密同理。因为加解密算法一致，所以此处不作区分。设置好K1和K2后，明文P

经过

C=EncK1,K2(P)P=EncK1,K2(C)1.2加密原理Enigma密码机的关键元件——转子完整的转子转子拆开后的零件工作原理每个转子额左右两侧各有26个点位，分别代表A-Z这26个字母。信号从一边进去，从另一边出来，但是在制造转子的过程中，位于转子左右两侧的26个字母的对应关系被打乱（单个转子的功能相当于一个单字母替换表）：侧视图，可以更清楚的看到位于转子两侧的26个点1.2加密原理Enigma密码机的关键元件——转子单个转子只能提供一个固定不变的密码表不安全德国人的改造：他们在恩格玛机上使用了三个串联在一起的转子三个转子的替换就相当于一个三轮替换。多表替换也并不安全。单纯的将三个转子串联起来，他们还是只能提供一个固定不变的密码表。1.2加密原理Enigma密码机的关键元件——转子德国人的改造：给三个转子加入新特性，做到密码学家们梦寐以求的每加密一次就换一次密码表的效果每输入一个字母以后，第一个转子就会自动转一格，当第一个转子转完一圈时，会带动第二个转子转动一格。同理，第二个转子转动一圈时会带动第三个转子转一格（类似于表盘上秒针、分针、时针的转动关系）。三个转子每个都有26种可能的位置三个转子一共可以提供263=17576个不同的密码表德国人不满足于此，继续改造：将三个转子设计为可以相互交换位置的形式三个转子可以有3！=6种不同的排列方式

密码表的数目又增加到17576*6=105456，也就是大约十万个德国人仍不满足：又增加了插线板和转子的数量，将密码数量进行一步扩大了1000亿倍1.2加密原理Enigma密码机的关键元件——转子信号输入转子的路径字母A从键盘被输入依次经过三个转子加密后到达反射器在反射器这里又被替换成另一个字母沿着转子返回加密最终输出字母G1.2加密原理Enigma密码机的关键元件——反射器反射器的重要性质性质一：反射器使得恩格玛机的加密过程是自反的。也就是如果输入A得到G，那么在机器配置不变时，输入G一定会得到A转子配置不变字母从同一边到另一边走的永远是一条固定的路径意味着上图中红色和蓝色路径是固定的反射器不变意味着绿色路径也是固定的那么就意味着字母A沿着红色路线、绿色路线、蓝色路线，一定会得到字母G。同理，字母G沿着蓝色路线，绿色路线、红色路线也一定会得到字母A。性质二：一个字母的加密后的输出结果绝对不会是自身假如字母A想让加密结果是自己，那么它必须沿着红色路径进入，并且沿着红色路径返回才行，但是反射器的加入，强制输入输出不相等，导致上述条件永远得不到满足。第二个性质看起来是一个优点，毕竟把一个字母加密成自身不就等于没有加密吗？但是这个看似优点的性质日后反而成了恩格玛机的一个重要漏洞。1.3安全性分析凯撒密码Enigma机本质多表替换维吉尼亚密码有字母频率的漏洞，因为他们的加密都是使用的同一张密码表Enigma机每加密一个字母，就会转动一下，相当于换了一张密码表，基本可以做到加密一个字母就更换一次密码表并且不重复。1.3安全性分析没有了字母频率攻击的“后顾之忧”，那我们再考虑暴力破解：对于3个转子的Enigma机，他的转子排列和初始位置的组合K2只有105456大小。这显然不够，我们来考虑接线板（K1）的作用。26个字母，有t根连线，那么就有种接线方式，如果有6根接线，t=6，那么K1

就有总密钥空间大小：1.3安全性分析接线板的重要性接线板对整体密钥空间的扩大起重要作用。穷举的不现实性二战时期没有高速计算机，通过人工穷举密钥，对于这种数量级的密钥空间是不现实的。即使是使用计算机进行穷举，大部分电脑的单秒运算量在10的七次方到10的九次方之间，我们假设每秒穷举109个密钥为例，筛选出正确密钥的期望时间约为400000年。综上可知：1.3安全性分析德军使用Enigma通信的操作流程010203使用会话秘钥来加密明文将这6个字母发送出去使用日秘钥加密一个会话秘钥（两次）三个字母例如：日秘钥ABC，会话秘钥QWE，那么QWEQWE

DCYXEV加密两遍是为了防止出现错误德军目的：为了保证每条信息都是用不同的密钥进行加密的，避免了使用同一个密钥加密过多内容而被破解者找到破绽。被波兰人破解：波兰人从这六个字母中找到了规律，实现了的初步的破解。但波兰的破解不具有普遍性，德军改进Enigma机和操作流程后便失效了。

ABC1.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给1.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给接线板K1在键盘上输入字母H（7）发现H没有与其它字母相连H首先经过接线板（Stecker）经过接线板后明文没有发生变化，仍为H（7）。1.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给2.正向扰频器组合（Rotors）通过密钥K2（4,4,16）将转子转动到相应位置。再将H（7）分别通过这三个转子。H对应位置为7，将7作为输入通过快速转子找到此时的第7个位置对应的左侧数字为11再找到右侧对应的11位置为6，所以经过快速转子，输出变为6然后再以位置6作为输入通过中速转子此时位置6对应的左侧数字为10找到右侧对应的10，位置为23，经过中速转子，输出变为23再将23作为输入通过慢速转子，位置23对应的左侧数字为13找到右侧对应的13，位置为7。经过慢速转子，输出变为71.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给3.反射器输出结果为21正向扰频器输出的结果为7将7作为输入，通过反射器1.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给4.逆向扰频器组合将上一步的结果21作为输入先通过慢速转子此时位置21对应的右侧数字为15找到左侧对应的15，位置为25通过中速转子输出变为24最后通过快速转子输出变为201.4加密算法实现加密算法的具体实现过程例：待加密字符为‘H’，K1,K2为题目所给5.接线板K1将20作为输入，通过逆向线路接线板得到输出为12，对应字母为M最终M作为最终结果在显示灯板上显示出来同理，可以对E进行类似的加密得到U1.4加密算法实现关键函数加密结果示意图Enigma机破解02PARTTWO2.1历史上的解密英法尝试破解0203但即使是最简单的3个转子，6对接线板的Enigma机，秘钥空间都有1016的数量级，以当时的算力是不可能破解的。于是英法放弃了对Enigma机的破解。Enigma机在投入使用之后，英法的情报部门曾经尝试破解。01尝试破解遇到困难放弃破解2.1历史上的解密波兰破解Enigma机波兰面对黑云压城的德军，没有放弃的借口波兰数学家雷耶夫斯基（MarianRejewski）手动破解Enigma机（参考Enigma机的破解一文）将秘钥空间降低到10万级别通过数学分析，避免了接线板的转换030201破解Enigma机的第一次突破2.1历史上的解密波兰破解无效德军改进了Enigma机增加转子数量接线板交换的字母从6对增加到10对使用日密钥加密会话密钥时不再加密两遍让波兰的破解无效1939年，德军入侵波兰，波兰人将Enigma机的复制品和掌握的破解方法提供给了英法。接下来就是英国数学家图灵的表演时间了。2.2Enigma机破解原理2.2.1寻找明密文对关系–Ciber因为Enigma反射器和转子的设计所以在Enigma机加密过程中，一个字母是不会被加密成自身的。如上题H加密成M的过程，如果H被加密为自身，那么逆过程和正过程必须完全一致，而因为反射器的存在，正逆两个过程一定不会输出一样的结果。根据Enigma的这个性质，我们就可以猜测明文的几个单词，并找到他们可能的位置。德国人在信息正文中喜欢用固定的词组，比如HeilHitler（希特勒万岁）等。德军喜欢在早上发送一条当天的天气预报，所以在早上6点钟截获的电文开头中肯定包含wetter（天气）这个单词。综上可知，在密文中猜测出几个单词的明文并不困难，因为德国人在信息正文中喜欢用固定的词组。2.2Enigma机破解原理2.2.1寻找明密文对关系–Ciber用wetter在密文段上滑动比较可以确定wetter可能的位置也就确定了它对应的密文可以理解为有限的选择明文攻击。将攻击时间｜K1｜*｜K2｜减少为｜K1｜+｜K2｜2.2Enigma机破解原理2.2.2通过环路屏蔽接线板在解题过程中，三个Ciber都经过尝试，这里用Ciber1来举例。2.2Enigma机破解原理2.2.2通过环路屏蔽接线板这样就可以消除掉接线板的作用，我们要利用这个环，通过筛选缩小密钥空间。2.2Enigma机破解原理2.2.2通过环路屏蔽接线板首先我们要遍历所有的转子组合，也就是26*26*26=17576种K2，每一种K2下，我们让v1遍历a-z。然后在上述转子状态下进行加密得到v2、v3、v4。判断v4是否和v1相等。如果相等，说明这一组[k2,v1]是满足这个环的。把所有的可能秘钥都记录下来形成一个较小的可能秘钥空间。前面提到，这个Ciber中还有另一个环E→L→O→E，此时我们只需要在第一个环筛选出的可能秘钥空间中，再用第二个环筛选一遍，就可以进一步缩小密钥空间。2.2Enigma机破解原理2.2.2通过环路屏蔽接线板秘钥筛选分析我们在遍历的过程中，对于有一些k2，可以让某一个字母经过环之后加密成自身，但是有些k2不行，我们称前一种为possibleK2，后一种为impossibleK2。对于impossibleK2，也就是说，在这种转子组合下，26个字母都不能被加密成自身。我们假设每个字母被加密后变成任一个字母的概率都是一样的，虽然这个假设对某一个k2是不合理的，但是考虑所有的秘钥空间，可以认为概率相等，那么impossibleK2就是一种”错排”，而这种”错排“一共有:总的字母排列有26!种，所以impossibleK2的比例就是因为我们的转子的内部连线是不能更改的，只能对转子进行转动，因为我们的密钥空间没有26!那么大，但是经过筛选之后，发现，通过一个环路筛选出的possibleK2占总K2的比例是这也说明我们的假设是比较合理的