密码学协议举例(四):秘密数字的比较

    让我们来看一个很实用的问题: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作比较了。

21 条评论

  • 小精灵

    8错。。。。先顶再看

    老大就看一看我的问题嘛~~~~~~~~~~~~~~~

  • prob.

    抢个高层……

  • prob.

    用+1吗?只要改成一个和原来不相同的数就行了

  • zfaustk

    呃..好麻烦..

  • prob.

    沙发的问题解决了。

    不妨设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结束

  • prob.

    那么就算B再赢9局也是输……

  • 滚动数组

    是的
    11:1是因为一方够分了,就没必要往下打
    其实如果双方愿意可以打满21局
    不影响结果的

  • looby

    想了另外一种脑残的方法

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

  • cuckoo

    后面对p取模的过程,好像是多余的。

  • shanren

    这个问题就是有名的姚氏百万富翁问题,有针对该问题的的解决方法。推广以后,可以抽象为两方计算问题。

  • Richardyi

    10L的是化学大牛?

  • yh

    mod p那步可以换成hash吧

  • 三江小渡

    还是十楼方法好,楼主的方法貌似有问题,如果俩个人都是22岁,这样得到的结果却是B大;如果B21岁,那么22岁的A就这个环境下,A是能够知道B是21岁的,如果A得知自己比B大的话。

  • minglingmaster

    双方各制作密度为(年龄/10)g/cm3,体积为10cm3金属球一个,然后再称

  • minglingmaster

    还有10楼的方法,量取之后可以用水稀释至相同体积(比如40mL)这样就不怕泄露了

  • cervelo

    10楼的方法好像也不错。至少可以证实一点

发表评论