【安全多方計(jì)算】百萬富翁問題
【問題描述】
? 百萬富翁問題是姚期智先生在1982年提出的第一個(gè)安全雙方計(jì)算問題,兩個(gè)百萬富翁街頭邂逅，他們都想炫一下富，比比誰更有錢，但是出于隱私，都不想讓對(duì)方知道自己到底擁有多少財(cái)富，所以要在不借助第三方的情況下，知道他們之間誰更有錢。
【問題分析】
①這里假設(shè)Alice和Bob就是這兩個(gè)百萬富翁，Alice擁有財(cái)富i百萬，Bob擁有財(cái)富j百萬，假設(shè)他們兩的財(cái)富都沒有超過N百萬，即1 ≤ i , j ≤ N，如下圖所示：
②Alice隨機(jī)選擇一個(gè)大隨機(jī)數(shù)x，用Bob的公鑰加密后得到x的密文c，如下圖所示：
③Alice將c-i發(fā)送給Bob（減去i是為了破壞密文c），如下圖所示：
④Bob首先計(jì)算N個(gè)數(shù)：yu=DSKB(c-i+u)， 其中u=1,2…N（這里加上u是為了能在yu的數(shù)列里面還原出被破壞的密文），然后隨機(jī)選擇一個(gè)大素?cái)?shù)p，再計(jì)算N個(gè)數(shù)：zu=yu mod p, 其中u=1,2…N，如下圖所示：
⑤接著Bob對(duì)于所有的0≤a≠b≤N，是否都滿足|za-zb|≥2（如果小于2的話，就可能導(dǎo)致第⑥步里面的數(shù)串,zj+1+1,zj+2+1,…,zN+1和zj+1相等），若不滿足，則重新選擇大素?cái)?shù)p并重新驗(yàn)證。如下圖所示：
⑥如果滿足，Bob將以下的N個(gè)數(shù)串和p：(z1，z2,…,zj,zj+1+1,zj+2+1,…,zN+1,p)一起發(fā)給Alice（這里從zj+1開始每一項(xiàng)+1是為了在第⑦步Alice驗(yàn)證的時(shí)候能得出正確的結(jié)論，而且也保護(hù)了Bob的隱私，不能泄露j的值），如下圖所示：
⑦假設(shè)Alice收到這N+1個(gè)數(shù)的第i個(gè)數(shù)滿足Zi=x(mod p)，則結(jié)論是i≤j，否則i＞j（對(duì)應(yīng)第④步中的zu=yu mod p）。如下圖所示：
【代碼實(shí)現(xiàn)】
這部分的算法思想?yún)⒖剂薱sdn上Bertramoon的博客，只不過這里換成java實(shí)現(xiàn)。
【前導(dǎo)模塊】
1.判斷素?cái)?shù)
public static boolean is_prime(int x) throws Exception {//判斷素?cái)?shù)
if (x <= 1) {
throw new Exception("0和1既不是素?cái)?shù)也不是合數(shù)，x應(yīng)為大于1的正整數(shù)");
}
for(int i = 2; i < (int) (Math.sqrt(x) + 1); i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
2.求最大公約數(shù)
public static int gcd(int a,int b) {//求最大公約數(shù)
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
3.求乘法逆元
? 首先，數(shù)學(xué)上的乘法逆元就是指直觀的倒數(shù)，即 a 的逆元是 1/a，也即與 a 相乘得 1 的數(shù)。ax=1，則x是a的乘法逆元。
? 這里我們討論關(guān)于取模運(yùn)算的乘法逆元，即對(duì)于整數(shù) a，與 a 互質(zhì)的數(shù) b 作為模數(shù)，當(dāng)整數(shù) x 滿足 ax mod b≡1 時(shí)，稱 x 為 a 關(guān)于模 b 的逆元，代碼表示就是a*x % b == 1。
這部分的實(shí)現(xiàn)代碼如下：
public static int[] get_inverse(int a, int b){
// a*x = 1 mod b
// b*y = 1 mod a
// 已知a、b，返回x, y
if (b == 0) {
int [] l = {1, 0};
return l;
} else {
int [] r = get_inverse(b, a % b);
int x1, x2, y1, y2;
x2 = r[0];
y2 = r[1];
x1 = y2;
y1 = x2 - ((int)a / b) * y2;
int [] r2 = {x1, y1};
return r2;
}
}
4.生成公鑰和私鑰
-
隨機(jī)生成兩個(gè)大素?cái)?shù)p 、 q ( p ! = q ) ；
-
n = p ? q , s = ( p ? 1 ) ? ( q ? 1 ) ；
-
隨機(jī)取一個(gè)大整數(shù)e ，使得2 ≤ e ≤ s ? 1且 g c d ( e , s ) = 1；
-
用擴(kuò)展歐幾里得算法求e 的乘法逆元 d ( e ? d = 1 m o d s , d > 0 ) ；
-
公鑰為( n , e )，私鑰為( n , d )；
public static int [][] create_key() throws Exception {
// 創(chuàng)建公鑰和私鑰
int p, q, n, s;
while (true) {
p = new Random().nextInt(90) + 10;
if (is_prime(p)) {
break;
}
}
while (true) {
q = new Random().nextInt(90) + 10;
if (is_prime(q) && q != p) {
break;
}
}
n = p * q;
s = (p - 1)*(q - 1);
int d,e;
System.out.println("n="+String.valueOf(n)+",s="+String.valueOf(s));
while (true) {
e = new Random().nextInt(s - 3) + 2;
if (gcd(e, s) == 1){
d = get_inverse(e,s)[0];
if (d>0){
break;
}
}
}
int [][] r = {{n,e},{n,d}};
return r;
}
【總體實(shí)現(xiàn)】
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
public class millionaire{
public static void main(String[] args) throws Exception {
// Alice的財(cái)富為i，Bob的財(cái)富為j，取值為0~10
// Alice選擇一個(gè)隨機(jī)大整數(shù)x
// Alice和Bob約定使用RSA算法
// Bob用RSA算法生成公鑰和私鑰，將公鑰發(fā)給Alice
// Alice使用Bob的公鑰加密x得C=E(x)，并發(fā)送C-i給Bob
// Bob使用私鑰計(jì)算Y(u) = D(C-i+u) (1<=u<=10)
// Bob隨機(jī)取一個(gè)小于x的大整數(shù)p，將Y(u) mod p得到Z(u)，驗(yàn)證對(duì)所有Z(u)都滿足0<Z(u)<p-1。若不滿足則更換p重新計(jì)算
// 再將Z(u)從第j-1位開始向右均+1得到K(u)，然后將K(u)和p發(fā)給Alice
// Alice將K[i-1]與(x mod p)進(jìn)行比較，如果相等，則說明i<j，即Alice不如Bob富有；若不相等，則說明i>=j，說明Alice比BOb富有或者和Bob一樣富有
Scanner input = new Scanner(System.in);
System.out.print("Alice:");
int i = input.nextInt();
System.out.print("Bob:");
int j = input.nextInt();
int x;
while (true) {
x = new Random().nextInt(90) + 10;
if (is_prime(x)){
break;
}
}
System.out.println("隨機(jī)整數(shù)x="+String.valueOf(x));
int [] pbk, pvk;
int [][] r = create_key();
pbk = r[0];
pvk = r[1];
System.out.println("公鑰(n,e)=("+String.valueOf(pbk[0])+","+String.valueOf(pbk[1])+")\n"+
"私鑰(n,d)=("+String.valueOf(pvk[0])+","+String.valueOf(pvk[1])+")");
int C = encrypt(x, pbk);
System.out.println("Alice發(fā)送C-i="+String.valueOf(C - i)+"給Bob");
int [] Y = new int[10];
for(int u = 1; u<11;u++){
Y[u - 1] = decrypt(C-i+u,pvk);
}
System.out.println("Y="+toS(Y).toString());
int p = new Random().nextInt(x - 11) + 10;
int [] Z = new int[10];
while (true) {
for(int u = 0; u<10;u++){
Z[u] = Y[u] % p;
}
if(max(Z) < p -1 &&min(Z)>0){
break;
}
p = new Random().nextInt(x - 11) + 10;
}
System.out.println("p="+String.valueOf(p)+"\nZ="+toS(Z).toString());
for(int u=0;u<10;u++){
if(u>=j+1){
Z[u] = Z[u] + 1;
}
}
System.out.println("k="+toS(Z).toString());
if(Z[i-1] == x % p){
if (i<j){
System.out.println("Bob更富有");
}else {
System.out.println("驗(yàn)證錯(cuò)誤，i應(yīng)該大于j，Alice可能更富有，也可能和Bob一樣富有");
}
}else {
if (i >= j){
System.out.println("Alice可能更富有，也可能和Bob一樣富有");
}else {
System.out.println("驗(yàn)證錯(cuò)誤，j應(yīng)該大于i，Bob更富有才對(duì)");
}
}
}
public static StringBuffer toS(int []d){
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("[ ");
for (int i=0;i<d.length;i++){
stringBuffer.append(d[i]);
stringBuffer.append(" ");
}
stringBuffer.append(" ]");
return stringBuffer;
}
public static int gcd(int n, int m){
int z = 0;
while (m%n != 0){
z = m%n;
m = n;
n = z;
}
return n;
}
public static int max(int []d){
int m = d[0];
for (int i = 1; i<d.length;i++){
if(m<d[i]){
m = d[i];
}
}
return m;
}
public static int min(int []d){
int m = d[0];
for (int i = 1; i<d.length;i++){
if(m>d[i]){
m = d[i];
}
}
return m;
}
public static boolean is_prime(int x) throws Exception {
if (x <= 1) {
throw new Exception("0和1既不是素?cái)?shù)也不是合數(shù)，x應(yīng)為大于1的正整數(shù)");
}
for(int i = 2; i < (int) (Math.sqrt(x) + 1); i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
public static int[] get_inverse(int a, int b){
// a*x = 1 mod b
// b*y = 1 mod a
// 已知a、b，返回x, y
if (b == 0) {
int [] l = {1, 0};
return l;
} else {
int [] r = get_inverse(b, a % b);
int x1, x2, y1, y2;
x2 = r[0];
y2 = r[1];
x1 = y2;
y1 = x2 - ((int)a / b) * y2;
int [] r2 = {x1, y1};
return r2;
}
}
public static int [][] create_key() throws Exception {
// 創(chuàng)建公鑰和私鑰
int p, q, n, s;
while (true) {
p = new Random().nextInt(90) + 10;
if (is_prime(p)) {
break;
}
}
while (true) {
q = new Random().nextInt(90) + 10;
if (is_prime(q) && q != p) {
break;
}
}
n = p * q;
s = (p - 1)*(q - 1);
int d,e;
System.out.println("n="+String.valueOf(n)+",s="+String.valueOf(s));
while (true) {
e = new Random().nextInt(s - 3) + 2;
if (gcd(e, s) == 1){
d = get_inverse(e,s)[0];
if (d>0){
break;
}
}
}
int [][] r = {{n,e},{n,d}};
return r;
}
public static int encrypt(int content, int [] pbkey){
BigInteger c = new BigInteger(String.valueOf(content));
BigInteger p0 = new BigInteger(String.valueOf(pbkey[0]));
int r = (c.pow(pbkey[1]).mod(p0)).intValue();
return r;
// return (int)Math.pow(content, pbkey[1]) % pbkey[0];
}
public static int decrypt(int encrypt_content, int [] pvkey){
BigInteger c = new BigInteger(String.valueOf(encrypt_content));
BigInteger p0 = new BigInteger(String.valueOf(pvkey[0]));
int r = (c.pow(pvkey[1]).mod(p0)).intValue();
return r;
// return (int)Math.pow(encrypt_content, pvkey[1]) % pvkey[0];
}
}
【測(cè)試結(jié)果】
文章來源：http://www.zghlxwxcb.cn/news/detail-448742.html
ps：本人也是這方面知識(shí)的初學(xué)者，如果有什么認(rèn)識(shí)不到位或者錯(cuò)誤的地方懇請(qǐng)批評(píng)指正。文章來源地址http://www.zghlxwxcb.cn/news/detail-448742.html
到了這里，關(guān)于【安全多方計(jì)算】百萬富翁問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
