一、提出问题

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

二、生活的方式解决

• 富翁 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 <= x="" mod="" p="" j=""> i