密码学协议举例（四）：秘密数字的比较

2009 年 2 月 9 日 / 23 条评论

    让我们来看一个很实用的问题：A和B两位女士希望知道她们俩哪个年龄大，但又都不愿意透露自己的年龄。有什么方法能够让她们在不泄露年龄的情况下比较出年龄大小呢？我们假设双方都是诚实可信的。她们会严格遵守协议并且不会撒谎。她们唯一不希望做的仅仅是泄露自己的年龄。
    不妨设A的年龄为a，B的年龄为b。为简便起见，假设这两个数都是21到30之间的整数。下面这个协议可以让双方比较出a和b的大小，而不透露a和b的实际值。这个协议也不需要第三方的参与。
    协议开始前，B生成一对RSA钥匙，例如n=3233, e=17, d=2753。首先，A选取一个大随机数x，比方说1117。A用B的公开钥匙给随机数1117加密，得到密文1652。A把1652减a的值发给B。如果A是一个22岁的漂亮MM，那么B实际接收到的数就是1630。
    接下来，B尝试用私人密钥来恢复x。由于B不知道a是多少，于是B枚举所有21到30之间的整数，用私钥对

1651, 1652, 1653, 1654, 1655, 1656, 1657, 1658, 1659, 1660

这10个数分别解密，得到的结果分别为

527, 1117, 1499, 2606, 3026, 3169, 3043, 1353, 1053, 1633

密码学协议举例（三）：另类的密钥交换协议

2009 年 1 月 29 日 / 9 条评论

    密钥是密码的命根，一切不安全的秘密交换都源于不安全的密钥交换。目前，绝大多数协议采取RSA算法进行密钥交换，但在RSA算法出现之前，人们又是怎么做的呢？据说，第一个密钥交换算法是一个名叫Ralph Merkel的人在1974年发明的，算法叫做Merkle’s Puzzles。这是一个非常奇特、非常邪恶的密钥交换协议。
    假设A和B想进行秘密通信，他们需要选取一个密钥。A准备好很多很多个形如“密钥编号为X_i，密钥是Y_i”的消息，其中X_i是一个随机标识符，Y_i是一个随机密钥。消息的个数越多越好，起码要有几十万几百万条。然后，A把这些消息都编码为一个个难题，比方说对第i条消息异或一个大质数P_i，并宣称P_i是某个数N_i最小的那个质因子。A把所有编码后的消息全部发给B。B收到这些消息之后，随便选择一条消息进行暴力破解（在上例中就是暴力分解某个N_i），得到某一对对应的x和y。B用明文给A发一个消息，说“我们就用编号为x的密钥吧”。由于A知道这个x对应的是哪个y，因此A知道B说的密钥是哪个。
    这个协议的核心就是，第三者不知道B当时选的是哪条消息。如果有第三者截获了他们之间的通信，要想获得密钥y，他必须一一破解所有的难题，直至解开了那个编号为x的密钥消息。由于这样的难题数量大得惊人，第三者要花费的努力是B的上百万倍。假如用计算机暴力破解一个难题需要一个小时的时间，那么第三者即使有百倍于B的计算能力，他也需要平均一年多才能解到正确的x和y。

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

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组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。

一个简单而有用的数据结构

2009 年 1 月 21 日 / 57 条评论

Hash表是一个很有用的数据结构，它用O(N)的空间描述一个元素在0到N-1范围内的集合，支持常数级别的添加、删除和查询。遗憾的是，Hash表不能在常数时间内批量删除元素，返回全部元素也需要O(N)的时间，而理论上说这几个操作可以做的更好。现在，你能否设计一个数据结构，它同样占用O(N)的空间，支持常数时间的添加、删除、查询、清空（删除所有元素）、势查询（返回元素个数），以及O(n)时间的元素遍历（其中n表示集合中的元素个数）。

趣题：在双向有序链表中查找指定的数

2009 年 1 月 16 日 / 17 条评论

大家都知道，在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没，在一个有序链表中又怎么样呢？让我们假设有这样一个链表，每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素（如果有的话）。另外，我们知道每个元素在内存中的地址，因此可以进行随机存取。或者可以说，这个有序链表中的所有元素都是储存在一个数组中的，但数组本身并不有序。
现在，我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来？