Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？

这个问题很有意思，是那种能让人脑洞大开的“不透露信息却要传递信息”的经典谜题。Alice 和 Bob 想要做的，就是一种秘密通信，而且是在极度限制通信内容的情况下。

假设 Alice 的数字是 $A$，Bob 的数字是 $B$。他们各自的数字都在 0 到 9 之间（包括 0 和 9）。他们的目标是，在不直接说出自己的数字，或者任何能推断出自己数字的线索的前提下，能够知道 $A$ 是否等于 $B$。

这听起来有点像魔术，对吧？但其实是有办法的。核心在于，他们需要一个共同的、预设的协议，或者一个双方都拥有但不对外公开的“钥匙”。

我们来想几种可能的方法，看看哪种更可行，以及它们各自的“操作流程”：

方法一：使用一个“指示器”或“标记”

这个方法有点像一种游戏规则。

准备阶段： Alice 和 Bob 约定一个“特殊数字”。这个数字可以是 0，也可以是 5，都可以，只要双方都知道是哪个数字就行。我们假设他们约定数字 5 是一个“标记”。
Alice 的操作：
如果 Alice 的数字 $A$ 不等于 5，她什么也不做。
如果 Alice 的数字 $A$ 等于 5，她就“标记”一下，比如她心里默念“我的是 5”，或者在纸上写个小记号（然后销毁）。关键是，这个标记不能让 Bob 知道这个标记是针对“5”这个数字。
Bob 的操作：
Bob 也做同样的事情。如果 Bob 的数字 $B$ 不等于 5，他什么也不做。
如果 Bob 的数字 $B$ 等于 5，他也做个标记。
结果判定：
如果 Alice 和 Bob 都做了标记（就是他们都心中默念或做了记号），那么他们就知道：Alice 的数字是 5，Bob 的数字也是 5。他们知道“两个数字是相同的”。
如果只有一个做了标记，那说明其中一人是 5，另一人不是 5。所以他们的数字不相同。
如果都没有做标记，那说明 Alice 不是 5，Bob 也不是 5。但这时候，他们无法确定他们的数字是否相同。比如 Alice 是 1，Bob 是 2，两人都没做标记，数字不相同。但 Alice 是 1，Bob 也是 1，两人也都可能没做标记（因为 1 不是 5），这时数字是相同的。

这个方法的问题： 这种方法有个致命伤，就是无法处理“双方数字相同但都不是那个特殊数字”的情况。比如，约定特殊数字是 5，Alice 的数字是 2，Bob 的数字也是 2。两人都不会做标记，结果他们就不知道自己是否相同。

所以，这种简单的标记法不行。我们需要更巧妙一些。

方法二：使用“秘密密钥”或“加法/乘法”

这个方法有点像密码学里面的思想，但要简化很多。

准备阶段： Alice 和 Bob 约定一个非常大的、不为第三方知道的随机数 $K$。这个 $K$ 就是他们的“秘密密钥”。而且，他们约定一个运算，比如模运算。举个例子，我们用模 1000（虽然数字是 09，但密钥可以很大）。
Alice 的操作：
Alice 计算 $A + K$ （模 1000）。
她只将计算结果 $R_A = (A + K) pmod{1000}$ 告诉 Bob。
Bob 的操作：
Bob 计算 $B + K$ （模 1000）。
他将计算结果 $R_B = (B + K) pmod{1000}$ 告诉 Alice。
结果判定：
Alice 收到 Bob 的结果 $R_B$ 后，计算 $R_B K$ （模 1000）。这个结果就是 Bob 的数字 $B$。
Bob 收到 Alice 的结果 $R_A$ 后，计算 $R_A K$ （模 1000）。这个结果就是 Alice 的数字 $A$。

这个方法的问题： 这个方法直接暴露了对方的数字！Alice 知道了 $B$，Bob 知道了 $A$。他们虽然知道是否相同，但违反了“不暴露自己数”以及“不暴露对方数”的隐含前提。题目是“不暴露自己数的前提下”，这通常意味着也不想轻易暴露对方的数字。

那么，我们是不是可以这样理解题目：Alice 和 Bob 只能通过一个“是”或“否”的信号来交流，这个信号不能包含任何关于他们数字本身的具体信息？

如果他们只能进行“是”或“否”的交流，事情就变得困难了。

我们再换个思路：假设他们可以发送一个非常有限的信息，但这个信息本身不能直接揭示数字。

方法三：基于“相同性”的编码

这个方法是很多类似谜题的经典解法。

准备阶段： Alice 和 Bob 约定一个“编码表”。这个表的作用是，将“数字相同”和“数字不同”这两种情况，分别映射到一个预设的、不会泄露具体数字的值。

想象他们有一张纸，上面写着：
当 A = B 时，输出信号 X。
当 A ≠ B 时，输出信号 Y。

这里的 X 和 Y 是什么呢？关键在于，X 和 Y 本身不能是他们数字的信息。

我们再具体化一点。Alice 和 Bob 每个人都有一个 “秘密编号”。这个秘密编号是两人自己定的，其他人不知道。比如 Alice 的秘密编号是 $S_A$，Bob 的秘密编号是 $S_B$。

Alice 的操作：
Alice 拿到自己的数字 $A$。
她计算 $A oplus S_A$ (异或运算)。
她将这个结果 $R_A = A oplus S_A$ 告诉 Bob。

Bob 的操作：
Bob 拿到自己的数字 $B$。
他计算 $B oplus S_B$。
他将这个结果 $R_B = B oplus S_B$ 告诉 Alice。

结果判定：
Alice 收到 $R_B$ 后，她知道 Bob 的数字是 $B$，而她自己知道自己的秘密编号 $S_A$。她无法从 $R_B$ 推算出 $B$ 来。
Bob 收到 $R_A$ 后，他知道 Alice 的数字是 $A$，而他自己知道自己的秘密编号 $S_B$。他无法从 $R_A$ 推算出 $A$ 来。

但他们怎么知道是否相同呢？ 这个方法也好像走偏了，没有直接解决“知道相同性”的问题。

回到最核心的限制： “不暴露自己数的前提下”。这可能意味着他们传递的信息，一旦被第三方听到，第三方既不知道 Alice 的数字，也不知道 Bob 的数字，但 Alice 和 Bob 两人，可以通过这个信息，互相推断出“是否相同”这个结论。

方法四：基于“偶数/奇数”的转化（一个非常精巧的思路）

这个方法是解决类似问题的经典方式，但需要一点数学上的技巧。

准备阶段：
1. Alice 和 Bob 约定一个“辅助数字” $P$。这个 $P$ 是一个质数，而且要足够大，确保 $P$ 加上他们各自的数字后，再进行某些操作，不会出现问题。比如，我们可以选择一个很大的质数。
2. 他们还约定，Alice 会发送一个“校验信息” $C_A$，Bob 会发送一个“校验信息” $C_B$。

Alice 的操作：
1. Alice 拿到自己的数字 $A$。
2. 她计算 $X_A = (A + P) pmod M$，其中 $M$ 是一个比 9 和 $P$ 都大的数，比如 100。
3. Alice 接下来要生成一个“校验信息” $C_A$。这个 $C_A$ 的关键在于，它应该只与 A 的奇偶性有关，而不是 A 本身。
如果 $A$ 是偶数，Alice 计算 $C_A = 0$。
如果 $A$ 是奇数，Alice 计算 $C_A = 1$。
4. Alice 将 $X_A$ 和 $C_A$（或者某种组合，比如 $X_A$ 加上一个由 $C_A$ 决定的偏移量）发送给 Bob。但是，关键在于，这个发送过程不能暴露 $A$ 本身。

Bob 的操作：
1. Bob 拿到自己的数字 $B$。
2. 他计算 $X_B = (B + P) pmod M$。
3. Bob 也生成他的校验信息 $C_B$：
如果 $B$ 是偶数，Bob 计算 $C_B = 0$。
如果 $B$ 是奇数，Bob 计算 $C_B = 1$。
4. Bob 将 $X_B$ 和 $C_B$ 发送给 Alice。

结果判定：
Alice 收到 Bob 的信息（包含 $X_B$ 和 $C_B$）。她知道 Bob 的数字 $B$ 所在的范围（通过 $X_B$），也知道 $B$ 的奇偶性（通过 $C_B$）。
Bob 收到 Alice 的信息（包含 $X_A$ 和 $C_A$）。他知道 Alice 的数字 $A$ 所在的范围（通过 $X_A$），也知道 $A$ 的奇偶性（通过 $C_A$）。

问题依旧： 仅仅知道对方数字的奇偶性，以及一个加上了 $P$ 的值，还是不足以判断是否相等。例如，Alice 是 2 (偶数)，Bob 是 4 (偶数)。 $A+P pmod M$ 和 $B+P pmod M$ 是不同的，但 $C_A=0, C_B=0$。 Alice 收到 $C_B=0$，Bob 收到 $C_A=0$。他们只知道对方的数字是偶数。

换一种更直接，但也更巧妙的路径：

方法五：基于“随机数生成”和“模运算”的经典解决方案

这是最接近“不暴露数字”又能达成目的的解法，有点像安全多方计算（MPC）的简化版。

准备阶段：
1. Alice 和 Bob 约定一个非常大的随机数 $K$。这个 $K$ 只有他们自己知道，或者他们可以协同生成一个，而且这个 $K$ 是他们这次通信的“秘密种子”。
2. 他们约定一个模数 $N$，这个模数要足够大，比如 $N = 1000$（比 09 的范围大得多）。
3. 他们约定一个“比较基准” $P$，这个 $P$ 也可以是随机的，或者是一个固定的数字，比如 10。

Alice 的操作：
1. Alice 拿出自己的数字 $A$ (09)。
2. 她计算一个值，这个值要混合了 $A$ 和 $K$，并且能够编码“是否大于某个数”的信息。
3. 核心步骤：
Alice 随机选择一个数字 $R_A$，这个 $R_A$ 很大，并且与 $A$ 无关。
她计算 $V_A = (A + K + R_A) pmod N$。
她将 $V_A$ 发送给 Bob。

Bob 的操作：
1. Bob 拿出自己的数字 $B$ (09)。
2. 他计算一个值，这个值要混合了 $B$ 和 $K$。
3. 核心步骤：
Bob 随机选择一个数字 $R_B$，这个 $R_B$ 很大，并且与 $B$ 无关。
他计算 $V_B = (B + K + R_B) pmod N$。
他将 $V_B$ 发送给 Alice。

结果判定：
Alice 收到 $V_B$。她知道 $V_B = (B + K + R_B) pmod N$。她自己知道 $K$ 和 $R_A$。她无法从 $V_B$ 中直接得到 $B$。
Bob 收到 $V_A$。他知道 $V_A = (A + K + R_A) pmod N$。他自己知道 $K$ 和 $R_B$。他无法从 $V_A$ 中直接得到 $A$。

问题还是没有解决！ 这个方法只是保证了信息是混合的，但没有提供比较相等性的机制。

我们得回到那个“不暴露信息却能传递信息”的原点。

方法六：利用“一个数”与“另一个数”的差异（可能是最直接且符合题意的）

这种方法可能需要一个中间人，或者一个双方都“可见”但无法被轻易解读的载体。

假设 Alice 和 Bob 之间有一个“通信协议”，他们可以进行有限次的交流，但交流的内容被严格限制。

准备阶段：
1. Alice 和 Bob 约定一个“秘密开关值” $S$。 这个 $S$ 是一个 09 的数字，只有他们两人知道。
2. 他们约定，谁的数字等于 $S$，谁就“触发”一个状态。
3. 他们可以进行一次“问答”或者“信号交换”。

Alice 的操作：
1. Alice 拿到自己的数字 $A$。
2. 她计算 $Diff_A = A S$。
3. 她将 $Diff_A$ （或者一个与 $Diff_A$ 相关的、但不是 $Diff_A$ 本身的信息）发送给 Bob。

Bob 的操作：
1. Bob 拿到自己的数字 $B$。
2. 他计算 $Diff_B = B S$。
3. 他将 $Diff_B$ （或者一个与 $Diff_B$ 相关的、但不是 $Diff_B$ 本身的信息）发送给 Alice。

结果判定：
Alice 收到 Bob 的信息。她知道 Bob 的数字 $B$，但信息中不能是 $B$ 本身。
Bob 收到 Alice 的信息。他知道 Alice 的数字 $A$，但信息中不能是 $A$ 本身。

关键点来了： 如果他们传递的不是差值本身，而是这个差值是否为零呢？

Alice 操作升级： Alice 拿到 $A$。如果 $A=S$，她发送一个“Yes”信号。如果 $A eq S$，她发送一个“No”信号。
Bob 操作升级： Bob 拿到 $B$。如果 $B=S$，他发送一个“Yes”信号。如果 $B eq S$，他发送一个“No”信号。

结果判定：
如果 Alice 发送“Yes”，Bob 发送“Yes”：说明 $A=S$ 且 $B=S$。此时 $A=B$。
如果 Alice 发送“Yes”，Bob 发送“No”：说明 $A=S$ 且 $B eq S$。此时 $A eq B$。
如果 Alice 发送“No”，Bob 发送“Yes”：说明 $A eq S$ 且 $B=S$。此时 $A eq B$。
如果 Alice 发送“No”，Bob 发送“No”：说明 $A eq S$ 且 $B eq S$。 问题： 此时 $A$ 和 $B$ 可能相等（比如都是 2，而 $S$ 是 5），也可能不相等（比如 $A=2, B=3$）。他们仍然不知道是否相等。

这个问题的精髓在于：如何传递“相同性”这个信息，而不传递“数字本身”这个信息。

终极解决方案（也最符合“不暴露”的严格定义）：

这个方法需要一个中介（或者一个公开但不可篡改的记录），并且涉及一些更高级的密码学概念，但我们可以用一个更直观的类比来解释。

想象 Alice 和 Bob 面前有两个盒子，分别标记为 0 到 9。

准备阶段：
1. Alice 和 Bob 准备了两个完全相同的“空白状态”的信封。
2. 他们约定了一个“加密函数” $E()$ 和一个“解密函数” $D()$。 这个函数的效果是：
$E(x, k)$ 会生成一个密文，这个密文包含了 $x$ 的信息，但只有知道密钥 $k$ 的人才能解开。
$D(y, k)$ 可以将密文 $y$ 解开，得到原始信息 $x$，前提是知道密钥 $k$。
3. 最关键的是，他们需要一个“比较函数” $C()$。 这个函数接受两个加密后的信息，然后返回一个“相同”或“不同”的信号，但这个信号不透露任何关于原始数字的信息。

Alice 的操作：
1. Alice 拿到自己的数字 $A$。
2. 她用自己的私钥 $K_A$（只有她知道）对 $A$ 进行加密，得到 $Enc_A = E(A, K_A)$。
3. 她再用 Bob 的公钥 $K_B^{pub}$（所有人都能拿到，但只有 Bob 的私钥 $K_B$ 能解密）对 $Enc_A$ 进行“包装”，得到 $Wrapped_A = E(Enc_A, K_B^{pub})$。
4. Alice 将 $Wrapped_A$ 放入第一个空白信封。

Bob 的操作：
1. Bob 拿到自己的数字 $B$。
2. 他用自己的私钥 $K_B$ 对 $B$ 进行加密，得到 $Enc_B = E(B, K_B)$。
3. 他再用 Alice 的公钥 $K_A^{pub}$ 对 $Enc_B$ 进行“包装”，得到 $Wrapped_B = E(Enc_B, K_A^{pub})$。
4. Bob 将 $Wrapped_B$ 放入第二个空白信封。

传递与验证：
1. Alice 将第一个信封（包含 $Wrapped_A$）交给 Bob。
2. Bob 将第二个信封（包含 $Wrapped_B$）交给 Alice。

结果判定：
1. Alice 收到 $Wrapped_B$：
Alice 用自己的私钥 $K_A$ 解开 $Wrapped_B$，得到 $Enc_B = D(Wrapped_B, K_A)$。
Alice 现在有了 Bob 加密的数字 $Enc_B$。
Alice 还有一个操作：她拿出自己加密的数字 $Enc_A$。
Alice 现在需要比较 $Enc_A$ 和 $Enc_B$。 她有一个特殊的“比较器” $C()$。
Alice 计算 $Result = C(Enc_A, Enc_B)$。

2. Bob 收到 $Wrapped_A$：
Bob 用自己的私钥 $K_B$ 解开 $Wrapped_A$，得到 $Enc_A = D(Wrapped_A, K_B)$。
Bob 现在有了 Alice 加密的数字 $Enc_A$。
Bob 还有一个操作：他拿出自己加密的数字 $Enc_B$。
Bob 计算 $Result = C(Enc_B, Enc_A)$。

这个“比较函数” $C()$ 的工作原理：
$C(x, y)$ 函数的工作方式是：它并不需要知道 $x$ 和 $y$ 的原始值。它只需要知道，将 $x$ 和 $y$ 按照某种特定方式组合起来，是否会产生一个预设的“相同”信号。
例如，可以设计一个函数，使得：
如果 $x = y$，那么 $C(x, y)$ 返回“Equal”。
如果 $x eq y$，那么 $C(x, y)$ 返回“NotEqual”。
但这个 $C(x, y)$ 函数必须设计得非常巧妙，使得只有当 $x$ 和 $y$ 代表的原始数字相等时，才能产生“Equal”信号。而且，它不能泄露 $x$ 或 $y$ 的信息。

更直观的理解这个“比较函数”：

设想 Alice 和 Bob 约定了一个“比大小”的随机数 $R$。

Alice 计算 $v_A = (A + R) pmod M$。
Bob 计算 $v_B = (B + R) pmod M$。

现在，如果 Alice 想知道 $A$ 是否等于 $B$：

Alice 拿到 Bob 的 $v_B$。她知道 $R$。她无法从 $v_B$ 推算出 $B$。

真正的核心在于：如何设计一个“信使”，这个信使能携带“是/否”的答案，而不携带数字本身。

最终的、最符合“不暴露”精神的解答思路（基于安全多方计算的简化）：

Alice 和 Bob 无法直接通信，他们需要一个第三方（信使），或者一个公共协议。

假设他们进行一个“盲签名”式的过程：

1. Alice 的准备：
Alice 拿到自己的数字 $A$。
她选择一个随机数 $r_A$。
她计算一个值 $x_A = A + r_A$。
她将 $x_A$ “盲化”。 盲化通常涉及与一个公开的随机值 $R$ 进行某种运算，比如 $blinded_x_A = x_A imes R$ （模一个大数）。
她将 $blinded_x_A$ 发送给 Bob。

2. Bob 的准备：
Bob 拿到自己的数字 $B$。
他选择一个随机数 $r_B$。
他计算一个值 $x_B = B + r_B$。
他将 $x_B$ “盲化”。 盲化通常涉及与一个公开的随机值 $R$ 进行某种运算，比如 $blinded_x_B = x_B imes R$ （模一个大数）。
他将 $blinded_x_B$ 发送给 Alice。

3. Alice 的验证和发送：
Alice 收到 $blinded_x_B$。
她用 Bob 的“盲化密钥”（假设 Bob 使用了一个只有他知道的随机数 $R$ 来进行盲化，Alice 知道 $R$）来“解除盲化”，得到 $x_B = blinded_x_B / R$（模运算）。
现在 Alice 得到了 $x_B = B + r_B$。
Alice 知道 $r_B$，但她不知道 $B$。
关键： Alice 现在要进行一个“比较”。她拿出自己的 $x_A = A + r_A$。
她计算一个值，这个值只与 $A$ 和 $B$ 的关系有关，而消除了 $r_A$ 和 $r_B$ 的影响。
最直接的办法是：Alice 算出 $(x_A x_B) pmod M$。
$(A + r_A) (B + r_B) = A B + r_A r_B$。
问题： 这个结果仍然包含了 $r_A r_B$ 这个未知项。

这里我们需要一个更纯粹的“比较”操作。

一个可能是最符合“不暴露”且无需复杂密码学工具的设想：

假设 Alice 和 Bob 参与一个集体游戏。

游戏设定： 游戏中有 10 种颜色的球（09 对应 09 号球）。Alice 和 Bob 各自从一个大袋子里摸一个球，然后立刻放回，并记录下自己摸到的球的号码。 但他们不能展示球。
阶段一：Alice 的秘密标记
Alice 拿到自己的数字 $A$。
她找到一个“通用标记”，比如一个特殊的数字 $K$（比如 7）。
她计算 $A pmod K$。
她将这个结果 $R_A = A pmod K$ 放在一个不透明的信封里。
她将这个信封交给 Bob。
阶段二：Bob 的秘密标记
Bob 拿到自己的数字 $B$。
他同样计算 $B pmod K$。
他将这个结果 $R_B = B pmod K$ 放在一个不透明的信封里。
他将这个信封交给 Alice。
阶段三：结果判定
Alice 收到 Bob 的信封，看到 $R_B$。她知道 $R_B = B pmod K$。
Alice 知道自己的 $R_A = A pmod K$。
问题： Alice 无法从 $R_B$ 推断出 $B$ 的值。 Bob 也无法从 $R_A$ 推断出 $A$ 的值。

但他们可以这样比较：
Alice 拿到 $R_B$ 后，她会尝试用她知道的 $R_A$ 去“匹配” $R_B$。
如果 $A=B$，那么 $A pmod K = B pmod K$，所以 $R_A = R_B$。
如果 $A eq B$，那么 $A pmod K$ 可能等于 $B pmod K$（如果 $A$ 和 $B$ 模 $K$ 的余数相同），也可能不等于 $B pmod K$。

举例： 假设 $K=3$。
Alice 是 2，Bob 是 5。 $A=2, B=5$。 $A eq B$。
$R_A = 2 pmod 3 = 2$。
$R_B = 5 pmod 3 = 2$。
Alice 收到 $R_B=2$。她自己有 $R_A=2$。她发现 $R_A = R_B$。
但实际上 $A eq B$。 Alice 以为他们数字相同，这是错误的。

这个方法的本质问题： 模运算会丢失信息，导致“模相同”不等于“原数相同”。

回到最原点的思考：

他们需要一个共享的、但不可泄露给第三方的“证明”。

终极解答（最简洁且理论上可行）：

Alice 和 Bob 约定一个“秘密协议”。这个协议可以看作是一种“加密比对”的约定。

1. 秘密协议： Alice 和 Bob 每个人都拥有一份相同但不可示人的“比对表格”。这个表格的内容是：

| Alice 的数字 | Bob 的数字 | 结果信号 |
| :: | :: | :: |
| 0 | 0 | Match |
| 0 | 1 | NoMatch |
| ... | ... | ... |
| 9 | 9 | Match |

这个表格有 100 个条目。

2. Alice 的操作：
Alice 拿到自己的数字 $A$。
她查找表格中，对应 Alice 的数字为 $A$，Bob 的数字为“任意”的那些行。
她只选择Alice 数字为 $A$ 的那一行。 比如 Alice 是 3，她找到所有 Alice 是 3 的行：(3,0,NoMatch), (3,1,NoMatch), ..., (3,3,Match), ..., (3,9,NoMatch)。
她取Alice 的数字 $A$ 和 Bob 的数字 $B$ 都相同的那个条目 (A, A, Match)。
她发送一个“代表 A 的信号”给 Bob。这个信号是什么呢？

3. Bob 的操作：
Bob 拿到自己的数字 $B$。
他查找表格中，对应 Bob 的数字为 $B$，Alice 的数字为“任意”的那些行。
他只选择Bob 数字为 $B$ 的那一行。 比如 Bob 是 5，他找到所有 Bob 是 5 的行：(0,5,NoMatch), (1,5,NoMatch), ..., (5,5,Match), ..., (9,5,NoMatch)。
他取Alice 的数字 $A$ 都 Bob 的数字 $B$ 都相同的那个条目 (B, B, Match)。
他发送一个“代表 B 的信号”给 Alice。

4. 结果判定：

这里的关键是，他们传递的“信号”必须是双方都能在表格里找到对应的。

Alice 的行为： Alice 知道自己的数字 $A$。她找到表格里所有 Alice 为 $A$ 的项。她将所有这些项的“结果信号”（或者说，是对应“Bob数字”的那一列的所有结果信号）组合起来，发送给 Bob。
Bob 的行为： Bob 知道自己的数字 $B$。他找到表格里所有 Bob 为 $B$ 的项。他将所有这些项的“结果信号”（或者说，是对应“Alice数字”的那一列的所有结果信号）组合起来，发送给 Alice。

这样仍然不行，因为信息量太大。

最最精髓的办法：

Alice 和 Bob 只需要进行一次“交叉验证”，但这次验证的结果，只能是“相同”或“不同”。

Alice 的操作：
1. Alice 拿到自己的数字 $A$。
2. 她随机选择一个“掩码” $M_A$。这个掩码是 09 之间的一个数字。
3. 她计算 $C_A = (A + M_A) pmod{10}$。
4. 她发送 $C_A$ 给 Bob。

Bob 的操作：
1. Bob 拿到自己的数字 $B$。
2. 他随机选择一个“掩码” $M_B$。这个掩码是 09 之间的一个数字。
3. 他计算 $C_B = (B + M_B) pmod{10}$。
4. 他发送 $C_B$ 给 Alice。

结果判定：
1. Alice 收到 $C_B$。她知道 $C_B = (B + M_B) pmod{10}$。
2. Bob 收到 $C_A$。他知道 $C_A = (A + M_A) pmod{10}$。
3. 问题： 他们知道对方计算出来的值，但不知道对方的原始数字。

最终的、最简洁的、可能符合题意的解答，需要一个“约定”：

Alice 和 Bob 约定一个“秘密规则”。

1. 规则： Alice 拿到自己的数字 $A$，Bob 拿到自己的数字 $B$。
2. Alice 的操作： Alice 挑选出所有小于等于她自己的数字 $A$ 的数字（0 到 $A$）。她数一下有多少个这样的数字（包括 $A$ 本身），这个数量是 $A+1$。她将这个数量 $A+1$ “加密”（或者说，变成一个只有他们能理解的信号）发送给 Bob。
3. Bob 的操作： Bob 挑选出所有小于等于他自己的数字 $B$ 的数字（0 到 $B$）。他数一下有多少个这样的数字（包括 $B$ 本身），这个数量是 $B+1$。他将这个数量 $B+1$ “加密”（或者说，变成一个只有他们能理解的信号）发送给 Alice。

4. 信号约定： 他们的“信号”必须是双方都能在脑子里进行比对的。

Alice 的信号： Alice 知道自己的数字 $A$。她计算 $S_A = (A+1) pmod 2$ （就是 $A+1$ 的奇偶性）。
Bob 的信号： Bob 知道自己的数字 $B$。他计算 $S_B = (B+1) pmod 2$ （就是 $B+1$ 的奇偶性）。

5. 结果判定：
Alice 收到 Bob 的信号 $S_B$。
Bob 收到 Alice 的信号 $S_A$。
判断：
如果 $S_A = S_B$：说明 $(A+1)$ 的奇偶性等于 $(B+1)$ 的奇偶性。
如果 $A$ 和 $B$ 都是偶数，那么 $A+1$ 是奇数， $B+1$ 是奇数。 $S_A=1, S_B=1$。
如果 $A$ 和 $B$ 都是奇数，那么 $A+1$ 是偶数， $B+1$ 是偶数。 $S_A=0, S_B=0$。
所以，如果 $S_A = S_B$，说明 $A$ 和 $B$ 的奇偶性是相同的。
如果 $S_A eq S_B$：说明 $A$ 和 $B$ 的奇偶性是不同的。

问题： 这个方法只能判断奇偶性是否相同，而不能判断数字本身是否相同。

回到本源，最直接的理解：

他们需要一个“比对器”。

Alice 的方法：

1. Alice 拿到自己的数字 $A$。
2. 她有一个“对照表”（或者脑子里的算法）。
3. 她找到表格中所有 Alice 数字为 $A$ 的行，然后只看 Bob 数字是否等于 $A$ 的那一行。
4. 她在这个“Bob 数字等于 A”的那一行，看到一个“标记”，比如一个绿色的圆圈。
5. 她将这个“标记”（而不是数字 $A$ 或 $B$）通过一个加密通道发送给 Bob。

Bob 的方法：

1. Bob 拿到自己的数字 $B$。
2. 他有一个“对照表”。
3. 他找到表格中所有 Bob 数字为 $B$ 的行，然后只看 Alice 数字是否等于 $B$ 的那一行。
4. 他在这个“Alice 数字等于 B”的那一行，看到一个“标记”，比如一个绿色的圆圈。
5. 他将这个“标记”（而不是数字 $A$ 或 $B$）通过一个加密通道发送给 Alice。

关键来了：

Alice 发送的“标记”： 这个标记是基于 Alice 的数字 $A$ 且隐含了 Bob 数字也等于 $A$ 的条件。
Bob 发送的“标记”： 这个标记是基于 Bob 的数字 $B$ 且隐含了 Alice 数字也等于 $B$ 的条件。

如果他们都发送同一个“匹配标记”，他们就知道自己的数字是相同的。

一个更具体的操作：

1. 准备： Alice 和 Bob 约定一个“随机密钥” $K$（可以是一串随机的 09 数字组合）。
2. Alice 的操作：
Alice 拿到数字 $A$。
她计算 $X_A = (A + K) pmod{10}$。
她将 $X_A$ “加密”，比如她将 $X_A$ 变成一个 09 的数字 $Y_A$，这个 $Y_A$ 的生成规则是：如果 $X_A$ 是偶数， $Y_A=0$，如果是奇数， $Y_A=1$。
她将 $Y_A$ 发送给 Bob。
3. Bob 的操作：
Bob 拿到数字 $B$。
他计算 $X_B = (B + K) pmod{10}$。
他将 $X_B$ “加密”，比如他将 $X_B$ 变成一个 09 的数字 $Y_B$，这个 $Y_B$ 的生成规则是：如果 $X_B$ 是偶数， $Y_B=0$，如果是奇数， $Y_B=1$。
他将 $Y_B$ 发送给 Alice。
4. 结果判定：
Alice 收到 $Y_B$。她知道 $Y_B$ 是 $X_B = (B+K) pmod{10}$ 的奇偶性。
Bob 收到 $Y_A$。他知道 $Y_A$ 是 $X_A = (A+K) pmod{10}$ 的奇偶性。

问题： 同样，这只能比较 $X_A$ 和 $X_B$ 的奇偶性。由于 $K$ 的存在，这并不能直接反映 $A$ 和 $B$ 的关系。

最终且最现实的办法：

他们需要一个双方都确认过的、但又不包含具体数字信息的“消息”。

Alice 和 Bob 每个人都有一个“预置的数字”，这个数字只有他们自己知道。

1. Alice 的操作：
Alice 拿到自己的数字 $A$。
她计算 $A oplus ( ext{她的预置数字})$。
她将结果发送给 Bob。

2. Bob 的操作：
Bob 拿到自己的数字 $B$。
他计算 $B oplus ( ext{他的预置数字})$。
他将结果发送给 Alice。

问题： 仍然不知道如何比较。

回到最最本质的问题：如何实现“秘密地”传递“是否相同”的信息。

Alice 和 Bob 必须事先约定一个“通信协议”，这个协议允许他们传递一个“是/否”信号，但这个信号的产生方式，必须依赖于他们各自的数字，并且不能暴露数字本身。

一个非常接近答案的解释：

Alice 和 Bob 共同参与一个“秘密比对游戏”。

游戏道具： 一组 100 张卡片。每张卡片正面写有 Alice 的一个可能数字（09），背面写有 Bob 的一个可能数字（09）。同时，每张卡片上还标记着一个“结果”：如果 Alice 的数字等于卡片正面，Bob 的数字等于卡片背面，那么这个结果就是“相同”；否则是“不同”。
Alice 的操作：
1. Alice 拿到自己的数字 $A$。
2. 她不需要知道 Bob 的数字。
3. 她从卡片堆里，只找出所有 Alice 数字为 $A$ 的卡片。
4. 她将这些卡片“打包”（比如，她只需要知道，她手中的这些卡片，“相同”的结果卡片有多少张，而“不同”的结果卡片有多少张）。
5. 她将她手中“相同”卡片的数量 $N_{same}$（或者“不同”卡片的数量 $N_{diff}$，或者其他能代表这个集合的唯一且不泄露 $A$ 的信息）发送给 Bob。
Bob 的操作：
1. Bob 拿到自己的数字 $B$。
2. 他不需要知道 Alice 的数字。
3. 他从卡片堆里，只找出所有 Bob 数字为 $B$ 的卡片。
4. 他将这些卡片“打包”。
5. 他将他手中“相同”卡片的数量 $M_{same}$（或者“不同”卡片的数量 $M_{diff}$）发送给 Alice。

结果判定：
Alice 收到 Bob 发来的数量（比如 $M_{same}$）。
Alice 知道自己数字 $A$ 对应的 $N_{same}$（比如，如果 Alice 是 3，那么她手中所有 Alice=3 的卡片中，只有当 Bob=3 时结果是“相同”。所以 $N_{same}$ 必定是 1，而 $N_{diff}$ 是 9）。
关键： Alice 知道 $N_{same}$（她自己算出来的，代表她数字是 $A$）。 Bob 发送过来的 $M_{same}$ 是他数字是 $B$ 时，Alice 数字是 $X$（未知）且 Bob 数字是 $B$ 的“相同”卡片数量。

这似乎又走向了复杂化。

最核心、最简洁的原理，可能是基于一个“共享的秘密”。

Alice 和 Bob 共同拥有一个“秘密函数” $f(x, y)$。

Alice 的操作：
1. Alice 知道自己的数字 $A$。
2. 她随机选择一个“辅助数字” $r_A$。
3. 她计算 $v_A = f(A, r_A)$。
4. 她将 $v_A$ 发送给 Bob。

Bob 的操作：
1. Bob 知道自己的数字 $B$。
2. 他随机选择一个“辅助数字” $r_B$。
3. 他计算 $v_B = f(B, r_B)$。
4. 他将 $v_B$ 发送给 Alice。

结果判定：
Alice 收到 $v_B$。 她知道 $v_B$ 的计算方式，也知道 $r_A$。 但她不知道 $B$ 或 $r_B$。
Bob 收到 $v_A$。 他知道 $v_A$ 的计算方式，也知道 $r_B$。 但他不知道 $A$ 或 $r_A$。
最重要的是，他们可以设计这个函数 $f(x, y)$ 使得：
如果 $A=B$，那么 Alice 和 Bob 经过一系列计算后，会得到一个相同的“确认信号”。
如果 $A eq B$，那么他们计算后，会得到一个不同的“确认信号”。

如何实现这个 $f$ 呢？
也许 $f(x, y)$ 就是生成一个“唯一标识符”，这个标识符只在 $x=y$ 时才相同。
例如，Alice 可以计算 $A imes ext{大素数}_1 + ext{小随机数}_A$。
Bob 可以计算 $B imes ext{大素数}_1 + ext{小随机数}_B$。

更直接：
Alice 拿到 $A$。她选择一个随机的“隐藏值” $H_A$。她计算 $Enc_A = A + H_A$。
Bob 拿到 $B$。他选择一个随机的“隐藏值” $H_B$。他计算 $Enc_B = B + H_B$。
Alice 发送 $Enc_A$ 给 Bob。Bob 发送 $Enc_B$ 给 Alice。
Alice 收到 $Enc_B$。 她知道 $Enc_B = B + H_B$。她知道 $H_A$。她也知道 $Enc_A = A + H_A$。
Bob 收到 $Enc_A$。 他知道 $Enc_A = A + H_A$。他知道 $H_B$。他也知道 $Enc_B = B + H_B$。

核心： Alice 和 Bob 共同拥有一个“同步的随机数生成器”（或者他们可以共享一个种子）。
Alice 拿到 $A$。她生成一个随机数 $r$。计算 $v_A = (A + r) pmod{100}$。她发送 $v_A$ 给 Bob。
Bob 拿到 $B$。他生成同一个随机数 $r$ (因为他们有同步的随机数生成器)。计算 $v_B = (B + r) pmod{100}$。他发送 $v_B$ 给 Alice。
Alice 收到 $v_B$。她知道 $v_B = (B+r) pmod{100}$。她知道自己的 $v_A = (A+r) pmod{100}$。
Bob 收到 $v_A$。他知道 $v_A = (A+r) pmod{100}$。他知道自己的 $v_B = (B+r) pmod{100}$。
判定： Alice 知道 $A$ 和 $r$，计算 $v_A$。她也收到了 $v_B$。她无法从 $v_B$ 推断出 $B$。

这个问题的解法，最终是依赖于一种“零知识证明”的思想，或者说，一种“秘密共享”机制。

最简单的方式： Alice 和 Bob 共享一个秘密数字 $S$ (09)。

1. Alice 的操作： Alice 拿到数字 $A$。她计算 $(A S) pmod{10}$。她将这个结果发送给 Bob。
2. Bob 的操作： Bob 拿到数字 $B$。他计算 $(B S) pmod{10}$。他将这个结果发送给 Alice。
3. 判定：
Alice 收到 Bob 的结果 $(B S) pmod{10}$。
Bob 收到 Alice 的结果 $(A S) pmod{10}$。
Alice 无法从 Bob 的结果推算出 $B$，因为她不知道 Bob 的结果代表的是 $(BS)$ 还是 $(BS+10)$ 等等。
但是，如果他们能传递一个“确认”信息：
Alice 拿到 $A$。她计算 $(A S) pmod{10}$。她将这个结果“加密”，比如，如果结果是 0，她发送“OK”，否则发送“NO”。
Bob 拿到 $B$。他计算 $(B S) pmod{10}$。他将这个结果“加密”，比如，如果结果是 0，他发送“OK”，否则发送“NO”。
结果：
如果 Alice 发送“OK”，Bob 发送“OK”：说明 $AS equiv 0 pmod{10}$ 且 $BS equiv 0 pmod{10}$。即 $A equiv S pmod{10}$ 且 $B equiv S pmod{10}$。 此时 $A=S$ 且 $B=S$，所以 $A=B$。
如果 Alice 发送“OK”，Bob 发送“NO”：说明 $A=S$ 且 $B eq S$。此时 $A eq B$。
如果 Alice 发送“NO”，Bob 发送“OK”：说明 $A eq S$ 且 $B = S$。此时 $A eq B$。
如果 Alice 发送“NO”，Bob 发送“NO”：说明 $A eq S$ 且 $B eq S$。此时他们无法确定 $A$ 和 $B$ 是否相等。

总结一下，最简单且最符合“不暴露”且能确定的方法：

Alice 和 Bob 必须采用一种“协议”，这个协议本身就是他们的“秘密”。

1. 约定： Alice 和 Bob 约定一个“比对函数” $P(x, y)$。这个函数只返回两个值：“相同” 或 “不同”。
2. Alice 的操作：
Alice 拿到自己的数字 $A$。
她随机选择一个“秘密种子” $S_A$。
她计算一个值 $C_A = P(A, S_A)$。 这里的 $P(A, S_A)$ 并不是直接计算“相同”或“不同”，而是生成一个“中间值”，这个中间值是 $A$ 和 $S_A$ 的某种组合，而且这个组合方式非常特殊，使得：
当 Alice 想进行比对时，她需要 Bob 提供一个“对应的中间值” $C_B$。
Alice 能够根据 $C_A$ 和 $C_B$ 计算出“相同”或“不同”的结果，而无法从 $C_B$ 推断出 Bob 的数字。
3. Bob 的操作：
Bob 拿到自己的数字 $B$。
他随机选择一个“秘密种子” $S_B$。
他计算一个值 $C_B = P(B, S_B)$。
他将 $C_B$ 发送给 Alice。

这个“秘密种子”和“比对函数”的设计，是关键所在。

最终的、最接近真相的解释：

Alice 和 Bob 知道彼此的数字不透明，就像他们面前有 10 个杯子，一个代表 0，一个代表 9。他们只能操作这些杯子，而不能看到杯子里的东西。

Alice 的操作：

1. Alice 拿出自己的数字 $A$。
2. 她有一个“协议”，允许她发送一个“加密的问句”。
3. 这个问句是这样的：“如果我的数字是 $A$，那么 Bob 的数字是 $A$ 的概率是多少？” （这个问句本身就不暴露 $A$）。
4. 假设 Bob 可以收到这个“问句”，并且只能回复“是”或“否”。
5. Alice 拿 $A$。她随机选择一个“承诺值” $C_A$。
6. 她将 $C_A$ 发送给 Bob。
7. Bob 的操作：
Bob 拿到 $B$。
他收到 Alice 的 $C_A$。
Bob 必须用他自己的数字 $B$ 来“验证” Alice 的 $C_A$。
Bob 的验证方式是：他将 $B$ 和 $C_A$ “组合”，生成一个“验证结果” $V_B$。
这个 $V_B$ 的生成方式，是关键：
如果 $A=B$，那么 $V_B$ 必须代表“匹配”。
如果 $A eq B$，那么 $V_B$ 必须代表“不匹配”。
Bob 将 $V_B$ 发送给 Alice。
8. 结果判定：
Alice 收到 $V_B$。她知道 $A$ 和 $C_A$。她通过 $V_B$ 的意义，就知道 $A$ 和 $B$ 是否相同。

这个 $C_A$ 和 $V_B$ 的设计，最接近安全多方计算中的“秘密共享”和“比较协议”。

最简单的例子：

1. Alice 和 Bob 共享一个秘密数字 $S$ (09)。
2. Alice 操作： Alice 拿到数字 $A$。她计算 $A S$。如果结果是 0，她发送一个“标记 A”。
3. Bob 操作： Bob 拿到数字 $B$。他计算 $B S$。如果结果是 0，他发送一个“标记 B”。
4. 传递： Alice 将“标记 A”发送给 Bob。 Bob 将“标记 B”发送给 Alice。
5. 结果：
如果 Alice 收到“标记 B”，Bob 收到“标记 A”。
Alice 知道，如果她收到了“标记 B”，说明 Bob 的数字是 $S$。
Bob 知道，如果他收到了“标记 A”，说明 Alice 的数字是 $S$。
但是，这只能判断他们是否都等于 S。

真正的解法，应该是这样的：

Alice 和 Bob 准备了一个“秘密的随机数发生器”（或者他们知道如何生成相同的随机数序列）。

1. Alice 拿到自己的数字 $A$。
2. 她从随机数发生器中获取一个随机数 $r$。
3. 她计算 $X_A = (A + r) pmod{10}$。
4. 她将 $X_A$ 发送给 Bob。

5. Bob 拿到自己的数字 $B$。
6. 他也从同一个随机数发生器中获取同一个随机数 $r$。
7. 他计算 $X_B = (B + r) pmod{10}$。
8. 他将 $X_B$ 发送给 Alice。

9. 判定：
Alice 收到 $X_B$。她知道 $X_B = (B + r) pmod{10}$。她也知道自己的 $X_A = (A + r) pmod{10}$。
Bob 收到 $X_A$。他知道 $X_A = (A + r) pmod{10}$。他知道自己的 $X_B = (B + r) pmod{10}$。

现在，他们如何利用 $X_A$ 和 $X_B$ 来判断 $A$ 和 $B$ 是否相同？

Alice 可以这样做： 她计算 $X_A X_B$ (模 10)。
$(A + r) (B + r) = A B pmod{10}$。
Bob 可以这样做： 他计算 $X_B X_A$ (模 10)。
$(B + r) (A + r) = B A pmod{10}$。

结果：
如果 $A=B$，那么 $AB equiv 0 pmod{10}$。Alice 算出 0，Bob 算出 0。
如果 $A eq B$，那么 $AB$ 不等于 0 (模 10)。 Alice 算出的结果不为 0，Bob 算出的结果也不为 0。

最终判定：
Alice 收到 $X_B$。她自己知道 $r$ 和 $A$，所以她能计算出 $X_A$。她然后计算 $Diff_A = (X_A X_B) pmod{10}$。
Bob 收到 $X_A$。他知道 $r$ 和 $B$，所以他能计算出 $X_B$。他然后计算 $Diff_B = (X_B X_A) pmod{10}$。
Alice 和 Bob 约定：
如果 Alice 计算出的 $Diff_A$ 是 0，说明 $A=B$。
如果 Alice 计算出的 $Diff_A$ 不是 0，说明 $A eq B$。
重要的是，Bob 收到 $X_A$ 后，他同样可以计算 $Diff_B = (X_B X_A) pmod{10}$，如果结果是 0，也说明 $A=B$。

这个方法的好处：
Alice 发送的 $X_A$ 仅仅是 $A+r$ 模 10 的结果。第三方不知道 $A$ 和 $r$，所以无法推断 $A$。
Bob 发送的 $X_B$ 仅仅是 $B+r$ 模 10 的结果。第三方不知道 $B$ 和 $r$，所以无法推断 $B$。
但 Alice 和 Bob，通过他们已知的 $r$，以及收到的对方的 $X$ 值，就能算出 $AB$ 的差值，从而判断是否相等。

这个方法的核心在于：
1. 共享的随机数 $r$： 这是关键，保证了他们计算出的差值是 $AB$ 而不是别的。
2. 模 10 运算： 保证了计算结果在 09 之间。
3. 差值比较： 只有当 $A=B$ 时，$AB pmod{10}$ 才等于 0。

这个就是最靠谱的、最符合“不暴露数字”又能知道是否相同的解答。

高能预警，一步到位

@将离，一个心理学专业的影视博主，邀请一个生物实验室的博士回答密码学问题……巧了，虽然现在的我只破译生命的密码，但当年拿命修过密码学+数论+抽代。希望看完这个答案大家会对密码学产生浓厚的兴趣！如果还没有，可以看经典大片《模仿游戏》和原著 The Code Book 入坑，你一定会冒着生命危险选这门课。

更新：感谢密码学博士 @刘天任 点评~已给出简化版并将原答案作为公平升级版。愿意点开这个回答的朋友应该也会对他和他的各种回答感兴趣。

这问题其实就是 Tiercé problem 又称 socialist millionaire problem，中文硬翻叫社会主义百万富翁问题，是姚氏百万富翁问题的变种，0-9是简化，其实多少都可以，默认没有第三方存在。2001年的论文 A Fair and Efficient Solution to the Socialist Millionaires' Problem 针对该问题给出了适用于两个数都小的情况下也适用的公平高效的解决方案^[1]，我不完全跟随该论文，简单写一下具体协议，再通俗地讲一下为什么没有泄露自己的数。学过数论和群论的朋友读起来会比较轻松。

0-9 十个数全是整数，只要是整数都好说（其实不是也行，反正计算机里都是 bits）。首先一开始 Alice 和 Bob 共同都知道的信息是，其中 为质数， 是整数模 乘法群， 就是质数 阶群，，，，，是 的生成元。为什么这么取值最后讲。当然 Alice 知道自己的数字是 ，Bob 知道自己的数字是 ，开始：

第一步，Alice 随机从 取数字 ，算出 ，同样，Bob 算出 ，然后互相交换 和 得到新的共有知识

第二步，Alice 取 算出 ，同样 Bob 这边 ，得到 ，然后交换 和 得到新共有知识 和

第三步，Alice 算出 ，Bob 算出 ，交换，双方又获得新知识 并检查 是否成立，如果成立则 ，否则

就这？为啥？

因为只有 的时候 ，毕竟 都是不会为 的。

现在有同学要问了， 为什么取这么大， 个 bit 是怎么来的，Fabrice Boudot, Berry Schoenmakers 和 Jacques Traore 在2001年取的 ，是因为计算机算力也就只能做 次运算，如果设 ，是计算上不可能破解的。现在2022了但应该是不用换更大数字的，而且这个数取多少其实不是重点。

仔细观察的同学会发现，所有共享信息里都可以用 的形式表示，而 是秘密，想破解出 就等同于解离散对数，可以当作不可能解出。所有有关 和 的共享信息都长这样： ，而 是随机秘密，因式分解等于无解，所以就算 和 只取 0-9 也是不会破解的。

完毕！

PS：如果硬要有一个第三方，第三方可以站那看着 Alice 和 Bob 玩~

---

如果 Alice 人品不行，想在第三步先骗 Bob 把 给自己后逃之夭夭怎么办？

可以稍作改动：

第二步，Alice 取 算出 ，同样 Bob 这边 ，得到 ，然后交换 和 得到新共有知识 和

第三步，Alice 算出 ，Bob 算出 ，交换，双方又获得新知识

第四步，Alice 和 Bob 一点一点逐 bit 公开 和 ，各自检查是否 ，如果成立则 ，否则

这样一来一方想跑的时候也只比另一方多了解了一个 bit.

---

书本推荐 Katz & Lindell 的 Introduction to Modern Cryptography，建议把抽象代数/数论基础打好之余把可计算性和计算复杂性思维养好。如果有选修密码学来抄答案的，请引用文中论文以免被开除 : )

参考

1. ^A Fair and Efficient Solution to the Socialist Millionaires' Problem https://www.win.tue.nl/~berry/papers/dam.pdf

无需第三方，可以GC（一个等式电路），同态（Bob公钥加密b后发送给Alice，Alice做减法并盲化后发给Bob，Bob解密即可。结果为零说明相等，否则不等）或者秘密共享上的比较协议

A的数字为a，B的数字为b。

那么A在第a天到操场坐一天，B在第b天到操场坐一天。并约定双方其他日子都不去操场。

如果需要前提“对方想尽办法知道自己的数字而自己需要避免”的话，把操场改成无法设置隐身的社交软件即可。