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, so it is always possible to construct an analog of exponentiation) 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 many applications including 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 general solution method that is not catastrophically expensive is known. Quite a few mathematicians have tackled this problem. No efficient general method has been found and mathematicians do not expect that one will be. It seems likely no efficient general solution to either of the main variants exists.

Note, however, that no-one has proven such methods do not exist. Also, there is at least one efficient solution for a special case . If an efficient general 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.

At least one recent paper suggests that a break of discrete log is a real risk [1]. It is not clear whether that contention is correct, but the claim that such a break would have very serious consequences seems beyond dispute.

Discrete log and factoring

A solution to the discrete log problem modulo an integer would imply a solution for integer factorisation, so it would also break the RSA cryptosystem which is based on that problem. Similar things hold in other fields; a solution to the elliptic curve version of discrete log would break the elliptic curve 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; with that known, factoring is straightforward. For example, suppose we want to factor 77 and have found 2³⁰ == 1 mod 77. This is equivalent to (2¹⁵+1)(2¹⁵-1) == 0 mod 77 and it is easy to compute 2¹⁵ == 43 mod 77, so we get 42*44 == 0 mod 77 and then the factors gcd(42,77) = 7 and gcd(44,77) = 11. There is a special case (when 2^x/2 == 1 mod p) where you need a bit more calculation before the factors fall out, but never an onerous amount.