Проблема с «То же самое?» значение неверно в шагах 15 и 16 задачи социалистического миллионера ⇐ Python

[Anonymous]

Я написал этот код для реализации проблемы социалистических миллионеров (SMP). Однако мне трудно понять, почему на шагах 15 и 16 значение «То же самое?» является ложным как для Алисы, так и для Боба.
Насколько я понимаю, если Алиса и Боб имеют одинаковое состояние (x), результат на шагах 15 и 16 должен указывать на совпадение (True). Я подозреваю, что может возникнуть проблема с тем, как я обрабатываю модульную арифметику, инверсии или случайные значения, выбранные во время протокола.
Вот соответствующие шаги:
И Алиса, и Боб обмениваются значениями [h^v mod p, h^w mod p] на шагах_1_2.
Они вычисляют свои собственные значения P и Q на шагах_5_на_8 на основе полученных значений.
/>На шаге_11_и_12 проверяют полученные значения P и Q и выполняют дальнейшие расчеты.
На шаге_15_и_16 проверяют, соответствуют ли результаты протоколу.
Для лучшего понимания я распечатал промежуточные значения, и они следующие:

Код: Выделить всё

Alice -> step_1_to_2: [22, 20]
Bob   -> step_1_to_2: [6, 6]
Alice -> step_5_to_8: [13, 6]
Bob   -> step_5_to_8: [9, 3]
Alice -> step_11_and_12: 9
Bob   -> step_11_and_12: 16
Alice -> step_15_and_16: Same? False
Bob   -> step_15_and_16: Same? False

Код: Выделить всё

from Crypto.Util.number import getRandomRange, inverse

class SMP:

def __init__(self, x, p, h, user_a = True):
"""
* x: fortune of this millionaire
* p: prime number
* h: value in Zp
* user_a: True if user is Alice, False if it's Bob
"""
self.x = x
self.p = p
self.h = h
self.user_a = user_a

# Variables that we will use in the steps
self.v = None       # Random for steps_1_2
self.w = None       # Another random for steps_1_2
self.P_own = None   # P calculated in steps_5_6_7_8
self.Q_own = None   # Q calculated in steps_5_6_7_8

self.P_other = None

def step_1_to_2(self):
self.v = getRandomRange(1, self.p - 1)
self.w = getRandomRange(1, self.p - 1)

hv = pow(self.h, self.v, self.p)  # h^v mod p
hw = pow(self.h, self.w, self.p)  # h^w mod p

return [hv, hw]

def step_5_to_8(self, hvalues):
# Receive [h^b1, h^b2] if we are Alice or [h^a1, h^a2] if we are Bob.
hv, hw = hvalues

# STEP 5: Check that h^b1 != 1 and h^b2 != 1 if we are Alice, or h^a1 != 1 and h^a2 != 1 if we are Bob
if hv == 1 or hw == 1:
return None

# STEP 6: Calculate g and f
#   g = (h^(a1))^(a1)  (or g = (h^(b1))^(b1) if we are Bob)
#   f = (h^(a2))^(a2)  (or f = (h^(b2))^(b2) if we are Bob)
# In our code, 'self.v' and 'self.w' represent a1 and a2 (or b1 and b2),
# and hv, hw represent h^(a1), h^(a2) (or h^(b1), h^(b2)).
g = pow(hv, self.v, self.p)
f = pow(hw, self.w, self.p)

# STEP 7: Choose a random number r that belongs to Zp
r = getRandomRange(1, self.p - 1)

# STEP 8: Calculate P and Q
#   P = f^r  mod p
#   Q = (h^r * g^x) mod p
self.P_own = pow(f, r, self.p)
# To compute Q = h^r * g^x (mod p), we do modular multiplication
self.Q_own = (pow(self.h, r, self.p) * pow(g, self.x, self.p)) % self.p

return [self.P_own, self.Q_own]

def step_11_and_12(self, pqvalues):
P, Q = pqvalues
# STEP 11: Check that they are not equal (mod p)
if self.P_own == P or self.Q_own == Q:
return None

self.P_other = P

# STEP 12
# Invert Q mod p
inv_Q = inverse(Q, self.p)

# Q_own * inv(Q)
Q_mult = (self.Q_own * inv_Q) % self.p

# Raise to self.w which represents a2 or b2
result = pow(Q_mult, self.w, self.p)

return result

def step_15_and_16(self, qsprod):
c = pow(qsprod, self.w, self.p)

if self.P_other is None:
return None

# Step 16: verify that c == (P_own * inv(P_other)) mod p
inv_P_other = inverse(self.P_other, self.p)
check_val = (self.P_own * inv_P_other) % self.p

return (c == check_val)

# Example usage
if __name__ == "__main__":
p = 23
h = 5

# Alice and Bob with the same fortune, x=5
alice = SMP(x=15, p=p, h=h, user_a=True)
bob   = SMP(x=15, p=p, h=h, user_a=False)

# ----- Steps 1 and 2 -----
hvhw_alice = alice.step_1_to_2()
hvhw_bob   = bob.step_1_to_2()

print("Alice -> step_1_to_2:", hvhw_alice)
print("Bob   ->  step_1_to_2:", hvhw_bob)

# ----- Steps 5,6,7,8 -----
# Alice uses Bob's [h^v, h^w] values
PQ_alice = alice.step_5_to_8(hvhw_bob)
# Bob uses Alice's [h^v, h^w] values
PQ_bob   = bob.step_5_to_8(hvhw_alice)

print("Alice -> step_5_to_8:", PQ_alice)
print("Bob   -> step_5_to_8:", PQ_bob)

# ----- Steps 11,12 -----
# Alice processes [P_bob, Q_bob], Bob processes [P_alice, Q_alice]
res11_12_alice = alice.step_11_and_12(PQ_bob)
res11_12_bob   = bob.step_11_and_12(PQ_alice)

print("Alice -> step_11_and_12:", res11_12_alice)
print("Bob   -> step_11_and_12:",   res11_12_bob)

# Alice and Bob invoke steps_15_16 exchanging the products of Q
final_alice = alice.step_15_and_16(res11_12_bob)
final_bob   = bob.step_15_and_16(res11_12_alice)

print("Alice -> step_15_and_16: Same?", final_alice)
print("Bob   -> step_15_and_16: Same?", final_bob)

Спасибо,


Подробнее здесь: https://stackoverflow.com/questions/793 ... illionaire