The discrete logarithm problem
Let p be a (large) prime. Then, there exists a primitive element g. This
means that every nonzero element of Fp is equal to some power of g.
In particular, gp−1 = 1 by Fermat’s little theorem, and no smaller power
of g is equal to 1.
Equivalently, the list of elements
1, g, g2, g 3 , . . . , gp−2 ∈ F∗p
∗
is a complete list of the elements in F p in some order.
Definition 1. Let g be a primitive root for Fp and let h be a nonzero element of
Fp.
The Discrete Logarithm Problem (DLP) is the problem of finding an exponent
x such that
gx ≡ h (mod p).
The number x is called the discrete logarithm of h to the base g and is denoted by
logg(h).
Remark: Fermat’s little theorem tells us that gp−1 ≡ 1 (mod p).
Hence if x is a solution to gx = h, then x + k(p − 1) is also a solution for
every value of k, because
gx+k(p−1) = gx · (gp−1)k ≡ h · 1k ≡ h (mod p).
Thus logg(h) is defined only up to adding or subtracting multiples of p-1. In
other words, logg(h) is really defined modulo p-1. —
∗
It is not hard to verify that logg gives a well-defined function logg : F p −→
Z/(p − 1)Z.
Sometimes, for concreteness, we refer to “the” discrete logarithm as the integer
x lying between 0 and p − 2 satisfying
the congruence gx ≡ h (mod p).
Example 1 . The number p = 56509 is prime, and one can check that g = 2
is a primitive root modulo p.
How would we go about calculating the discrete logarithm of h = 38679?
Ans: The only method that is immediately obvious is to compute
22, 23, 24, 25, 26, 2 7 ,... (mod 56509)
until we find some power that equals 38679.
It would be difficult to do this by hand, but using a computer, we find that
logp(h) = 11235.
You can verify this by calculating 2 11235 mod 56509 and checking that it is
equal to 38679.
///
Diffie–Hellman key exchange
The Diffie–Hellman key exchange algorithm solves the following dilemma. Alice
and Bob want to share a secret key for use in a symmetric cipher, but their only
means of communication is insecure. Every piece of information that they
exchange is observed by their adversary Eve. How is it possible for Alice and
Bob to share a key without making it available to Eve?
It was a brilliant insight of Diffie and Hellman that the difficulty of the
∗
discrete logarithm problem for F p provides a possible solution.
The Diffie–Hellman key exchange algorithm is summarized in Table below:
Public Parameter Creation
A trusted party chooses and publishes a (large) prime p
∗
and an integer g having large prime order in F p.
Private Computations
Alice Bob
Choose a secret integer a. Choose a secret integer b.
Compute A ≡ ga (mod p). Compute B ≡ gb (mod p).
Public Exchange of Values
Alice sends A to Bob −−−−−−−−−−−−−−−−−−→ A
B ←−−−−−−−−−−−−−−−−−− Bob sends B to Alice
Further Private Computations
Alice Bob
Compute the number Ba (mod p). Compute the number Ab (mod p).
The shared secret value is Ba ≡ (gb)a ≡ gab ≡ (ga)b ≡ Ab (mod p).
Example 2.7. Alice and Bob agree to use the prime p = 941 and the
primitive root g = 627.
Alice chooses the secret key a = 347 and computes A = 390 = 627347
≡
(mod 941).
Similarly, Bob chooses ≡the secret key b = 781 and computes B = 691=627781
(mod 941).
Alice sends Bob the number 390 and Bob sends Alice the number 691.
Both of these transmissions are done over an insecure channel, so both A =
390 and B = 691 should be considered public knowledge.
The numbers a = 347 and b = 781 are not transmitted and remain
secret.
Then Alice and Bob are both able to compute the number
470 ≡ 627347·781 ≡ Ab ≡ Ba (mod
941),
so 470 is their shared secret.
///
Remark: Suppose that Eve sees this entire exchange. She can reconstitute
Alice’s and Bob’s shared secret if she can solve either of the congruences
627a ≡ 390 (mod 941) or 627b ≡ 691 (mod 941),
since then she will know one of their secret exponents. As far as is known,
this is the only way for Eve to find the secret shared value without Alice’s or
Bob’s assistance.
Definition 2. Let p be a prime number and g an integer. The Diffie–Hellman
Problem (DHP) is the problem of computing the value of gab (mod p) from the
known values of ga (mod p) and gb (mod p).
It is clear that the DHP is no harder than the DLP. If Eve can solve the
DLP, then she can compute Alice and Bob’s secret exponents a and b from the
intercepted values A = ga and B = gb, and then it is easy for her to compute
their shared key gab. (In fact, Eve needs to compute only one of a and b.)
But the converse is less clear. Suppose that Eve has an algorithm that
efficiently solves the DHP.
Can she use it to also efficiently solve the DLP? The answer is not known.
