科学网 › 标签 › harsh

标签: harsh

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

科普一下网络绑票背后的技术（一）: 热度 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是怎么破译的，再讲讲怎么做计算机花几百年都不能破译的密码系统）; 12160 次阅读|33 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: harsh

相关帖子

相关日志

关闭安全验证