Number of Keys when y is Forced (Version One: Random Experiments)

An Interactive Applet powered by Sage and MathJax.

(By Alyssa Vorpahl and Prof. Gregory V. Bard)


This page will discuss an interesting modification of the Diffie-Hellman protocol. Namely, what are the security consequences if Bob's y-value is forced to be a particular value, instead of being chosen randomly?


In this example, suppose that Bob has been entrusting his y generation to a random number generation program, method, function, or procedure. Now suppose that something has gone wrong with that program due to a malicious update, and now it always spits out the same number. (For the sake of example, you choose what it spits out.)

Assuming Alice is still generating purely random numbers within the acceptable range, will their shared secret still be random? Furthermore, how will this impact the number of possible keys? After all, an attacker could loop through all the possible keys. Therefore, if there are far fewer keys than expected, this will make it much easier for an attacker to guess the shared secret.


Once you load the applet, there will be four sliders: one to control the modulus, one to control the generator g, one to set Bob's y value, and one to set the number of trials. For each trial, a random x will be chosen and gxy will be calculated. (Note that for the last slider, the chosen k value tells the applet to run 2k trials, so that k=8 indicates 256 trials, for example.) If 'verbose' is left unchecked, then it will hide the results of the individual trials. If 'verbose' is checked, then it will display the results of eacy trial, but this option is disabled for k values greater than 8.

The results of each trial will be checked against a list of keys seen so far; if the result has not been seen before, it will be added to the list. Once all trials are complete, the number of keys found (as well as their values) will be displayed.

Last modified by Alyssa Vorpahl on December 8th, 2018. Updated to Python 3 by Prof. Bard on April 10th, 2020.