【安全多方计算】百万富翁问题
前导知识
判断素数
素数：除了1和它本身以外不再有其他的因数，且大于1的自然数。
定理：若x是素数，那么x的最小质因数y≤sqrt(x)，sqrt(x)指对x开根号。
【代码实现】
import math
def is_prime(x: int):
'''
判断x是否为素数
'''
if x <= 1:
raise ValueError("0和1既不是素数也不是合数，x应为大于1的正整数")
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
return True
欧几里得求最大公约数
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
=
…
=
g
c
d
(
∗
,
0
)
,
∗
即
为
a
和
b
的
最
大
公
约
数
gcd(a, b) = gcd(b, a\%b) = … = gcd(*, 0), *即为a和b的最大公约数
gcd(a,b)=gcd(b,a%b)=…=gcd(∗,0),∗即为a和b的最大公约数
图解计算过程
【代码实现】
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
Python的math库也内置了函数可以求解
import math
print(math.gcd(6,9))
扩展欧几里得求乘法逆元
两个不完全为0的整数a、b，存在满足
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a, b)
ax+by=gcd(a,b)的一组解x、y。
当
g
c
d
(
a
,
b
)
=
1
gcd(a, b)=1
gcd(a,b)=1时，满足
a
∗
x
=
1
m
o
d
b
b
∗
y
=
1
m
o
d
a
a*x=1\ mod\ b \\ b*y=1\ mod\ a
a∗x=1 mod bb∗y=1 mod a
而求解x、y，我们使用扩展欧几里得算法。
g
c
d
(
a
,
b
)
=
a
∗
x
1
+
b
∗
y
1
(
1
)
g
c
d
(
b
,
a
m
o
d
b
)
=
b
∗
x
2
+
(
a
m
o
d
b
)
∗
y
2
(
2
)
g
c
d
(
a
m
o
d
b
,
b
m
o
d
(
a
m
o
d
b
)
)
=
(
a
m
o
d
b
)
∗
x
3
+
(
b
m
o
d
(
a
m
o
d
b
)
)
∗
y
3
(
3
)
⋮
g
c
d
(
1
,
0
)
=
x
n
(
n
)
gcd(a,b)=a*x_1+b*y_1 \ \ (1) \\ gcd(b, a\ mod\ b)=b*x_2 + (a\ mod\ b)*y_2 \ \ (2) \\ gcd(a\ mod\ b, b\ mod(a\ mod\ b)) = (a\ mod\ b)*x_3 + (b\ mod(a\ mod\ b))*y_3 \ \ (3) \\ \vdots \\ gcd(1, 0) = x_n \ \ (n)
gcd(a,b)=a∗x1+b∗y1 (1)gcd(b,a mod b)=b∗x2+(a mod b)∗y2 (2)gcd(a mod b,b mod(a mod b))=(a mod b)∗x3+(b mod(a mod b))∗y3 (3)⋮gcd(1,0)=xn (n)
由(1)、(2)得
x
1
=
y
2
,
y
1
=
x
2
−
[
a
b
]
∗
y
2
x_1=y_2, y1=x_2 -[\cfrac{a}{b}]*y_2
x1=y2,y1=x2−[ba]∗y2，由此可得，递归出口是(n)中的
a
=
1
,
b
=
0
a=1,b=0
a=1,b=0，我们可以就用代码实现求解了
def expandEuclid(a, b):
'''
a*x = 1 mod b
b*y = 1 mod a
已知a、b，返回x, y
'''
if b == 0:
return 1, 0
else:
x2, y2 = get_inverse(b, a % b)
x1, y1 = y2, x2 - a // b * y2
return x1, y1
生成公钥和私钥
- 随机生成两个大素数
p
、
q
(
p
!
=
q
)
p、q(p!=q)
p、q(p!=q)
n
=
p
∗
q
,
s
=
(
p
−
1
)
∗
(
q
−
1
)
n=p*q,\ s=(p-1)*(q-1)
n=p∗q, s=(p−1)∗(q−1)
- 随机取一个大整数
e
e
e，
2
≤
e
≤
s
−
1
2≤e≤s-1
2≤e≤s−1 且
g
c
d
(
e
,
s
)
=
1
gcd(e, s) = 1
gcd(e,s)=1
- 用扩展欧几里得算法求
e
e
e的乘法逆元
d
(
e
∗
d
=
1
m
o
d
s
,
d
>
0
)
d(e*d=1\ mod\ s, d>0)
d(e∗d=1 mod s,d>0)
- 公钥为
(
n
,
e
)
(n, e)
(n,e)，私钥为
(
n
,
d
)
(n, d)
(n,d)
百万富翁问题
问题
有两个喜欢攀比的百万富翁Alice和Bob。有一天他们相遇了，他们想要跟对方比比看谁更有钱，但是又不想让对方知道自己有多少钱。
问：如果在不借助第三方的情况下，知道谁更有钱？
解决思路
代码实现
Python的简单实现代码如下（i和j的取值为1-10）
import random
import math
# Alice的财富为i，Bob的财富为j，取值为0~10
# Alice选择一个随机大整数x
# Alice和Bob约定使用RSA算法
# Bob用RSA算法生成公钥和私钥，将公钥发给Alice
# Alice使用Bob的公钥加密x得C=E(x)，并发送C-i给Bob
# Bob使用私钥计算Y(u) = D(C-i+u) (1<=u<=10)
# Bob随机取一个小于x的大整数p，将Y(u) mod p得到Z(u)，验证对所有Z(u)都满足0<Z(u)<p-1。若不满足则更换p重新计算
# 再将Z(u)从第j-1位开始向右均+1得到K(u)，然后将K(u)和p发给Alice
# Alice将K[i-1]与(x mod p)进行比较，如果相等，则说明i<j，即Alice不如Bob富有；若不相等，则说明i>=j，说明Alice比BOb富有或者和Bob一样富有
def is_prime(x: int):
'''
判断x是否为素数
'''
if x <= 1:
raise ValueError("0和1既不是素数也不是合数，x应为大于1的正整数")
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
return True
def get_inverse(a, b):
'''
a*x = 1 mod b
b*y = 1 mod a
已知a、b，返回x, y
'''
if b == 0:
return 1, 0
else:
x2, y2 = get_inverse(b, a % b)
x1, y1 = y2, x2 - a // b * y2
return x1, y1
def create_key():
'''
创建公钥和私钥
'''
while True:
p = random.randint(10**1, 10**2)
if is_prime(p):
break
while True:
q = random.randint(10**1, 10**2)
if is_prime(q) and q != p:
break
n, s = p*q, (p-1)*(q-1)
print(f"n={n}, s={s}")
while True:
e = random.randint(2, s-1)
if math.gcd(e, s) == 1:
d = get_inverse(e, s)[0]
if d > 0:
break
return [(n, e), (n, d)]
def encrypt(content, pbkey):
return pow(content, pbkey[1]) % pbkey[0]
def decrypt(encrypt_content, pvkey):
return pow(encrypt_content, pvkey[1]) % pvkey[0]
def main():
i = int(input("Alice: "))
j = int(input("Bob: "))
while True:
x = random.randint(10**1, 10**2)
if is_prime(x):
break
print(f"随机整数x={x}")
pbk, pvk = create_key()
print(f"公钥(n, e)=({pbk[0]}, {pbk[1]})\t私钥(n, d)=({pvk[0]}, {pvk[1]})")
C = encrypt(x, pbk)
print(f"Alice发送C-i={C-i}给Bob")
Y = [decrypt(C-i+u, pvk) for u in range(1, 11)]
print(f"Y={Y}")
p = random.randint(10**1, x-1)
while True:
Z = list(map(lambda a: a % p, Y))
if max(Z) < p-1 and min(Z) > 0:
break
# p = random.randint(min(10**2, min(Y)), max(10**3, min(Y)))
p = random.randint(10**1, x-1)
print(f"p={p}\nZ={Z}")
for u in range(10):
Z[u] = Z[u] + 1 if u >= j-1 else Z[u]
print(f"K={Z}")
if Z[i-1] == x % p:
if i < j:
print("Bob更富有")
else:
print("验证错误，i应该大于j，Alice可能更富有，也可能和Bob一样富有")
else:
if i >= j:
print("Alice可能更富有，也可能和Bob一样富有")
else:
print("验证错误，j应该大于i，Bob更富有才对")
if __name__ == '__main__':
main()
【样例输入】
3 2
【样例输出】
随机整数x=83
n=2449, s=2340
公钥(e, n)=(943, 2449) 私钥(d, n)=(67, 2449)
Alice发送C-i=2003给Bob
Y=[1382, 1499, 83, 1889, 96, 1141, 739, 1131, 2246, 1918]
p=69
Z=[2, 50, 14, 26, 27, 37, 49, 27, 38, 55]
K=[2, 51, 15, 27, 28, 38, 50, 28, 39, 56]
Alice可能更富有，也可能和Bob一样富有
【样例输入】
3 3
【样例输出】
随机整数x=29
n=649, s=580
公钥(e, n)=(91, 649) 私钥(d, n)=(51, 649)
Alice发送C-i=576给Bob
Y=[16, 50, 29, 19, 306, 197, 132, 441, 13, 377]
p=23
Z=[16, 4, 6, 19, 7, 13, 17, 4, 13, 9]
K=[16, 4, 7, 20, 8, 14, 18, 5, 14, 10]
Alice可能更富有，也可能和Bob一样富有
【样例输入】
4 6
【样例输出】
随机整数x=47
n=2117, s=2016
公钥(e, n)=(223, 2117) 私钥(d, n)=(895, 2117)
Alice发送C-i=220给Bob
Y=[746, 2114, 1205, 47, 1193, 1271, 81, 1834, 1701, 101]
p=30
Z=[26, 14, 5, 17, 23, 11, 21, 4, 21, 11]
K=[26, 14, 5, 17, 23, 12, 22, 5, 22, 12]
Bob更富有
总结
我以为，百万富翁问题是安全多方计算中的一种模型框架，以公钥加密安全通信和标记的方式实现双方数值的比较，重点在于模型本身，具体的实现可以根据现有的技术进行改良，提升安全性和可靠性。
本人也是这方面的初学者，看到网上的资源比较少因此写了这篇博客，有很多地方认识还不够，如果有不对的地方还请帮忙指正。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/97117.html
