Posts By Philip Ye

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。

Linux 定时器的正确打开姿势

最近上层子系统使用我们封装的定时器时,发现定时不准确,比实时时间慢了一些。本文记录定位过程及解决方法。

使用定时器的一般步骤

Linux 下使用定时器的一般步骤如下:

(1) 使用 timer_create() 创建定时器

struct sigevent evp;

memset(&evp, 0, sizeof(struct sigevent));
evp.sigev_notify = SIGEV_SIGNAL;
evp.sigev_signo = timer_no;

if (timer_create(CLOCK_REALTIME, &evp, &tTimer[timer_no].timer) < 0)
{
return -1;
}

return 0;

其中的 timer_no 为定时器编号,tTimer 为事先定义的一个定时器结构体。刚创建的定时器不会自动运行。

(2) 使用 timer_settime() 设置定时器超时时间

timer_settime(tTimer[timer_no].timer, 0, &tTimer[timer_no].timevalue, NULL);

设置之后定时器立即开始运行。

(3) 在定时器线程中使用 sigwait() 等待定时器超时

sigset_t tsigmask;
int isigrcv, i;
long ret;

sigemptyset(&tsigmask);
for (i = 0; i < NUM_OF_TIMERS; i++)
{
sigaddset(&tsigmask, SIGRTMAX – i);
}

while (1)
{
ret = sigwait(&tsigmask, &isigrcv);
if (ret >= 0)
{
/* 调用定时器回调函数 */
}
}

查看内核的 date 是否准确

首先从源头开始,验证内核的实时时钟是否准确,借助 date 命令拷机实现。

先输入一次 date 命令,拷机一段时间之后,再输入一次 date 命令,通过对比两次命令输出的时间差与 SecureCRT 两条 log 记录的时间差,确认内核实时时钟准确无误。

(11:46:30.614) $ date
(11:46:30.645) Mon Jul 17 11:46:30 CST 2017
(13:48:02.798) $ date
(13:48:02.798) Mon Jul 17 13:48:02 CST 2017

查看用户态和内核的定时器计数是否一致

先在用户态的定时器线程的回调函数中,增加计数,定时器每超时一次就累加 1。

然后打开内核的 CONFIG_TIMER_STATS 配置项,重新编译内核并运行后,执行如下命令打开定时器统计:

echo 1 > /proc/timer_stats

之后使用如下命令查看所有定时器的计数信息等:

cat /proc/timer_stats

输出的信息类似如下:

Timer Stats Version: v0.2
Sample period: 55521.903 s

14205534, 1501 linux.out .common_timer_set (posix_timer_fn)

389290862 total events, 7011.482 events/sec

其中 linux.out 那行就是上层子系统所使用的定时器,超时计数为 14205534。而在应用代码中的计数为 14205535,比 timer_stats 的计数多了 1。且再次开启关闭一次定时器(同样通过调用 timer_settime() 实现),应用代码中的计数比 timer_stats 的计数多了 2,如此递增。此为疑点。

发现定时器使用时的问题

重新走查用户态中定时器相关代码,发现了问题所在。

在使用 timer_create() 创建定时器之后,设置 timer_settime() 时,对于第三个入参 new_value,只将超时时间赋值给了 it_valueit_interval 设置为 0。

参考 timer_settime(2) 中关于 it_valueit_interval 的说明:

If new_value->it_value specifies a nonzero value (i.e., either subfield is nonzero), then timer_settime() arms (starts) the timer, setting it to initially expire at the given time. (If the timer was already armed, then the previous settings are overwritten.) If new_value->it_value specifies a zero value (i.e., both subfields are zero), then the timer is disarmed.

The new_value->it_interval field specifies the period of the timer, in seconds and nanoseconds. If this field is nonzero, then each time that an armed timer expires, the timer is reloaded from the value specified in new_value->it_interval. If new_value->it_interval specifies a zero value then the timer expires just once, at the time specified by it_value.

也就是说,it_value 确定第一次超时时间,it_interval 确定后续的超时时间。那么现有的代码中如何实现定时器多次执行的呢?

原来是在定时器线程的 while 循环部分再次调用 timer_settime() 重新设置一次 it_value

while (1)
{
ret = sigwait(&tsigmask, &isigrcv);
if (ret >= 0)
{
/* 调用定时器回调函数 */
tTimer[timer_no].clkCallback(tTimer[timer_no].argCall);
timer_settime(tTimer[timer_no].timer, 0, &tTimer[timer_no].timevalue, NULL);
}
}

那么在定时器此次超时到再次调用 timer_settime() 启动定时器之间,存在一定的延迟而引入误差,长时间运行之后此误差将累积,导致定时器比实时时间慢。

这也可解释为什么启动停止定时器会导致用户态的计数比内核的计数多 1 的现象。内核的定时器已经超时停止,但用户态回调最后还会累加 1。

解决方法

  • 在调用 timer_settime() 时,同时设置 it_valueit_interval 的值,使定时器自动重新加载并循环运行。
  • 在定时器回调函数中,去掉调用 timer_settime() 重新设置定时器超时时间的代码。仅保留调用上层子系统挂载的回调函数即可。

这才是 Linux 定时器的正确打开姿势。

以上。