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

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

Alice and Bob

2009 年 2 月 9 日 / 22 条评论

来源：http://abstrusegoose.com/113

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

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 月 15 日 / 17 条评论

    我们常常在电视上看到这样的一幕：一位老太太兴冲冲地走上台去，翻过三个商标牌，发现上面尽是5块钱、10块钱的小奖，垂头丧气地回到观众席；然后马脸李咏会跑出来，边翻着另外几个牌子边说，1000块的大奖在这个后面，800块的在这里，之类的。或许有人会纳闷了，为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单，节目组想通过这一个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这后面，只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖，摸完奖之后还能证实大奖真的存在，这就是带有防欺骗的承诺。
    但是，同样的事情在网络上似乎是办不到的。一个典型的例子就是QQ原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋，屏幕右边那个是金蛋，你鼠标选一个敲下去，看能否砸出QQ宠物来。大量测试表明砸出宠物的概率远远低于50%，让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋，很可能不管你点了哪个蛋蛋结果都一样，系统按照概率直接显示出抽奖结果来。当然，怀疑游戏的公平性也没办法，要想在网络上实现带防欺骗的承诺是比较困难的，毕竟让你看一段从另一个蛋蛋里跳出一个宠物的Flash动画不能让你相信刚才你是真的“选错”了吧。
    我们的问题就是：如何设计一个协议，用以保证一个二选一的网络互动抽奖游戏的真实性？换句话说，假如你选择了金蛋，结果没有中奖，那么系统如何能够令你相信奖品刚才真的在银蛋里？