Number of Keys when y is Forced (Version Two: Exact)

An Interactive Applet powered by Sage and MathJax.

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

Overview

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

Discussion

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.

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.

In the previous page, we saw what happens if y is fixed, and if x is chosen randomly. That gives us a good statistical idea of what is going on if we use a large number of random trials. The fewer examples we use, the more we risk getting estimates that are misleading. However, that approach - often called a "Monte Carlo Approach" - is not necessary in this case. We can do better by considering each possible x exactly once. Then we have a probability distribution for g^xy, and it is exact. Our histogram does not represent the outcome of an experiment, but rather the true probability distribution.

Instructions

Once you load the applet, there will be three sliders: one to control the modulus, one to control the generator g, and one to control the y value that will be checked. Then, an array with length equal to the number of possible keys will be created to count how many times each key is generated. Afterwards, for each possible x value, the key g^xy will be calculated, then the appropriate listing in the counting array will be incremented.

Once each x value has been used, the number of times each key was generated will be printed, as long as that value is nonzero. Then, the total number of generated keys is printed at the very end.

There is also a check box at the start to say whether or not you want to show a histogram of the keys at the bottom instead of the written listing.

Hint: Consider p=101, g=2, y=25 as well as p=101, g=2, y=29. Do the two y values producing similar results, or very different results? See if you can reproduce this behavior with p=197, g=2, and any two y values that you think are good.