这些序列都是自相似序列……

2009 年 2 月 2 日 / 14 条评论

如果说数学家是魔术师的话，无穷就是一根最强大的魔杖。在Manfred Schröder的一篇题为Fractals in Music的论文里，作者提到，把每个正整数对应的二进制数中“1”的个数依次写下来，得到的数列有一个很神奇的性质：划掉所有的奇数项，得到的序列仍然是整个序列本身。

十进制数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 二进制数 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1的个数 1 1 2 1 2 2 3 1 2 2 3 2 3 3 取偶数项 1 1 2 1 2 2 3

最初我是在《算法艺术与信息学竞赛》里见到这个东西的，当时硬是被震撼住了。这样的序列叫做“自相似序列”，意思是说自己的一部分等于本身。注意到，这个“自相似”可以无限制地进行下去。再次取出所得的序列中的偶数项，结果还是与最初的序列一样；再这样做下去做无数次，每一次的结果都会与原始序列相同。也就是说，无穷里面包含了无穷多个规模不同的无穷，并且所有这些无穷都和原来完全相同。不过呢，仔细一想你会发现这个一点也不奇怪，奥妙就在于，n和2n的二进制表达中唯一的差别就是末尾的那个“0”。

密码学协议举例（二）：秘密共享的门限方案

2009 年 1 月 21 日 / 11 条评论

电影中经常出现这样的情节：有一份绝密文件需要交给5位特工，为了防止某个特工被捕或者叛变，5名特工各自只持有其中1/5的文件（更好的做法是只持有其中1/5的密钥），这5名特工需要同时在场才能获取文件全文。但这也有一个隐患：如果真的有特工被抓了，当坏人们发现只拿到其中一份文件没有任何用处的同时，特工们也会因为少一份文件无法解开全文而烦恼。此时，你或许会想，是否有什么办法能够让特工们仍然能够恢复原文，即使一部分特工被抓住了？换句话说，有没有什么密文发布方式使得，只要5个人中半数以上的人在场就可以解开绝密文件？这样的话，侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为(3,5)门限方案，意即5个人中至少3人在场才能解开密文。

实现(m,n)门限方案的一个传统办法是，把这份文件的密钥拆成C(n,m-1)份，每个人持有C(n-1,m-1)份密钥。在(3,5)门限方案中，我们需要C(5,2)=10个密钥，不妨分别用0到9编号；5个特工各持有6个密钥，密钥的分配如下：

特工#1: 012345 特工#2: 012 678 特工#3: 0 34 67 9 特工#4: 1 3 56 89 特工#5: 2 45 789

上述分配表的构造其实很简单：为特工的每一种5选3组合分配一个密钥，例如把密钥0分给特工1、2、3，把密钥1分给特工1、2、4，把密钥9分给特工3、4、5。这样的话，任意两个人在场都无法打开文件，因为他们始终缺少一把钥匙（这把钥匙分给了其余三个人）。而任意三个人在场都足以打开文件，因为根据鸽笼原理，任何一个5选3组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。

身份验证、中间人攻击和数字签名：浅谈密码学（中）

2008 年 12 月 16 日 / 24 条评论

事情还没有结束呢！我们前面假设，大家公开公钥的方式是“发布在一个众人可信的网站上”，这种假设是有原因的。需要临时交换双方公钥的通话协议是不安全的，这里面存在一个戏剧性的漏洞。举个例子，假如A和B认为，任何网站都是不可靠的，他们从未并且今后也不会在网上公布自己的公钥。为了加密通信，A需要亲自告诉B他的公钥，B也需要亲自告诉A自己的公钥。收到公钥后，双方便用对方的公钥加密进行数据传输。因为用这个公钥加密后，只有对方才能解开密码，因此双方都认为这条通信线路是安全的。其实，他俩的麻烦大了。这条线路并不是安全的，第三者可以用一种很搞笑的方式来窃听消息。假设有一个人C知道A和B之间将有一次加密通话。C劫持了A和B之间的通讯线路。现在，A把他的公钥发给B，这个公钥传到一半时被C拦截下来，于是C获得了A的公钥；C再把他自己的公钥发给B，让B把C的公钥错当成A的公钥。同样地，B把他自己的公钥发给A，被C拦截下来。C把自己的公钥发给A，让A以为那是B的公钥。以后，每当A给B发加密消息时，A其实是用C的公钥在加密；C把A的消息解密后，再用B的公钥加密后传给B。类似地，一旦B给A发送消息，C都可以将消息解密，并用A的公钥进行加密后传过去。此时，A和B都以为自己在用对方的公钥加密，并都能用自己的私有钥匙解开对方传来的密文；殊不知，这中间有人仅仅用了一点雕虫小技，无声无息地窃走了所有的信息。C正是利用了公钥加密术“谁都可以加密”的性质，结结实实地玩弄了A和B。这种攻击方法叫做“中间人攻击”。
这让我想起了经典的国际象棋骗术。一个象棋白痴宣称自己是个大牛。为了证实这一点，他将要与两位大师同时对弈。他说，我先下后下都能赢。于是，在与大师A的对弈中他为白方，与大师B对战则执黑。结果呢，两盘比赛下来居然都打成了平手。怎么回事呢？其实那个象棋白痴耍了个小伎俩，他把大师A走的棋记了下来，跑到另一边去下给B看，又把B的应着原封不动地搬到了和A的棋局上。来来回回搞了半天，他自己只起了个传递信息的作用，真正在对弈的是两个大师。

身份验证、中间人攻击和数字签名：浅谈密码学（上）

2008 年 12 月 11 日 / 35 条评论

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

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