Posts By Philip Ye

雅思备考两个月首战 7.0

好吧,我承认有点标题党了。我考的是 G 类雅思,按照惯例,先报分数,第一场在深圳考的:

第二场在悉尼:

11 月 30 号才决定要考,目标是均分 6.5,无单项分要求。当天晚上报了 1 月 20 号的深圳场,前后不到两个月时间。在准备了半个月之后,担心自己考不过,同时结合原定去澳洲过春节的计划,又报了 2 月 10 号的悉尼场。因为 2 月 9 号才能到悉尼,同时 G 类考试可选择的场次不多,所以特地选了非 IDP 考场,可以在笔试当天下午考口语。

从成绩单来看,除了 G 类阅读较简单而分数较高外,其它几个单项分数都不高,能够首战就刚好踩线上 7 也完全得益于阅读。简单总结下各个单项我是如何备考以及两场考试的经历吧。

听力

刚报名就立马在淘宝买了剑桥真题 4~12。从剑 11 才开始区分 A 类和 G 类,我买的是 A 类套装,因为价格更低,还附赠一本阅读词汇手册。做了剑 4 的两套听力之后,发现大部分段落都能听懂大概意思,但填单词时总是出错,尤其是单复数弄错。之后在同一家店买了王陆的《雅思王听力真题语料库》,第 3/4/5/11 单元按顺序只刷了一遍,正确率基本上不到 70%,但对于听力初期的备考确实有点帮助,对考点词汇都有大致印象,听到了也能比较快速地定位并正确拼写。

由于担心听力真题做完了就没真题可练习了,所以一直在控制着进度不要太快。结果在第一场考试之前,只做完了剑 4~剑 6 以及挑着做了剑 8 和剑 12 的第一套听力,分数一直在 5.5 和 6.5 之间徘徊,所以一直很担心。第一场考试的前一晚实在太紧张了,每两个小时就醒过来一次,考试当天整个人都是懵的,做听力时完全没进入状态就结束了,结果只考了 6.5 分。

在备考第二场时,开始按计划有规律地把剩下的听力题刷完,直到出发飞澳洲的前一晚,才最终把所有听力做完。各种题型中,填空题稍好,配对题和多选题是我的弱项。从刷题的分数来看,但凡选择题比例高的真题,分数都比较低,但至少慢慢有点感觉,分数也稳步地提高了。可第二场考试的听力偏偏遇上了两个配对题和一个地图题,最终还是只有 6.5 分,真是失败。

阅读

刚开始备考时,做了几套剑 4 的 A 类阅读,在一小时之内根本做不完三篇 40 道题,即使做完了也只能拿 6 分,非常气馁。直到做了一套 G 类阅读,轻松拿到 7.5 之后,总算找回点自信。此前给自己定的目标是 7.5/7.5/6/6,此后随即调整目标为 7/8/6/6,同时在备考的时间分配上也减少了阅读的部分。

和听力一样,在第一场考试之前,只做了剑 4~剑 6 以及挑着做了剑 8 和剑 12 的第一套,同样也是在飞澳洲之前刷完了剩下的所有阅读。各种不同的题型中,填空题基本是 100% 的正确率,错误主要出现在判断题。总结错题后发现,判断题不能做推论或推理,必须完全以原文给出的信息为准,题目与原文信息完全相同的为 TRUE,与原文信息有任何不符的为 FALSE,原文中没有给出的为 NOT GIVEN。很幸运地,在第一场考试的阅读中拿了满分,然而此后再也达不到满分的高度,第二场阅读 8 分,也就是错了两题。

顺便贴一下听力和阅读是如何算分的。下图第一二列是听力中正确的题数和对应的分数,第三四列是 A 类阅读,第五六列是 G 类阅读。听力和阅读都是一共 40 道题,每道题一分,各个 Section 没有权重的不同。G 类阅读想要拿同样的分数需要有更高的正确率。比如说,A 类阅读要拿 8 分,40 道题只要做对 35 道即可,而 G 类阅读需要做对 38 道。

写作

写作备考我用的之前 Linda 考雅思时买的《十天突破雅思写作》,没有额外买书。这本书对我最大的帮助是让我快速地了解雅思的作文应该写成什么样,通读全书后对雅思作文的框架了然于心,再熟读背诵高分短语并多加练习是我预定的策略。然后在淘宝买了作文批改,一共买了 32 篇。

可是直到两场考试结束后,我一共就只写了 3 篇小作文和 3 篇大作文(累计批改了 6 篇)。第一篇大作文写得异常艰难,断断续续两天才写完,完全找不到感觉;第二第三篇大小作文都是在模拟真实考试的一小时内完成的,完全是在硬着头皮往框架里凑字数的感觉。临近第一场考试了还一直懊恼没有多练几篇,考试时紧张得全身大汗,紧张程度也是平生第一次。好不容易凑够了字数,自我感觉逻辑非常混乱,最后居然有 6 分,完全出乎我的意料之外。

第一场考试过后,我依然没有练写作……但第二场考试大概因为最先考写作,头脑清晰,写得从容很多,大小作文时间分配正好,大作文正反方观点的论证逻辑自我感觉也更好,最后拿到 6.5 分。

口语

口语一直是我最担心的部分,在很久以前听说雅思考试还要考口语时就心里发怵。根据豆瓣的一篇经验贴买了口语合意包,大致过程是先给我一张调查表,填写与口语话题相关的个人经历,然后老师根据这个调查表写好素材发给我,还可以选择不同的外教录音,配合录音同时素材又都是自己的亲身经历,背起来更快更轻松。另外,在淘宝找了口语老师,菲律宾人,有一点口音,但基本不影响交流。采用微信语音聊天的形式上课,自己跟老师预约上课时间。我当时的课表是每周一二四晚上九点、周六周日晚上七点,因为口语老师 Ellis 每周三和周五晚上要去教堂。第一场考试前上了 8 节课,第二场考试前又上了 4 节。

由于第一次考试,不知道口语还有换题季一说,每年的 1、5、9 月是口语题库更新的月份,每次换题会淘汰掉一部分旧题,新增一部分新题。而我正好撞上了 1 月份的换题。我 12 月 12 号买的口语合意包,当时先给了我一半话题的素材,等换题季稳定之后,才能提供剩下一半话题的素材。等我拿到完整的题库素材时,距离第一场口语考试只剩不到一周的时间了,只能利用最后的一个周末抓紧背,能背多少背多少。

口试当天一直没觉得紧张,直到坐在考场外面等待的最后不到一分钟时间,想着背后一墙之隔就是考官,紧张得要命。考试进行到 Part 2 的一分钟准备时间,紧张得都写不出字来了。所幸抽到的是旧题(an achievement you are proud of),背得还算熟练。考试时觉得时间过得太快,犯了不少语法错误,有两个问题也没听懂,总体上自我感觉还行,可最后只拿了 5.5 分。

第二场口语考试时,由于知道第一场已经考过了,第二场就是去打酱油了。当时 Linda 就在考场外等着我,我在候考区没等多久,考官 Rachel 就喊我的名字,喊得还挺标准(我的名字经常会被 native speaker 念成 Queen-lin)。考试时自我感觉表现远远不如第一次,Part 2 抽到的新题(a sportsman you know about),我准备的素材里有大量的哪年在哪里举行的什么比赛、获得什么奖项的内容,说得磕磕绊绊,最后居然给了 6.5 分,真该窃喜。

国内外考试的比较

澳洲雅思属于亚太考区,国内单独一个考区,不仅考题不同,其它还有很多差异,比如:

  • 笔试顺序不同:国内是听力、阅读、写作;澳洲是写作、阅读、听力。
  • 笔试时的铅笔橡皮不同:国内都是打着 IELTS 和 British Council 标志的专用铅笔橡皮,考完可以自己带走;澳洲至少我参加的悉尼 Navitas 考点,是两支削好的普通铅笔、一个用过无数次的橡皮,外加一个小小的转笔刀!你见过一边考试还要一边削铅笔的吗?而且考完了还不能带走,失去了集齐七支雅思铅笔的机会。
  • 听力设备不同:国内考试人手一个耳机;澳洲是利用多媒体教室的扩音器,我考试那次正好音响有问题,折腾半小时声音还是很小,最后考官问大家意见,大家一致同意以这个音量继续,还好教室不大,对考试成绩完全没有影响。
  • 口试时间安排不同:国内基本是在笔试前的一周内,而且系统上预定的时间往往不是最终的考试时间;澳洲是直接联系考点预约考试时间,可以提前几天考,也可以在考试当天下午,只要还有考位。
  • 安检严格程度不同:国内考试在进入考试之前,工作人员拿着个安排仪器在你身上哔哔一顿扫;澳洲考试在进入考场之前,考官口头问你带手机手表电子设备了吗?没有,好的,请进。
  • 口试考官态度不同:国内口试考官据说普遍态度不友好,我考试时的考官就跟个机器人似的播放着每一道问题,我没听清楚问题问 Pardon?他又跟个机器人似的重播一遍问题,我还是没听懂,机器人「哼哼」冷笑一声,换下一个问题;澳洲考试就完全不同了,口试之前会收到一张考试通知单(如果预约在笔试当天下午考口语的,会在笔试结束后由笔试考官发放),上面不仅列出口试具体时间地点,连口试考官名字都给出了,这就是为什么我知道考官叫 Rachel 的原因。考试过程中考官面带微笑,态度友善,和我有互动,像是真正的聊天,基本没有打断,体验不要太好!
  • 写作和口语给分不同:国内考试写作和口语压分严重,深圳场我分别得分 6/5.5,仅仅隔了三周之后的悉尼场,得分 6.5/6.5,口语提高了整整一分,说国内没有压分我是绝对不信的。

假如将来再考雅思,我应该会试试 A 类,并且尽量在国外考。从个人经历来看,不管是考试体验还是最终成绩,在国外考都是更明智的选择。

最后,感谢 Linda 陪我度过了这充满无限焦虑的两个月。虽然不在身边,但是每天的视频聊天都是我缓解焦虑的通道,尤其第一场考试前的两周时间,我几乎每天都在向她絮絮叨叨地重复着各个单项分数的计算,她也不厌其烦地微笑听我说着。我能两次均分都上 7,有她不可或缺的功劳。

以上。

Resolution 2018 (Philip)

时间紧迫,简单整理一下 2017 年的总结以及 2018 年的计划。

2017 总结

Resolution 2017 (Philip)》中制定的目标完成得并不好。

1、 每月输出一篇工作文档

工作相关的博客完成了 10 篇,其中尝试写了两篇英文博客。即便是技术相关,写得也比较吃力。另外,下半年的工作也没有做到很好的提炼。

2、 完成一次日语 N2 等级考试

7 月份考了一次日语 N2,单项分都达标了,总分差得有点多…… I tried, but I failed.

日语学习笔记整理到初级第 10 单元后也中断了。2018 还要继续学日语,继续和日语死磕。

3、 阅读至少 30 本书

说来惭愧,今年只看了 8 本书(参见《2017 年讀過的書》),其中《Mastering Bitcoin》在看第二版并整理笔记中;《How Google Works》一直没啃完……整理了几篇书摘,都是在下半年完成的。嗯,下半年没写工作总结,都在整理书摘了。

另外,电影看得也没有去年多了,参见《2017 年看過的電影》。

4、 和 Linda 一起去一趟台湾

这是今年的家庭旅行计划,逆时针从花莲到高雄,走马观光地浏览了大半圈。Linda 整理了花莲、宜兰和台北部分:

曼谷跨年计划也即将开始,相隔半年后马上要和 Linda 见面了,内心充满了小激动。

5、 制作一档播客节目

11 月份和七喜录了一期关于个人数字信息安全的播客,在荔枝上线了。本来打算放到又拍云并生成 iTunes 格式的 RSS 订阅列表,但因为突发事件暂时搁置了。

2018 计划

1、每月输出一篇技术相关文档

明年要多用英文写点东西,还是从技术博客开始。

8 月份在 Coursera 上完成了一个加密相关课程,明年的后继课程也已经报名。这部分内容会尽快整理出笔记。

博客后台还有几篇关于比特币、字体、网络协议等内容的草稿,也要尽快扫清。

2、阅读至少 10 本书

去年没有听 Linda 的建议,把目标定得太高。这次务实一点,先给自己定一个小目标,先看它 10 本书……

3、完成两次雅思考试

一月和二月各报了一场,正在紧张地备考当中。时间非常紧迫,12 月初因为奶奶的事情占用了不少时间,白天还得上班,只能晚上和周末有大片的时间准备。

现在每天都非常焦虑,担心自己考不好,担心重蹈日语考试的覆辙。真心佩服那些考过十几场雅思的烤鸭们,希望一切付出都会有回报。

4、去澳洲和 Linda 过春节

作为明年家庭旅行计划的一部分,「去妳去过的地方,看妳看过的风景」。

目前签证和机票都已搞定,酒店和行程安排就靠小助手 Linda 了,哈哈哈哈。

希望 2018 年我们的生活能有所改变,可以离梦想更近一步。

以上。我们明年元旦见。

费马大定理(下)

本文为西蒙・辛格《费马大定理》的书摘,共分上下两篇:

  • 上篇:包含原书第一、第二章的内容。
  • 下篇:包含原书第三~第八章的内容。

数学史上暗淡的一页

莱昂哈德・欧拉(Leonhard Euler)1707 年生于瑞士巴塞尔,是基督教新教加尔文宗的牧师保罗・欧拉(Paul Euler)的儿子。莱昂哈德服从父亲的意愿在巴塞尔大学学习神学和希伯来语。幸运的是,巴塞尔城的伯努利(Bernoullis)家族的丹尼尔和尼古拉是莱昂哈德・欧拉的好友,他们向保罗・欧拉呼吁,请求他允许莱昂哈德放弃教士的职务而选择数学。老欧拉过去曾经向老伯努利(即雅各布・伯努利)学习过数学,对这个家族怀有特殊的敬意,便勉强地同意了。欧拉不久就离开瑞士,在俄国沙皇那里开始了他的专业生涯,随后应普鲁士的腓特烈大帝的邀请到了柏林科学院,最终他又回到俄国,当时正是俄国女皇叶卡捷琳娜二世统治期间,在那里他度过了最后的岁月。

欧拉最重要的成就之一是对理论计算方法的发展,欧拉的计算方法适合于处理那些看上去是不可能解决的问题。太阳、地球和月亮的轨道计算问题,就是所谓的「三体问题」,直到今天仍然不可能得到精确解。但欧拉发展了一种方法,可以得到一个不完全但充分准确的解。这种方法(算法)首先求出一个粗糙但尚能使用的结果,然后将它反馈回算法中再产生一个更为精细的结果。然后这个精细的结果再反馈回算法中产生一个更加准确的结果,如此反复进行,经过百次或更多的迭代以后,欧拉就能提供月球的位置,这个结果用于航海是足够准确的了。欧拉关于月球位置的计算是在他失明期间完成的。

柯尼斯堡桥游戏:普鲁士城市柯尼斯堡(Königsberg)现为俄罗斯的加里宁格勒市,这个城市建立在普雷格尔河边上,由 4 个分离的、被 7 座桥连接起来的地区组成,如下图所示:

问题是能否设计一次旅行,穿越所有的 7 座桥却无须重复走过任何一座桥?欧拉论证了这样的旅行是不可能的:为了进行一次成功的旅行(即通过所有的桥仅一次),一个点应该连接着偶数条线。这是因为在旅行中当旅行者通过一块陆地时,他必须沿一座桥进入,然后沿不同的桥离开,但有两个例外——开始或结束时。在旅行开始时,旅行者离开一块陆地,仅需一座桥给他离开;而在旅行结束时,旅行者到达一块陆地,也仅需一座桥给他进入。如果旅行开始和结束于不同的位置,那么这两块陆地可以允许有奇数座桥,但如果旅行开始和结束于同一个地方,那么这个点(与所有其他的点一样)必须有偶数座桥。总结来说:对于任何桥网络,如果所有的陆地块都有偶数座桥,或者恰好有两个陆地块有奇数座桥,那么才有可能越过每座桥仅一次的完全的旅行。在柯尼斯堡的情形中,4 块陆地都连接着奇数座桥,所以不可能穿越每一座仅一次。

欧拉进一步发现了一条所有的网络的基本定理,即所谓的网络公式:V + R – L = 1,其中 V 是网络中顶点(即交点)的个数,R 是网络中区域(即围成的部分)的个数,L 是网络中连线的个数。论证网络公式时,欧拉从最简单的网络即一个单一的点开始,V = 1,R = L = 0,公式显然成立。然后对这个单一的点扩充,就需要增加一条线。这条线可以将已有的顶点与自己连接,或者它可以将已有的顶点与另一个新的顶点连接。前一种情况:当增加一条线后,生成了一个新的区域,增加的区域抵消了增加的连线,网络公式仍然成立。以这种方式增加更多的连线也同样成立,因为每一条新的连线会制造一个新的区域。后一种情况:增加的线将原来的点与一个新的顶点连接,增加的顶点抵消了增加的连线,网络公式仍然成立。以这种方式增加更多的连线也同样成立,因为每一条新的连线会制造一个新的顶点。

在《算术》的另一个注记中,费马给出了费马大定理对于 4 次幂的证明,而欧拉在 1753 年给普鲁士数学家克里斯蒂安・哥德巴赫(Chritian Goldbach)的信中宣布,他采用费马的无穷递降法并引入虚数 i 的方法成功地证明了 3 次幂的情形。100 多年来,这是第一次有人针对费马的挑战成功地取得了进展。

根据让・勒隆・达朗贝尔(Jean le Rond d’Alembert)的建议,约瑟夫—路易・拉格朗日(Joseph-Louis Lagrange)接替欧拉成为腓特烈大帝宫廷中的数学家。欧拉回到了俄国,叶卡捷琳娜二世迎回了她的「数学的独眼巨人」。

费马大定理(上)

费马大定理》是西蒙・辛格的第一本书,相比《密码故事》来说,这本书的中译本虽然封面上把 Fermat 错误地拼写成 Fremat,正文中也有几处小错误,但瑕不掩瑜,全书整体的翻译质量好很多,尤其是将人名、地名等专有名词翻译出来的同时,还在括弧中保留了英文,可方便地据此搜索相关资料并延伸阅读。

本文为西蒙・辛格《费马大定理》的书摘,共分上下两篇:

  • 上篇:包含原书第一、第二章的内容。
  • 下篇:包含原书第三~第八章的内容。

我想我就在这里结束

1993 年 6 月 23 日,英国剑桥大学牛顿研究所,安德鲁・怀尔斯(Andrew Wiles)向全世界最杰出的数学家讲述他对费马大定理(Fermat’s Last Theorem)的解法。剑桥正是怀尔斯是家乡,这里是他出生成长的地方。他在 20 世纪 80 年代移民到美国,在普林斯顿大学任教授。这次牛顿研究所举行的研讨会的题目是「L-函数和算术」,只有怀尔斯意识到 L-函数可能握有解决费马大定理的钥匙。

1963 年,10 岁的安德鲁・怀尔斯在弥尔顿路上的图书馆发现了埃里克・坦普尔・贝尔(Eric Temple Bell)写的《大问题》(The Last Problem),其中讲述了费马大定理的起源及形成,由此迷上了费马大定理,立志要解决它。

费马大定理立足于毕达哥拉斯(Pythagoras)定理:

在一个直角三角形中,斜边的平方等于两直角边的平方之和。

萨摩斯岛(Samos)的毕达哥拉斯是数学史上最具影响但又是最神秘的人物之一。他研究了一些特殊的数的性质、它们之间的关系以及它们的组成方式。他生活在公元前 6 世纪,游历时从埃及人和巴比伦人那里学到了许多数学技能和工具。这两个古老的民族当时已经超越了简单计数的范围而能够进行复杂的计算,这使他们能建立复杂的记账系统和建造独具匠心的建筑物,但他们将数学看成仅仅是解决实际问题的一种工具,而没有人会费神去寻求隐藏在背后的逻辑。

经历 20 年的周游后,毕达哥拉斯回到爱琴海中的萨摩斯岛,想要建立一所学校致力于哲学研究,特别是研究他新近获得的一些数学法则。但僭王波利克拉特斯(Polycrates)在毕达哥拉斯外出期间已将曾经自由的萨摩斯岛变成了一个不容异说的保守的社会,并邀请毕达哥拉斯加入宫廷,但遭到毕达哥拉斯的拒绝。毕达哥拉斯离开了城市,选择了岛上边远地区的一个山洞。他花钱使一个小男孩成为他的第一名学生,这名学生根据有些历史学家的观点可能也叫毕达哥拉斯。这名学生后来是第一个建议运动员应该吃肉以增强自己体质的人,并因此而出名。学生每出席一节课,老师要付给他 3 个小银币。几个星期后,学生最初对学习的勉强已转变成对知识的热情,即使毕达哥拉斯佯装付不起金钱无法继续上课时,学生也表示宁可付钱受教育。遗憾的是,这是毕达哥拉斯在萨摩斯岛上仅有的一个信徒。

由于毕达哥拉斯关于社会改革的观点不受欢迎,他被迫离开萨摩斯岛,来到意大利南部的克罗敦(Groton),并在米洛(Milo)的赞助下建立了毕达哥拉斯兄弟会——一个有 600 名追随者的帮会。一旦参加兄弟会后,每个成员就必须将其一切财产捐献给公共基金,如果离开该会,可收到相当于他们最初捐献的两倍的财产,并为其竖立一场墓碑以志纪念。兄弟会的每个成员被迫宣誓永不向外界泄露他们的任何数学发现,甚至在毕达哥拉斯死后,还有一个兄弟会成员因为公开宣布发现一种由 12 个正五边形构成的正十二面体而被淹死。兄弟会奉行平等主义,吸收了几名姐妹。毕达哥拉斯最喜欢的学生是米洛的女儿,美丽的西诺(Theano),两人最终结婚了。建立兄弟会后不久,毕达哥拉斯撰造了一个名词「哲学家」(philosopher),定义为「献身于发现生活本身的意义和目的的人」。

毕达哥拉斯缔造了一种社会精神,它改变了数学的进程。兄弟会实际上是一个宗教性社团组织,他们崇拜的偶像之一是数,他们相信,通过了解数与数之间的关系,他们能够提示宇宙的神圣的秘密,使他们自己更接近神。

密码故事(下)

本系列为《密码故事》的书摘,共有上、中、下三篇,各篇链接及包含内容如下:

  • 上篇:单字母替换密码,多字母替换密码。
  • 中篇:加密的机械化,恩格玛机及其破解,象形文字和楔形文字的破解。
  • 下篇:公开密钥,PGP,量子密钥分发。

公开密钥

除了恩格玛机之外,德国还有一套更强大的加密法,称为洛伦兹密码(Lorenz cipher),用来加密希特勒和他的军官之间的通讯。布莱切利的两位破解员,约翰・蒂尔特曼(John Tiltman)和比尔・塔特(Bill Tutte)发现了洛伦兹密码的一个破绽,需要综合寻找、匹配、数据分析和谨慎的判断,而「炸弹」很难变通地应付洛伦兹密码的精妙之处。而布莱切利的数学家马克斯・纽曼(Max Newman)基于图灵的「万能机器」的概念,发明了可以针对不同问题进行自我调节的机器,现在我们称之为「可编程计算机」。1943 年,工程师汤米・弗劳尔斯(Tommy Flowers)无视布莱切利高级官员的怀疑,根据纽曼的蓝图,花了 10 个月时间,制造了科洛希斯(Colossus computer,其中总共有 1500 个电子管。事实上,科洛希斯正是现代数字计算机的前身。

然而,在二战结束后,汤米・弗劳尔斯根据命令将科洛希斯及其蓝图销毁,世界上第一台计算机的设计图就此消失。1945 年,宾夕法尼亚大学的约翰・墨西里(John Mauchly)和 J・蒲利斯普・埃克特(J. Presper Eckert)完成了 ENIAC,它含有 18000 个电子管,每秒能计算 5000 次。几十年来,ENIAC 而非科洛希斯被认为是计算机之母。

用计算机加密和机器加密只有三个重要的区别:

  • 密码机受限于实际建造中的困难,而计算机可以模拟出任何无限复杂的机器。
  • 速度上的区别:电子设备比机器的扰频器运转起来要快得多。
  • 最重要的区别:计算机加密的是数字而非字母。

即便如此,加密过程仍然是按照古老的原则进行的,这些原则就是移位和替换。每次加密,无论多么复杂,都可以还原成一些简单操作的组合。

随着越来越多的公司采用计算机,公司之间的通讯加密也越来越频繁,就出现了加密标准化的问题。1973 年,美国国立标准局正式征求一套标准的加密方案,能够使企业之间进行秘密通讯。IBM 的托马斯・J・沃森实验室(Thomas J Watson)的霍斯特・菲斯特尔(Horst Feistel)发明卢斯福密码机(Lucifer cipher)。1976 年,56 位版本的卢斯福密码机被国家安全局正式采用,称之为数据加密标准(Data Encryption Standard,即 DES)。选用 56 位版本(密钥数目 1018)是因为国家安全局相信这样的密钥对民间通讯来说是安全的,因为没有一个民间组织拥有如此强大的计算机能够在一个合理的时间内检查每个密钥,但国家安全局拥有世界上最快的计算机资源,刚好能破解卢斯福的密钥。

卢斯福系统的加密步骤如下所述:首先,电文翻译成一长段二进制数字串。然后,以每 64 个数字为一个单位,分解这段数字串。每个单位数字串分别独立加密。第三步,我们把注意力集中在每个单位数字串上。把 64 个数字像洗牌那样分成两组,每组 32 个数字,分别把它们叫做左 0 和右 0。右 0 中的数字加入「切碎机函数」中进行复杂的替换。然后,把「切碎」后的右 0 加到左 0 上,形成新的一组 32 个数字的序列,称作右 1。把最开始的右 0 标记为左 1。这一系列的操作称为一个「回合」。然后整个操作又重复做一次,不同的只是这一次以右 1 和左 1 开始,得到的数字序列称为右 2 和左 2。加密过程总共要进行 16 个「回合」。这个过程就像是和面一样:试想在一大块面上写着信息,首先,将这块面分成 64 厘米长的小块;然后,挑出其中的一半碾压后折叠起来,再加到另一半上拉长,从而形成一个新的面块。这个过程不断地重复,直到消息文字彻底地被面块混合起来。经过 16 个回合的「揉面」后,密文发送出去。另一端的接收者收到密文后,将加密过程反过来进行,从而解码出明文。「切碎」的具体实施方法是可以变化的,它取决于发送者和接收者达成的密钥。换言之,只要密钥不同,同样的电文可以用成千上万种不同的方式加密。

除了加密标准化问题之外,密码通讯中存在的另一个问题是「密钥分发」。20 世纪 70 年代,银行尝试雇用专职的密钥分发员,他们带着一个锁着的箱子(padlocked briefcase)走遍全世界,亲手将密钥交给客户。二战时,德国高级指挥部每个月都需要分发《每日密钥》月刊给所有的恩格玛机操作员。美国政府的密钥是 COMSEC(通讯安全局)掌管和分发的。20 世纪 70 年代,COMSEC 每天分发的密钥数以吨计,当装载着 COMSEC 密钥的船靠港时,密码分发员会到甲板上收集各种卡片、纸带以及软盘和其他一切贮存密钥的介质,再把它们分发给客户。计算机改变了密码的实施方式,但 20 世纪密码学最伟大的革命是发明了密钥分发的技巧,这被认为是两千年来自单字母替换密码发明以后最伟大的成就。

密码故事(中)

本系列为《密码故事》的书摘,共有上、中、下三篇,各篇链接及包含内容如下:

  • 上篇:单字母替换密码,多字母替换密码。
  • 中篇:加密的机械化,恩格玛机及其破解,象形文字和楔形文字的破解。
  • 下篇:公开密钥,PGP,量子密钥分发。

加密的机械化

20 世纪初,意大利物理学家古列尔莫・马可尼(Guglielmo Marconi)发明了无线电。无线电具有双重特性:易通信性和易拦截性,这在一战爆发后表现得尤为突出。所有成员都想充分发掘无线电的资源,却苦于不知如何保障安全。在 1914 年到 1918 年间,密码编码者提出了几个新密码,但一个个均被破解了。

ADFGVX 密码(ADFGVX cipher:是一战时德军使用的一种密码,在 1918 年 3 月 5 日首次使用。德国的密码编码师组成的一个小组从各种密码中选择了 ADFGVX 密码,他们相信它是不可破解的。这个密码的特点在于它错综复杂,综合了替换和移位两种处理方法。法国密码破译学家乔治斯・佩因芬(Georges Painvin)中尉在 6 月 2 日的晚上,破解了一段 ADFGVX 信息。佩因芬的突破导致了一系列其他密码依次被破解。ADFGVX 密码的破解成了一战期间密码学的典型。尽管产生了无数的新密码,但它们无非是 19 世纪已经破解了的密码的变形或组合。对于密码破译师来说,最大的问题是如何应付信息数量的急剧增长。一战期间,无线电的使用使得截获的信息激增。据估计法国在一战期间共截获的德国通讯信息达 1000 万个单词。

公元前 400 年,中国的孙武在他的著作《孙子兵法》中提到:「三军之事,莫亲于间,赏莫厚于间,事莫密于间。」大意为:在军队中,没有比间谍更为亲近的人,给予奖赏时,没有比间谍更为优厚的,没有什么事情比间谍更为秘密。法国人坚信孙武的话,在磨炼破译密码技能的同时,还发展了几个收集无线电情报的辅助技术。

法国监听员学会了如何辨别一个无线电操作员的「手迹」,一旦一条加密的信息以摩斯电码的形式发送出来,它就变成了一系列的点和短横,而我们可以通过分析每个无线电操作员的传送速度,他的停顿以及点和短横的相对长度来确定他们的身份。此外,法国人还建立了六个方向的搜索站,它们能够检测每个信息发自哪里。每个站点不断移动它的天线直到收到的信号最强,这就确定了信息源的一个方向。通过组合两个或两个以上站点的信息方向,就可能定位出敌方传送线的确切源头。再加上第一条信息即操作员的手迹,就可能确立某特定军营的身份和地点。法国的情报员可以在几天内跟踪它的走向,一般能推出某敌军部队的目的地和军事目的,这种形式的情报搜集被称作信道分析,它在一个新的密码出现后,前期显得非常有用。对于每个新密码来说,密码分析师可能暂时无法破解它,但即使一个信息无法破译,信道分析仍会提供一些有用的信息。

齐默尔曼的电报(Zimmermann Telegram:1917 年 1 月 17 日,英国截获了一个德军电报,由英国海军部的密码局「40 号房」的蒙哥马利教士(Reverend Montgomery)和曾为出版商的内格尔(Nigel de Grey)破解。这封电报由德国新上任的外交大臣阿瑟・齐默尔曼(Arthur Zimmermann)发出,齐默尔曼的策略是从 2 月 1 日起发动无限制潜艇战争,同时为了使美国保持中立,将和墨西哥联盟,说明墨西哥总统进攻美国,收回诸如得克萨斯、新墨西哥以及亚历桑那的领土,同时希望墨西哥总统说服日本也进攻美国,以此牵制美国使其无法派遣部队到欧洲。他将加密电报发给德国驻华盛顿的大使,再转交给德国驻墨西哥的大使,最后转交给墨西哥总统。

密码故事(上)

西蒙・辛格的《密码故事》生动有趣、引入入胜,但中文译本存在多处人名前后翻译不一致的现象,且原著中关于针孔加密法的示例也完全丢失,建议有条件的同学尽量阅读英文原著《The Code Book》。

本文对于专用词汇的翻译不仅做了统一,索性和通用的翻译对齐,所以和中文译本里的译名可能有出入。共有上、中、下三篇,各篇链接及包含内容如下:

  • 上篇:单字母替换密码,多字母替换密码。
  • 中篇:加密的机械化,恩格玛机及其破解,象形文字和楔形文字的破解。
  • 下篇:公开密钥,PGP,量子密钥分发。

单字母替换密码

隐文术:通过把信息隐藏起来的这种秘密通信称为 Steganography(隐文术),由希腊词 Steganos(意为「覆盖」)和 Graphein(意为「写」)派生而来。

希罗多德(Herodotus)以编年史的形式记载了公元前 5 世纪希腊和波斯之间的冲突,其中提到住在波斯的希腊人德马拉图斯(Demaratus)利用已上蜡的一副可折叠的刻写板,先将蜡刮去,再将波斯的阴谋刻写在木板的背面,然后再涂上蜡盖住消息,从而将信息秘密地传递给希腊人。得到警告的希腊人开始武装自己,并最终在波斯人进攻时佯装被包围,并诱使波斯船队进入海湾,运用策略打败了波斯。

希罗多德还讲述了希斯塔亚乌斯(Histaiaeus)的故事:希斯塔亚乌斯想鼓励米勒图斯(Miletus)的阿里斯塔哥拉斯(Aristagoras)反叛波斯国王,为了秘密地传达他的指示,希斯塔亚乌斯剃光了他的一个信使的头发,将信息写在其头皮上,再等信使的头发重新长起来,很明显这段历史时期发生的还不是什么紧急事件。这个信使显然不用携带任何异物,能够自由穿行,不会有麻烦。一旦到达目的地,他就剃光头发,指给联络人看。

中国古代将信息写在小块丝绸上,塞进一个小球里,再用蜡封上,然后让信使吞下这个蜡球。

16 世纪,意大利科学家乔瓦尼・波塔(Giovanni Porta)描述了如何将信息隐藏在一个煮熟的鸡蛋里:把少许明矾和一点醋混在一起制成一种墨水,再用这种墨水将信息写在鸡蛋壳表面。墨水溶液就会经蛋壳上的微孔渗透进去,在已凝固的鸡蛋白表面留下印迹,这样只能剥去蛋壳后才能读取。

早在公元 1 世纪普林尼(Pliny the Elder)就解释了体液如何用作隐形墨水。用体液写的字晾干后即变得透明,但轻轻地加热就能把液体烤焦,从而字迹就以棕色显现出来。许多有机液体都有这样的性质,因为它们富含碳因而很容易被烤焦。事实上,即使是现代间谍也很少知道在标准配备的隐形墨水用完之后还可以用自己的尿液来临时代替。

密码术:在隐文术发展的同时,还有另一种方法也在演化,那就是 Cryptography(密码术),从希腊词 Kryptos(意为「隐藏」)派生而来。密码术的目的不是隐藏信息本身,而是要隐藏它的意思,也就是一种加密的过程。

隐文术和密码术常常混合使用。例如,二战期间流行的微粒照片是一种隐文术。德军在拉丁美洲的间谍将一页文件缩小在直径不到 1 毫米的微型照片上,看上去就是一个点,再将这个点状照片贴在看似无关紧要的一封信的某个句号上面。这种微型照片在 1941 年第一次被美国联邦调查局发现后,德军间谍开始有所防范,在缩小之前,将照片中的信息打乱。

密码术分为两种,即移位和替换。在移位中,字母不变,位置改变;在替换中,字母改变,位置不变。

S. 中使用的加密法

S.》中使用到了四种经典的加密法。本文介绍这四种加密法的加解密方法、在书中的应用和解密过程。

波雷费加密法

波雷费加密法(Playfair cipher)由 Charles Wheatstone 于 1854 年发明,由 Lord Playfair 大力推广并以后者的名字命名。此加密法在第二次波尔战争和两次世界大战中都有应用,主要用于短时间内保护重要但非致命的信息。现代电子计算机的出现使得波雷费加密法在几秒钟内就会被破解,而不再被军方使用。

波雷费加密法首先需要生成一个 5×5 的矩阵,使用关键字或短语(去掉重复的字母)及剩下的英文字母按顺序填充这个矩阵。填充顺序可以是从左到右、从上到下填充,也可以是从最左上角开始、顺时针方向螺旋向内填充。由于英文字母有 26 个,而矩阵只有 25 个位置,因此可以去掉字母 J 或 Q,或者字母 I 和字母 J 使用同一格等。

加密时,将明文每两个字母作为一个二元组,对照上面生成的矩阵,对每个二元组依以下四条规则处理:

  • 如果二元组中两个字母相同,则将第二个字母替换为 X 再继续加密;如果只剩一个字母(即明文长度为奇数),则加上字母 X 再继续加密。也可以使用字母 Q 或其它任意不常用的字母。
  • 如果二元组中的两个字母在矩阵中位于同一行,则分别使用右边的字母替换(矩阵中最右边的字母则翻转到最左边的字母替换)。
  • 如果二元组中的两个字母在矩阵中位于同一列,则分别使用下面的字母替换(矩阵中最下面的字母则翻转到最上面的字母替换)。
  • 如果二元组中的两个字母在矩阵中既不在同一行,也不在同一列,则分别使用各自同一行且与对方同一列的字母替换(也就是对角上的两个字母,注意替换后二元组中两个字母的顺序)。

解密时,对密文两两组成的二元组使用上述后三条规则相反的操作处理(同行左移,同列上移,其余对角),并根据第一条规则去掉末尾不合理的字母 X 或 Q,或将字母 X 或 Q 替换为其前面的字母,即可得到明文。

双棘轮算法

PGP 自我扫盲

前言

久闻 PGP 大名,印象中是使用非对称加密算法,且经常能在邮件列表的签名档中看到一长串的 PGP Public Key,却一直不知其原理及用法。最近把这块知识盲区扫除并记录成文。

PGP、OpenPGP 和 GPG

PGP 是 Pretty Good Privacy 的缩写,由 Philip R. Zimmermann 于 1991 年编写并上传到 USENET 而在全球流行,被广泛用于文本、电子邮件、文件甚至整个磁盘分区的签名、加密和解密。上传行为因涉嫌违反美国的加密软件出口限制而使 Zimmermann 陷入长达三年的犯罪调查。政府的调查终止之后,Zimmermann 创立了 PGP 公司,PGP 由此成为商业软件(PGP 公司在辗转多次之后最终被 Symantec 收购)。

OpenPGP 是由 PGP 衍生出的开源规范,而 GnuPG(简称 GPG)就是遵循 OpenPGP 规范的 GNU 实现。在不需要特别说明差异的情况下,三者统称为 PGP。