科学网

 找回密码
  注册

tag 标签: Enigma

相关帖子

版块 作者 回复/查看 最后发表

没有相关内容

相关日志

从Enigma到“鳄鱼追斑马”
热度 7 lev 2015-8-8 23:51
从 Enigma 到“鳄鱼追斑马” 按:本文分为两个部分.这两个部分有没有关系或者有什么样的关系,我不知道...... I. Enigma 我终于抢在彻底下线前去电影院看完了《模仿游戏》( The Imitation Game, 放心没有“剧透” )。 大概几周以前,我偶然在影院门口看到了这部电影的海报。由于海报上信息较少(或者我没有察觉到),我完全没有想到 Benedict Cumberbatch 与 Alan Mathison Turing 有任何联系(说实话,一点也不像!)。我唯一注意到的信息是海报左下方一个极限公式的书写“瑕疵”。多亏这个“瑕疵”,我估计这可能是部有关数学家的电影,便回去上网搜了搜,这才知道传主正是 Turing。 上周我抽空到“西财”附近的一家影院准备看这部片子,却被告知上映两天就在该影院下线了。无奈就这样捱到了今天。 最早知道 Turing, 源自 小时候读一本大概叫《中外科学家故事》的书,其中一篇大约名为《一枚数学的珍贝》(那本书各个篇目的名字都很有特点,至今都还记得,比如牛顿那篇叫“沃尔索普村燃起的科学之火”,可惜书的确切名字和出版社实在记不清了)就是讲 Turing 破译 Enigma 的故事。前些年又在《科幻世界》上读到一篇长铗写的科幻短篇《 ACE 小姐的心事》,主体情节的“底本”也不外乎这段故事。 我对计算机这门学科的历史并不了解。仅就我掌握的资料,这部改编自B iography of Alan Turing( Alan Turing: The Enigma ) 的电影对涉及的计算机科学概念做了较大程度的“简化”,对相关史实尤其人物关系也做了不少“调整”,甚至包括 Turing 的性格和人际关系(为什么一定要塑造成 monster 呢?)。但是我们毕竟没必要在《三国演义》里找“曹操”。我注意到,当电影进行到后半段时,放映厅变得很安静——我想一部电影达到这样的效果,已经足够了。 在某种程度上,一个多月前美国联邦最高法院的那一项裁定使得这部电影变得十分应景,其中关于人性或者人与人关系的反思,在传播价值上已经远远盖过了其中的数学或计算机科学元素。但对我来说, Turing 仍然是最初留下的印象——那个破译了不可能破译的 Enigma 的 数学家。 II. 鳄鱼追斑马 让我下定决心去看看 Turing 的原因是今天早上看到一则新闻《苏格兰“高考”数学难哭考生,分数线被降至34分》( http://life.gmw.cn/2015-08/07/content_16574089.htm ) 以前就看过 A-Level 的高中物理题,我辈只能 smilence。 这次看了看据说是拉低了10.7万考生的及格分数线(从去年45到今年33.8,60分可拿A——“60分万岁”乎?)的数学题——1.4万考生心目中的“不可能完成的迷题”—— Enigma??? 联系到近来“九九乘法表”(我以前真的天真地以为全世界小朋友都会)、“广播体操”之类的定向出口,“英国人数学不好”的说法甚嚣尘上..... The Great Britain, The Great Britain! Where came Maxwell and Newton, Where went Dirac and Hamilton ...... Few heroes or lots of strangers, That is an Enigma! Alan Mathison Turing 1912~1954
个人分类: 莫名其妙|5750 次阅读|17 个评论
科普一下网络绑票背后的技术(一)
热度 24 lujiangxiao 2015-2-2 12:01
过圣诞过 年乱哄哄的,好久没静下心写科普了。好容易等到一个不用打牌的周末,写点什么呢? 据 说写科普的最高境界是写自己不懂的科学, 咱就挑战自己,向这个高度靠拢一下吧。 我要力求做到 科普的基本要求:把复杂的原理用简单的几句话正确地讲出来。 -------- 一 个恐怖的故事 那天 (01/24/1015) 听到美国国家公共 电 台( NPR )里 讲的 一 个恐怖故事:一个人的 计 算机中了病毒,把他所有的文件, 电邮 ,照片都被病毒加了密,完全没法 读 了。勒索者 说 你可以交勒索 费 ( Ransomware) 把它 们赎 回来。 由于 计 算机加密后是目前技 术 不可解的,受害者只好乖乖交 钱 , 赎 回一个密 码 ,解开了他所有文件。 NPR 的 这 个 节 目[ 1 ]做得满拼的 , 为 了加深听众印象,他 们专门 找了一个受害者当 场电话 叩 应 : 这 是一个中招的警察局,里面的一个警察用局里的机器看网,不知点了个什么中了毒。立刻把警局所有文件 锁 住了,里面包括 15 年来所有 办 案文件,案件照片,口供等等。 这 些重要文件肯定是有 备 份的,可是 备 份机也同 时 被感染了,所以把所有 备 份都同 样 加了密。 警局抓狂了,找来 FBI ,然后 FBI 说这个加密和米国国安局水平是一样的,没解。 您 还 是 认 栽, 按 找勒索者的要求付 赎 票 费吧。你们的文件比原则更重要,等等等等。于是老革命遇上新问题,警察蜀黍硬着头皮上网学买网币( bitcoin),然后乖乖向小毛贼交钱,拿回所有文件。 好,这使我很感兴趣了。这种数字勒索背后究竟是什么技术呢?为啥能一个穷小子做案后,倾国王的千军万马,全部经费解不开呢?这道理实际很简单,就是正运算容易,逆运算难。比如算术里的正运算乘法,其逆运算是除法。乘法有口诀,但是除法就没有。小学老师教我们做除法的时候用“试商”就是先假想一个答案,然后用乘法验证其是否对。这样用两个数通过乘法算出一个结果,要把结果通过逆运算还原成那两个数,就要花费更多的时间。如果两个乘数都很大,逆运算就需要世界最强的计算机花一万年才能完成,就算理论上肯定能算出来,实际上却行不通,这数字基本就勒索成功了。 逆运算为什么这样难 什么逆运算可以这么难呢?比如咱小学学过的质因数分解,是乘法的逆运算。质因数分解就是一个数分解成几个相乘的质数,比如把1457分解成 37 乘以 41。我们可以用一个计算器把两个质数很快地乘起来,比如把两个质数,1000000000193 和999999999673 相乘得到999999999865999999936889,这需要的时间可以忽略不计,但把999999999865999999936889,分解成上面两个质数,需要的时间就长多了。所以当两个质数都很大,分解解质因数的计算时间就与数字长度的指数成正比,可以轻易长到几百年几万年,谁都不能容忍的地步。这样如果用其中一个质数作为密码,别人虽然知道两数之积,也没办法找出这个质数。当然数学家也在钻研分解质因数的捷径,而且已经钻研出很多小把戏,可以很快地分解比较特殊的质数对。所以在选择两个质数的时候必须避开一些可以被这些把戏攻破的质数对。上述的网络绑架的病毒就是利用类似的,数学上还没解决的“硬难题”(harsh functions) 方法进行加密, 造成只有加密者可解的方法。节目上说每年至少有几百万计算机中招。大多数人是付钱消灾。 我下面顺便科普一点信息加密和密码学吧。所谓加密就是把咱们说的大白话通过一个变换变成常人不懂的乱码,这样就可以通过公共的渠道传播信息,虽然谁都能收到你的乱码,但只有你和你的收信人能对乱码进行变换和反变换。 举个例子, 如果你把wang_luo_bang_piao (网络绑票) 这个短语加密成不可解密的乱码,可以用一串随机数,如319981309075395484….,作为密码钥匙来加密。方法非常简单,就是字母串对准密钥字符串,然后根据密钥的数字对字母在字母表上进行位移。如第一个字母w 对密钥第一位3,移三位,w,x,y,z,变成z。第二位字母a对 准密钥的第二位1,移一位变b。如此整个字母短语就变成了乱码 zbwphmxoibhsjiumis, 没有密码钥就不可分解的了。看到这儿您一定会说,既然加密用随机数就行了,这么简单,那为什么上面你还要讲一大通什么逆运算啦,质数啊什么的,直接用随机数位移加密不就行了吗? 红灯记的故事 可是这里还有个细节:您的随机数密钥必须要只给收信人,如果泄露给外人,你的密码就没秘密了。而利用数学硬难题的加密方法可以公开传送密钥。传送密钥的危险在样板戏里演过,就是红灯记里李玉和把密电码藏在粥底下的故事,需要抛头颅洒热血的。这个密电码就是一本写着一串串随机数的书,发信者和收信者每封电报用一页。只要随机数密电码不重复使用,从理论上讲这种加密手法是不可破解的。问题来了。战争中指挥部要和那么多战斗单位联系,如果用不重复的随机秘密本,实际操作有问题。一个折中的办法就是利用很长,很少重复的数字串来加密,密级低的通讯用重复较多的密钥,密级高的通讯用重复很少的密钥。可是这个问题带来的问题就是同一信息有可能出现在密级低和密级高的电报中。敌方从密级低的电报入手,破译后再攻密级高的。这种破译技术的一个传奇故事就是国军的密码破译家导致山本五十六的行程暴露,被美机埋伏击落。 密码机之迷 密码本传递的麻烦重复使用的问题使人研究更先进的技术,用机器产生重复程度低的密钥。于是就有人研究了机械计算机的方法。二次世界大战中德国的密码机“迷”(Enigma)就是这类机械计算机的典型. 1920年代德国工程师阿瑟 舍尔碧乌斯(Arthur Scherbius)开发 出一种机械的字母位移方法。原理非常简单,就是用一个轮子上有26个接点,把它们以一定方式俩俩连接起来,比如1和5,2和17,3和14….下图是他的专利附图,其左上角(Fig 2)就是这种连接的示意。 有了这样的连接,你输进第一个接点的电流就会从第五点流出,第二个接点的电流就移到 17位出…. 这样如果把26个接点对应26个字母,就成了一个机械的位移密码钥。可是一个轮子只能做一次位移,太容易被破解。如果再加几个轮子,破解难度就越来越高了。所以军用的Enigma有三个轮子。德国人脑子灵,让每个轮子通过电流两次,这样三个轮子就起到六个轮子的转换作用。下图就是这种机器的原理,有三个转换轮,加最左边一个“反射”轮,使输入码经过七次位移。 可以看到经过七次位移, A进去会出来一个G。而只要把右边轮子移一格,A进去就出来一个C。 所以根据每个轮子起始位置的不同,Enigma可以变换出非常很多的密码型式。军用的Enigma机器加上其他一些输入连接键盘,一共有 158,962,555,217,826,360,000 (1.5万亿亿 种)密 码变换型式,很接近用随机数加密 。 下 图 是 Enigma 的照片, 在实用的时候,先转动上面的三个齿轮设定好一种密码型式,比如图中的 ABY,还有反射盘的4,定为今天使用的密钥。这时在键盘上按一个键(如A),上面的灯盘上就会显示出一个加密后的字母,(如Y).另外每按一个键转换一个明码字符那三个轮子都会自动进一格, 明码的位移数就会再变一下。 如此你打进AAAAAAA….., 出来就是YCFQRTS…..。如果换另一个密码型式,如EIN, 按入AAAAA…出来就可能是BGYET…. 看起来几乎没有任何规律。德国人很自信地说,这种密码是不可破解的, “即使敌人获取了一台机器,它仍旧能够保证其加密系统的保密性。” 可是看起来没规律的事其实总有规律的。 看着像随机数,可实际还是差远了 。 1.5万亿亿种变换型式放进现代计算机,用不了多少功夫就破译了。令人尊敬的是破解Enigma之迷的时候还没有现代的数字计算机。完全是凭一些聪明的头脑。 [ 1 ]NPR 的节目在这里 http://thedianerehmshow.org/shows/2015-01-22/ransomware_the_latest_cybersecurity_threat_to_personal_computers_and_smartphones (待续,下篇先讲Enigma是怎么破译的,再讲讲怎么做计算机花几百年都不能破译的密码系统)
12191 次阅读|33 个评论

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-6-4 21:23

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部