Discrete logarithm

Discrete logarithm is a problem of finding logarithms in a finite field. Given a field definition (such definitions always include some operation analogous to multiplication) and two numbers, a base and a target, find the power which the base must be raised to in order to yield the target.

The discrete log problem is the basis of several cryptographic systems, including the Diffie-Hellman key agreement used in the IKE (Internet Key Exchange) protocol. The useful property is that exponentiation is relatively easy but the inverse operation, finding the logarithm, is hard. The cryptosystems are designed so that the user does only easy operations (exponentiation in the field) but an attacker must solve the hard problem (discrete log) to crack the system.

There are several variants of the problem for different types of field. The IKE protocol uses two variants, either over a field modulo a prime or over a field defined by an elliptic curve. We give an example modulo a prime below.

Given a prime p, a generator g for the field modulo that prime, and a number x in the field, the problem is to find y such that g^y = x.

For example, let p = 13. The field is then the integers from 0 to 12. Any integer equals one of these modulo 13. That is, the remainder when any integer is divided by 13 must be one of these.

2 is a generator for this field. That is, the powers of two modulo 13 run through all the non-zero numbers in the field. Modulo 13 we have:

         y      x
       2^0  ==  1
       2^1  ==  2
       2^2  ==  4
       2^3  ==  8
       2^4  ==  3 that is, the remainder from 16/13 is 3
       2^5  ==  6          the remainder from 32/13 is 6
       2^6  == 12 and so on
       2^7  == 11
       2^8  ==  9
       2^9  ==  5
       2^10 == 10
       2^11 ==  7
       2^12 ==  1

Exponentiation in such a field is not difficult. Given, say, y = 11, calculating x = 7 is straightforward. One method is just to calculate 2^11 = 2048, then 2048 mod 13 == 7. When the field is modulo a large prime (say a few 100 digits) you need a cleverer method and even that is moderately expensive in computer time, but the calculation is still not problematic in any basic way.

The discrete log problem is the reverse. In our example, given x = 7, find the logarithm y = 11. Of course this is easy with a tiny prime like 13; searching for the answer takes few steps and a table of all possible answers takes little memory. However, when the field is modulo a large prime (or is based on a suitable elliptic curve), this is indeed problematic. No solution method that is not catastrophically expensive is known. Quite a few mathematicians have tackled this problem. No efficient method has been found and mathematicians do not expect that one will be. It seems likely no efficient solution to either of the main variants exists.

Note, however, that no-one has proven such methods do not exist. If a solution to either variant were found, the security of any cryptosystem using that variant would be destroyed. This is one reason IKE supports two variants. If one is broken, users can switch to the other.

Discrete log and factoring

A solution to the discrete log problem modulo a integer would imply a solution for integer factorisation, so it would also break cryptosystems such a RSA based on that problem. Similar things hold in other fields; a solution to the elliptic curve version of discrete log would break the elliptic cutve analog of RSA.

Suppose you want to factor N = pq with p, q odd primes, the RSA problem. Use discrete log to solve for x in 2^x == 1 mod N; the totient function is a multiple of x. With that in hand, factoring is straightforward.