【公布答案】豆瓣校招直通车解密
关于9月份发布的校招直通车考题贴,回顾请点击。
-------------------以下是本次出(工)题(程)官(师)原版解答----------------------
上图初看可能摸不着头脑,而聪明的同学很快就能想到电脑屏幕上的字母是密文,题目就是根据图片上的信息破解出原文。
解密的第一个关键在于要看出使用了何种加密方法。图中左边的六个轮子给出了提示,这是在二战时期由计算机科学之父艾伦·图灵(Alan Turing)和盟军的密码学家设计制造的机器 Bombe,其目的是破解纳粹德国用于加密军事情报的密码机 Enigma。
彼时,英国秘密情报局(也称军情六处 MI6,007 系列电影的主要题材)在布莱切利公园(Bletchley Park)设立了一个密码研究学校,召集了牛津剑桥的语言学家、数学家和英国最聪明的学生们从事密码破译工作。人们普遍认为二战时盟军在西欧的胜利能够提前两年,完全是因为 Enigma 被成功破译[1],而图灵正是找到破译方法的主要推动者。这是一段数学家拯救世界的极其传奇而热血的历史,后被改编成许多文学作品和电影。去年上映的电影《模仿游戏》就是描述了这个故事,想必感动了不少人。在《模仿游戏》的海报和剧照也曾多次出现这个图案。
在推断出密文是由 Enigma 加密后,接下来就去了解一下 Enigma 的加密原理。首先,Enigma 是一种替换密码。即将原文中的一个字母替换为另一个字母,从而得到密文。著名的凯撒密码就是一种简单的替换密码。
转子(Rotor)是 Enigma 的关键部件,它能将一个字母映射为另外一个字母。而转子的强大在于它会转,由于转子的起始位置不同,同一个字母在不同位置可能会得到不同的结果。例如 A 可能被加密为 E,而下一个位置 A 又被加密为 K。转子有 5 种型号,对应不同的字母映射。可以选其中的 3 个转子排列在一起像钟表的时分秒针那样轮转,使重复的概率进一步降低。德军就是将每天该用的三个转子的排列和起始位置作为密钥,每月做成小册子发到各军队中。[2]
反射器(Reflector)和最后一个转子相连,它使加密过程与解密过程变得一致,这样德军只要设置好转子的起始位置和排列,输入密文就能得到原文。但它也有一个致命缺陷,即加密的字母不可能和原文字母相同,这成为后来图灵破解 Enigma 的关键。[3]
替换密码破解的策略之一是利用字母在语言中出现的概率猜测加密的字母映射,例如英文中字母 e 出现的概率最高,但这对于 Enigma 这种映射结果可变的方式是不管用的。另外还有一种方式就是枚举加密方法,利用常见的英文单词 the, and 等寻找有意义的信息。Enigma 有 5 种型号的转子,从中挑选出 3 个有 60 种排列方式,每个转子的起始位置有 26 种选择,这样就有 60 * 26^3 = 1054560 种配置方式,在还没有真正的计算机的年代已经是很难暴力破解了,但对于计算机如此发达的今天简直是轻轻松松。后来德军改进 Enigma 加入了连接板(Plugboard),将多对字母两两交换,这就将可能的组合方式扩大到了一亿亿种。[4] 而为了简化,在这题中是没有设置连接板的。
解密的第二个关键就是找到原文中包含的单词。图灵就是根据经验德军情报中总会包含“天气预报”和“希特勒万岁”等词语,加上字母的映射环等信息排除了很多不可能的组合。而图上的六个轮子上面标出了字母 DOUBAN,不妨也加进词库试一下呢。
接下来就可以尝试解密了:
1、用程序模拟 Enigma。如果嫌麻烦的话,GitHub 上搜 enigma 也有一大堆现成的开源项目可用。
2、穷举转子和反射器的起始位置和型号,解码后看原文是否包含有意义的信息。
附上解密代码:https://gist.github.com/anonymous/8ffd8c6fad118c36f374
最后揭晓答案,加密前的原文是 DOUBANWANTAWESOMEYOU
Douban Want Awesome You 独一无二的公司期待独一无二的你
[1] [2] [3] [4] 引自维基百科 https://zh.wikipedia.org/wiki/恩尼格玛密码机
-------------------以下是本次出(工)题(程)官(师)原版解答----------------------
上图初看可能摸不着头脑,而聪明的同学很快就能想到电脑屏幕上的字母是密文,题目就是根据图片上的信息破解出原文。
解密的第一个关键在于要看出使用了何种加密方法。图中左边的六个轮子给出了提示,这是在二战时期由计算机科学之父艾伦·图灵(Alan Turing)和盟军的密码学家设计制造的机器 Bombe,其目的是破解纳粹德国用于加密军事情报的密码机 Enigma。
彼时,英国秘密情报局(也称军情六处 MI6,007 系列电影的主要题材)在布莱切利公园(Bletchley Park)设立了一个密码研究学校,召集了牛津剑桥的语言学家、数学家和英国最聪明的学生们从事密码破译工作。人们普遍认为二战时盟军在西欧的胜利能够提前两年,完全是因为 Enigma 被成功破译[1],而图灵正是找到破译方法的主要推动者。这是一段数学家拯救世界的极其传奇而热血的历史,后被改编成许多文学作品和电影。去年上映的电影《模仿游戏》就是描述了这个故事,想必感动了不少人。在《模仿游戏》的海报和剧照也曾多次出现这个图案。
在推断出密文是由 Enigma 加密后,接下来就去了解一下 Enigma 的加密原理。首先,Enigma 是一种替换密码。即将原文中的一个字母替换为另一个字母,从而得到密文。著名的凯撒密码就是一种简单的替换密码。
转子(Rotor)是 Enigma 的关键部件,它能将一个字母映射为另外一个字母。而转子的强大在于它会转,由于转子的起始位置不同,同一个字母在不同位置可能会得到不同的结果。例如 A 可能被加密为 E,而下一个位置 A 又被加密为 K。转子有 5 种型号,对应不同的字母映射。可以选其中的 3 个转子排列在一起像钟表的时分秒针那样轮转,使重复的概率进一步降低。德军就是将每天该用的三个转子的排列和起始位置作为密钥,每月做成小册子发到各军队中。[2]
反射器(Reflector)和最后一个转子相连,它使加密过程与解密过程变得一致,这样德军只要设置好转子的起始位置和排列,输入密文就能得到原文。但它也有一个致命缺陷,即加密的字母不可能和原文字母相同,这成为后来图灵破解 Enigma 的关键。[3]
替换密码破解的策略之一是利用字母在语言中出现的概率猜测加密的字母映射,例如英文中字母 e 出现的概率最高,但这对于 Enigma 这种映射结果可变的方式是不管用的。另外还有一种方式就是枚举加密方法,利用常见的英文单词 the, and 等寻找有意义的信息。Enigma 有 5 种型号的转子,从中挑选出 3 个有 60 种排列方式,每个转子的起始位置有 26 种选择,这样就有 60 * 26^3 = 1054560 种配置方式,在还没有真正的计算机的年代已经是很难暴力破解了,但对于计算机如此发达的今天简直是轻轻松松。后来德军改进 Enigma 加入了连接板(Plugboard),将多对字母两两交换,这就将可能的组合方式扩大到了一亿亿种。[4] 而为了简化,在这题中是没有设置连接板的。
解密的第二个关键就是找到原文中包含的单词。图灵就是根据经验德军情报中总会包含“天气预报”和“希特勒万岁”等词语,加上字母的映射环等信息排除了很多不可能的组合。而图上的六个轮子上面标出了字母 DOUBAN,不妨也加进词库试一下呢。
接下来就可以尝试解密了:
1、用程序模拟 Enigma。如果嫌麻烦的话,GitHub 上搜 enigma 也有一大堆现成的开源项目可用。
2、穷举转子和反射器的起始位置和型号,解码后看原文是否包含有意义的信息。
附上解密代码:https://gist.github.com/anonymous/8ffd8c6fad118c36f374
最后揭晓答案,加密前的原文是 DOUBANWANTAWESOMEYOU
Douban Want Awesome You 独一无二的公司期待独一无二的你
[1] [2] [3] [4] 引自维基百科 https://zh.wikipedia.org/wiki/恩尼格玛密码机
没有plugboard!不是逗我么,白搞
果然是苹果死忠粉
> 我来回应