[1] 
点击: 4224  回复: 22  已被28人收藏

 密码学的故事

2445
7
来自:保密
注册:2001-06-03
发帖:178+4256

之前好好说话的帖子被锁了


科学思维、独立思考任重而道远


这个帖转密码学的故事


这总可以了吧


获网友奖分100点  

------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 22:04:08
2445
7
来自:保密
注册:2001-06-03
发帖:179+4258

卓老板:


密码学的总体图景,是个什么样子呢?简单来说,它有一道分水岭 —— 在计算机出现之前,叫做古典密码学,之后叫做现代密码学。

不论是古典还是现代,有一条主线剧情一直贯穿其中,那就是加密与解密在几千年中此消彼长的对抗。有的时候,任何加密法都不保险;可有的时候,任何解密法都不管用。

在这场人类顶尖智力的漫长博弈中,出现了大量跌宕起伏的故事。




其中就有这么一个,它不涉及复杂的技术细节,但又体现了密码学的底层逻辑,这就是第一节课我要给你讲的——俚语加密


1

俚语,就是我们常说的“方言”,也就是使用敌方完全听不懂的地方话来进行沟通,实现加密的目的。

别看这种方法挺土的,但很多国家都用过。20世纪70年代,中国在越战的时候,就使用过莆田、温州、高淳的方言进行加密通讯;类似的,1973年的阿以冲突中,埃及也使用过非洲的努比亚人进行俚语加密。

问题是,这种土办法好不好用呢?简单回答:出人意料的好用。




不过这里有必要解释一下,什么算“好用”?很多人认为,密码强度高,破解不了就是好用。这实在是对密码最大的误解。破解不了只能证明它安全,并不代表好用。历史上有很多被誉为“无法破解”的加密法,就是因为太繁琐了,出现后甚至几百年都没人用,这就是很好的反例。


所以说,破解不了并不代表好用,真正好用的密码,是在安全性和效率上找到平衡点。



2

二战时期,美国使用的“纳瓦霍语”加密,就是当时最好用的加密法。你可能看过吴宇森执导的好莱坞电影《风语者》,它讲的就是纳瓦霍通讯兵的故事。


今天我就从密码学的角度,给你讲讲这个故事。通过它,你会知道什么样的密码叫好用,而这也是我们理解密码学的关键。


在密码学中,有这样一条重要的准则:


为了保证密码足够安全,需要假设敌方已经拥有了和自己一样的解密水准,然后在这个基础上制定加密手段。

当时图灵已经破解了德军的恩尼格玛机,那盟军要用什么手段才能比恩尼格玛机更可靠呢?最简单的办法,就是使用更复杂的机器。实际上,在二战期间,英美使用的密码机复杂度已经到了上限,继续增加复杂度会导致加密成本太高,不只是机器贵,关键是加密解密的时间长。尤其是前线交战,每条信息都要迅速反应,一条信息加密了几分钟还没发出去,这是不能接受的。


这里就要再次强调加密法“好用”的原则了——需要在安全和效率上找到平衡。



3

在最初的太平洋丛林战中,美军为了效率,甚至没有加密。不幸的是,日军文化水平可以,负责通讯和****的日本兵听得懂英语。


正在美国寻找全新加密方法时,1942年初,美军收到一个工程师的来信,建议他们用俚语加密。这个工程师从小皇冠娱乐网在亚利桑那州的纳瓦霍(Navajo)保留区,说的一口流利的纳瓦霍语。他深知,纳瓦霍语不但和当时世界上流行的拉丁语系很不一样,甚至连美洲其他土著也完全不能理解。


美军听到这个建议后初步测试了一下,发现不但内容传达准确,而且效率还挺高:一条有3行文字的信息,纳瓦霍语加密和解密只需要20秒,而当时的加密机器要花30分钟。

不过,美军并没有马上采纳,这就体现出科学素养高了。他们考虑到如果这个方法可行,我们有那么多种土著语言,有没有比纳瓦霍语更好的选择呢?


选择标准很多,首要条件是,部族里潜在的通话员数量足够多。当时,纳瓦霍族、苏族、齐本瓦族、皮玛帕帕戈族是四个备选。


最终让美军做出选择的,是一份人类学方面的统计综述。




这份综述统计了德国学者对世界各地人类学的研究状况,结果发现:这4个还不错的备选中,纳瓦霍族是德国人类学家唯一没有发表过研究论文的。所以相对于另外三种土著语,纳瓦霍语密码被破译的可能性最低。

最终,纳瓦霍语入选通讯兵培训计划。





------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 22:40:32
2445
7
来自:保密
注册:2001-06-03
发帖:179+4259
4


在珍珠港被袭后4个月,第一批29名纳瓦霍人开始了通讯培训。


培训中如何使用设备倒是次要的,关键是想办法解决文化中的外来词。比如,中文里自古就没有巧克力、玻璃、经济这些词。而且这些单词,很多都不能把字与字分开理解。像“巧克力”,单拎出力、克、巧,没有一个字能跟原意挂钩。


对土著来说,飞机的名字、军师旅团建制的名字、轻重型武器的名字,还有地名,也都是外来词。作战中这些名字不但常用,而且必须准确传达才行。怎么办?




美军的解决办法是,专门为纳瓦霍人编一份生词词典。


生词都这么处理,比如太平洋Pacific,第一个字母P就写成Pig,第二个字母a就写成ant,第三个字母c就写成cat……这样,在纳瓦霍语里,太平洋就变成了“猪蚂蚁猫冰狐狸冰猫”。我试着用纳瓦霍语念一下,大约就是 bi-sodih,wol-la-chee,moasi,tkin,ma-e,tkin,moasi。这就是太平洋。







5


俚语加密的保密程度怎么样呢?结论是比预期还要好很多。


这29人培训结束后,先做了一次实战测试。对真正的军事情报做加密,然后把通话内容录音交给美国海军情报处。这个机构当时的水平,是可以破解恩尼格玛机的。结果美军情报处集中力量分析了3个星期,仍然毫无进展。


解密专家对纳瓦霍语的评论是:


一连串奇怪的喉音、鼻音、饶舌音,别说破解它们了,我们甚至没法用普通文字把它们准确誊写到纸上。


不知道你刚刚注意到没有,纳瓦霍语的一个重要特点是,这种语言压根没有文字,只存在于发音中。破译一种没有文字的语言,这本身属于另一个维度的任务。


其他密码难度再高,密码专家都至少知道破译的终点是一种我们熟悉的语言,只不过表面样式发生了变化。但如果破译的终点是一套欧美文明全然陌生的语言结构的话,难度就可想而知了。


而纳瓦霍语更是难上加难,因为破译的终点不但语言结构未知,而且一连串像鸟鸣一样的发音,根本落不到纸面上。


所以,纳瓦霍语加密的安全级别,远超当时的各种加密机。


后续人类学家对纳瓦霍语的研究显示:


它是一种跟亚洲、欧洲所有方言都毫无关联的语言。比如说,如果宾语是铅笔之类的长条状,动词的尾音就拉长;如果宾语是像沙子那样带颗粒的东西,尾音就要模拟出沙粒的感觉;陈述句中那件事如果他本人亲历过,会加特别的副词;有的时候,一个发音实际上就能表达一句话。


总之,作为密码专家,你没法要求他去假设一些他根本没听说过的语言表达技巧存在,然后再在此基础上解密。




到了1942年4月,已经有420名纳瓦霍人成了通讯兵。


当时的海军陆战队的少将霍华德·康纳评价:如果不是纳瓦霍人,硫磺岛绝对拿不下来。



6

加密的部分说完了,我来补充一些让人感慨的细节,这对于我们理解密码学也非常重要。




纳瓦霍人在入伍前对现代战争毫无了解,战场上他们最大的困难,就是要克服内心深深的恐惧。纳瓦霍人的世界观中,最重要的一件事就是处理好死者。纳瓦霍人都相信,如果没给死者安排好丧葬仪式,这些挣扎的灵魂会向活人复仇。


可太平洋战役又格外血腥,到处尸横遍野,每个纳瓦霍人内心都是恐惧不安的。尽管文化差异极大,但这400多人还是隐忍着,恪尽职守出色的完成了通讯工作。







经过战争的剧变,纳瓦霍通讯兵大都没再回到家乡,而是融入了现代城市皇冠娱乐网中。但由于保密法的限制,他们的特殊贡献直到1968年才被外人得知。


解密后的第二年,这些密语者第一次举行战友联谊会,当年参战的最年轻的族人也已年过半百,还有一些老兵已经过世。之后十几年大量资料披露,历史研究和文艺作品出炉,让整个美国和全世界人知道了这段少数族裔的英勇历史。


1982年,里根总统表彰他们的事迹,并把8月14日定为“纳瓦霍密语通话员国家纪念日”。国家给予的荣誉当然是一种巨大的肯定,但比这更大的荣誉是,纳瓦霍语是唯一一个从未被破译的军事密码。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 22:43:45
364
32
来自:皇冠现金.黄浦
注册:2017-08-27
发帖:37+5461

图灵唠


------------------------------------------------------------------------------------------- 名师大将莫自牢,千军万马避白袍。
2019-01-19 22:44:56
1417
42
来自:皇冠现金
注册:2002-06-20
发帖:220+4347

楼主贴的是加密方法的一种。


家里买过一本密码学通俗读物,我记得谈到密码就要说密钥,没有密钥,就谈不上密码学。


请您继续。


------------------------------------------------------------------------------------------- 重要的不是技術, 重要的是一顆深然沉穩的心。 不管飞翔在阳光下 还是绽放在黑夜里 你的姿势总是唯一
2019-01-19 22:50:14
2445
7
来自:保密
注册:2001-06-03
发帖:179+4260
古典与现代:密码学的两个时代



第一节课里我们说到了俚语加密,其实它并不算完整的加密与解密,因为纳瓦霍语始终没被破译,所以缺少解密环节。




但从这节课开始,加密和解密就会成对儿出现了。在几千年历史中,它们一直此消彼长的对抗。


这其中有没有总体脉络呢?有的。这个剧情大致有7个世代,下面咱们一一梳理一遍。


1


最原始的第一代加密法说起来很简单,我们每个人都用过,就是“隐藏法”,也就是把信息藏起来。


从有文字出现,一直到现在都在用。破解方法就是认真搜找,纯粹是体力活。


史上第一个加密法的记载,是古希腊历史学家希罗多德记录的一个加密术的故事。这段故事,发生在他出生前300多年。


当时,强大的波斯帝国计划入侵希腊。斯巴达曾经的老国王得知后,偷偷把这个消息写在木板上又涂了一层蜡。这片木板成功躲过沿路卫兵的检查,到达斯巴达。收信人刮去表面的那层蜡,就发现了下面的密报。得知波斯人的入侵计划后,希腊开始备战。公元前480年,波斯舰队以为对方毫无准备,结果自己一天之内200多艘战舰被击沉,五年多的准备毁于一旦。




可以说,这次密报挽救了雅典和斯巴达,其实也等于挽救了现代文明。


因为现代文明有两个思想根源,一个是公元前5世纪巅峰时期的古希腊思想,一个是后来的基督教思想。


这场战争发生的前后,正是古希腊思想达到巅峰之时。如果当年雅典和斯巴达输掉的话,科学和民主可能都不会出现。


类似的“隐藏法”,在希罗多德的记录中还有更高级的。


比如先把送信人的头发剃光,然后把保密消息写在那人的头皮上,等他头发长出来后,让送信人出发,到了目的地再把头发剃光,保密消息就读出来了。


这个方法不但可以躲过沿路的盘查,甚至连送信人也不知道消息内容,只是送一次消息至少要2个月时间,有点长。


隐藏法还有很多种,比如把消息写在绸缎上,用蜡裹成一个小球,让送信人吞下去,到了目的地再想法取出。还有在熟鸡蛋壳上用一种药水儿(明矾和醋)写密文,之后蛋壳上不会有痕迹,只能剥了皮才能看到蛋白上有字。


这些隐藏法对付完全小白的人还可以,对付稍加提防的卫兵就不灵了。让他们留意一下蜡板,留意头皮颜色,见到熟鸡蛋就剥皮检查,这些信息就全都暴露了。





讲到这里,第一代加密法和破解法就全都讲完了。


简单来说,就是想方设法藏匿,解密方法就是想方设法翻找,有时候就是个体力活。但自从有了文字后人们就一直在用,直到今天人们藏私房钱时用的还是这个套路。


2


有很多家长爱翻孩子的日记,但假如孩子听过下面的第二代加密法,对文字进行简单加密,就完全可以把日记本摆在桌上,任凭家长怎么看也不知道写了什么。


这就是第二代的加密法,移位法和替代法


它们是大约5000年前出现的,直到9世纪才被阿拉伯人发明的频率分析法破解,中间隔了足足有4000年。在另一边的欧洲,实际上直到16世纪,都还没掌握这种破解方法。从这里我们也能感受到,阿拉伯文明曾经的辉煌。


移位法很简单。我举个例子,比如我的车牌号是1874,把每个数字都在数列中往后加1,那么1变2,2变3,1874就变成了2985。


因为都是数字你可能觉得反差不大,但如果字母也这样变化,看起来就很不一样了。字母顺序改变也是一样,从a排列到z,比如我要对hello world加密,加密规则呢,是每个字母都向后移动2位, “hello world”就变成了“jgnnq yqtnf”。


作为小白一看,这都什么啊,看不懂,其实它只不过做了基础加密而已。这就是移位法。


替代法也很好理解,就是把文中一部分字母用其他字母代替。




比如 For man is man and master of his fate(人就是人,是自己命运的主人)。那如果,把其中的a都用z代替,o用y代替,e用w代替,i用x代替。就成了一段谁也看不出来的文字:


For man is man and master of his fate. Fyr mzn xs mzn znd mzstwr yf hxs fztw

大约在距今5000多年前,古埃及人就在文字中使用了移位和替代法。别看基础,但很管用。这个方法广泛运用了接近4000年时间。


在漫长的时间里也出现了很多变种,比如顺序倒着写,或者奇数位和偶数位的变化不一样,或者把奇数和偶数位的字母拆分后,首尾相连等等。


这两种加密法的加密原理就是这样,你一听就懂,但是,想解密可就不容易了。




一条消息的长度如果有十几个词,想用试错的办法猜出来,只能采用排列组合。假设任何一个字母都有可能是26个字母中的任何一个,那这条消息每增加一个字母,排列方式就增加26倍。一句话可能的排列总数,也许要超过整个宇宙原子的总数,靠碰运气是没法猜出来的。


所以直到16世纪,欧洲人都没有破解法。


3


你发现没有,只是两代加密法,一下就讲了5000年密码学发展史的前4500年。


为什么会跨度如此之大?其实就在于前4500年的加密法太简单了。那为什么简单的加密法还被使用这么多年?原因很简单,它们跟数学的关系非常微弱。


无论是加密还是解密,一旦用上了数学,就有意思多了。因为破解移位法和替代法的,就是我们每个人都知道的“概率”这个概念。具体的破解方法,我们下一讲详细讲。


我这里想说的是:不只是密码学,可以说,一切科学深奥程度,都可以大致用它背后的数学工具的复杂度衡量。


就拿第三代的维吉尼亚密码来说,它是16世纪出现的,成功压制解密法长达300年,直到1900年左右被破解。


但也就是从这一代开始,加密和解密的迭代速度越来越快。原因你肯定也猜到了,因为现代科学出现了,复杂的数学工具开始在几乎所有领域应用。


而且也是从这一代加密法开始,“钥匙”的概念诞生了。这可以说是整个密码学最重要的一个概念,我们后面每一讲,几乎都是围绕它展开的。


比如第四代加密法,是一战后发明的一种机器,叫恩尼格玛机(Enigma)。它成功压制解密法只有25年左右,后来被数学家图灵破解,而钥匙就是最重要的突破口。




从第一代的隐藏法到图灵破解第四代的恩尼格玛密码机,实际上密码学的古典时代就已经进入了尾声。


从纸笔时代到机械电子时代,最显著的差异就是加密的复杂度以及效率的大幅提高。


4


但从第五代加密法,也就是70年代出现的魔王加密系统(Lucifer)开始,密码学就出现了分水岭。


因为计算机的出现,让加密解密的最小单位从字母变成了数字,数字的变化打乱了信息的底层结构。二进制的0和1,让密码的复杂度一下就上升了不知道多少个数量级。


所以,在计算机出现之前的密码学叫做古典密码学,之后的叫做现代密码学。


第五代加密法虽然很难破解,但递送钥匙的过程有明显漏洞,还有待提升。这个咱们会在后面详细讲到。


70年代末,第六代的RSA加密系统出现了,它解决了钥匙递送中的漏洞,可靠性大幅提升。虽然它并不是无法破解,但因为计算量太大,在理论上破解时间无限长。


目前互联网加密的底层,就是RSA加密法。我们皇冠娱乐网的这个加密一方赢面较大,解密一方处于劣势的时代,正是建立在第六代加密法的基础上。


但如果量子计算机出现,计算机算力大幅增加,无限长破解时间可能会缩短为几分钟到几小时。而在这之前,RSA加密法暂且可以算作没有破解方法。也是从第六代开始,你会越来越强烈的体会到“钥匙”这个东西的重要性。




第七代加密法是量子加密,它背后的理论支撑是测不准原理和特殊的算法。


当前因为技术水平不够,只能对长度比较短的钥匙加密,而不能对整个信息加密。据说在一些国家的高级保密单位已经开始使用。它从物理学和数学原理上是不可破解的,是最强的加密法。



5


说完了这7代加密法的出现和破解,不知道你发现了一个规律没有:


每一个加密法出现,到它的破解法诞生,间隔时间在剧烈的缩短。比如最初,替代法和它的破解方法频率分析,相隔了四千年时间;而到了二战时候,恩尼格码机的出现到破译只用了十多年时间。


其实这也映射出科学技术提升的趋势。科技一直发展是尽人皆知的,而加速的程度在变得更剧烈,就很少人察觉了。


可能有的人要问,不对,RSA加密,不都出现了40年了吗,为什么没有破解?


这就要说到另一个贯穿整个密码学发展的规律:


我们能了解到的现代密码学进展,都是军方、保密机构允许我们知道的。今天一定有很多进展和破解法已经出现,但出于国家安全的需要,只能等它们彻底过时,官方才会公布资料,我们才能知道其中的细节。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 22:51:52
2445
7
来自:保密
注册:2001-06-03
发帖:179+4261
概率论:数学让密码学加速进化



1


你想过一个问题没有:是什么因素决定了一个密码能否被破译呢?


我给你对比一下古典密码和现代密码,你就能发现答案了。


古典密码学,加密和解密过程中,最小操作单位都是单个字符或者符号,所以古典密码学的核心就是移位法和替代法。


现代密码学,把研究对象用数来描述,再对数进行运算。不但突破了字母作为最小变化单位的限制,还可以使用更高等的数学工具做运算,因此破译就变得越来越难。


所以,加密时所用的数学工具,决定了一个密码能否被破译。


上节课我们说到,第二代的移位法和替换法的安全性很好,也比较好用,但到了16世纪,这个局面扭转了。因为概率论的出现,这两种加密法可以破解了。


自此之后,加密与解密的对抗战中,因为数学的应用,解密一方暂时占据优势。




这节课,我们讲两个破解第二代加密法最经典的案例。


一个发生在16世纪的苏格兰女王玛丽一世身上,一个发生在17世纪中后期到18世纪初的法国国王路易十四身上。


2


我们先说玛丽一世女王,她是我听说过的最刚烈的女人。在这门课《密码学人物列传》的模块中,我会专门用一讲详细讲讲她的故事。这节课,我们还是主要围绕密码展开。

27岁时,玛丽一世被自己的姑姑英格兰女王伊丽莎白一世关押了起来,一关18年。到44岁时,监狱里的她和外界反叛军密谋要杀害姑姑,一旦谋杀成功,她自己就能坐上王位。当时的信件都是通过特殊渠道传入监狱,最后由侍女在递送红酒时,藏在瓶塞中带进去。




玛丽一世很聪明,包含暗杀计划的并不是普通的信,而是加密过的。就算不慎落入伊丽莎白一世的手中,也没人看得懂。


其中用到的加密方法,就是替代法。所有的英文字母被类似符文的东西替换,一些常用词也用符号代替。具体的对应方式,你可以参考下面这个图表。





玛丽此后就通过这个特殊渠道和反叛军通信,几个月后,她熟练掌握,写信可以直接用密文,不用一个个字母查对照表了。


不幸的是,这个特殊消息传递的渠道里,竟然隐藏着一个双面间谍,他把情况汇报给了伊丽莎白。在位的女王正愁抓不到把柄,这下终于有机会名正言顺的处死玛丽了。




不过现在还急不得,必须抓到足够硬的证据,而且最好把整个阴谋背后所有的参与者一起除掉,所以伊丽莎白没有打草惊蛇。


此后玛丽和外界的通信,每一封都先经过双面间谍送到密码学校,花1个小时誊写好,然后再密封好,就像从没有被截获过那样,递出皇宫。密码学校的人再拿着誊写好的密文想法破解,最终他们成功了。


3


破解方法,就叫做“频率分析法”。这种方法其实在9世纪的阿拉伯就出现了,只是到了16世纪才被欧洲数学家注意到。





下面咱们讲讲它的原理。很简单,英文中字母出现的频率,是不一样的。比如字母e是出现频率最高的,占12.7%;其次是t,9.1%;然后是a,o,i,n等,最少的是z,只占0.1%。




除了英语,其他语言也有详细统计。









玛丽和外界用密文往来很多,字符总量足够多,全部收集到一起,统计哪个符号出现的比例最高,那个字符大概就是字母e。


当然,有些字母出现的频率极为接近,比如h,r和s,分别是6.09%,5.98%和6.32%。但只要稍微留意字母前后的关联,就可以区分出来。比如:t几乎不可能出现在b,d,g,j,k,m,q这些字母的旁边,h和e经常连在一起,ee一起出现的频率远比aa一起出现高得多等等。


频率分析法的实质,就是大幅降低字母排列组合的可能性。


从前我们假设每个符文都可以是26个字母的任意一个,有多少个替代符号出现,就有26的多少次方种可能。但频率分析法把很多符号的可能性大大降低,有的降低为只有1种可能,有的降低为只有2-3种可能。


这样一来,即便第一步统计各种符号出现的频率时并不完全确定,但只要再根据拼写规律筛选一下,替代符号对应的真实字母就确定了。


在审讯的过程中,尽管玛丽始终没有承认谋反,但证人和密码学专家一起向公众展示了密文和原文,讲解了解密规则,最后玛丽一世还是被砍了头。




这是加密和解密在皇权斗争中最著名的一次应用,解密法大胜。


4


解密方法公布后,替代法就不再有效。起码对欧洲王室来说,决心要破解的话,一定可以破。


加密一方当然不甘落败,怎么办?




很快就出现了另一种叫做“同音替代法”的方法。


比如说字母a可以用11,23,41三个数字替代,这三个数字翻译过来都是a。越常用的字母,比如e,就用越多的符号代替它。这种想法的终极目标,就是让每个数字出现的频率都大致相等。频率特征没有了,密码就不容易破解了。







从上面这张同音替代法的表格中可以看到,最常使用的e,替代的字符最多。




不过这种方法的解密法马上也出现了,就是通过字母前后顺序关系来猜。


最典型的例子是,q后面出现的最大可能是u,而q又是一个不常用的字母,有很大概率猜出来。其他字母猜出来的难度大一些,但只要肯花时间,总能破解。


5


史上最有名的采用同音替代法的密码,是法国国王路易十三、十四时期的“大密码”(Grand Chiffre)。它使用了40多年后,随着拿破仑倒台突然失传。直到1890年才被完整破解,破解方法就是从单词拼读规律入手的。


这套加密法用了587种数字,来表示不同的发音。其中陷阱还很多,比如有些数字只代表字母,不代表发音;很多数字是干扰字符,它们没有意义;还有一些数字既不是发音也不是字符,而是代表删掉前一个字符。


大密码被破解后,很多200年前路易十四的宫廷秘闻才大白于天下。


其中有一段,是法国宫廷传奇“铁面人”的新发现。铁面人的故事在欧洲,就像咱们关心康熙晚年雍正是怎么即位的故事那样。无数小说都以这个为背景,大仲马和伏尔泰都写过。


故事说的是一个犯人从1669年被捕后,一直关押。而且负责关押他的监狱长不论工作怎么调动,总把这个犯人带上,一关就是34年。按说这么重的罪,就让他把牢底坐穿吧。不,给他吃的都是美味,穿的都是华服,还可以弹琴,有医生定期探望,甚至转移监狱时都是高级马车护送。什么都有,只是没自由。


有狱卒看到过这个人在远离其他犯人的地方散步,脸上总带着一个铁面具,没人知道他长什么样。


铁面人到底是谁,有N种猜测,在大密码告破之前,有猜是路易十四同父异母哥哥的,有猜是路易十四亲生父亲的,有猜是英国国王私生子、法国财务大臣、意大利外交官的。之所以有争议,是因为每个说法都有漏洞。




在大密码告破后,又多了一种解释,那就是当时路易十四手下的德布隆德将军(Vivien de Bulonde)。解密后,有一封信是战争部长写给路易十四的,提到立即抓捕德布隆德将军,晚上关进牢房看管,白天可以允许他带着面具在城垛上活动。


这个说法虽然后来也发现了漏洞,但因大密码破解而公布的文件和信件,让法国宫廷内部的历史变得更有据可查。


6


你想过为什么替代法会被破解吗?是宫廷天才对猜字游戏很擅长,还是双面间谍的勇敢机智?


这些因素当然都有。但最重要的观察视角是——那个年代的数学突飞猛进,终于诞生了“概率”这种新概念。


今天的人听到“某个字母在一篇文章里出现的概率”这样的表述,当然不会觉得难以理解。但400多年前的人虽然也知道,****扔出去,女王头像一面朝上的机率是一半,这样粗浅的概率知识。但他们大都不会用这个视角衡量感兴趣的对象。


其实直到现在,大多数人也没什么机会用这个视角去思考,唯一涉及切身利益的就是买彩票。


而当年概率论之所以诞生,正因为第一个研究概率论的那个数学家卡尔达诺(Girolamo Cardano)是个赌徒,他还是三次方程一般解法的发现者,也是最早使用复数概念的人。世界上第一本概率著作《论赌徒的游戏》,就是他写的。正是这本书写完5年后,玛丽女王被姑姑囚禁了起来。


数学的发展,有两个高峰。一次是公元前500年到公元前300年,那之后一直在下滑,大约在公元500年跌到谷底。另一次高峰是在这1000年之后,大约在玛丽女王时代,才超越古希腊巅峰时期的水平,而且这个高峰现在还没出现最高值。


随着数学水平的提高,不只是密码学,所有使用到数学的应用学科也会跟着变。很多在1500年之前只是旁门左道的事情,逐渐成为独立的行业,或者单独的学科分支。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 22:59:42
82
0
来自:保密
注册:2018-10-27
发帖:0+172

对称加密就略过吧,快进到非对称加密RSA


------------------------------------------------------------------------------------------- 这个家伙很懒,什么也没留下......
2019-01-19 23:02:55
2445
7
来自:保密
注册:2001-06-03
发帖:179+4262
维吉尼亚密码:加密强悍,却为何没人用?



这节课我们讲第三代加密法,诞生于1586年的维吉尼亚加密法




上节课咱们讲到,概率论出现之后,传统的移位法就不好使了。


这节课讲的维吉尼亚加密法,就是为了对抗频率分析出现的——使用这套加密方法之后,字母的频率特征会消失。


1


一般认为,做出这套加密法的是法国外交官布莱斯·德·维吉尼亚。


但这个结论有很多争议,在他之前40多年的德国炼金术士约翰尼斯发明的表格法,也包含其中关键部分;在他之前80多年,意大利诗人莱昂也提出过这种方法的关键部分。

一个发明到底归属谁有必要考据细节吗?


当然没有。我主要是想指出一个规律——凡是出现了一个发明权一堆人抢的情况,就说明那个领域已经形成了成熟的行业。


密码学也是如此。我们暂且认为维吉尼亚就是发明人吧。问题来了,他一个外交官怎么会对密码学研究那么深呢?有两个原因:


1. 工作需要,从16世纪起欧洲外交官频繁通信,怎么让信件更安全,自然是个重要问题。


2. 数学是法国的国学,密码和数学关系紧密,所以法国人使用加密法的门槛比较低。

在18世纪初,欧洲各国都有隶属于情报机构,专门负责加密解密的部门,叫“黑房厅”。它是和邮政系统配合运行的。


每天有大批信件本来是从各地寄到邮局,再从邮局分发出去。黑房厅出现后,一部分信就不是从邮局直接递给收信人了,而是要先经过黑房厅,再送到收信人手里。


哪部分信件要绕这么一道弯儿呢?


其实就是所有寄给当地大使馆的信件,会受到这种特殊待遇。因为这里很可能有机密信息。


虽然我直接把内幕说出来了,但黑房厅在当年运作的时候是完全保密的,人不知鬼不觉。信件不能因为破译需要时间,而让对方使领馆人员察觉到递送超时。


以当时最著名的维也纳黑房厅来说,每天早上7点,信件先抵达黑房厅,工作人员小心翼翼的融开封口,由专门的速记员把信件誊写抄录,如果是很偏门的语言,就由专家出马誊写。然后马上把信封好口,在三小时内送回邮局,邮局再按正常流程递送出去。


那时各国都在重要信件上使用了加密法,最初普遍采用替代法和移位法的混合,但对掌握频率分析法的黑房厅来说,总是可以破译。




奥地利除了自己偷看信,还暗中把消息卖给其他国家的情报部门。没过几年,很多国家察觉到自己的加密可能失效了,于是就催生出下一代加密法。


2


为了弄懂后面新的加密法,我们有必要先来回顾一下第二代加密法存在哪些漏洞。


上节课我们讲了替代法的破解原理,因为每个字母实际使用的频率是有固定值的,所以不论那些字母被什么符号替代了,都可以从频率上找出它的真身。




玛丽女王就皇冠娱乐网在加密法打不过解密法的年代。其实在她被砍头的40年前,新的加密法已经出现了,它是替代法的改进版,叫“多套符号加密法”


为了掩盖字母使用中暴露的频率特征,解决办法就是用多套符号代替原来的文字,比如原文的字母是A,从前只把它替换成F,现在把它替换成F或者G这两个。那什么时候用F什么时候用G呢?可以自行规定,比如说,字母在奇数位时用F代替,字母在偶数位时用G代替。


从前单套符号替代的时候,凡是文字中频率为7.63%的符号,差不多就代表A了。但现在A由F和G混合在一起,7.63%的特征不再出现,哪个符号代表A就没人知道了,于是频率分析法暂时失效。


3


而且,多套符号加密法并没满足于2-3套,后来典型使用的是26套。

这个用了26套字符的方法,就是第三代密码“维吉尼亚加密法”。就是它,成功压制了解密一方的频率分析法。



它是一个表格,第一行代表原文的字母,下面每一横行代表原文分别由哪些字母代替,每一竖列代表我们要用第几套字符来替换原文。一共26个字母,一共26套代替法,所以这个表是一个26×26的表。



它具体是怎么加密呢?


假设我要给“hello”加密,现在的思路和单套的加密方法不一样了。单套的时候,我们可以指定这个表里任意一横行,比如指定第8行的意思就是说,原文中的字母都往后移8位,只使用这一行的规则,“hello”就变成了PMTTW。


但现在我们的思路是用多套密码,不能只用第8行第8套。于是我们就这样指定:


原文第一个字母用第8套密码代替,第二个字母用第12套密码代替,第三个字母用第5套密码代替,第四个字母用第9套密码代替。




你说这听着怎么这么乱啊?具体每个字母移动多少位竟然要单独指定,太麻烦了吧?


如果原文只是hello这种词还好,要是一封信的话,一个字母一个字母的规定用哪套替代,不但加密费劲,解读也费劲。只能单独再写一本说明书出来,照着它一个字母一个字母的还原,费时费力、容易出错不说,连加密的初衷都实现不了。


因为这份说明书的文字量比原文还要多得多,而且这个说明书还必须以谁都可以看懂的方式书写。想让收信方看明白,必须要送一本加密说明书给对方,如果说明书被截获,内容也就白加密了。


4


这个问题是这么解决的:


第三代的维吉尼亚加密法在真实使用时,人们事先规定每个字母用了哪套移位法时,并不是毫无规律的瞎指定,而是要约定一个规则,这个规则就叫作 “钥匙”。




钥匙最初只是一个单词,比如,像钥匙是yes,那怎么加密呢?


你看,yes的y是第25个字母,就代表加密时把原文第一个字母往后移25位;yes的第二个字母e是字母表中第5个字母,就代表把原文的第二个字母往后移5位;yes的第三个字母s在字母表中是第19个字母,就代表把原文第3个字母后移19位。这样原文的前三个字母,就分别用了第25套、第5套、第19套替代法。


那原文第4个、第5个、第6个字母怎么解决呢?好办,就按刚刚的规则循环就好。




这样“hello”在钥匙是yes的情况下,就被加密成了FIDJS。


这样的好处是,原文里同一个字母会被加密成不同字符,hello中的两个“l”分别变成了D和J。而且密文中同样的字符也可能代表不同的原文,谁和谁都不对应。




1586年,维吉尼亚把这个想法写在了《密码论》中发表。


而上节课我们说的玛丽女王是在1587年被砍的头,如果她和反叛军能用到这本书里的加密方法,也许会是另一种命运。


5


维吉尼亚法相比从前的加密法,破解难度上了一个新的台阶,按理说应该倍受青睐吧?结果恰恰相反——它在出现后的200年里,几乎没有人使用。


原因很简单,太麻烦了。咱们第一节课就讲到,真正好用的密码,是在安全性和效率上找到了平衡点。




你想,用单套密码的时候,当年玛丽女王稍作训练,在监狱里就可以抛开字典直接用密文回信,但是如果用维吉尼亚密码的话,估计她老得翻字典。


而且大家也可以设身处地的想想,加密法可是一套26×26的表格,而且还有长短不一的钥匙。每加密一个字母,都要在表格里找来找去,就算是在熟练操作的情况下,加密一个字母也得要3秒钟的时间。写完一篇500字的短文,要3个多小时的高强度工作。慢还不说,这样来回来去的查和写,还容易出错。


所以在它诞生后的200多年时间里,几乎没有人用。既然没人使用,自然200多年也就没有人破解。


6


直到1861年到1865年美国南北战争时期,维吉尼亚加密法才被广泛使用。


为什么会这样?是因为人们脑子变聪明了,手更快了吗?


不是的,而是因为随着科学技术的发展,那时候加密解密的工作已经可以由机械来完成。1860年代,不但已经有了蒸汽机,也有了电动机,这种有规律的体力活儿机器是最擅长干的,既不会抱怨累,也不太会出错。


从维吉尼亚法推迟200多年才得到实际使用,我们能明白一个道理——


基础学科的发展是工程领域发展的根基,新理论的发明要比产品的发明重要得多。


就算是只限于密码学领域,这个规律也反复出现了多次,而且大都集中在维吉尼亚密码法诞生之后。


因为16世纪初,现代科学已经在欧洲出现了。科学理论用得好就能生出新技术,新技术解决一个个困难,让人类更愿意把精力投入到科学中,于是又产生出更多的技术,形成了一个正反馈。


在这样一个新环境里,出现了一个有意思的情况:一项技术发明到底归属于谁,总是说不清。做出同样发明的人,在时间上经常只相隔几天或者几个月。维吉尼亚加密法是这样,维吉尼亚加密法的破解也一样是这样。


这并不是偶然,而是现代科学出现后的常态,在任何领域都是如此。


知道了这个规律,我们就会少一分对伟大发明家的崇拜,多一分对背后科学原理的敬畏。


维吉尼亚密码法的出现,让加密一方暂时处于上风,解密一方肯定不会善罢甘休。


------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:05:49
5259
75507
来自:皇冠现金
注册:2004-02-06
发帖:484+18049

Mark


------------------------------------------------------------------------------------------- 这个家伙很懒,什么也没留下......
2019-01-19 23:11:31
2445
12
来自:保密
注册:2001-06-03
发帖:179+4263

帖这些只是为了让大家在看故事休闲的同时感受一下科学的精神


我是菜鸟我不懂的


关于之前我发的百位诺贝尔奖得主联名支持转基因的帖子我就不再帖了,被删一次,锁二次的,还有一个朋友在我每个回复上绿一回,也真是很执着啊


希望国人在科学思维与独立思考方面可以持续进步


------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:17:51
2445
12
来自:保密
注册:2001-06-03
发帖:179+4264
钥匙:为什么是密码学最关键的概念?



上节课我们讲到了第三代维吉尼亚密码的加密思路,从这个加密法开始,密码学领域最关键的概念——“钥匙”就出现了。


它是加密和解密的核心,我们的课之后凡是涉及到加密解密,就再也离不开钥匙了。

对于想了解现代密码学基础的人来说,这节课是最重要的,一定要认真听。


1


我们先回顾一下什么是钥匙——


我们默认要用多套密码给原文加密的时候,具体操作中每个字母由哪套密码来加密,是由钥匙规定的。


为了处理方便,钥匙最初都是一个正常的单词,比如dream、flower、king等。钥匙中每个字母的顺位,表示原文中对应的字母在加密时采用第几套加密法。


原文很长,钥匙最初很短。但没关系,为了让原文和钥匙一一对应,就反复使用钥匙。比如钥匙是bed,只有3个字母,我们可以bedbedbed这样一直循环下去,和原文中每个字母一一对应。


维吉尼亚加密法,我们也简单回顾一下。


如果钥匙是bed的话,这个钥匙由3个字母组成,长度是3。那么原文中任何一个字母,都有可能被加密成三种其他字母。因为bed中的b代表后移2位,bed中的e代表后移5位,bed中的d代表后移4位,原文中任何字母都有可能被后移2、4、5位。


那么当钥匙是bed的时候,原文中经常出现的定冠词the,会被加密成3种样式。但如果钥匙是university这样由10个字母组成的长钥匙,原文加密后变成什么样,种类就是10种。这个看起来并不多,但当我们不知道钥匙文具体是什么的时候,种类就会变得无穷多。


而可能性多,其实并不是维吉尼亚密码法的优势,因为即便是单套加密,也有无数多可能性。


那维吉尼亚加密法的优势是什么呢?


维吉尼亚加密法真正的优势是,密文中拼写完全一样的字符,对应的原文可能性也是巨量的,比如说,如果密文是10个字母,钥匙也是10个字母,那么原文就有10^10,也就是100亿种可能性。


同样的原文对应上亿种密文,相同的密文也一样对应上亿种原文。这才是维吉尼亚加密法难以破解的关键。


曾经人们为了抹去字母的频率特征,选用同音替代法。但这样最多只能做到一种原文对应N种密文,而且N一般不会超过10,但反方向上密文一定只对应一种原文。


所以同音替代法的强度,远不及维吉尼亚密码法。


2


既然维吉尼亚密码法这么强大,是不是无法破解呢?当然不是。


下面我先按步骤讲讲破解方法,再说说这种漏洞的出现是什么因素决定的。




我们先来看一个例子,在这个例子里,原文是“the sun and the man in the moon”,钥匙是KING,密码文是一串看起来没什么规律的字母。这3样,我们现在都知道。




原文的内容中,有3个定冠词the,变成密文后,the变成了两种样子,第一种是DPR,第二和第三种是BUK。第一个我们不管,关键点就在于——


第二个和第三个竟然加密成了相同的密文。


你肯定还记得我刚说过维吉尼亚加密法的优势,现在就忍不住要问:


你刚才不是说同一个原文会被加密成非常非常多的形式吗?怎么这短短一句话,原文里的the就被两次加密成同样的密文了?只是因为太巧合了吗?


不是的。我们可以看钥匙单词KING,它由4个字母组成。我们再看密文中,后两个代表the的BUK,间隔了8个字母,间隔距离正好是钥匙长度的2倍。也就是说,正好在KING这个钥匙循环到整数倍的时候,如果也正好赶上出现了同样的原文,那巧合就出现了——原文就会被加密成相等的密文。




这一点,就是破解维吉尼亚密码最关键的部分。



3

当然,刚刚为了让你好理解,我把钥匙是什么,原文和密文是什么全写出来了。实际破解的时候,你手中只有密文,既不知道钥匙是什么单词,也不知道这个单词的长度,难度会大大增加。但还是有方法——


从密文中把完全一样的单词挑出来,从中总结规律,分析出钥匙的长度。


你一定会质疑:


刚刚不是说维吉尼亚加密法中,相同的密文对应的原文不但不是唯一的,而且数量还极为庞大吗?钥匙是4个字符的情况下,如果密文长度也是4个字符,那密文对应的原文会有256种可能。现在怎么好像原文经常会被加工成相同的密文了?


哎,这背后的原因就是,虽然密文可以变成原文的可能性非常非常多,比如说,有256种之多,但其中大部分拼写出来,根本不是有意义的单词,而是一串没意义的字母,当然就谈不上能拼成完整的句子。


所以,密文对应的原文虽然理论上数量巨大,但拼写规则一卡,数据量就急剧减少。




而且密文里的字符串长度越长,对应真实存在的单词数量就越少。


比如说,让你随口举例由3个字母组成的单词,你光凭脑子想就能找出10多个。但现在我要你随口举出几个由15个字母组成的单词,估计你一个都想不出来,就算查字典,数量也不是特别多。


4


所以,破解维吉尼亚加密法的方法就是——


第一步,是从密文中找出拼写完全相同的字母串,尤其是那些长度大于4的重复出现的密文。比如一篇几百个字母的密文中,长度超过4,并且重复出现的字母串一共有4种,我们就把它们叫作甲乙丙丁。


第二步呢,我们就数一数,它们第一次出现到第二次出现,中间隔了多少个字母。比如说,如果甲字符串重复间隔了20个字母,那它代表了什么意义呢?




它就代表这段密文对应的钥匙,在这20个字母中,正好反复使用了若干次。那具体是反复使用了1次、2次,还是4次呢?其实都有可能。我们把所有可能性都列出来。


比如说间隔20个字母后同样的密文再次出现,就有这样几种可能:


如果钥匙长度是2的话,说明钥匙正好反复使用了10次, 如果钥匙长度是4的话,说明钥匙正好使用了5次, 如果钥匙长度是5的话,钥匙正好使用了4次。 如果钥匙长度是10的话,钥匙正好使用了2次。 如果钥匙长度是20的话,钥匙正好使用了1次。

你发现没有,其实就是把间隔数的所有因数都找出来就对了。这时候乙、丙、丁的情况,也按同样的步骤操作。我们还会得到很多种钥匙长度的可能性。




到底哪个可能性才是对的呢?我们只要看看,哪个因数在所有甲乙丙丁密文的因数列表里都存在,那个因数对应的钥匙长度就是最终的答案。


到此为止,大功告成。


5


可能有些人觉得,这没什么可高兴的,知道钥匙具体的内容才管用啊,知道它的长度有什么用呢?


其实不然。


比如说,我们已经知道钥匙的长度是5了,那就意味着在原文中第1、第6、第11、第16……,这些字母单独挑出来放在一组叫作A组。A组可是由维吉尼亚密码表中,同一行移位的字母加密得到的结果。我们再把第2、第7、第12、第17……,这些字母挑出来放在一起称作B组,它们又是用另一行移位字母加密得到的。




那么使用单一一套移位法加密过的文字,我们能不能破解呢?当然了。具体怎么操作,估计你已经想到了——就是我们之前讲的频率分析法。这时候凡是那些出现频率最高的,我们都可以猜它是原文中的字母e,然后再依次分析下去。


所以,猜中钥匙长度就等于,把维吉尼亚密码法化简为N套最基础的移位法了。


6


这节课,我们完整讲了怎么破解第三代密码——维吉尼亚密码法。核心就是猜钥匙长度,而钥匙也是之后所有加密法和破解法关注的重中之重。


当年抓住钥匙长度破解维吉尼亚密码法的过程,别看我们说出来只用5分钟,但历史上,破解法与加密法足足相隔了230多年的时间。


上节课我们讲过,到底是谁发明了维吉尼亚加密法,有很多争议。其实它的解法到底是谁发明的,也有争议。


在20世纪之前,人们一直以为是卡西斯基在1863年破解的,所以一直以来这套破解法叫作“卡西斯基试验法”。但是后来更多的资料公布,发现剑桥大学的巴贝奇在更早的9年前就已经写下了解法。只不过受限于当时英国和俄国在打克里米亚战争,英国情报部门禁止他公开发表成果。


损失了一个发明者的荣誉,但是换来的是英国在之后9年里,轻松获得俄方机密文件的技术优势。


发明者受委屈,这既是密码学领域的特点,又是密码学研究者躲不过的委屈。


不论是剑桥大学的巴贝奇,还是普鲁士军官卡西斯基,虽然他们破解了维吉尼亚密码法,但他们在世的时候,始终都不知道自己其实已经在密码学上引起了一场革命。


最后对这节课做个总结:


破解维吉尼亚密码法的关键,就是猜出钥匙的长度;知道了钥匙的长度,维吉尼亚密码就变成了最基础的移位法,用频率分析法就能破解。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:20:41
2445
12
来自:保密
注册:2001-06-03
发帖:179+4265
字母类语言:为什么在加密上有基因优势?



1

前面的课我们讲了替代法、移位法、维吉尼亚加密法,以及它们对应的破解法。


现在有个问题:这些加密法和解密法进化的动力是什么?是一些绝顶聪明的人要挑战别人留下的难题吗?


只能说一小部分是。更多进展,是被逼出来的。


以维吉尼亚加密法来看,从算法出现到真正广泛使用,之间隔了200年。原因我们说过,它加密解密的过程,在纸和笔的年代操作起来太繁琐,太容易出错。安全性在当时真的是高,但效率实在太低了。


但在之后200多年时间里,迫使人们不得不用维吉尼亚加密法的因素积累得越来越多。


第一个因素,是欧洲各国都成立了自己的“黑房厅”,也就是专门从事破译工作的情报部门。


基础水准的加密法对付老百姓还可以,但对情报机关黑房厅来说,只需要几个小时就可以破译。所以迫不得已,只好花大量时间成本,使用维吉尼亚加密法。


第二个因素,是电报出现了。信息传递的效率大大提高,但如果是需要保密的内容,用电报发送就存在一个问题——你需要让电报员把文件从原文翻译成摩尔斯电码。


既然是保密信息,那对谁都应该是保密的,电报员也不应该看到。为了防止电报员看到原文,只能先加密再给电报员,让他把密文翻译成摩尔斯电码传给收件方,收件方拿到后再解密。


但电报还有一个问题,就是线路途中会有人搭线窃听。如果只是为了让电报员看不懂,用一套简单的替代法就足够了。但如果真的存在一些搭线窃听的人,这人一定也是密码从业者。所以,应付电报员的基础加密法就不能再用了,只能使用维吉尼亚加密法。


起码上面这两个最重要的因素,逼得那时候的有关部门不得不使用更好的加密法。




如果不得不用的话,那索性就得用利索了,所以在维吉尼亚加密法出现后200多年,加密解密的操作就不得不换用其他工具了。不再是用纸和笔完成了,而是用一些带着齿轮和圆盘一样的机器,来做这样简单重复、高强度的工作。


也就是从那时起,制造计算机的念头就出现了。


2


上面所说的情况大都是针对密码专业从业者的,老百姓在1850年代会不会用到密码学呢?


也会的。比如像年轻的男女互相表达爱意,但父母反对,俩人的来信经常被偷看甚至销毁。怎么办?于是就有人选择在当地报纸上刊登个人启事,用这种方式向对方表达爱意。有些报纸的个人启事,后来干脆就成了相思专栏。


但情人们为了不让别人看懂自己说给恋人的话,登出的内容都是加密过的。一般读者确实会被基础加密法挡住,但它可挡不住那时的密码学家。有些密码学家就出于好奇,破译每天相思专栏的内容,自己看了解闷儿。


还有一个对每个人都有实际好处的事情,也会用到加密法。


当时英国的邮政系统有个漏洞,寄信很贵,但递送报纸的服务却是是免费的。有些人就想占这个便宜,用缝衣针在报纸上按摩尔斯电码的规律刺小洞,这些小洞在灯光下一照是很明显的,收件人把小洞翻译出来,就是信的内容了。这样一来,相当于免费寄信。




还有一些小说,会把密码学写进故事情节。


比如,法国著名科幻小说家儒勒·凡尔纳的《地心历险记》《桑道夫伯爵》,还有英国著名小说家柯南·道尔的《福尔摩斯探案集》中,都出现了以密码为主线剧情的内容。


3


这些小说内容虽然精彩,但都是虚构的。我下面要讲的,可是实打实的出现在那个年代的密码传奇故事——比尔密码


1885年,有一本只有23页的小册子《比尔密码》出版了,里面讲了一个发生在60多年前的神奇故事:


在美国西部淘金热的时候,1820年,一个小伙子比尔在弗吉尼亚州的一个小旅馆住了2个月,当时给人印象挺好的,后来不声不响走了。2年后他回来了,又住了2个月,临走时什么话没说,给店老板留下了一个上锁的盒子。几个月后,老板又收到比尔一封信,说盒子里有他和他合作伙伴非常重要的东西,但暂时拿不回去,请老板代为保管10年时间。如果真的超过10年都没人来领,老板就可以自行打开了。


这盒子里除了有一份说明书是可以读懂的,其他文字都是加密过的,解密的钥匙在另一个人手里,这个人会在10年期限到的时候把钥匙内容告诉店主。





老板也确实信守承诺,不止等了10年,等了23年才打开盒子,但那个据说要给他钥匙的人始终没有来信。盒子里除了有份说明书外,还有3封加密的信。店老板花了17年时间也没破解密文,在去世前把这盒子东西交给了他的朋友。


这个人就是在1885年出版那本小册子《比尔密码》的人。在他手中倒是有所突破,其中第二封信被破解了,其他两封实在没搞懂,他就希望大家一起来努力。



其中第二封信被作者猜中了,钥匙是《独立宣言》的原文。第二封信的内容说的是:


在1819年到1821年,比尔和另外30个合作伙伴分两次把2000多磅黄金和5000多磅白银埋了起来,除此之外还有价值13000美元的珠宝。然后把埋藏地的地形特征详细描述了一下,但没说在哪儿。最后说,具体的埋藏地址在第一封信里,第三封信写了30个合作伙伴的详细信息。


1885年,这本小册子出版后引起轩然大波。以现在的市值算,埋在地下的财产大约合4300万美元。


所以很多聪明人都想破解第一封信。很多人从一九二几年一直研究到一九七几年,甚至在60年代,关注宝藏埋藏地的人还成立了一个比尔密码与宝藏协会,希望通力合作,如果最后真的挖出来了,财富大家一起分。




当然,也有质疑说这就是一场恶作剧,其实质疑的也有道理。反正一个23页的密码小册子,让一部分美国人如痴如醉长达100年,也一定程度上说明普通民众至少对密码学不陌生。


4


到了现在,我们可以回头看看中西方文化在密码学上的差异。


你思考过这个问题没有:每个国家都有加密的需要,尤其是在战争时期,但为什么欧洲国家就走得很远呢?中国为什么没有发展出复杂的加密方法呢?


直接告诉你答案,这是因为信息的记录方式把中文卡住了。只要使用表意类的书写方式,注定要卡在隐藏法这个级别,很难发展出更高级的密码学方法。


比如说,“祝你生日快乐”,这是原文,用移位法向后移动3位加密。对于英文来说,直接把每个字母后移三位就可以了;但对中文来说,压根不存在祝贺的“祝”往后移动3位是什么字这个概念。


对中文来说,能做的顶多也就是藏头诗,或者把相邻两个字调换顺序,或者奇数位的汉字挑出来,偶数位的也挑出来,然后把这两列汉字首尾相接连起来。


总体上说,如果你用中文,那么可以把加密规则用数学语言描述出来的可选方案,大大少于字母书写的文字。所以在拼音出现之前,汉字的加密方法大都是在各种包装、封印,还有藏匿技巧上下功夫。


而表音的字母文字,天生就有一个顺位表,一切单词都可以视为数字。于是对数字的运算就成了自然而然的加密方法,而且方法是无限多的,类型和差异也会非常大。




所以,字母类语言在加密和解密的对抗中会逐渐升级,从猜字谜的层次升级到数学运算的层次;而表意类文字在数学化之前的加密,只能停留在浅层方法上。


但汉字真的就没有可以数学化的方法吗?起码唐宋元明清这几百年没出现过。


于是密码学领域从播种开始,就是依照字母类文字和数学结合的方式在欧洲生长。几百年过后,当19世纪末科学技术第一次在中国推广的时候,起码在密码学这个狭窄的领域,我们只能跟随已有的行业规则研究,没有机会自己建立一套新思想了。


表意的文字除了在密码学上因为文字本身属性被卡住,还被卡在印刷技术上。


比如活字印刷虽然早早就在中国出现了,但事实上,中国历代始终没有多少书是用活字印出来的。因为汉字的数量实在太多,制造活字排版印刷的成本都超高。




从16世纪欧洲的科学革命开始,我们就已经知道一个规律:


凡是可以用数学详细描述的对象,都有巨大的发展潜力;在这场仍未结束的革命中,凡是把一直没能数学化的事物完成了数学化的人,都将被写进科学史。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:26:33
2445
12
来自:保密
注册:2001-06-03
发帖:179+4266
改进钥匙:你以为的“随机”都是“伪随机”




如果以密码学的视角,我们怎么划分年代呢?


其实可以这样分。比如,我们现在皇冠娱乐网在一个加密法胜于解密法的年代;而1860年到1920年的人,可就没有那么幸运了,因为他们皇冠娱乐网在一个解密法胜于加密法的年代。


那时候加密法顶多是给解密专家设置很多麻烦,把工作量变大,但解密者知道,理论上来说它们都是可以破解的。




而到了1920年,加密法终于翻身了。


虽然并不是什么横空出世的全新方法,只是继续在第三代的维吉尼亚加密法1.0版本上做了一些小改进,就让它变得极为难破,或者压根就没法破。


1


之前我们讲破解维吉尼亚密码的时候就知道,它的缺陷在于钥匙的循环。


假如一个钥匙有5个字母,那对应的密文,每逢5个字母就会用到同一套密码加密。所以只要知道钥匙的长度,再分别对5套密码用频率分析法,维吉尼亚加密法就破解了。


处于下风的加密一方自然不甘心,怎么才能补上这个缺陷呢?


答案可能你也想到了——增加钥匙的长度。


比如说一篇文章有1000个字母,如果钥匙的长度是5,也就是说用了5套加密法,那么每套加密法会匀到200个字母。


对于频率分析法来说,要想把字母出现的频率统计准确,有一个必要条件——字母足够多才行。


200个字母还是可供分析的,但一个ok、no这样的短消息,什么频率特征都体现不出来。而这,正是加密者希望出现的局面。


那么现在,还是那篇1000个字母的文章,我们的钥匙长度从5增加到50的话,每套加密法匀到的字母只有20个了,连26个字母每个出现一次的量都没到,这样的量几乎就不会表现出字母的频率特征。


如果再继续增加钥匙长度呢?比如说钥匙文和原文等长,也是1000个字母,那之前破解维吉尼亚加密法的所有方法都会失效了。




这时候钥匙又要怎么设计呢?一般是用一首诗或者一篇其他文章当做钥匙,这样方便大家约定规则。


这种加密法,我们可以把它当做维吉尼亚加密法的2.0版本



2


不过2.0版,还是有破解方法。


之所以能破解,就是因为钥匙和原文等长时,为了方便,人们往往会使用一首诗或者一篇文章当钥匙。而一首诗、一篇文章是有意义的单词组成的,它们的字母排列一定是符合拼读规律的。


有规律可循,就可能被破解。


破解的方法,是先假设原文中一定会出现常用的单词,然后拿它去和密文对照,倒推钥匙的单词是什么。


原文中短小的词假设它是个什么呢?最好的选择就是定冠词the,或者at、in,这些总会用到的单词。




比如,假设原文中任何三个相连的字母都可能是the,在我们已经知道密文是什么,又假设了原文是the的情况下,我们去对照维吉尼亚的字母表,对应的钥匙是哪三个字母也就确定了。


不断的把the放在所有位置上,然后去观察钥匙的样子,有时候钥匙就会呈现出一些符合单词拼写规律的样子。




反正这个方法就是先假设原文里一定有the这样的词,然后还有一个前提,就是假设钥匙是像一篇文章或者一首诗那样有规律的单词拼写成的。


在假设原文有the,手中又有密文的基础上,求出the对应的钥匙字母就不难了。


看看这部分算出的字母,是不是也符合单词拼写规律。如果符合,很可能这部分钥匙字段你就猜对了;如果不符合,就说明猜得还不对。


这种方法完全避开使用频率分析法,不需要有足够大量的字母出现,都可以分析出原文。只是除了规定步骤外,还要有很好的猜字谜的功底,总体来说属于体力活。




到此为止,维吉尼亚加密法的第一个改进版2.0版,也就是把钥匙长度增加到和原文一样长的方法,也被破解了。


3


加密法不服,继续改进,这次的改进其实是修补了2.0版本的漏洞。


你还记得是什么漏洞吗?就是钥匙是一段完全符合拼写规律的文字。


如果钥匙根本不是一首诗、一篇文章,而是一大段完全随机的字母,那顺着上一版的方法,接下来的任务就是猜测随机字母是哪些,这实在是个不可能完成的任务。


而且不光是听着不能完成,之后有数学家分析了整个过程,证明了这种把钥匙编成随机字母的方法,在数学理论上就是不可破解的。


这个方法在第一次世界大战后出现,后来就被叫做“单次钥匙簿密码法”。我们可以把它定义为,维吉尼亚加密法的3.0版本。


这是我们目前说了这么多,第一个绝对安全的加密法。


但实际情况是,它几乎就从没在实战中规范使用过。原因你肯定也猜到了——

它的效率异常的低,根本就无法用在需要大量通信的领域。


当时的具体操作是这样,通讯部门人手一本厚厚的钥匙簿,大约几百页,每页都是密密麻麻的随机字母。加密第一页时就用钥匙簿第一页,凡是用过的那页就撕掉销毁,直到这本密码簿全部用完,再等总部发第二本。




假如像一战那个规模,一共有几万个发报机,每个人都要有一份钥匙簿,不方便携带先不提,就算是这几万人能协调一致,把该用哪页这件事搞明白就很不容易了。


4


这只是操作层面的障碍,更大的门槛在于 —— 产生随机字母排序,是一件几乎不可能的事。


这一点是超过很多人日常经验的。你说平时听歌儿,播放顺序不就有随机播放的选项吗?但我要告诉你,其实那都是伪随机。


在真正的随机播放下,你听起来会明显感觉,“播过的歌儿怎么又播了一遍?”或者“本来就20首歌,为什么播了一下午我最爱的第三首歌从没出现过?”


苹果公司曾经就因为用户抱怨随机播放不合理,才修改的算法。原来是真的随机,后来就把随机播放改成了用户“感觉上的随机播放”。


其实苹果最后采用的这种播放顺序,应该叫做“循环同余随机”。也就是让人听起来感觉每首歌都不是我刚听过的,而且在比较合理的次数后,每首歌都能轮到播放一次。


可以这样说,凡是通过软件制造的随机都是伪随机。只有在大自然中,一些已经被证明是随机的量子物理过程,才是真的随机。


比如说一种半导体管叫齐纳管,它被电流击穿后产生的白噪音是真随机。或者有些放射线的原子,在衰变的时候会向外辐射α粒子,如果把α粒子一个个射出来的时间间隔记录下来,这些间隔的数字是真随机的。


所以,对于人来说,真随机是一个很难获得的东西。


而我们脑中以为的随机,比如随机字母、或者我的双手在键盘上一通乱敲,那其实都不是真随机。


你信不信,只要敲的数量足够多,大数据是可以从中分析出来的。不同的人乱敲的“笔迹”,是不一样的。小明乱敲的模式和阿花乱敲的模式也是不一样的,于是就可以从中找出规律。


而这种规律,就可以当做是一种类似于一首诗、一篇文章那样的拼写规律,那么破解维吉尼亚加密法2.0的方法就还是可以用上。




所以,虽然理论上说单次钥匙簿密码法是不可破解的,安全性没有破绽,但真的随机是很难轻易获得的,而获得了以后又很难大规模使用,效率极为低下。所以这种方法,几乎没有在真正的战场上使用过。


5


到这里,我们在算法上的讲解就要告一段落了。


这节课我们讲了维吉尼亚加密法的2.0改进版和2.0改进版的破解法,还有3.0改进版——单次钥匙簿加密法。理论上说,3.0改进版是无法破解的,但实际上又是几乎没法用的。


我们回顾一下密码学的应用就会发现——


它其实是一种想方设法给别人读取信息制造更多麻烦,与此同时又不给自己读取信息增加太多麻烦的学问。


实际考量后的加密目标,并不是追求绝对的安全、无法破解,而是在尽可能增加安全性的基础上,保证使用上的效率,找到平衡点。


因为给别人增加麻烦的同时,也给自己成倍的增加麻烦,导致最终加密的算法虽然出现,但没能马上用起来的例子,咱们的课里到现在已经遇到过两个了。


第一个,是维吉尼亚加密法1.0版。它是1580年出现的,但当时人们只能用纸和笔解读,加密解密的过程对自己人都太麻烦,所以实际要到19世纪末才开始使用。


第二个,就是这节课讲的单次钥匙簿密码法。这个方法甚至还没有维吉尼亚加密法1.0那么幸运,因为在它尚未轮到好时机被人用上的时候,新一代的加密法就诞生了。




------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:29:23
511
29
注册:2015-09-03
发帖:337+3366

马克


------------------------------------------------------------------------------------------- 这个家伙很懒,什么也没留下......
2019-01-19 23:29:40
2445
12
来自:保密
注册:2001-06-03
发帖:179+4267

密码与战争 信息为什么比武器更值钱



说起密码学和战争的关系,通常的逻辑是:


某个加密法,让战争出现了什么变化;



什么被破解,战局发生了逆转。


这些都没错,但都不完整。



完整的逻辑除了密码学对战争的影响,还应该包括战争对密码学的影响。


第一部分,第一次世界大战中由密码学决定的战局;


第二部分,从反方向看待一战对密码学的影响。


密码学对战争的影响来说,可以总结:



信息的价值比武器的价值要高得多。


尤其在现代战争里,当任何一方都拥有足以毁灭对方N次的武器装备时,N是10次还是10000次,武器对战局的影响已经不太大了,反而是知道对方的作战计划才最重要。所以,信息才是最宝贵的。



密码学对一战影响最大的事件有2个。第一个是在整整4年时间里,在密码学领域,德军一直处于下风,很大程度上削弱了他们武力上的优势。



德军在信息战上的失利,是被法国一整套圈套设计出来的。



在一战开打前,无线电报就已经广泛使用了。当时欧洲密码学最强的国家是法国,法国的情报部门马上就意识到,无线电这个新发明会让更多人不得不使用加密法。



因为从前的电报,是用电缆传输的,虽说中间可以搭线窃听,但也要在沿途挖地三尺,把线缆找到,动一番手脚才能把线搭好。可无线电信号是在大气层里传播的,谁架设天线都可以收到。而且从无线电报上不仅能得到密文,还能分析出其他信息:



当时法国****人员甚至可以做到,听出摩尔斯电码发报人的动作习惯,比如说发点和线的间隔时间的长短、点与点的间隔时间等。



此外,还能测量电磁波是从哪个方向发出来的,如果****点很多,最终就可以通过三角定位法,找出发报员的地理位置。发报员的位置,一般也就是队伍的位置。队伍的位置被暴露意味着什么,相信大家都明白。



而德军对此是一无所知的,他们甚至在开战后的前2年都没有专门设立分析密码的部门。这倒也不完全因为他们不重视,而是因为英国、法国的信息基本都采用有线电缆传输,压根就没什么无线电信息可拦截的,也就没有什么密文需要破解。



在德国攻占法国的战争中,法军一旦守不住准备撤退时,第一个任务就是把桥、路,还有电报电缆炸掉。这样德军到了新的占领地,根本没法使用当地的有线电缆,只能用无线电通信。而撤退的法国军队,却可以继续使用未占领区的电缆通讯。



这样,法军能破译德军的情报,而德军却不能破解法军的情报,一定程度上削弱了德军军事上的优势。


如果说上面这件事是密码学削弱了德军的军事优势,那下面的这个事件,就直接导致德军的失败了。



直到开战2年后,德军才匆匆忙忙用上了密码。但因为学科基础薄弱,密码的水平有限,基本都是一些替代法和移位法的叠加。所以经常是没用多久就发现被破解了,只好重新换其他的密码。



其中有一封特别重要的信被破译,最终扭转了一战的结局,这封信史称“齐玛曼电报”。



一战开打后战事焦灼,英国法国,甚至是美国社会都在一直呼吁美国参战。而美国在大西洋另一侧,欧洲打成一锅粥也不会伤及它,所以最初美国政府就没打算加入。



但打急眼了难免误伤,比较严重的一次是1916年,德国的潜水艇在大西洋上击沉了一艘邮轮,有1200名旅客死亡,这些都是平民,其中还有128个美国人。德国怕事态恶化,把美国拉入战争,赶紧道歉赔款,并且承诺今后一定只针对作战目标,不再伤及平民。美国总统威尔逊也接受了这种处理方式,不参战的国策依然不变。



但其实德国海军最大的优势就是有几百艘潜艇,如果潜艇一定要确认好是不是平民船只再做决定,偷袭的最佳时机早就错过了。所以实际上德军指挥官暗中下的命令就是,不用管是不是平民,只要不是我们的船只,就可以发射****击沉。



但他们同时也忌惮美国,万一没能在6个月内拿下整个海上控制权,再把美国平民打死打伤无数,美国也许真的会到欧洲参战。



为了防止这样的事出现,德国制订了一个拖住美国的保险计划,具体内容就是——给墨西哥提供军事支持,让它攻打美国南部,然后许给墨西哥几个州的领土。与此同时,让日本攻打美国的西海岸,自己再分一些兵力攻打美国东海岸。这样美国一下三面受敌,自顾不暇,就不会来欧洲参战了。



这项计划的传达和说服工作,是由德国新任外交部长齐玛曼(Arthur Zimmerman)负责的。


德国自己的海底电缆,其实在一战一开打的时候就被英国的军舰捞上来割断了,所以没法直接发电报。而这种攻打美国的重要信息,通过无线电发送风险太高。



德国辗转从中立国瑞典发电报给墨西哥和日本,结果电报还是被英国情报部门截获了,而且没过多久,电报内容就被破译了出来。



英国人是怎么办的呢?他们没有马上告诉美国,现在没有好时机。因为一旦美国因此宣布参战,德国肯定会怀疑当前的加密法已经被破解了,马上会更改新的加密方式。



最终,英国选择的是继续观察时局。因为德国已经开始实施无限制海上攻击了,又不断有美国平民伤亡出现,如果美国因此宣布参战的话,齐玛曼电报内容等他们宣战后再告诉美国人也不迟。



这样一来,既帮了美国的忙,而且从德军角度思考,美国参战的原因显然是因为平民被德军攻击大量死亡,而不会想到是因为齐玛曼电报被破解。这样德军还会沿用从前的加密法,不会换新,英国法国就可以继续对德军的动态一览无余。



谁知美国的平民一而再、再而三被德军攻击,美国依然坚持不参战。美国认为如果真的参战,死亡数字一定远超过现在的规模。



这下只有一条路可走了,就是让美国知道齐玛曼电报的内容,但仍然不能让德国人怀疑英国已经破译了德军的加密法。




精明的英国人想出了一个天衣无缝的方法:



想办法让特工潜入墨西哥的电报局,在那里窃取一份由德国驻美大使馆发给德国驻墨西哥使馆的通知原文。虽然主体内容依然是三面合围计划,但这份电报在抬头、称呼等小细节上,就和英国直接拦截德国的那份不一样了。



派出的特工非常给力,成功窃取后,把消息透露给了欧洲其他国家的现金游戏媒体,马上这条现金游戏就传到了美国领导人耳中。美国惊出一身冷汗,随即布防到位。



德国人也掉入陷阱当中,发现这么机密的电报竟然泄露了,于是就对泄露原因展开了调查。调查结果表明是墨西哥有叛徒走漏了这封机密电报,德军始终都根本没有怀疑自己的密码被破解了。



1917年4月2日,美国总统终于宣布:德意志帝国政府最近的行径,无异于对美国政府和人民开战,我们被迫只得接受交战状态。



你想,两年多来,那么多船只被炸、平民伤亡,那么多国家的外交部门努力都没用,结果让英国的密码学家搞定了。



如果一定要给这则电报信息解密标出一个价值的话,你觉得它的价值有多大呢?我想可能是美国参战的所有兵力吧。



假如美国在不知情的情况下被三面合围,也许第一次世界大战,交战双方的胜负结果会对调。这信息不比武器值钱多了吗?


说完密码学对战争的作用,我们再来看看战争对密码学的影响。



在密码学的发展历史上,有这么一个规律 ——密码学总是在信息流动量突然增加时飞速进展。



一战时,由于涉及全世界主要国家,仅仅法国一家就截获了德军超过1亿条电报。二战期间,各国几乎发动了全世界最顶级的数学家,最精通语言的,最会猜字谜的聪明人一起搞加密解密。



所以,这两场战争都相继破译了之前被认为是无法破解的加密法。而随着旧加密法被破译,又总会诞生新一代的加密法。



后来,手机的出现,互联网的出现,也都导致信息流动量猛增,解密者甚至已经不止是官方情报机构的人了,比如黑客就是民间解密者的典型代表。


密码学和战争的关系,可以分为两方面来看——


一方面信息的价值比武器的价值要高得多,密码学会深刻影响战争的结果;另一方面战争对于加密解密的需要,又直接推动了密码学的发展。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:39:16
2445
12
来自:保密
注册:2001-06-03
发帖:179+4268
恩尼格玛机:密码战进入机械电子时代




1


前面的课里,我详细讲了前三代密码加密法——隐藏法、替代法和维吉尼亚加密法。这节课我们要讲的,是著名的第四代加密法——恩尼格玛密码机(Enigma)。


这个名字翻译版本挺多的,不论是叫英格玛机,或者是哑谜机器,还是奇谜机,指的都是图灵在二战后期破译的那种机器。在我们课里,就统一叫它“恩尼格玛机”。


它使用的加密方式,本质上还是第二代加密法——替代和移位,但因为可以切换无穷多种加密配套组合,所以在对抗频率分析法上极其有效。





恩尼格玛机是一种机械电子式的加密机,由一堆齿轮、电线、灯泡、转盘、摇杆组成。其实使用机器做繁琐的加密工作在之前也有过,只是因为它们都没有量产,所以也没有流行。而恩尼格玛机,是第一个大规模量产的加密机。


也正是从它开始,密码学不再依赖纸和笔的运算,使用机械和电子加密的时代正式到来,所以它是第四代加密法。



2


第一台恩尼格玛机,是一战刚刚结束的时候由德国发明家雪毕伍斯(Arthur Scherbius)和里特(Richard Ritter)制造出的。




这台机器分3部分,3部分之间由齿轮和电线相连:


第一部分,是敲原文用的键盘; 第二部分,是把原文加工成密文的编码器; 第三部分,是密文的显示板。

操作员只要做好设定,在键盘上敲入原文,经过编码器编码,密文显示板会按规则点亮密文字母,抄写员把点亮的字母的顺序记录下来,加密过程就完成了。


这其中重点就是编码器,编码器的工作原理有点复杂,下面我详细说说:


编码器由一堆可以手工设置的机械部件组成,任何地方的调整都会改变加密的结果。


其中最大的部件是齿轮式的字母盘,它前后通过导线与敲原文用的键盘,以及密文显示板相连。键盘那边敲一个字母,信号通过导线传给齿轮上的触点,再通过导线传到密文显示板上,原文就这样被加密成另一个字母了。


听起来好像没什么,但恩尼格玛机的真正高明之处在于 —— 每敲一个字母,齿轮会往下转一格,齿轮的转动导致线路连接的变化,而连接线一变,又直接导致加密结果的不同。


所以同一个字母敲入第二次、第三次,输出到密文显示板的结果也都不一样。总之,齿轮能转多少格,就意味着有几套加密法等着轮替。




更高明的是,恩尼格玛机的加密可能性,理论上是无限多的。最早齿轮一圈只有6格,也就是只有6套加密法。后来感觉这不够用,齿轮就增加到了26个格。


再后来,单套齿轮格数不再增加,而是增加了第2套齿轮,上面也有26个格。只有在第1套齿轮转完一圈后,第2套齿轮才前进一格。这样一来,有两套齿轮的恩尼格玛密码机,相当于拥有26×26,也就是676套密码。如果还觉得不稳妥,可以继续增加齿轮的套数。






上面这是一张早期的恩尼格玛机的照片,可以看出它有3套齿轮。后来这个规模的恩尼格玛机,主要用于商业领域




上面这张图是使用了八组齿轮的机器,它是德军在二战中使用的最高水准的加密机。

它如果每个齿轮都有26格,那么使用的加密法有26^8套,也就是2000多亿套,这是一个非常大的量。当然,机器也很贵,最终只有德国海军配备了。




机械加电子的方式让加密解密错误大大降低,效率也高了很多。但关键是设计规范,可以量产。


3


好,现在我们从密码学细节上想想,恩尼格玛机属于哪一类加密呢?


没错,其实还是类似于维吉尼亚加密法。


它和维吉尼亚加密法1.0、2.0、3.0的最大区别就是钥匙,而维吉尼亚加密法各种版本之间的区别,也在于钥匙的设定上。


我们回忆一下前面讲过的内容:


1.0版,钥匙是随便想出来的一个词,然后重复的用; 2.0版,钥匙长度增加了很多,但为了便于双方协同使用,往往是一篇文章、一首诗; 3.0版,钥匙是纯粹随机字母,而真随机很难制造,密码簿又厚到不能用,所以3.0版只停留在理论上,实际几乎没人使用。

现在的恩尼格玛机,也仍然是在钥匙簿上做改进。


一方面,它比互相约定一首诗、一篇文章要没有规律得多得多;另一方面,这种钥匙肉眼看上去好像随机,但又不是真的随机。它依赖于齿轮和电缆的机械和电结构,其实有内在规律的。


而从密文中找出这种规律,就是破解恩尼格玛机的核心任务。


恩尼格玛机的方便之处在于,几组齿轮的初始值是可以随意设置的。


比如说都封装好了以后,每组齿轮在正上方都留一个小窗口,三组齿轮各自露出一个小窗口,收发双方约定好,这3个窗口在初始时各显示哪3个字母,然后他们按这个顺序编码信息、解码信息,互相之间就可以通信了。


为了更安全,可以每天更换一次3组齿轮的初始设定,一个月里需要约定的初始设定也只有90个字母而已,非常方便。


4


那现在问题来了,这种恩尼格玛机能不能用在战争中呢?


我们在第一节课就说过战时加密的原则,要假设敌方已经拥有了和自己一样的解密水平。以这样的标准来看,恩尼格玛机是很可靠的。


因为即便敌方有了一模一样的恩尼格玛机,但只要不知道我们事先约定的钥匙,也就是机器的初始设定是什么,有机器也白搭。


那这样的机器是完全没有方法破解吗?


直接告诉你答案——不是的。


原因还是我们反复说过的,恩尼格玛机通过齿轮生成的钥匙,只是看上去很随机,它内在还是有规律可循的。这个规律就是它会按次序转动,第一个齿轮转一圈后,第二个齿轮动一个格,第二个齿轮转一圈后,第三个齿轮动一格。光光就这个规律,就能给人提供破解机会了。我说的机会,就是用穷举法去暴力破解。


既然三个轮子,每个提供26个字符,那钥匙的初始值可以出现的最大组合就是26×26×26,也就是17576种。我就买回来100台机器,每个人都发一份同样的密文,挨个试,每台机器负责尝试其中的175种,说不准几个小时就能把初始值碰对了。




设计者早就考虑到暴力破解的问题了,所以他们在键盘和编码器之间又增加了一个叫“接线板”的结构,可以调换6对字母的线路。


比如你在键盘上按的是a,但电流信号却是沿着b的线路输出到编码器上的。通过调换26个字母中随意的6对,组合一下就增多到了1000多亿种,所以恩尼格玛机是可以扛住暴力破解的。


实在不行,还可以添加更多组齿轮,就像德国海军那样,甚至用到了8组,这让军用恩尼格玛机的安全性更有保障。


5


上面讲的是原理,下面我们来说说这第一代恩尼格玛机的命运。


可能跟你想的非常不一样,它第一代非常不顺利。


雪毕伍斯对产品做了一个高低端的区分。高端型号的售价折算到今天,相当于****18万元一台,重量大约100斤。最初推广给商业公司,宣传的理由是商业机密泄露会是巨大的损失。可是老板普遍却认为,买这台昂贵又不实用的机器造成的损失更大。


雪毕伍斯也试过找德国外交部门和军方,但前面我们讲过了,1918年的德国还没认识到自己的密码学远远落后于西欧大部分国家,所以也完全不用。


雪毕伍斯并不是那个时代唯一做出这项发明的人,当时荷兰人、瑞典人、美国人都注册过类似的专利,但没有人卖得出去。


有的人破产,有的人因欠款坐了牢。只有雪毕伍斯坚持到了最后。这倒不是因为他的机器有多好,而是因为他的家底厚。他原来的工厂什么都生产,恩尼格玛机卖不出去,那就卖涡轮机,卖卖枕头,这些都可以赚钱,所以就靠这些东西强撑着。


到了1923年,英国报纸刊登的两则消息,突然唤醒了德国情报部门。其中一条还是英国首相丘吉尔写的,他讲了1914年英国和俄国是怎么搞定德军密码的传奇故事,另一条是英国军方解密的关于一战的历史数据,尤其夸耀了自己在密码学上的优势。


结果德军看了之后感觉像被打了脸,同时也吓得不轻。从前他们以为自己在密码学领域,和欧洲其他国家水平同齐。现在突然发现,第一次世界大战那几年,自己的军事机密一直在被泄露,现状太可怕了。


经过仔细评估,德军找来几年前向他们推销过恩尼格玛机的雪毕伍斯,开始大量订货。不但如此,后来德国的国企也开始大量订购。


直到二战结束,雪毕伍斯一共卖掉10万多台恩尼格玛机。这些机器在后来20多年里一直保障着德国的通讯安全,但没想到就差最后一哆嗦。后来德国在二战中的败局,也正是因为对恩尼格玛机太过于依赖。这些我们后面会详细讲到。




二战中的恩尼格玛机影响到底如何?


其实雪毕伍斯自己根本不知道。因为他在机器刚刚大卖第5年的时候,就因为一次马车失控,撞墙身亡。


6


回顾一下,这节课我们讲了恩尼格玛机的加密过程。


正是恩尼格玛机的诞生,使密码学彻底进入了机械电子时代。


这个时代的加密,在原理上甚至还不如维吉尼亚加密法3.0坚固,但它在加密成本和加密坚固程度上达成了平衡。虽然在理论上依然是可以破解的,但这个弱点通过机械电子化弥补上了,弥补的方法就是无限增加破解的工作量。


也就是说,在1918年后,任何一个人通过肉身,通过纸和笔的运算,都无法和那时候的加密法抗衡了。哪怕那种加密法是可破解的,也没办法。谁想破解,也只能借助机械电子化的设备才可以。





------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:43:09
1568
50
来自:皇冠现金
注册:2011-06-11
发帖:4+1591


------------------------------------------------------------------------------------------- 这个家伙很懒,什么也没留下......
2019-01-19 23:45:15
2445
12
来自:保密
注册:2001-06-03
发帖:179+4269
数学家参战:密码战全面升级



我们来说说恩尼格玛机是怎么被破解的。


这可能是密码学史上最著名的攻防战。


1


很多人都知道,恩尼格玛机最终是被图灵破解的,电影《模仿游戏》说的就是这件事。

所以在大众心中,自然会觉得:恩尼格玛机是图灵在战争胶着状态下,凭一己之力攻破的,从此图灵的人生就升了一级。


其实这样的理解,有两个错误:

第一,恩尼格玛机的破解难度极高,它并不是一道难解的数学题,而是一套由情报部分负责运转的复杂的机械电子设备,所以光有脑子是不够的。准确来说,它是各国科学家和军人通力合作才破解的,图灵只是完成了最后一步。

前面至少有5个关键性的突破,如果没有它们,图灵是没法破解恩尼格玛机的。




这五个突破分别是:


1. 波兰密码学家与法国间谍合力搞清了机器的内部结构; 2. 波兰政府把密码学家破译的成果分享给了英国和法国; 3. 英国海军成功捕获了德国的一艘舰艇,从上面得到了一台真实的恩尼格玛机和一本钥匙簿; 4. 德军士兵在使用恩尼格玛机时,经常不按规范操作; 5. 盟军采用诱骗战术让德军故意发送特定词语。

有了上面5个前人做出的突破,在破解恩尼格玛机“万事俱备,只欠东风”的时候,图灵正好出现在正确的时间、正确的地点,最终发挥出常人难以想象的智力破解了它。




第二,图灵完全没有因为破解恩尼格玛机而受到应有的嘉奖。


图灵和那个年代所有在英国密码部门工作的同事直到去世,都不知道自己的成果具体被用在了哪场战斗,破译的消息挽救了谁,也不知道自己的工作对后世产生了什么影响。

图灵破译恩尼格玛机是多么耀眼,多么有价值的结论,都是在他去世后20年才为人所知的。


2


知道这两个典型误读后,我们再来看恩尼格玛机是怎么一步步被破解的。


其实破解的最大动力,就是威胁下的恐惧感。


一战后世界处于暂时的停火状态,英法虽然知道德国开始启用恩尼格玛机,也发现自己没有能力破解,但因为有《凡尔赛条约》限制德国军力发展,英法的密码局就没有特别重视破解方法。


当时对恩尼格玛机最重视的国家,你可能想不到,是波兰。


这个国家东边经常被苏联渗透,西边的德国又谋划着收复失地,所以波兰的警惕性极高,总感觉随时会被两边的强敌攻陷,从没放松过密码学研究。


他们先是弄到了一台商用恩尼格玛机,不过马上就意识到军用版的和商用版内部结构不一样。


后来听说法国间谍从德国的叛徒手里,弄到了军用版的《使用说明书》和《钥匙指南》两份重要资料,就强烈要求分享。法国密码局自己试了试破解不了,就转手把材料给了波兰人。




波兰密码学家分析后发现,说明书只能帮他们搞懂军用版的内部结构,但还是破解不了。因为当初德军就是假设敌人也有一模一样的机器,还是不能破解的情况下,才批准使用恩尼格玛机的。


3


那破解的关键是什么呢?


是要知道每次加密前人工设定的初始状态。




这个初始状态,包括3部分:


1. 设置接线板,要从26个字母中任意挑出6对儿接好; 2. 设置编码器中三套齿轮的前后顺序; 3. 设置每个齿轮的第一个字母是什么。

操作员每个月都会收到一本新的密码簿,上面记录着每天的初始设定。


但德国人并不会整整一天所有信息都使用密码簿上的这一把钥匙,这太危险了。因为当信息量足够多的时候,钥匙是很容易被猜中的。就算没有被猜中,比如说密码簿被特工截获了,那也是巨大的损失。


为了堵上这个漏洞,德国人其实是每发一条信息,都单独使用一把钥匙。


或许你马上就感觉这不太可能,因为要发那么多信息,还要单独约定每条信息的钥匙,这不又变得繁琐的过程了吗?传递钥匙的过程又是怎么实现呢?


德国人当时是这样做的:




这个机器每天的初始状态里,需要设置的3个部分中,有两个全天都是不变的。唯独一个变的,就是这三个齿轮每个齿轮的第一个字母是什么。


假设那本密码簿里,当天对应的3个字母是QCW,这并不是说今天所有消息都用它当钥匙,实际上当天每条消息都有一把小钥匙,QCW只是用来给当天无数把小钥匙加密的总钥匙。


4


具体的技术细节,下面我详细说说:


发信息前,先把齿轮的初始状态设为QCW,然后脑子里随意想3个字母,比如说ABC,用设置成QCW状态的机器给ABC加密,比如说加密后ABC变成了BMW。但一次还不够,还要再加密一次,比如第二次ABC又变成了NBA。然后把两次加密的结果并列写一起,形成BMWNBA。


这六个字母形成之后,这段信息真正的消息主体是从第七个字母才开始的。


那你可能要问,干嘛要加密两次呢?有两个功能。


1. 让对方知道对应当前这条信息的小钥匙到底是什么。


收信方如果收到了以BMWNBA六个字母开头的密文后,他怎么做呢?他也要查一下当天的密码簿,一看当天要设置成QCW,那他就也这样设置。用QCW去解码刚才这六个字母,就会发现是ABCABC。


他就会知道,对应这条消息的后面内容主体的小钥匙是用ABC解密,然后再把ABC当做齿轮的初始值,去解码后面消息的主体,就知道说的是什么了。


2. 确认信号在传输中没有被干扰,或者对方操作没有失误。


因为任何失误和干扰都会导致解码后,信息的前六位不是两次重复的样子。所以只要收信方发现不是两次重复的格式,就会丢弃掉这段,让对方重新发。




所以,密码簿里写的当日钥匙QCW,其实只是给当天成千上万条小钥匙加密的总钥匙,是钥匙的钥匙。


这样一来,就安全多了。


5


面对复杂的恩尼格玛机,单纯依靠语言专家不行了,波兰找来了20位数学家。这是密码学有史以来,第一次把数学提到这么重要的位置。在短期高强度培训后,又从中选出3位在破解上能力最强的。


就是他们,找到了第一代恩尼格玛机的破解方法。


具体的破解过程,大概是这样:


因为之前间谍透露的消息,数学家们知道每条消息的头部都是6个字母。它的样式是什么呢?就是ABCXYZ的样式。这些,就是破解的关键。


所以说,数学家们面临的难题就是:


有一堆6个6个的字段,比如说ABCXYZ,现在我们知道,A和X对应同一个原文,B和Y对应同一个原文,C和Z对应同一个原文,而ABC和XYZ又是由同一个钥匙加密而来的。

现在的问题是,求这个钥匙是什么?


数学家的方法很复杂,我们省略不讲,直接给你说结果——把当天截获的信息中,所有可以对应的字母都找出来。


比如在ABCXYZ中,A和X是对应的,但是又在某些六位中,X还能跟F对应;可是在其它的对应中,又能找到F又对应回A。你看,从A出发,又绕回了A,正好凑成一个环。

那我们数一下,形成这个环涉及了3个字母——AXF。所以在这个环上,连接数就是3。

而且A可不止有这一种方式可以绕回A,当天那么多条消息中,A还有其他方式也能绕回A,但可能需要的连接数比较多。


没关系,把它们都总结出来。


这样,数学家就总结出钥匙字段中第1个字母有几种可能能形成环,每个环上又涉及到几个连接数。同样的,第2个字母也能找出有多少条环,也能找出有多少个连接数……


每个字母分别会出现几条环,每个环上有几个连接数。直到把所有的规律和对应的初始值做成一本大字典,这个工作才算结束。


这个收集整理工作一共进行了一年多的时间,然后就发现:


环的数量、连接数的数量,是由恩尼格玛机初始设定决定的。


最后的破解任务就是查表——先截获当天的密文,统计这6个字母一共形成了几种环,每种环里又有多少个连接数。这些特征掌握之后,再去查查字典里满足这些环和连接数的条件的初始值对应的是哪个,就能知道敌人当天的初始值是怎么设定的了。




所以第一代的恩尼格玛机,就这样被破解了。


6


最后,我们再从数学的角度,看看恩尼格玛机的破解。


这个破解方法是到现在为止,让人听了最费解的。这不只是因为破解的细节比较多,还是因为我们使用了数学工具。


你可能会说,破解第二代的移位法和替代法,不也用了数学的频率分析吗?


没错。虽然频率分析法也是数学工具,但频率分析中字母出现的概率有特定值这种想法,依然有着浓重的猜字谜的成分。这就意味着,数学参与的计算过程和破解原理之间的对应关系非常浅显。


但到了恩尼格玛机,这种浅显的对应关系就不再有了。


我们可以想想,破解恩尼格玛机时我们在做的运算动作是什么?


对,就是去数截获的信息里字母环的数量和每个环上的连接数量。这个计算过程非常简单,就是数一数嘛。但环的数量和连接数,与恩尼格玛机的内部结构是怎么对应的呢?就不容易想了。


但经过详细统计后,机械电子结构和背后的数学描述却精确的吻合,每个齿轮的动作都和环与连接数,有逻辑关系。这就是数学方法,超越头脑风暴式猜字谜的最好例证。


虽然我之前说过,恩尼格玛机彻底破解有很多因素,还包含了不少间谍伎俩,但起最重要作用的,就是数学。


在解密中,数学所占的成分会越来越重。这一点我们接下来的课里还会讲到。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:47:26
2445
12
来自:保密
注册:2001-06-03
发帖:179+4270
人性弱点:图灵破解恩尼格玛机的关键




1


恩尼格玛机的破译一共有两次:第一次是我们上节课讲的波兰数学家做出来的,第二次是图灵做出来的,这也是我们这节课的重点。


为什么要破解两次呢?因为这两次使用的恩尼格玛机,结构上不一样。


如果第一次破解难度是65的话,第二次破解难度就要到95了。这还只是难度对比,如果从必要性上对比,第一次破解甚至都是不必要的。


因为波兰情报局在那7年时间里,一直能通过德国间谍搞到每天的钥匙。


情报局只是担心万一今后恩尼格玛机改版,自己没有B方案,所以希望密码学家提前动手。那几年,当那帮密码学家每天埋头破解的时候,情报局高层其实早就提前知道每天的结果了。


可就在二战开打前一年,两个破解渠道一起断掉了:


首先,德国把恩尼格玛机的编码器齿轮增加到了5个,接线板的数量同时也增加了;




其次,那个长期提供当日钥匙的间谍,也突然消失了。





2


1939年4月,德国撕毁和波兰的互不侵犯条约。所有人都能预见到,德军马上要打来了。波兰坐不住了,赶紧把至今为止其他国家都还不清楚的第一版军用恩尼格玛机的结构、破解方法,公布给了盟友。


英国对波兰提供的方案很重视,甚至为了信息安全扩充了密码队伍。


从从前的密码局40号房换到了布莱切利园(Bletchley Park),面积扩大了几十倍;工作人员从最初的20多人,扩增到五年后的9000多人。


与此同时,员工的结构也有变化。从前主要是语言学家,现在的主力是数学家。大量招募数学家,这是波兰人特地嘱咐英国人的。




英国的资源比波兰丰富得多,所以虽然恩尼格玛机升级过,但靠着堆人力、堆机器的方法,在战争初期,英国竟然可以勉强应付新版恩尼格玛机。


但这时候的破解,可以说是在摸透了人性规律的情况下做出来的,比如:


设定那3个初始值时,按操作规范应该是随机设置,但实际上德军操作员根本做不到这一点。类似QWE、ADS、JKL这样键盘上3个相邻字母的情况,经常出现。操作员就是懒,随手摁出来。 就算3个字母不连着,但手指的活动总是有规律的。3个字母在键盘上的位置总会趋向于集中,所以这些组合总是解码者优先尝试的。 甚至还有用女朋友名字的前三个字母的,以至于后来英国的密码专家每次都先试女人名字。

除此之外,德军的恩尼格玛机操作指南也有漏洞。


比如,5组齿轮中选3组作为当天的编码器,但却有一个规定——不能让同一个齿轮在同一位置连续出现2次。听上去好像是避免了重复,但其实减少了齿轮组合一半的可能性。


还有,接线板对调字母时不能对调相邻的两个字母,比如B不能和A对调,也不能和C对调,理由是这样对调太容易被识别出来。结果这样一规定,可能性的总数又锐减。


所以,英国最初就是利用一切可利用的人性的漏洞、规则的漏洞,外加灵活运用波兰的老方法,勉强支撑着对恩尼格玛机的破译工作。


3


但这种水平的破译,是远远不够的。一旦德国发现,每条信息的前6位是破译者可以抓住的漏洞的话,就会改变钥匙的传递方式。那样的话英国就没办法了。


所以,图灵的任务就是找到一种全新的破解法,完完全全的猜透恩尼格玛机。


图灵是怎么做的呢?简单说,他也是从一些军事规律导致的漏洞入手的。


比如,德军消息里类似——


无特殊情况(Keine besonderen Ereignisse)


希特勒万岁(Heil Hitler)……


这样的词语,会经常出现。


图灵还分析出了一个更好用的词——“天气”(wetter)。这个词每天早上6点到6:05必然出现,而且大都出现在信息的开头,此外这个词里出现了两个t挨着的情况。


根据我们之前讲过的:


恩尼格玛机对同一个字母连续加密的话,是不会加密成相同字母的,而且这个字母也不会被加密成它本身。


根据这两个规则,图灵就可以拿着wetter这个字段当作原文,对照着密文一位一位的挪动,排除掉那些不符合刚刚两个规律的方案。




又因为wetter很高概率出现在信息最开头,所以只要试几次,就能发现wetter对应的密文到底是哪几个字母。


4


到了这儿,只是成功的第一步。


因为现在图灵得到的题目就相当于说:已经知道了6个原文和它对应的6个密文,让你求出恩尼格玛机的初始设定。


你说这个问题怎么解决呢?


最直接的方法,就是用恩尼格玛机所有的初始设定,一个一个去试。把原文wetter输入,看看密文和我们截获的一样不一样。如果一样,那就说明初始值找对了。


但是,军用版恩尼格玛机的初始值有1.6×10^20那么多种,是不可能用暴力去试的。

所以,可用的方法只有一个——


在手头已有的少量原文和密文之间,想办法建立它们对应的数学关系,来反映出恩尼格玛机的内部结构。


其实这个想法,和波兰破解第一版军用恩尼格玛机有点像。


图灵把原文写一行,密文写在下一行,排成两排,他管这个叫“对照文”(Crib)。然后也建立了环,环上也有连接数的概念。具体细节在这里没法说了,因为非常繁琐,而且和密码学知识的逻辑没太大关系。


我们知道结果就行——图灵通过数学过程的转换,军用版恩尼格玛机1.6×10^20这么多可能性,一下被缩减到了105万种。


可能有人说“这也不少啊”,但这已经是所有可能性的一百万亿分之一了。


这个105万的计算过程,肯定也不能由人来做了,而是用一种机器来破解。这个破解机,就被起名叫“****”。****体积挺大,有2米见方,****机越多破解就越快。






1940年5月10日,德军也不知是察觉到了什么,突然改变了交换钥匙的方式。每条信息开头的6位,不再是从前的格式了。英国情报部门从此,完全失去了破解德军恩尼格玛机的能力。


好在这个空窗期并不久,3个月后,依照图灵方法制造的第一台****机投入使用。在之后2年里,有50台****机投入使用,英国又能破解德军的密码了。




到1942年的时候,破解德国陆军恩尼格玛机当天的钥匙,大约只需要1小时的时间。


5


即便有了****机,破译也不轻松。德国加密水平最高的是海军,他们甚至在通讯中都不使用格式化的语言,所以就没有固定的原文可以参考。


但英军也有办法,就是在特定地点布****,这些****其实是信息诱饵。德军发现****后,肯定会发这样的电报:在东经xxx,北纬xxxx水域,发现大量****。这样一来,原文中很多的词就可以确定了。


不过为了防止德军起疑,这招不能用得太频繁。


英国很重视来之不易的破解,所以尽量装成什么都不知道。比如说已经知道德国军舰的位置,准备去偷袭,却要先派出侦察机像模像样的巡航一番。好像德军舰艇的位置是通过侦察机捕捉到的,而不是破解密码得到的。


图灵破解海军版恩尼格玛机的实际效果怎样呢?我给你两组数据你就知道了:


1. 破解之后,盟军全年被击沉船只的吨位下降了60%。


2. 德军潜艇的损失率,从破译前的不到7%,猛增到50%。




利用这套破解装置,也成功搞定了日本和意大利的密码系统。


虽然有些人评论得比较夸张,说“破译了恩尼格玛机,盟军才最终胜利”。但公平的说,如果恩尼格玛机没被破解,二战至少要延续到1948年以后。所以你看,全世界至少有上千万的家庭受惠于密码学家。


6


可密码学家大都没有受到什么嘉奖,因为保密法涉及国家安全。


二战结束后,布莱切利园就彻底解散,****机也拆解了。少部分密码学家进入改制后的政府通讯总部做公务员,大部分人又回到了从前的皇冠娱乐网中。而且他们必须严守秘密,否则就会被判刑坐牢。


其他军人都能谈论自己的英雄事迹,而密码学家只能默不作声。


根据《保密法》的限制,二战中的密码学资料在1970年才公布,第一本专门写布莱切利园的书在1974年才出版。而这时,很多当年参战的密码学家已经去世了。




图灵就是这样,他一辈子也不知道自己的破解对战争具体产生了什么效果,战后继续从事数学研究。


1952年时,因为被发现有同性恋行为,被强迫执行了化学阉割。后来在雌激素的作用下,身材发胖,胸部变大,精神更是遭到折磨。最终在1954年的夏天,吃下****浸泡过的苹果自杀了。


图灵在破解恩尼格玛机上所有的成就,都是在他去世以后20年才为人所知的。


7


回头看密码学的发展,你会发现有一个东西的神秘感在逐渐褪去,那就是关于“如何加密”的操作过程。


在隐藏法的年代,如何加密的细节绝对属于核心机密;


而在替代法和移位法中,大部分操作原理人们都知道,只是不知道具体移动了几位;


但到了机械电子加密的时代,加密设备的工作原理,不论是理论还是技术细节,敌我双方都了如指掌,密码的安全性全部落在钥匙上,而不再依赖于加密的操作细节。


这个趋势在之后还会更明显,我在后面的课里还会讲到。


图灵破解了恩尼格玛机后,在加密解密的对抗中,解密一方又暂时占据了上风。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:53:14
2445
12
来自:保密
注册:2001-06-03
发帖:179+4271
二进制:让字母参与运算是现代密码的标志




1


如果说咱们前面讲的密码学,都停留在古典密码时代;从这节课开始,密码学就要进入计算机时代了。


从计算机时代开始,字母作为操作的最小单位的概念就消失了。


我举个例子你就明白了:


二进制咱们都知道,在计算机里,所有的数据都被表示成0和1的数字组合,字母也不例外。把字母数字化得有个标准,现在这个标准就叫做ASCII。


早期,每个字母和符号都对应一个7位的二进制数字,比如说,a=1100001,!=0100001。字母一旦变成数字,在计算机中字母的符号属性、发音属性等就完全消失了。


它只是一个二进制数字,我们可以随意对它做改变。比如AB=1000001 1000010,我们可以把其中的奇数位、偶数位分别挑出来,然后再首尾相接就变成另外一个数字了

(1001001 0001000),这个数字实际对应的符号就是“H+退格符号”。


我们也可以做其他指定,比如奇偶互换形成一段新的字符……


虽然最终输出的仍是两个有意义的字符,但它和以往加密法的最大区别在于:


以往的加密,都是对单个字母进行操作;但数字化后的加密,打乱的是语言规律的底层结构,改变发生在字母内部。所以说,数字化使加密法步入一个新的世代。


我刚刚举的例子很简单,其实在计算机出现后不久,就出现了操作步骤很复杂的加密方法。这些方法是怎么计算的呢?


过程不但不保密,而且每个人都可以查到技术细节。


从前恩尼格码机的时代,德军还会想方设法保密军用版机器的内部结构和使用说明书。但到了计算机时代,所谓内部结构和操作说明根本不用保密,完全公开。




到底有多公开呢?


从1976年11月起,有一套规范就成了美国国家标准局的加密系统官方标准,简称DES。任何人只要想了解,都可以得到这份规范。


这个规范还有一个外号——“魔王”(Lucifer),这是最典型的诞生在计算机时代的第五代密码法。


2


据说,当初设计者一直把这套算法叫做“示范算法”(Demonstration),但70年代的操作系统对文件名长度有限制,于是只能截取前几位字母Demon,而Demon又是“恶魔”的意思,后来大家就用另一个恶魔的名字——路西法(Lucifer),也就是“魔王”来称呼这个算法了。


计算机科学中经常会出现一些新词怪词,比如黑客(hacker)、程序错误(bug)、垃圾邮件(spam)、博客(blog),包括魔王这个名字在内,它们背后都有故事。


这些故事综合在一起,在70年代后形成了一种全新的主流文化——IT文化。




而在接下来的密码学进展中,还会出现3个著名的IT虚拟人物。如今就算在正式的学术讨论中,这3个人名也都是标准用语。它们是爱丽丝(Alice)、鲍勃(Bob)和伊芙(Eve)。

记住这三个名字,咱们后面的课还会反复用到。


3


现在,咱们就用这3位来举例。假如爱丽丝和鲍勃通信,但伊芙想偷听,怎么解决呢?

有人说,就使用刚才说的魔王系统加密嘛。但是信息加密后,钥匙的安全怎么保障呢?

爱丽丝得想法把每条消息对应的钥匙给到鲍勃才行,最稳妥的方法是爱丽丝直接和鲍勃见面,告诉他钥匙内容。


你说不用见面,双方约定一下,比如说用《独立宣言》的字母顺序当钥匙,就可以省去见面了。但这消息一旦走漏给伊芙,此后两人的通信就没法保密了。


所以用魔王系统加密能保证信息主体的安全,但双方还是要交换钥匙,而钥匙的安全是没法保证的。这就是魔王系统最大的漏洞。


对双方约定钥匙内容这件事来说:


钥匙越没规律,密码越保险,但也就越需要双方见面沟通;钥匙越有规律,密码越不安全,但却省去了见面沟通的成本。




没办法,在新方法出现前,像有些一个月才需要沟通一次,却又对保密等级要求极为严格的场合,真的会采用见面的方式交换钥匙。


70年代的大银行就专门有个职位,那人每天提着保险箱,飞到世界各地给客户送钥匙。


4


现在问题来了:如果是既对安全性要求特别高,又需要频繁沟通呢?怎么办?


那就需要等到新一代密码系统诞生,才能解决。这套系统解决了一个问题,就是在传输加密内容时不必单独传递钥匙了,这就把魔王加密系统的漏洞给补上了。


这是在密码学发展了2000多年后才有人想到的。


有人说:怎么会这么复杂?我马上就能想出一套不需要交换钥匙的方案出来。比如:


爱丽丝把机密放在盒子中,上一把锁,盒子寄给鲍勃; 鲍勃收到盒子后,因为没有爱丽丝的钥匙,所以打不开,但鲍勃又给盒子加了把锁,寄回爱丽丝。这会儿盒子上就有两把锁了。 爱丽丝收到挂了两把锁的盒子后,用自己的钥匙打开其中那把自己的锁,然后再把只有一把锁的盒子寄给鲍勃; 鲍勃收到盒子后,上面只有一把自己的锁了,他又有自己的钥匙,所以就可以打开看到里面的机密文件。

整个过程中双方就没交换过钥匙。听上去是不是很完美?但是实际上却行不通。


原因就是,把加密比喻成上锁是行不通的。


因为在加密中,当一套字符先使用A加密一次,又使用B加密一次,我们就必须先用B解密,再用A解密,也就是后加密的先解。如果这个顺序颠倒了,解出来就是乱码。可是开锁上锁,一般不用讲顺序。



这个例子也提醒我们:


比喻虽然对难的知识是一种辅助,但比喻法不能代替数学的理解。


5


那能用什么来解决这个问题呢?还是数学。


具体来说,就是用一种不可逆的函数。密码学中为了简单,把它叫作“单向函数”。其实严格的说,单向函数存在与否的数学证明,到现在还没有做出来。但我们不纠结,就叫它单向函数。


函数指的是某种固定操作,比如×2,就是一种函数操作。我们大多数情况接触到的函数,都是可逆的。如果把3进行了×2的操作,可以得到6;那么也可以可逆的,从6÷2得到3。


那不可逆的操作是什么呢?


数学上还真的有一类特殊的运算,它有时候就是不可逆操作,这种操作叫作“模运算”(modular arithmetic)。


模运算很像我们看手表的思路。比如晚上22点再过3小时是几点呢?结果不是25点,而是1点,所以钟表就是一个模等于24的体系。我们可以任意规定模的大小,比如在模是7的体系里,2+3=5 (mod7),2+6=1 (mod7)。


乘法也一样可以用模运算,比如在模为13的体系中,11×9等于多少呢?加入不考虑模,我们知道结果等于99。可是在模等于13的表盘里没有99,所以数字的增加只能等同于不断的转圈,99相当于转了7圈后又走了8格。所以在模13的体系中,11×9=8 (mod13)。




模运算怎么就是单向函数了呢?


我们可以看看刚才的例子:11×9=8 (mod13) 这个算式,从左往右推可以推出来,而且结果是唯一的。但是从右往左呢,就相当于问你“在模等于13的体系中,什么数×9以后余数为8”。这个问题能不能逆运算呢?答案是不能。


当然,不一定模运算就一定没有乘法逆。当模比较小的时候,可以逆运算的数字比较多;但是当模大到一定程度时,就完全没有逆运算了。这是由数学决定的。


6


明白了模运算,我们就能知道它是怎么用来传递钥匙的了。过程是这样,比如说:


1. 爱丽丝和鲍勃两个人都约定使用7^X这种函数,只不过是在模等于11的情况下运行的。


2. 爱丽丝随便想出一个数A,比如说是3,鲍勃也随便想出一个数B,比如说是6;


3. 他们两个人分别把自己想出来的这个数,带入刚刚那个函数计算一下。比如爱丽丝算完等于α,鲍勃算完等于β;


4. 两人把计算结果告诉对方,直接打电话也行,写信也行,反正是不怕被伊芙偷听的。原因我们刚刚说过:因为伊芙偷听到的只不过是模运算的结果,而这个结果是不可逆的,所以就算伊芙知道结果,也没法倒推出之前的值;




5. 等爱丽丝和鲍勃都得到对方的结果之后,爱丽丝再做一次计算题,她做的是β^A(mod11),鲍勃也算一次,他的题目是α^B(mod11)。


当然,你不用管为什么非得是β^A 、α^B,这个是数学运算保证的,这样算是一定正确的。


这两个人算完后,奇怪的事就会出现——他们将得到完全一样的结果,这个结果就是9。他们得到的结果相同,那么这个结果就可以当作他们的钥匙。


整个过程没人传递过钥匙,但双方都拿到了同样的钥匙。对窃听者伊芙来说,她偷听到的只是模运算的结果。因为这种运算没有逆运算,所以伊芙偷听了也白听。


你可能很困惑,最后两人计算的结果为什么恰恰都等于9?


这就是整个过程的精髓所在。不过这可不是巧合,而是阳升(Sun)的高级工程师迪菲(Whitfield Diffie)和斯坦福大学电子系教授黑尔曼(Martin Hellman),两个人花了两年多的时间才找出的这种函数。也因此,这套方法被称为“迪菲-黑尔曼钥匙交换方案”


具体的证明过程非常复杂,我们不需要了解。我们只要知道经过这样的运算,双方都会得到相同的结果就可以了。


2000年来,密码学一直信奉用户必须特地为交换钥匙而额外碰面;


1976年之后,这个信条就完全破灭了。


总结一下这节课的内容,进入计算机时代,加密法出现了几个重大进展:


1. 加密对象从字母变成了数字;


2. 加密的具体操作步骤不再需要保密,甚至可以写成规范公布给所有人看;


3. 不可逆函数,让人们不需要专门的交换钥匙了。


这几个进展,全都是由数学推动的。事实上,不只是密码学,每个科学分支最重要的理论突破背后,都有数学的巨大贡献。




那这种加密法能不能实用呢?如果说不实用,又要如何改进呢?



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:57:22
2445
12
来自:保密
注册:2001-06-03
发帖:179+4272
RSA加密:公开的钥匙反而更安全



上节课我们已经知道,通过模运算这种不可逆的数学工具,密码学已经发展到不需要单独发送钥匙了。


这个突破很大,但它实用吗?答案是不行。


因为这套方案有个前提——需要双方一直同时在线,通信才能启动。而现实中,像我们用微信、发短信、发邮件,一般都不用对方立刻回复。这个应用场景的问题不解决,这套方法就没法商用。


最终实现这个功能的,是第六代密码法——RSA加密法




这门课到现在,我们讲了很多加密方法,如今大多数都不再使用了。而RSA加密法,仍是目前使用最广泛的方法。像我们的手机支付加密、网银加密,都会用到它。


关乎钱包和信息安全,你一定得认真听。


1


RSA这3个字母,分别代表的是它的3位创立者——Ron Rivest、Adi Shamir、Leonard Adleman。


下面我们用打比方的方式,来说说具体的加密过程:


爱丽丝有很多把锁,每把锁都有两把不同的钥匙,一把专门用来上锁而不能开锁,另一把专门用来开锁而不能上锁。


2. 爱丽丝把那把用来上锁的钥匙,尽量多的赠送给每个可能和她通信的人。这些人拿到钥匙后,就可以把要跟爱丽丝说的话写下来,再用爱丽丝给的钥匙把锁锁上,然后寄给爱丽丝。


3. 爱丽丝拿到锁好的盒子后,用另外一把只有她才有的专用钥匙打开盒子,就可以看到信里的内容了。




这个过程的关键点就是,对同一把锁来说,上锁和开锁用的是两把不同的钥匙,而之前我们说的所有加密法都是使用相同钥匙的。


所以之前的都叫“对称钥匙”,而RSA因为使用了不同的钥匙,所以叫“非对称钥匙”,或者“非对称加密”。


2


刚刚我们用一个非常简单的比喻,把非对称加密过程形容了一下。但还是那句话,比喻是不能代替理解的,实际的思考逻辑是这样的:


爱丽丝要设计出一把公开钥匙,之所以公开,是为了让每个人都能复制这把钥匙,用来给自己发信息加密用。但这把钥匙,又一定不能解开加密过的信息。


所以这一步,需要一种不可逆的函数运算,只能加密不能解密,这个就可以用我们上节课说的模运算来实现。


爱丽丝本人还得有一把私人钥匙,它是不公开的。而这把钥匙,可以解开用她的公开钥匙加密过的信息。


具体的细节比较难懂,需要公式的辅助,我来说说关键步骤:


爱丽丝展示出来的公开钥匙,是通过两个比较大的素数p和q相乘得到的一个更大的数N得到的。p和q具体是多少,爱丽丝只要自己知道就行,千万不要告诉别人。而乘积N是公开的,谁都可以知道。


凡是要给爱丽丝发消息的人,都需要用N来加密。加密的过程依然用的是模运算,而且模就是N。整个数学过程会保证这个模运算不可逆,所以伊芙就算知道N也没用。


那爱丽丝是怎么解密的呢?她解密时就不需要N了,而是要用到p和q的具体值,而这两个值别人都不知道,只有爱丽丝自己知道。具体来说,爱丽丝私下做的另外一个模运算中的模,不是刚才我们说的N,而是另外一个值(p-1)×(q-1)。你看,在这个公式中就必须要知道p和q到底是多少才行。


至于为什么一定要是(p-1)×(q-1),你不用纠结,数学原理保证这样操作能算出一把新钥匙,这把新的钥匙就是爱丽丝自己的私钥。用这把私钥,一定可以解出原文。


你说,这样做就能保证安全吗?伊芙已经知道了一个大数N,她难道不能利用精巧的算法,找出N到底是由哪两个大的质数相乘得到的吗?


不能的,这种不能是由数学保证的。N越大,找到p和q两个因数的时间就增加得越夸张。现在银行使用的RSA加密,都要求N是一个超过300位的大数。想分解这样一个数,大约需要把全球计算机的算力集中起来算上几亿年才行。




有人可能会问,为什么非要用两个大的质数相乘呢?用两个巨大的合数相乘得到N,想把这个N的因数找齐,不是也要很久吗?没错,是要很久。但这样做的话,最后算出的私钥也没法解出原文了。所以,找两个质数相乘,也是由数学决定的。


3


1978年2月,顶级期刊《ACM通信》刊登了一篇文章,叫《一种实现数字签名和公钥密码系统的方法》(A Method of Obtaining Digital Signatures and Public-Key Cryptosystems),作者就是姓名以RSA这三个字母开头的密码学家。


文章的第三页就出现了这么一句:“我们假设一个场景,爱丽丝和鲍勃是公钥密码系统中的两个用户。”这篇文章此后所有的技术细节,爱丽丝和鲍勃就成了主角。这是密码学史上,爱丽丝和鲍勃的首次出现。




这种论文风格很另类,看上去好像在讲故事。那为什么是爱丽丝和鲍勃,而不是汤姆和杰瑞呢?


只要参考之前的通信类论文你就会发现,以往用来指代发送方和接收方的,一直都是A和B,而且由A发出的内容大都是α,由B发出的内容大都是β。


可能这三位密码学家不想太枯燥,就把名字以A开头的Alice当做A,把名字以B开头的Bob当做B,于是爱丽丝和鲍勃就这样尽人皆知了。


4


现在我们再来回头看,密码学发展的过程中,公开透明的部分越来越多。


到了第六代的RSA加密法,不但加密的操作公开了,连部分钥匙都公开了。而且公钥不是情不得已才公开的,而是越公开益处越大,因为这样才能有更多的人给你发加密消息。到了现在,唯一不能公开的就只有私钥。


可能听到这里,你会感觉RSA加密法使用的数学工具很陌生。没错,这个方法用到了两大数学领域的知识——质数方面的应用和数论有关,单向函数的应用和群论有关。


这个算法背后的数学证明,一般在计算机系《算法导论》有详细论述。如果想深入了解,你可以参考这类教科书。




数学有很多分支,现在大多已经成为工程应用的理论基础了。不过它们化身为应用的范围有宽有窄,比如群论的应用就广阔很多,而数论部分就狭窄很多,目前只有密码学在应用。


5


1979年,RSA注册了专利后,还成就了很多信息安全公司。但如果就这样介绍完RSA加密法是如何创生的,那真的有人要受委屈了。


因为同样的加密法,其实早在4年就已经有人完整的做出来了。那他们为什么没有成为这种非对称钥匙系统的专利发明人呢?


道理还是我之前说的,密码学领域注定会有很多受屈者。


最早发明这种方法的,并不是RSA这三个人,而是詹姆斯·艾利斯(James Ellis)、克里佛·考克斯(Clifford Cocks)和马尔科姆·威廉森(Malcolm Williamson),我们简称他们三人为JCM。


他们都是英国政府通讯总部的员工。不知道你是不是还记得图灵破解恩尼格玛机时,那个庞大的情报部门布莱切利园。当时9000名员工,战后绝大部分都回到了原来的皇冠娱乐网中,只有少数转去英国通讯总部做了公务员,这3位密码学家就是这样留任的。


他们之后的研究也全都带有军方项目的性质,所以是国家机密。别看1975年他们就做出了整套非对称钥匙加密系统,但直到24年后的1997年,人们才知道这件事。这时不要说和RSA争夺专利发明权了,连RSA的专利甚至都要过期了。


其实在1975年,JCM刚刚做出全套算法的时候,他们曾经向国家通讯总部提出过注册专利的要求,但总部没有批。


几年后他们听说RSA三个人注册了专利后,特别失落,因为他们才是最早的发明人,专利应该属于他们。但因为军方的限制,他们只好保持沉默。


到了80年代,随着计算机性能持续提升,RSA实用性越来越高,连当年拒绝JCM申请专利的通讯总部的长官,都开始后悔了。


而且这种遗憾,随着时间推移还在持续增加。2006年,RSA数据安全公司被EMC公司花2.1亿美元收购。又过了10年,EMC公司又被戴尔公司收购,成为戴尔技术品牌的一员。




1997年,英国公布JCM三人成果不久之后,他们举行了一次公开演讲。


演讲结束后,JCM里的威廉森接受采访,被问到错失专利的感受时,他说“没办法,人生就是这样”。另一个人考克斯的反应要更淡定一些,他说“我要是想得到公开的赞扬,就不会来做当前这份工作了”,他指的就是在英国通讯总部的工作。


而第三个人,也是最早参与研发的詹姆斯·艾利斯,在演讲前一个月刚刚过世,享年73岁。


6

讲到现在,密码学近代史上,已经有3个重要人物没有在他们有生之年获得应有的嘉奖了。


第一个,是首位破解了维吉尼亚加密法的查尔斯·巴贝奇;


第二个,是破解了恩尼格玛密码机的图灵;


第三个,就是首次提出非对称钥匙加密系统的JCM三人小组。




他们都是因为军方需要保密,而不得不做出牺牲。可从事密码学研究的人,有相当高的比例就是为政府情报部门工作的。这个属性就决定了,他们很容易受到历史不公正的评价。而对我们这些看客来说,关于密码学的突破,我们能了解到的,只是各国情报部门允许我们了解到的部分。


这是密码学这个学科分支,独有的文化特征。




这节课我讲了RSA加密法的加密原理,知道了这种“非对称加密”的高明之处。



------------------------------------------------------------------------------------------- PcHome日月潭资深会员 ☆☆☆RYT---㊣上情☆
2019-01-19 23:59:19
4659
40
来自:皇冠现金
注册:2003-03-10
发帖:1101+18491

mark


------------------------------------------------------------------------------------------- 这个家伙很懒,什么也没留下......
2019-01-19 23:59:50
x
引用20楼@ 特雷西00 发表的:

首先,请你以一种,团成一个团的姿势,然后,慢慢地比较圆润的方式,离开这座让你讨厌的城市,或者讨厌的人的周围首先,请你以一种,团成一个团的姿势,然后,慢慢地比较圆润的方式,离开这座让你讨厌的城市,或者讨厌的人的周围

回复主题 返回kds皇冠娱乐网
主题: 密码学的故事
热门文章排行
  1. 本周
  2. 本月
热门产品排行
  1. 本周
  2. 本月
房车头条
  • 扫描关注官方微信
  • 扫描下载客户端

短信

x
收信人:
内容:
插入:  发送 
  • 默认

帖子奖分

奖分者: ( )

得分者:

奖励分值:您今日还有 3 点分值可以奖励 [ 20 点奖分可自动换取 1 点PP]

看不清楚吗?点击更换一张

请输入4位有相同表情的数字

验证码:看不清楚吗?点击更换一张

奖分理由:

删除

        

                            

        当事人要求删除

                    

          

理由:

扣除hp值:

皇冠娱乐网警务室

用户反馈

        

内容:

已报名参加的人员: