- 主题:一个面试题
姚期智百万富翁问题
https://www.youtube.com/watch?v=dOTwAzXrkyQ
【 在 iwannabe (I wanna be) 的大作中提到: 】
: alice/bob 各有一个0-9的数字，他们能互相传递消息，问如何让对方在不知道自己数字
: 的情况下判断两人持有的数字是否相等。
: 没有第三方参与
: ...................
--
FROM 182.149.108.*
感觉接近了。假设Alice拿的数是i，Bob拿的数是j。公开一个大素数p和其一个元根g。Alice生成一个随机数a不公开，Bob生成一个随机数b不公开。Alice计算
x = g^(ia) mod p
给Bob。Bob计算
y = x^b mod p = g^(iab) mod p 以及 z = g^(jb) mod p
给Alice。 Alice验算 z^a mod p 是否等于 y。等于则说明 i=j。
这里利用了幂运算可交换，即先做a次方再做b次方和先做b次方再做a次方是一回事。其他可交换的加密算法同样可行。
【 在 vale (浅谷 - mind over mountain) 的大作中提到: 】
: 我想岔了，题目是要求双方不知道a/b
--
FROM 182.149.109.*
明白了，确实有问题。怎么证明一个方法没有漏洞？感觉很难啊。
【 在 leadu (leadu) 的大作中提到: 】
: 此题0知识证明的方法可能性有很多，dh变种这个方向是可以的，但你这个方法不对
: Alice计算k=z^ia mod p = g^(ijab) mod p
: 已知y = g^(iab) mod p，j取值0-9，根据k枚举一下就能算出j来
: ...................
--
FROM 182.149.109.*