2009-02-09 19:19| 
14 Comments | 本文内容遵从 让我们来看一个很实用的问题：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
当然，解出来的10个数里面，只有一个恰好等于x，其余的数其实都没啥意义。不过，B也不知道哪个数等于x。接下来B选取一个素数p，这个素数p应该比x小几个数量级（B不知道x是什么，但A可以透露出x大致的数量级）。假设B选的素数等于97，B把解密得到的10个数全部模p，得到
42, 50, 44, 84, 19, 65, 36, 92, 83, 81
假设B的年龄是25岁，那么B把后面5项全部加一，然后把下面这10个数和素数p=97传给A：
42, 50, 44, 84, 19, 66, 37, 93, 84, 82
A只需要（也只能够）算一算1117模p是否等于序列中的第2个数。由于1117≡50 (mod 97)，这就说明被加了一的那些项还在后面，换句话说a≤b。另外，如果说B的年龄是21岁，那么B发送的序列中后面9项都是加了一的，A发现1117和51模97不同余，便可知a>b。
A不可能知道b是多少，因为A收到的序列是模了p的，A不能把序列还原成模p前的序列，自然也就不能用B的公钥返回去计算并与序列1651, 1652, ..., 1660作比较了。
8错。。。。先顶再看
老大就看一看我的问题嘛～～～～～～～～～～～～～～～
抢个高层……
用+1吗？只要改成一个和原来不相同的数就行了
沙发很执着……
呃..好麻烦..
沙发的问题解决了。
不妨设c=1-a，d=1-b。
假设按照第一种规则打的时候把2*n-1局打满，那么每一个最终小结果概率的形式都会是一串a和c（共n个）的连乘积乘以一串b和d（共n-1个）的连乘积，而且A胜当且仅当a和b的个数加起来>=n。
现在，按照第二种规则打时，树形图不是满的，接下来我们不继续用第二种规则，而用另外的规则把它补满：在某个终端结点处，如果A胜剩下的都让B发球，B胜都让A发球。
这样，小结果就可以一一对应了。我们把第一种规则下的一个小结果写成两行，一行n个a和c（A发球），一行n-1个b和d（B发球），将其对应于第二种规则补满后的小结果：
从第一行开始读。每次读到a或d（发球胜）就接着读，读到c或b（接球胜）就转到另一行，开始读第一个没读过的。
读到一方胜利后，剩下的一列的结果依次当作最后“补满”比赛的结果。
这样必然恰好有一列读完，因为如果最后A胜，那么A开始发了一次球，最后赢了一个球，中间的发球/赢球对应，恰把n个发球对应n分；B开始不发球，易知只发球n-1次。
接下来的证明就十分简单了。
楼层: 地基 | 2009-02-09 23:32 | prob. 说：
沙发的问题解决了。
不妨设c=1-a，d=1-b。
假设按照第一种规则打的时候把2*n-1局打满，那么每一个最终小结果概率的形式都会是一串a和c（共n个）的连乘积乘以一串b和d（共n-1个）的连乘积，而且A胜当且仅当a和b的个数加起来>=n。
////////////////////////////////
看到这里十分不解，假设按第一种规则打满2n-1小分能证两者相同，
但按第一种规则未必是2n-1小分阿，也可能11：1结束
那么就算B再赢9局也是输……
是的
11：1是因为一方够分了，就没必要往下打
其实如果双方愿意可以打满21局
不影响结果的
想了另外一种脑残的方法
先在一不透光试管中加入未知量的水
A女士量取她年龄那么多毫升的1mol/L的HCl 加入试管
B女士量取她年龄那么多毫升的1mol/L的NaOH 加入试管
然后用Ph试纸就可判断谁的年龄大了
后面对p取模的过程，好像是多余的。
这个问题就是有名的姚氏百万富翁问题，有针对该问题的的解决方法。推广以后，可以抽象为两方计算问题。
10L的是化学大牛？
10L亮了。。。