百万富翁问题

2021-05-25 鲁鲁槟 收藏

一、提出问题

  • 有两个百万富翁,他们想比较财富,但是又不想公开财富,有没有办法?

二、生活的方式解决

  • 富翁 A 有 i 亿元,富翁 B 有 j 亿元,0 < i,j <= 10
  • 有 10 个排放成一列的带锁的箱子,A 有钥匙,B 没有钥匙
  • A 找出第 i 个箱子,在 i 之前的箱子放上写有数字 0 的纸条,在 i 和之后的箱子放上写有数字 1 的纸条,然后锁上
  • B 找出第 j 个箱子拿给 A,并把其他箱子销毁
  • A 用钥匙打开 B 拿给自己的箱子,若箱子里面是写有数字 0 的纸条,那么 j > i;若箱子里面是写有数字 1 的纸条,那么 j >= i

三、数学的方式解决

  • 数学中,锁称为公钥,钥匙称为私钥
  • 富翁 B 有公钥,没有私钥
  • B 选出一个大数 x,用公钥进行加密 E(x) = k(解密 D(k)=x)
  • B 计算 k-j+1 = m,把 m 发给 A
  • 富翁 A 有公钥,有私钥
  • A 计算 k-j+1,k-j+2 ...... k-j+j ...... k-j+10,其中 k-j+j=k
  • A 对上面的数进行解密 yu = D(k-j+u):y1 , y2 ...... yj ...... y10,其中 yj = D(k) = x
  • A 对 yu 求模 zu = yu mod P,P 是一个质数:z1 , z2 ...... zj ...... z10,由于 yj=x,则 zj = x mod P
  • A 对 zi 和之前的不变,对 zi 之后的数加 1,传递给 B
  • B 拿到一串数字后,关注 zj,若 x mod P = zj,那么 j <= i,若 x mod P ≠ zj,那么 j > i
阅读 328