兩富人比誰錢多。如何能實現互相保密但可以比出誰錢多？

1樓：Horizon

2023年，姚啟智教授在提出百萬富翁問題後就給出了該問題的一種解決方案。該方案用於對兩個數進行比較，以確定哪乙個較大。Alice知道乙個整數i；Bob知道乙個整數j, Alice與B0b希望知道究竟i>=j還是j>i，但都不想讓對方知道自己的數。

為簡單起見，假設j與i的範圍為[1，100】。Bob有乙個公開金鑰Eb和私有金鑰Db。

百萬富翁問題協議一

(1)Alice選擇乙個大隨機數x，並用Bob的公開金鑰加密c=Eb(x)；

(2)Alice計算c—i，並將結果傳送給Bob：

(3)Bob計算下面的100個數：Yu=Db(c-i+w), u=1，2，．．．，100 其中Db是Bob的私有解密金鑰。B0b選擇乙個大素數p(p應該比x稍小一點，Bob不知道x，但Alice能容易地告訴他x的大小)，然後計算下面的100個數：

Zu=(Yu mod p), u=1，2，．．．，100。然後驗證對所有的u≠v, |Zu-Zv|>=2，並對所有的u驗證：0(4)Bob將以下數列傳送給Alice：

Z1，Z2，．．．，Zj，Zj+1+1．．．，Z100+1，p；

(5)Alice驗證這個數列的第i個數是否與x模p同餘。如果同餘，她得出的結論是i<=j;如果不同餘，她得出的結論是i>j;

(6)Alice把這個結論告訴Bob。

或者還聽說過乙個有趣的方法，就是每個人按照一定的換算調製不同PH的酸鹼試劑，比如一位調酸性，一位調鹼性，然後將兩種試劑混合，最後使用試紙，如果試紙紅色，則說明酸性更強，藍色則說明鹼性更強，以此達到比較目的。

2樓：雪梨最酷手機殼

我竟然不知道姚氏百萬富翁演算法。

尷尬了，哈哈哈

就題目而言，不停設定購買物給他們兩個，直到有一方買不起為止。

在演算法上的應用...... 加權值的做法吧。

3樓：

這篇文章寫得很清楚了：知道了這個方法，兩個人不需要裁判就能玩暗軍棋

簡單的說，分為三步：

第一步，經過特定的操作，讓乙方構造出 n 把鎖，甲方有且僅有第 j 把鎖的鑰匙，但是乙方不知道 j 是多少；

第二步，乙方給甲方 n 把鎖鎖著的標誌位，其中前 i 個標誌位置0，後 n-i 個置1；

第三步，甲方檢查第 j 把鎖鎖著的標誌位是否為0。如果為0則 i >= j，否則 i < j。

假設富翁王有 i 億資產，李有 j 億資產。王選取乙個公鑰，使得李可以傳遞加密的資訊。

首先，李選取乙個隨機的大整數 x ，把 x 用王的公鑰加密，得到密文 K 。李傳送 K-j 給王。

王收到密文 c=K-j 之後，對 c+1,...,c+10 進行解密，得到十個數字。再選取乙個適當大小的素數 p , 把這十個數字除以 p 的餘數記作 d1,...,d10.

注意：這十個數字看起來應該是完全隨機的，關鍵是等式 dj=x mod p 成立。

第一步是整個過程的點睛之筆，由非對稱加密實現的。李通過用王的公鑰加密，得到K，但是傳送 K-j 給王。這時候李知道王能夠解密c+1,...

,c+10中的某乙個(第 j 個)，但是並不知道 j 是幾。

最後，王對這一串數字作如下操作：前面 i 個數不動，後面的數字每個加一，然後發回給李。

這樣一通複雜的操作之後，李檢查第 j 個數字。如果等於 x mod p 的話，說明這個數字沒有被加一，所以 i >= j. 反之，則 i < j。

第二步，因為王只能解密第 j 項，也就是只知道 dj, 對 d1 到 d10 中的其他項一無所知，這時候把前 i 項不變，後面的加 1，發回給李。李只能知道 dj 是否被加了1，通過這個資訊判斷兩者大小關係。

4樓：kimmking

豔紅：來我們比比誰有錢，但不能說出來自己有多少錢，你有什麼辦法嗎碼雲：很簡單哈，說富比士國內排名唄，你多少豔紅：我第5

碼雲：哈哈，我第一