The Discrete Logarithm, Part 1

Given a group $G$, and an element $g\in G$ (the "base"), the discrete logarithm $\log_g(h)$ of an $h\in G$ is an element $x\in G$ such that $g^x = h$ if it exists. Its name "discrete logarithm" essentially means that we are only allowed to use integer powers in the group, rather than extending the definition of exponentiation as with the usual logarithm for the real numbers.

Because of cryptographic applications, usually the discrete logarithm is seen in the world of finite fields or elliptic curves. Here, given a finite field $\F_q$, the discrete logarithm is considered in the multiplicative group $\F_q^\times$. It so happens that this group is cyclic, and hence it must be isomorphic to $\Z/(q-1)$. So, given a $g\in \F_q$ that generates $\F_q^\times$ as a multiplicative group, the discrete logarithm always exists and thus defines a function
$$\log_g: \F_q^\times\longrightarrow \Z/(q-1).$$

Example. Let's consider the finite field $\F_7$. The element $3\in \F_7$ generates the multiplicative grouop $\F_7^\times$. In $\F_7$, we have $3^4 = 4$ so that $\log_3(4) = 4$.

Unlike the usual complex-number logarithm, the discrete logarithm is hard to compute. Of course, this statement is vague because for real and complex numbers, computing the logarithm means writing down a rational approximation to some predefined accuracy. With the discrete log, we want the answer exactly.

The discrete logarithm problem (DLP) refers to the problem of solving for $x$ in an equation of the form $g^x = h$. When people speak of solving the discrete logarithm problem, there is a specific group like $\F_p^\times$ that they have in mind.

What can we do with the discrete log?

Whit Diffie and Marty Hellman came up with a way for two parties (Alice and Bob) to exchange a secret key while communicating in public, even though this mind sound impossible at first. Alice and Bob first pick a prime number $p$ and a base $g$. Alice and Bob each choose exponents $a$ and $b$ respectively that they do not share. However, Alice gives Bob $g^a$ and Bob gives Alice $g^b.$ Now Alice can compute $(g^b)^a = g^{ab}$. Bob can also compute $(g^a)^b = g^{ab}$, so they now both have $g^{ab}$.

The fascinating thing about this is that they now both have the number $g^{ab}\in\F_p$. However, the outsider eavesdropper Eve, who can only view their public communication, cannot readily compute $g^{ab}$. Of course, if Eve could solve the discrete logarithm problem very quickly in $\F_p^\times$, then she could also compute $a$ and $b$ from the publicly exchanged $g^a$ and $g^b$. If $p$ is chosen sufficiently large and $g$ is chosen so that it has large prime order, then it will take a long time to compute $a$ and $b$ just by knowing $g^a$ and $g^b$.

This protocol is known as the Diffie-Hellman Key Exchange because the number $g^{ab}$ known by only Alice and Bob can now be used as a key for a symmetric encryption algorithm, though in actual practice there is a better way of exchanging keys for this sort of practice. Or maybe they could use $g^{ab}$ as a combination to a safe or something. The Diffie-Hellman Problem (DHP) is the problem of computing $g^{ab}$ (the secret key) just by knowing $g^a, g^b$, and of course the base $g$ and the prime $p$.

By what we've already observed, if you can solve the discrete log problem (DLP) easily, then you can solve the Diffie-Hellman problem (DHP). There are a whole host of other problems with the DHP besides the potential that someone with find an easy way to solve the DLP. For example: if Eve can manipulate the communications channel arbitrarily then she could substitute fake values for $g^a$ and $g^b$ while they are being exchanged and therefore lead Alice and Bob to believe that they are in possession of the secret key even though eve has it too.

The ElGamal Encryption Scheme

The Diffie-Hellman key exchange is a way of two parties agreeing upon a secret key, but this does not allow them to exchange arbitrary messages without an additional symmetric encryption scheme that uses the agreed upon private key.

There is another way to use modular exponentiation to exchange a message, which implements the idea of public-key encryption. In this scheme, Alice and Bob still agree upon a base and a large prime $p$. If Alice wants to receive messages, she now chooses a private exponent $a$ and shares $g^a$ with Bob. To send a message $m$ to Alice, Bob now chooses a temporary key $k$ and sends Alice the pair $(g^k,mg^{ak})$, she can compute the quantity $g^{ak}$ because she knows $a$, and therefore she can compute $g^{-ak}$. Multiplying this by $mg^{ak}$ recovers $m$.

The temporary key $k$ has to be chosen because $g^a$ is public, and therefore $m$ can be found from the quantity $mg^a$ simply by inverting $g^a$. Again, the security of this system depends on the value $g^{ak}$, which only Bob and Alice know. In effect, the Elgamal encryption protocol could be thought of as two steps: Alice and Bob exchange $g^{ak}$ through the Diffie-Hellman key exchange, and then Bob uses $g^{ak}$ is used to scramble the message. Therefore, if you can solve the discrete logaritm problem then you can crack the Elgamal encryption scheme. It's also true that if you can crack Elgamal, then you can crack the Diffie-Hellman key exchange by cracking the message $(g^{-b},1)$.

Difficulty

To summarise what we've already mentioned, solving the discrete log problem (DLP) solves the DHP and the ElGamal encryption scheme and the latter two are equivalent in difficulty: cracking ElGamal allows you to solve the DHP and a solution to DHP gives you the ability to find $g^{ak}$, thereby allowing you to decrypt the encrypted message $(g^k,mg^{ak})$. If we use $S(x)$ to denote "x can be solved", then we have:

Here, the arrows indicate implication. Of course, what "to be solved" means different things in different contexts. From a practical context, it means that if someone can solve a DLP on your encryption system in a couple of hours, then you're toast.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.