密码学协议举例[4]–秘密数字的比较（百万富翁问题）|文艺数学君

秘密数字的比较（百万富翁问题）

让我们来看一个很实用的问题：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加密，得到密文1117^17mod3233=1652。A把1652减a的值发给B。如果A是一个22岁的漂亮MM，那么B实际接收到的数就是1630。

接下来，B尝试用私人密钥来恢复x。由于B不知道a是多少，于是B枚举所有21到30之间的整数，即使用1630+i，其中i属于21-30，用私钥对

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

当然，解出来的10个数里面，只有一个恰好等于x（A选取的大随机数），其余的数其实都没啥意义。不过，B也不知道哪个数等于x。接下来B选取一个素数p，这个素数p应该比x小几个数量级（B不知道x是什么，但A可以透露出x大致的数量级）。假设B选的素数等于97，B把解密得到的10个数全部模p，得到

假设B的年龄是25岁，那么B把后面5项全部加一，然后把下面这10个数和素数p=97传给A：

A只需要（也只能够）算一算1117（这个是A选取的大随机数）模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作比较了。

但是上面的方法有一个问题，即两个人年龄相同的时候无法比较；

一种有意思的想法

1. 先在一不透光试管中加入未知量的水
2. A女士量取她年龄那么多毫升的1mol/L的HCl 加入试管
3. B女士量取她年龄那么多毫升的1mol/L的NaOH 加入试管
4. 用Ph试纸就可判断谁的年龄大了