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

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 月 11 日 / 35 条评论

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

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

Al Zimmermann编程大赛已经开始

2008 年 8 月 23 日 / 11 条评论

来自MathPuzzle的消息：新一轮的Al Zimmermann编程大赛开始了。这次比赛的问题描述如下：

对于一个给定的n，找出n个正整数，使得通过它们之间的加减运算能够得到尽可能多的质数。

具体的说，对于一个指定的n，参数选手需要提交n个数A1, A2, …, An。这n个数将由公式ΣAi*Ci产生3^n个和（其中每个Ci可以取-1、0和1中的任一个），这3^n个和中（不同的）质数越多越好。例如，当n=4时，10, 29, 82, 106可以产生9个不同的质数：

5 = 106 + 10 – 82 – 29
19 = 29 – 10
29 = 29
43 = 82 – 29 – 10
53 = 82 – 29
67 = 106 – 29 – 10
101 = 82 + 29 – 10
149 = 106 + 82 – 29 -10
227 = 106 + 82 + 29 + 10

    参赛者需要完成n=3, 4, …, 14共12个问题，提交的每一组数的和不能超过2^32-1。比赛将在2008年11月10日结束，你可以在此之前提交任意多次。获胜者可以从下面两个网页中任选一个雕刻品作为奖品。说实话，奖品很诱人，我很想要。
    http://www.bathsheba.com/sculpt/
    http://www.bathsheba.com/math/

一个与矩形剖分有关的命题（四）：简便的数论证明

2008 年 8 月 2 日 / 5 条评论

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

不假，利用数论知识我们真的可以证明这个和数论八杆子打不着的题目。证明的关键就在于，质数有无穷多个。给定一个满足要求的大矩形，如果你宣称它的每条边都不是整数，它们都至少多出了大小为ε的“零头”。那么，我就找出一个足够大的质数p，使得1/p < ε，然后说明有一条边的长度除去整数部分后的“零头”不会超过1/p。这样的话，至少有一边恰好是整数长才行。仍然是把大矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑所有形如(i/p, j/p)的点所形成的点阵（其中i, j均为整数）。我们需要把整个点阵平移到一个合适位置，使得点阵中没有点恰好落在小矩形的边界上。这总是可以办到的，例如我们算出每个小矩形的横边到点阵中离它最近的点的距离，取所有这些最近距离中最小的非0的值，然后竖直方向上移动一个比这还小的距离；另一个方向亦是如此。注意到每个小矩形内部所含的点数都是两个数的乘积，由于其中至少有一个数是p的倍数，因此每个小矩形内都有p的倍数个点。那么，整个大矩形所含的点的个数（即每个小矩形所含点数之和）也是p的倍数。大矩形内的所有点的个数也是两个数的乘积，然而p是质数，因此两个数中至少一个是p的倍数（数论的一个基本结论）。那么，对应的那条边就应该是整数长，并且最多有1/p的误差。（三）（四）两种证明均来自http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/May1999.html

经典证明：质数无穷多与两个更强的命题

2008 年 6 月 18 日 / 13 条评论

又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+…)(1+1/3+1/9+…)(1+1/5+1/25+…)…展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+…+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。