На обмен ключами Диффи-Хеллмана

Question

Книга, которую я читаю, объясняет алгоритм следующим образом:

• 2 человека думают о двух открытых числах "n и g", о которых знают оба.
• 2 человека думают о двух частных числах "х" и "у", которые держат в секрете

Обмен происходит как показано

Я собрал следующий код Python, чтобы увидеть, как это работает, и.... это не так. Пожалуйста, помогите мне понять, что мне не хватает:

 #!/usr/bin/python

 n=22 # publicly known 
 g=42 # publicly known

 x=13 # only Alice knows this 
 y=53 # only Bob knows this

 aliceSends = (g**x)%n 
 bobComputes = aliceSends**y 
 bobSends = (g**y)%n
 aliceComputes = bobSends**x


 print "Alice sends    ", aliceSends 
 print "Bob computes   ", bobComputes 
 print "Bob sends      ", bobSends 
 print "Alice computes ", aliceComputes

 print "In theory both should have ", (g**(x*y))%n

 ---

 Alice sends     14  
 Bob computes    5556302616191343498765890791686005349041729624255239232159744 
 Bob sends       14 
 Alice computes  793714773254144 

 In theory both should have  16

Answer 1

Вы забыли еще два модуля:

>>> 5556302616191343498765890791686005349041729624255239232159744 % 22
16L
>>> 793714773254144 % 22
16

Answer 2

Роман прав. Однако вам лучше взглянуть на функцию трех аргументов pow(). Гораздо быстрее и третий аргумент является модулем

Answer 3

Для двух человек

#!/usr/bin/python
p=141301# publicly known 
g=5728435 # publicly known
x=76435 # only Alice knows this 
y=37846 # only Bob knows this
aliceSends = (g**x)%p 
aliceComputes = (bobSends**x)%p
bobSends = (g**y)%p
bobComputes = (aliceSends**y) %p
bobSends = (g**y)%p
bobComputes = (aliceSends**y) %p
print ("Alice sends    ", aliceSends )
print ("Bob computes   ", bobComputes )
print ("Bob sends      ", bobSends)
print ("Alice computes ", aliceComputes)

Для трех и более человек

#!/usr/bin/python
p=141301# publicly known 
g=5728435 # publicly known
x=76435 # only Alice knows this 
y=37846 # only Bob knows this
z=23# only carol knows this
aliceSends = (g**x)%p 
bobSends = (aliceSends**y)%p
carolComputes=(bobSends**z)%p
bobSends2=(g**y)%p
carolSends=(bobSends2**z)%p
aliceComputes=(carolSends**x)%p
carolSends2=(g**z)%p
aliceSends2=(carolSends2**x)%p
bobComputes=(aliceSends2**y)%p
print ("Alice computes ga and sends it to Bob.",aliceSends)
print ("Bob computes (ga)b = gab and sends it to Carol.",bobSends)
print ("Carol computes (gab)c = gabc and uses it as her secret.",carolComputes)
print ("Bob computes gb and sends it to Carol.",bobSends2)
print ("Carol computes (gb)c = gbc and sends it to Alice.",carolSends)
print ("Alice computes (gbc)a = gbca = gabc and uses it as her  secret.",aliceComputes)
print ("Carol computes gc and sends it to Alice.",carolSends2)
print ("Alice computes (gc)a = gca and sends it to Bob.",aliceSends2)
print ("Bob computes (gca)b = gcab = gabc and uses it as his 
secret.",bobComputes)