身份验证、中间人攻击和数字签名:浅谈密码学(上)

    说到“密码学”,大多数人的第一念头或许是Morse电码、Ceasar移位密码、同音替换密码之类的东西。这些东西在各类小说中都已是老面孔了,“字母e在英文中出现频率最高”这一最基本的破密码方法已经是耳熟能详了。几天前和网易的云风聊了一下,突然体会到了密码学的真谛。密码学关注更多的并不是加密解密的各种数学算法,而是在已有数学算法上如何实现各种安全需求。防止消息泄露只是众多安全问题中的冰山一角,而这个问题本身又有很多复杂的变化。

    当我们谈到“消息泄露”时,我们头脑中想到的往往是,在信息传输过程中如何防止第三方截获。当然,小偷防是防不住的,不过我能保证他偷到东西也没用。双方只需要事先约定一套加密函数和解密函数,以密文的方式进行传输,这样便能很好地防止消息泄露。但有时候,“消息泄露”的内涵复杂得多,加密解密的传统方法并不适用。考虑这么一个问题:10个人坐在一起谈天,突然他们想知道他们的平均年薪,但又都不愿意透露自己的工资数额。有没有什么办法让他们能够得出答案,并且不用担心自己的年薪被曝光?事实上,最简单的解决办法不需要依赖任何密码学知识:第一个人随便想一个大数,比如880516。然后他在纸条上写下这个数与自己的年薪之和,传给第二个人;第二个人再在这个数上加上他的年薪数额,写在另一张纸条上传给第三个人;直到最后一个人把纸条传回第一个人后,第一个人把纸条上的数减去只有自己知道的那个880516,便得到了全部10个人的工资和。

Read more…

八卦的学问:实现所有人消息共享最少需要多少通电话?

    最近看到了一个有趣的问题Gossip Problem。假如我们班有n个MM,每一个MM都有一个独家八卦消息。两个MM可以通过电话联系,一通电话将使得双方都获知到对方目前已知的全部消息。要想所有n个MM都知道所有n条八卦消息,最少需要多少通电话?
    一个最简单的办法就是从n个人中选一个消息汇总人,所有n-1个人都打电话给她,她再打电话给所有人。这样总共需要2n-2通电话。其实,汇总阶段的最后一通电话和发布阶段的第一通电话可以合并为一通电话,这样的话该方案实际上只需要2n-3通电话。打电话的次数还能更少吗?给出一个最优解,并证明这个数目已经不能再少了。

 
    显然,n=2时只需要一通电话,n=3时必须要3通电话。当n=4时,可以让AB互相通话,CD互相通话,此时每个人都知道了(包括自己的)两条消息;然后A和C通话,B和D通话,从而使得每个人都获知另外两条自己还不知道的消息。显然,对于4个人的情况,4通电话已经是最少的了。
    对于n>4的情况,有一种算法可以保证在2n-4通电话内解决问题。首先,选出4个人作为消息汇总人。其余每个人都选择一个汇总人并与之通话;然后4个汇总人再用4通电话互相更新一下消息(用刚才n=4的办法);最后4个汇总人把电话再打回去,实现所有消息全部共享。下面我们证明,2n-4已经是最少的了。证明方法很多,也都很复杂。最常见的证明由Brenda Baker和Robert Shostak在1972年给出。

Read more…

漫话二分(下)

    很多问题并不完全符合二分的模型。最常见的一个情况估计应该是无穷长的有序队列中的二分查找问题。例如,前文所提到的求解x^x=a实际上就是这样的问题,这里x的取值范围可以是大于0的所有实数。当然,这里的x明显有一个上界,比如x明显要比a小。但是,如果有什么二分问题,它没有一个明确的上界呢?比如,我们再玩一次猜数游戏,我想一个数,然后告诉你你的猜测是大了还是小了。不同的是,我不告诉你这个数是在什么范围内选的,我想的数可以是任意一个正整数。那你该怎么办呢?最初的想法当然是,不断往大的猜,直到某个时候它超过了目标值为止;然后以它为上界,剩下的就可以看作有限多了。关键是,我们以什么样的跨度来枚举这个上界?首先必须肯定的是,这个上界枚举序列必须是发散的,否则会有数我们一辈子也猜不到;同时,线性增长的策略也是很傻的:跨度太小了你可能得到猴年才能找出上界,跨度太大了的话一来就确定了上界,但待考虑的队列也可能远远超过所需。一个比较灵活的想法是:按照1, 2, 4, 8, 16, …, 2^n的序列来猜测上界。这是一种“相对大小”的思想:既然连前面N个数都小了,我们也就不在乎那么一两个了,不妨直接再跳过N个数直接考察2N。这样的话,整个猜测过程仍然保持log(n)的复杂度,整个算法也更加美观一些。

    假如你有一台时光机,可以让你到任意远的未来去,你打算怎么来使用它?或许你会说,先去100年后看看,生活一年之后再去200年后体验体验,然后再去300年后生活一年,再去400年后生活一年……其实,这种线性的时光旅行并不科学。当你已经跨越了数千年以后,相比之下100年的跨度已经不算遥远了,1000年后与1100年后的差异远远没有今天和100年以后的变化那样令人震撼。我说我和Stetson MM的思维如出一辙,那不是说着好玩的。一次MSN聊天时我们讨论到这个话题,两人同时想到了这样的时间旅行方式:先直接跳到1年后生活,再到2年后生活一段时间,再到4年后,再到8年后……用这种方式来体验未来,即使我在每一个时间点停留一年,我也能保证见到从我余生的感情生活到人类文明的各种不可思议的形态,甚至到文明的轮回与宇宙的毁灭等各种尺度下的牛B事。我的确能够看到充分远的未来,了解到足够宏大的文明史和宇宙史:假设我还能活80年,那么我可以看到2^80=1208925819614629174706176年内的种种,这么多年里估计就是宇宙热寂也该结束了。
    折纸后的高度、在棋盘里放米、Hanoi塔与世界末日……无数火星的例子告诉我们,倍增的力量是异常强大的。如果你不信的话,下次来北京时请我喝酒,不妨这样来试试:先我喝一杯,你喝一口;然后我喝一杯,你喝两口;然后我喝一杯,你喝四口……看咱俩谁坚持的久。

Read more…

漫话二分(上)

    二分思想真的是无所不在,即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到,一个音位可以由一组区别特征确定下来,这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在,因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样,我想一个数字后让你来猜,我告诉你你的猜测是大了还是小了。只是在这里,回馈的信息不再是大小,而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏,一系列火星的称球问题,基于比较的排序算法的复杂度下界,或者经典的20q在线游戏
    一个有趣的事实是,相当多的人都错误地理解了“二分”这个词,但他们在生活中却拥有很强的二分意识。我们语言学概论的老师(这里就不说是谁了)在讲解二分时举了一个甚为荒谬的例子:如果你要在房间里找一根针,那么你可以把房间划分为两半,如果这一半找不到的话说明针一定在房间另一半,此时再把那一半分成两部分,不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角,因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的,而且最关键的是它并不具有规模减半的功能,或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话,同样是拿找东西打比方,在合唱队中找出跑调了的人是一个绝佳的例子,因为在合唱中我们能轻易分辨出一个不和谐的声音(虽然无法准确判断这个声音是从哪儿传来的),不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是,这老师在举这个错误例子的同时,竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了,我们可能看不清,于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号,发现字已经超出屏幕了;然后把字体改成20号,又觉得还能再大一些;进而又改到28号(工具栏上的字号调整以4为步长),最后确定到了24号字。

    如果真的叫一个课讲的好的老师来说二分,课程可以变得相当有意思。每次回我们高中时我都讲了很多次课,我最喜欢聊到的话题之一就是二分。从猜数游戏引入二分查询有序队列中的指定元素,然后提出一些标准的有序队列二分搜索的实际应用,比如解方程x^x=100一类的问题。紧接着提出二分的各种有趣的变形,例如如何在有序整数序列中查询A_i=i的元素。提出这些问题的目的就在于告诉大家,二分的思想不仅仅是用在猜数游戏一类的情况下。二分判断并不只限于“比目标值大/比目标值小”,只要能判断出目标值在哪边都行,例如在这里,A_i<i表明目标元素一定还在右边,A_i>i则表明目标元素在左边。

 i  =    1   2   3   4   5   6   7   8   9   10
A_i = -100 -20  -3   0   2   6  13  14  27  298

Read more…