An Interactive Applet powered by Sage and MathJax.
(By Alyssa Vorpahl and Prof. Gregory V. Bard)
This page will discuss the discrete logarithm problem, a problem that is very important in modern cryptography. Computing the discrete logarithm is assumed to be hard. Moreover, if an efficient way to solve discrete logarithms were to be found, it would render many current tools in cryptography useless - including the Diffie-Hellman Key Exchange protocol.
The discrete logarithm problem requires two things: That you are working with a group G, and that g is a generator of G. Then, for a given y in G, can you find a positive integer x such that gx = y? By the way, this problem can be done in many different groups G, but we will discuss the integers mod p for simplicity. In cryptography, elliptic curves are often used for the group G, as well as the integers mod p.
Notably, when the group you're working with is Zp for a very large value of p, and you consider multiplication to be the group's operation, finding the required integer x (given some G, a generator g in G, and some y in G) is difficult. That's why the Diffie-Hellman Key Exchange protocol is trusted.
If there were a fast algorithm to determine the unique solution to this problem, it would prove problematic for several tools of today's cryptography. However, there are ways to solve it that are not fast enough to be a problem.
First, we will explore how difficult this problem is to solve by brute force. We will perform a number of modular exponentiations (in worst case) equal to the size of G. Later we will see how, with the Baby-Step/Giant-Step method, this can be reduced to a number of modular exponentiations proportional to the square root of the size of G, which is shockingly smaller for moderately large G. Yet, cryptography uses huge groups G, so even the Baby-Step/Giant-Step method is infeasible.
In this context, brute-force attack means trying every possible x value. Given the group G, the desired y in G, and the generator g in G, we can loop through each x value from 0 to Phi(p) until we find an integer x where gx> = y mod p.
By the way, the discrete logarithm is not unique. Suppose gx = y and phi = Phi(p). Because xphi = 1 mod p for any x coprime to p, we have the following behavior:
which means that x, x+phi, x+2*phi, ... are all solutions of the discrete logarithm.
So, discrete logarithms are not unique when the answer is considered an integer. However, discrete logarithms are unique when the answer is considered an integer mod phi.
Once you load the applet, there will be 3 sliders: one to control the desired y value, one to control the modulus p for the group Zp, and one to control the generator g. Once all of the initial conditions are verified (the modulus must be a prime, g must generate Zp, and 0 < y < p) to ensure that the discrete logarithm problem has a solution.
Once that has been verified, every possible x value will be looped through until gx = y. That x will be flagged as the solution, and the loop will end.