Factoring and Discrete Logarithms - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 64

for x inafinitefieldwhileknowing a and b iscalledsolvingforthe discretelogarithm. (Thestandardlogarithm
is solving for the exponent in a x = b with real numbers.)
For groups defined by addition of points on elliptic curves, the operation becomes taking a fixed point and
adding it to itself some large number of times, or, for P, computing aP in the elliptic curve group over ( p , +, ×)
for some prime p.
Examples of such algorithms are the Diffie-Hellman key exchange protocol [4], ElGamal public key encryp-
tion [5], and various elliptic curve cryptography methods. To provide a concrete example, the Diffie-Hellman
key exchange protocol on a finite field p works as follows:
1. Two parties, A and B, agree on a finite field p and a fixed generator g.
A generates a secret integer a , and B generates a secret integer b.
2. A → B: g a ∈ p
B can then compute ( g a ) b = g ab in p .
3. B → A: g b ∈ p.
A can then compute ( g b ) a = g ab in p .
Both parties now share a secret element, g ab . An interceptor listening to their communications will know p ,
g , g a , and g b and will strive to find g ab from this information. The easiest way of accomplishing this is to solve
for a = log g ( g a ) or b = log g ( g b ), which is computing the discrete logarithm. However, this problem, it turns out,
is incredibly difficult.
For the following problems, we will consider the case that we are in a finite field p , where p is a prime
number. To make notation consistent, we will consider finding x such that a x = b in our finite field, where a is a
generator and b is the desired result.
Note, however, that the following algorithms are equally applicable on other algebraic structures, such as
elliptic curve groups.
3.5.1 Brute-Force Methods
There are, in general, two brute-force methods for computing a discrete logarithm.
If the number of elements in the field is small enough (less than a few billion or so, at least with today's com-
puters), we can pre-compute and store all possible values of the generator raised to an exponent. This will give
us a lookup table, so that any particular problem will take only as much time as it takes to look up the answer.
Obviously, there are some strong limitations here. With large fields, we can have extremely large tables. At
some point, we aren't going to have enough storage space to store these tables.
At the other end of the spectrum is the second method for computing a discrete logarithm. Here, each time
we want to solve a discrete logarithm problem, we try each and every exponent of our generator. This method
takes the most amount of time during actual computation but has the advantage of no pre-computation.
It's easy to see that there should be a trade-off somewhere, between pre-computing everything or doing all
the work every time. However, we need to be a little clever in choosing that trade-off point. Some people have
put a lot of cleverness into these trade-off points, discussed below (and similar concepts are discussed in later
chapters).