I'm new here, therefore I hope to be clear in this question. Firstly, I want to underline that I'm not a programmer, and I attended only a beginner course in Python, but I like to solve problems writing down some codes (using Python 3.8). However, here's my issue.
My task is to reproduce the plot below.
Where is this picture from? It comes from this journal (pg 137-145)
Now, it's better to expose the whole story behind this picture. In this article, the authors describe a kleptographic attack called SETUP against Diffie-Hellman keys exchange. In particular, they write this algorithm 
Now, in 2 the authors thought "Maybe we can implement honest DHKE and malicious DHKE, and then we compare the running time of the two algorithms". Then, the plot above was born. For this purpose, they say
"We have implemented contaminated and uncontaminated versions of Diffie-Hellman protocols in ANSI C and linked with RSAREF 2.0 library using GNU C v 2.7 compiler. All tests were run on Linux system using a computer with a Pentium II processor (350 MHz) and 64 Mb memory. Computation time for a single protocol was measured in 10- 2s."
Good. Now, I want to do the same, i.e. implement good and evil DH and compare the running time. This is the code I produced
import timeit #used to measure the running time of functions import matplotlib.pyplot as plt #plot the results import random import numpy as np import pyDH #library for Diffie-Hellman key exchange X= pyDH.DiffieHellman() #Eve's private key Y= X.gen_public_key() #Eve's public key #The three integers a,b,W embedded by Eve W=3 a=2 b=2 #Honest DH def public_key(): d1 = pyDH.DiffieHellman() return d1.gen_public_key() #Malicoius Diffie_Hellman (SETUP) #line 1-7 in the algorithm def mal_public_key(): d1 = pyDH.DiffieHellman().get_private_key() t=random.choice([0,1]) z1=pow(pyDH.DiffieHellman().g,d1-W*t,pyDH.DiffieHellman().p) z2=pow(Y,-a*d1-b,pyDH.DiffieHellman().p) z= z1*z2 % pyDH.DiffieHellman().p d2=hash(z) return pow(pyDH.DiffieHellman().g,d2,pyDH.DiffieHellman().p) #function that plot the results def plot(ntest=100000 ): times = [] times2=[] for i in range(ntest): #Running time HONEST Diffie-Hellman (worked two times = two key generations) elapse_time = timeit.timeit(public_key, number=2) #here I collect the times times += [int(round(elapse_time* pow(10, 2) ) )] # Running time MALICOIUS Diffie-Hellman elapse_time2 = timeit.timeit(mal_public_key, number= 1) times2 += [int(round(elapse_time2* pow(10, 2)) )] x_axis=[i for i in range(0,20)] #collect how many tests last i seconds y_axis = [times.count(i) for i in x_axis] y_axis2 = [times2.count(i) for i in x_axis] plt.plot(x_axis, y_axis, x_axis, y_axis2) plt.show() plot() where I used pyDH for honest Diffie-Hellman. This code showed me this figure 
I think the blu line (honest DH) is ok but I'm a little bit suspicious about the orange line (SETUP DH) which is linked to this function
def mal_public_key(): #line 1-7 in the algorithm d1 = pyDH.DiffieHellman().get_private_key() t=random.choice([0,1]) z1=pow(pyDH.DiffieHellman().g,d1-W*t,pyDH.DiffieHellman().p) z2=pow(Y,-a*d1-b,pyDH.DiffieHellman().p) z= z1*z2 % pyDH.DiffieHellman().p d2=hash(z) return pow(pyDH.DiffieHellman().g,d2,pyDH.DiffieHellman().p) - Can the above function be considered as an "implementation" of SETUP attack against DH? Otherwise, what would you write? (any comments to the whole code will be really appreciated)
- In the article, one can read
"It is interesting that the curve representing the contaminated implementation has a small peak at the same value of computation time where the correct implementation has its only peak. [...] There are two different parts which occur every second call to device. The first one is identical to original [...] protocol and exactly this part is presented on the small peak. The disproportion between two peaks of curve representing contaminated implementation is clearly visible. The reason is that for practical usage after the first part of the protocol, (i.e. lines 1-3) device repeats the second part (i.e. lines 4-7) not once but many times."
Can you explain to me this statement? In particular, why there is no small orange peak in my plot? Maybe the mal_public_key() function is bad.
I'm working with Windows10 64bit, 8Gb RAM, AMD A10-8700P radeon R6, 10 compute cores 4C+6G 1.80GHz where I use Python 3.8. I know my computer should be better than the authors' one (I think). Maybe this can affect the results. However, here a similar experiment on elliptic curve is showed and the plot is close to the original one (but, it's elliptic curve).
(P.S. I used a=b=2 and W=3 because Young and Young don't say what these integers should look)
Thanks in advance for your help.
