微信号:MathAndAlgorithm

介绍:从生活中挖掘数学之美,在实践中体验算法之奇,魅力旅程,从此开始!

悄悄话都是些什么姿势?恩尼格玛和他的爸爸们到底都是些什么鬼?| 游斯彬专栏

2018-04-09 21:05 算法与数学之美

 (定场诗)

伤情最是晚凉天,憔悴斯人不堪怜;邀酒摧肠三杯醉,寻香惊梦五更寒。(此处应有赞美声)


>>>> 


各位观众大家好,我又来讲数学了。你们看看为了说个评书我容易嘛我,专门配了个醒木,这回还弄了个“定场诗”,讲的好不好是水平问题,装备其不其就是态度问题了。今天咱们继续讲密码学。




上次咱们讲到波兰是二战时期的弱邦小国,但是却是破译恩尼格玛的桥头堡,而最终的破译奠定了关键的数学基础。不过他们,且按下不表,咱们今天就来聊一聊,“恩尼格马”的前世今生,有道是,“不知道老虎的牙有多利,就不知道打虎的汉子有多猛!”也就无法体会到,数学在二战中作为破译“恩尼格玛”的利器是有多“犀利”!而您才能知道数学家,有多牛!



“恩尼格马”是个什么东西呢!人类历史上首台密码机,而且是“数千年来加密技术的大成者”!融合了各种古代密码加密系统的精髓,所以在说他之前,还得聊聊他的爸爸们。

加密系统的本质,就是“单向函数“,信息x被加密变成密文y,本质就是信息x经过函数f的变换变成了密文y,就是f(x)=y,函数f也称为密钥。但对于有效的密码的要求是特别的是,必须要求反函数不可求,不然就破译了。

 




举个例子,古代有部军事著作叫“六韬”咱们常说的“韬略”那个“韬”说的就是这本书。书里面有一章叫龙韬,主讲战略,就记载了中国古代最早的密码系统应用。


相传,商纣王末年,姜太公辅佐文王伐纣。有一次,没打过让人家围了,弹尽粮绝之际,想派人突围,但是身边大将都再据守要塞,而且敌人都认得,目标太大,离开不得。找谁好呢?找个机灵的小卒乔装突围,回朝通报,但怎么能让文王相信他是姜子牙派来的呢?还得保证消息不泄露,就算沿途的商军抓住他了,也不能发现他就是信使。怎么办呢?老姜急中生智,就将文王赠与他的鱼杆子切下一节,让他带回国了,以示求援之意。后来,信使折回朝中,面见了周文王,文王迅速明了其意,亲率大军,赶往战场,解了姜太公之危。

鱼竿不仅能钓鱼,还能发送密文


后来,老姜头儿就发现这招好,干脆,把自己的鱼干切成了N个长短不一的短节,分别代表,胜利、求援、被围、撤退、进攻等不同的意思,这就是再定义函数f的运算准则。到后来啊,而且这就是单向函数。你看f(求救)=鱼竿5厘米;f(胜利)=鱼竿6厘米,加密起来很简单,但基本没有解密的可能,你就算截获了“鱼竿”,你怎么能知道他是求救的意思还是就是一节小木棍?

 



书归正传,总结起来恩尼格玛的爸爸有俩个。第一个叫“单表加密系统”,起源于凯撒大帝时期的“特洛伊之战”,叫“凯撒密码”。咱们前文书讲过,是一种“错位型”密码,a变d,b变e,顺着往后挪,乍一看apple,变成dssoh,挺唬人,但其实总共25种变化,试吧试吧,就出来了。


凯撒密码,错位变化字母,但是好破译


所以很快就被破译,就出了“变种” 第二代单表加密密码,也叫“简单替换密码”!怎么玩儿呢?我按顺序后错,你不是就很快“暴力破解”了嘛,那我这样,我将字母的变换不按顺序来了,原来我是按顺序换a变b,b变c,c变成d。。这回我随机换,a变b,b变z,z变x,x再变c。别小瞧这个小变化啊,就根本不可能试出来了,暴力破解的难度一下就呈指数型上涨了!直接变成了26的阶乘,约等于4*10的26次方!400亿亿亿次!这一下就把手工暴力破解的可能性基本降到了0,单向函数基本成立!


维吉尼亚密码是放在坐标方格中的,这个方格纸叫做维吉尼亚方格,它的横竖都有26个格。第一行和第一排的字母是按字母表的顺序排列的,不过接下来就是一位一位地位移了。


也因为这个小变化,要直到1000年后的,公元九世纪,才最终被阿拉伯的数学家找到破解他的方法,也是唯一的弱点!“频率”!怎么回事儿呢?这个数学家通过反复观察这套系统的原理,突然想到,哎?但凡拼音文字,都是有一定之规,在行文措辞上是有常用词汇的,就像咱们说话,你好啊、再见啊一样,老出现,对应的也是有常用字母的,像五个元音aeiou。而且他发现,这些个词汇、字母在每一篇文章中都大致呈差不多的频率出现。那你把a替换成了b,原本a是明文里最高频率,在你的密文里b,就变成了最高频率,其他的也都如是,所以他就统计了大量的文章去找字母频率,再带入到密文里,把频率一一对应,瞬间就把这套加密系统破译了!


 我就说啊,如果你想知道人类智慧有多光辉、想象力有多灿烂,其实只要看看“加密与破译”的博弈就可以了,已经展现的淋漓尽致了。


又过了几百年,有个叫“维吉尼亚”的法国数学家数学家,又发明了“第二个爸爸”,所谓你有长粱计,我有过墙梯,他就发明了多表加密方式。啥意思呢?就是,第一行a变成b,b变成c,c变成d,第二行不这么变了,变成a变成x,x变成别的什么,第三行再变,第四行还变,这个时候如果你把变化规律列个表写下来,就出现了一个字母变换的方形表格。如第一行a什么什么,b什么,第二行a又什么什么,b又什么什么,他是个方的。这种加密可就厉害了。字母之间几乎没有“频率差异”,或者说与正常语言的频率完全不同!字母间的使用频率被加权平均了!这个厉害了啊,可谓独领风骚数百年,没人能破译!


但是他的问题的是,如果“密钥的长度”,也就是方表的边唱几乘几,太短,比如1行,敌人就很容易猜到他的规律,就基本是单表加密那很容易就用频率发破解了。但如果太长了呢?比如30行,用起来就废了劲了,每一行都要重新加密,抄写极不便利,不光敌人敌人破译费劲,自己人的解秘也费劲。老得查表。恨不得写个100字,加密解密三天。。。所以“密钥”一般能横纵7、8行就不错了,而且因为操作性不强很长时间就被束之高阁,你安全归安全,但是用着不合算。

 这两种密码,基本就是二战之前的密码的精华了,各自解决了原始密码的问题,却各自都留下了一个破绽!单表加密的好处是,暴力破解极难,但如果你统计频率。。就废了。多表是,我可以规避频率。。可是要想加强强度,用着就费劲!





 而,恩尼格马,是把他俩的优势呈指数型放大,而且全然规避掉了他的弱点!才使得,波兰数学家在获取了“恩尼格玛”之后,陷入了,更深层次的绝望!如果你没见过这台机器,你都根本想不到他到底是怎么加密出来的!

他啊,先通过3个转子,也就是3个标有26格字母的轮盘构成,将每一封情报进行“多表加密”,使得密钥的最大长度就达到了26的三次方17000多,再接入一个“连接板”,把加密后的密文的字母进行两两置换,进行一次单表加密,您要知道经历过“多表加密”所以再做“单表”的时候就通过频率法就没用了,因为单表加密前已经把字母频率加权平均藏起来了。反而把“多表”的“密钥”藏的更加的隐蔽!着就能有1000亿多种变化!但您可能说了,密钥这么长不是“不便操作”嘛,密钥长度10000多怎么查表抄录啊?

密码机的转子组。三个转子位于右边的固定接口和左边(标着B)的反射器两个装置之间


这就是,恩尼格玛,最绝的地方,他自带一个反射镜,从机器左边输入明文,自动加密成密文输出;如果你是友军已知“密钥”,将转子的排列按照“正确方式”设定好,你从右边把密文输入进去,根本不用查抄表格,明文自动从左边显现,完全不需要查表!这也就是为什么德军可以动不动发动闪击战!因为德军可以通过恩尼格码将“电报”发送、接收、加密、解密的时间控制在半小时,就极大程度的加强了他部队的配合能力,将他的机械化兵团的优势运用到极致!

 

在键盘上打出普通的字母,电流就沿着接触点流动,流到转子的另一个 触点,显示屏上相应的字母就亮灯。如果把转子转到不同的位置,就改变了接触点连接键盘的方式。这样打入同一个字母,就可能产生不同的密码字母。


而盟军呢?同时期,加密、解密的周期是3个小时,而且密码还老被破,就根本无法形成大兵团对于突击情况的迅速应对,所以,为什么德国的著名将领隆美尔被称为沙漠之狐呢?就是因为他快,机动速度贼快,英军与德军一遭遇,马上开打,德军这边指挥若定,英军呢?与德军一遭遇,光说一句。。我看见德军了啊,打不打?

3小时过去了,等收到一句“打”。。。6格小时过去了。。这边都被消灭了。。。。德国人都撤了。。。这也就是为什么恩尼格玛可以在二战初期让德军可以取得如此辉煌的战绩,以一挑了欧洲各国一群。



好!终于把,恩尼格马讲完了。。。下一回,咱们接着讲,立下汗马功劳的“波兰人“,欲知后事如何,请听下回分解,波兰三杰!

∑编辑 | Gemini

来源 | 游斯彬 Mathaholic游斯彬


算法数学之美微信公众号欢迎赐稿

稿件涉及数学、物理、算法、计算机、编程等相关领域

经采用我们将奉上稿酬。

投稿邮箱:math_alg@163.com

 
算法与数学之美 更多文章 吴军:数学,为人生之题解出漂亮的答案 数学的关键是思想 为什么要从自然数扩大到实数,进而扩大到复数? 时间之箭:从熵到大爆炸再到万物理论 我为什么鼓励你读博士?
猜您喜欢 自以为是 【CCTC 2016大牛说】六位资深实践者寄语2016中国Spark技术峰会 最新数据:来自OpenStack社区,Kubernetes击败Docker Swarm! “庖丁解牛”式问诊Linux启动全过程 42个生活定律