1128-Diffie-Hellman Key Exchange (1).sagews

Diffie-Hellman Key Exchange (1)

step  [removed] [removed] [removed] [removed]

Figure 2.1 This graphic illustrates the Diffie-Hellman key exchange consisting of steps 0 to 5. Click on the numbers to see it
step by step. Note that everything in the blue boxes happens secretly (with Alice or Bob), and everything in the yellow box is
sent over the insecure network and may be seen by Eve.

Number of Possible Keys

p  g  [removed] [removed] [removed] [removed]

Figure 2.2 Choose values for p and g and let the program tell you how many possible values there are for the key. If you have made
a good choice and chosen g as a primitive root mod p, then there are p-1 possible keys.

Calculation of Primitive Roots

p  [removed] [removed] [removed] [removed]

Figure 2.3 This program calculates a primitive root mod p for a given prime number p.

Diffie-Hellman Key Exchange (2)

p  g  show secret values  show calculations (with secret values)  [removed] [removed] [removed] [removed]

Figure 2.4 Try generating some secret keys. Remember that the size of the key depends on the size of the chosen prime p. Of
course the keys used in reality are much larger (typically 1024 or even 2048 bits), but this toy example, which allows p to be
between 5 and 499, is a better illustration of the process as its output can be verified by hand.

Diffie-Hellman Key Exchange (3)

p  g  a  b  show secret values  show calculations (with secret values)  [removed] [removed] [removed] [removed]

Figure 2.5 This program is the same as the one above, except that you may now choose a and b yourself.

DLP Brute-Force Search

p  g  A  show output  [removed] [removed] [removed] [removed]

Figure 2.6 This application conducts a brute-force search. Enter a prime number p (up to 100 000), a generator g and a value A and observe
how the discrete logarithm is calculated by trying out possible values for a until the discrete logarithm of A to base g is found. Notice that it
takes longer for larger values of p. For very large values of p, turn off the output. If you do not know a generator g for your selected prime p,
you can calculate it with Figure 2.3.

Figure 2.7 Running time comparison of exponential, sub-exponential and polynomial-time algorithms.