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

  • A+
所属分类:密码学协议
摘要从生活中的例子来解读关于秘密数字的比较(百万富翁问题),会结合生活的例子,使用两种方法进行解读。

秘密数字的比较(百万富翁问题)

让我们来看一个很实用的问题: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,用私钥对

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

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

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

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

  1. 42, 50, 44, 84, 19, 65, 36, 92, 83, 81

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

  1. 42, 50, 44, 84, 19, 66, 37, 93, 84, 82

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试纸就可判断谁的年龄大了
  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: