DISCRETE LOGARITHM (CONTINUED)

MATH 195

An example

Here is a baby example of a Diffie-Hellman exchange. Recall A picks an integer a (and keeps it secret), computes g^{a}, and sends g^{a} to B. Similarly, B picks an integer b (and keeps it secret), computes g^{b}, and sends g^{b} to A. A computes h = (g^{b})^{a} ∈ G, B computes h = (g^{a})^{b} ∈ G, and h is the common secret key. E given G, g, g^{a}, g^{b} hopefully cannot compute g^{ab}.

Take G = 𝔽_{32}^{∗}, 𝔽_{32} = 𝔽_{2}[X]/(X^{5} + X^{2} + 1), g = 00010 = X is a primitive root. Note that 𝔽_{32} ≠ ℤ/32ℤ!

A picks a = 4, g^{a} = X^{4} = 10000; B picks b = 5, g^{b} = X^{5} = X^{2} + 1 = 00101. We have h = (00101)^{4} = ((00101)^{2})^{2} = (10001)^{2} by the freshperson’s dream, and this is 100000001. We reduce this against X^{5} + X^{2} + 1 = 100101 and get the remainder 01100 = X^{3} + X^{2}:

1 0 0 0 0 0 0 0 1
1 0 0 1 0 1
1 0 0 1 0 1
0 1 1 0 0

In the same manner, we verify that (10000)^{5} = 01100 as well.

ElGamal

Now we describe the cryptosystem of Taher ElGamal (1985) based on G, g. We have P = G, C = G × G, and let R = {1, 2, …, m − 1} be the space of

random numbers. Prior to all communication, B picks an integer b (and keeps it secret) and makes g^{b} public. This is the public key.

Suppose A wants to send a message x to B, where we assume x ∈ G. A picks an integer a (and keeps it secret) and she sends g^{a} and x·(g^{b})^{a}. This is the encryption map:

K × P × R ⟶^{E} C
(k = g^{b}, x, a) ↦ E_{k,a}(x) = (g^{a}, x(g^{b})^{a}).

B recovers x by computing

x · (g^{b})^{a}((g^{a})^{b})^{−1} = x.

Decryption can be described as:

K × C ⟶^{D} P
(k = g^{b}, (f, y)) ↦ D_{k}(f, y) = y · (f^{b})^{−1}

This is some of the material covered April 18–23, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Example. Let G = 𝔽_{32}^{∗} as above, g = X = 00010. Take b = 5, k = g^{b} = 00101. Let us send the message x = 10101, a = 4. A sends to B: g^{a} = 100000 together with

x(g^{b})^{a} = (10101) · (01101) = 00111.

B computes

(00111) · (10000)^{−5}.

We cheat a little: 10000 = X^{4} so (10000)^{−5} = X^{−20}. We have X^{31} = 1 since #𝔽_{32}^{∗} = 31, so X^{−20} = X^{11} = 100000000000, which reduces to 00111, hence

(00111) · (00111) = (00111)^{2} = 10101

by the freshperson’s dream, which is the correct message.

The problem faced by E: Knowing G, g, g^{b}, g^{a}, xg^{ab} but not b, a, she wants to compute x. We compare this to the previous problem faced by E (in Diffie-Hellman): knowing G, g, g^{a}, g^{b}, she wants to compute g^{ab}. It is clear that the ability to solve one of these problems is equivalent to the ability to solve the other (if you can compute x knowing xg^{ab}, you can divide to get g^{ab}, and if you can compute g^{ab} knowing xg^{ab}, you can divide to get x).

One possible improvement: send g^{a} once and for all.

Algorithms for Computing Discrete Logarithms

Recall that the discrete logarithm problem given a group G and an element g ∈ G is the problem of finding log_{g} h upon input h. Recall log_{g} h = i if h = g^{i} (i ∈ ℤ/mℤ, m = ord(g)), and log_{g} h is undefined if h ∉ ⟨g⟩.

Method 1 (Complete enumeration). Compute g^{0} = 1, g^{1} = g, g^{2} = g · g, g^{3} = g · g^{2}, …, g^{n+1} = g · g^{n} until you encounter h. If you find g^{n} = h then n = log_{g} h. If before finding h you find g^{m} = 1, then h ∉ ⟨g⟩. This algorithm is naive, and takes time m/2 ∼ m operations in G, which in this case are all multiplications.

This is fast for small m, and slow for large m.

Method 2 (Baby step-giant step). Pick a positive integer M with M^{2} ≥ m = ord(g), e.g. ⌈\sqrt{m}⌉ (or the squareroot of any upper bound on the order of g or of the group will work).

Compute h, h · g, h · g^{2}, …, h · g^{M−1} (the baby steps) and g^{M}, g^{2M}, …, g^{M^{2}} (the giant steps). Note that we step by 1 in g for the baby steps and by M in g for the giant steps. We check whether these two sequences have a member in common. If so, then h·g^{i} = g^{jM}, so h = g^{jM−i} and log_{g} h = jM −i. If they do not, then log_{g} h doesn’t exist.

Example. Let G = 𝔽_{p}^{∗}, p = 29, g = 2, h = 3. We take M = ⌈\sqrt{29}⌉ = 6. We compute the baby steps

3, 6, 12, 24 = −5, −10, −20 = 9

(notice that we double every time) and the giant steps

2^{6} = 6, 6 · 6 = 7, 13, …

but we see already that 6 is in common to both of these lists, so 2^{6} = 3 · 2 in 𝔽_{29}, so 3 = 2^{5} in 𝔽_{29}.

Notice that we must compare two lists. If one does this naively (by comparing every two pairs of elements), then one requires time O(M^{2}). However, by keeping the list sorted (using a quicksort algorithm or some such), then the time required is O(M) (or perhaps slightly faster) with space O(M).

Here is a proof that if log_{g} h exists, the algorithm will find it. Say h = g^{a}, 0 < a ≤ m. Then a ≤ M^{2}, so the least multiple jM of M that is ≥ a is ≤ M^{2}, so 0 < j ≤ M. Write jM = a + i. Then i ≥ 0 and i < M (otherwise (j − 1)M ≥ a, contradicting the choice of j). Hence

hg^{i} = g^{a}g^{i} = g^{a+i} = g^{jM}

so the sequences intersect, and the algorithm finds the logarithm.

If you want to find the least positive a with h = g^{a}, pick j minimal such that g^{jM} is in the first sequence and given j, pick i maximal such that g^{jM} = hg^{i}. Applying this method to h = 1, it will find the least positive a with g^{a} = 1, in other words, it will determine m.

If G is not required to be abelian, it may be wise to first test whether hg = gh. If hg ≠ gh, then log_{g} h does not exist! (If it did, and h = g^{a}, then hg = g^{a}g = g^{a+1} = gh.) If hg = gh, then ⟨g, h⟩ is an abelian subgroup of G, so it is enough to have crytographic systems built upon abelian groups in some sense.

Method 3 (Pohlig-Hellman). The input: G, g, m = ord(g), m = m_{1}m_{2} … m_{t}, m_{i} ∈ ℤ_{>0} positive integers. It is important to know the order of g and a factorization of this order. The output is log_{g} h, with time “dominated by” the quantity

max\{\sqrt{m_{1}}, \sqrt{m_{2}}, …, \sqrt{m_{t}}\}.

(We are using the following fact from algebra: we have ⟨1⟩ ⊂ ⟨g^{m_{t}}⟩ ⊂ ⟨g⟩, where now g^{m_{t}} has order m′ = m/m_{t}, so we may compute the logarithm in a smaller group.)

Here is the algorithm, by steps:

(1) Compute m′ = m_{1}m_{2} … m_{t−1} = m/m_{t}.

(2) Use the baby step-giant step method (or complete enumeration) to find a = log_{g^{m′}} h^{m′}. If it doesn’t exist, then log_{g} h doesn’t exist either, and the algorithm stops. [Note: h = g^{a}, where a is taken modulo m, becomes h^{m′} = (g^{m′})^{a}, where now a is taken modulo m_{t}.]

(3) Compute hg^{−a}. If it is equal to 1, then we are done at this stage: h = g^{a}.

(4) Use the Pohlig-Hellman method with input

G, g^{m_{t}}, m′ = m_{1}m_{2} … m_{t−1}, hg^{−a},

to compute b = log_{g^{m_{t}}} (hg^{−a}) (in time essentially max\{\sqrt{m_{1}}, …, \sqrt{m_{t−1}}\}). Output log_{g} h = m_{t}b + a if b exists, and if it does not, then the log_{g} h does not exist either.

The correctness of this method relies on the following claim:

Claim. We have as sets {x ∈ ⟨g⟩ : x^{m′} = 1} = ⟨g^{m_{t}}⟩.

Proof. Suppose that x = g^{c} with x^{m′} = g^{cm′} = 1. Then cm′ is divisible by m = m′m_{t}, so

\frac{cm′}{m} = \frac{c}{m_{t}}

are both integers, and hence c is divisible by m_{t}. This proves one inclusion, and the other is clear: any element g^{m_{t}d} is a power of g with (g^{m_{t}d})^{m′} = g^{md} = 1. □

Example. Given G, and g ∈ G, m = ⟨g⟩ = m_{1}m_{2} … m_{t}, t ≥ 1, and h ∈ G, we compute log_{g} h by reducing the problem to a computation involving m′ = m_{1} … m_{t−1}, h^{m′}, g^{m′}.

Take G = 𝔽_{101}^{∗}, with g = 2 ∈ G, m = 100 = 10 · 10, h = 3. We have m′ = 10, and we compute

h′ = h^{m′} = 3^{10} = ((3^{2})^{2} · 3)^{2} = (−60)^{2} = 3600 = −36.

We also compute g′ = g^{m′} = 2^{10} = 1024 = 14 = g^{m′}. Note that since g has order 100 (it is a primitive root), g^{m′} has order 10.

Now we compute log_{g^{m′}} h^{m′} using the baby step-giant method. We need M^{2} ≥ m_{t}, so M = 4. We compute h′, h′g′, …, (h′)(g′)^{M−1}, which is the sequence

−36, −36 · 14 = 1, 1 · 14 = 14, 14 · 14 = −6.

Now we compare it to the sequence (g′)^{M}, (g′)^{2M}, …, (g′)^{M^{2}}, and get

14^{4} = 36, 36^{2} = −17, −17 · 36 = −6

so bingo (!): we see that 14^{12} = −36 · 14^{3}, so −36 = 14^{9}. In other words,

a = log_{g′} h′ = log_{14}(−36) = 3M − 3 = 9.

Of course, since −36 · 14 = 1, we know already −36 = 14^{−1} = 14^{9}, since 14 has order 10. In fact, it is easier to work with a = −1, since we only care about a modulo 10.

Now we compute hg^{−a} = 3 · 2^{−(−1)} = 6 ≠ 1. We compute g^{m_{t}} = 2^{10} = 14, and m′ = 10, and hg^{−a} = 6. We compute b = log_{g^{m_{t}}} (hg^{−a}) = log_{14} 6. We can do this again using baby step-giant step: if we start computing, we get 6, 6 · 14 = −17, which already occurs in our second list (which is unchanged) as 36^{2} = 14^{8}, so 14^{7} = 6, or b = 7.

We then output log_{g} h = log_{2} 3 = m_{t}b + a = 70 − 1 = 69. Whew! We check our work:

2^{4} = 16, 2^{8} = 256 = −47, …, 2^{6}4 = 1089 = −22

and 2(16)(−22) = 2(−352) = 2(−49) = −98 = 3.

In fact, there are (much) better discrete logarithm algorithms that apply to 𝔽_{p}^{∗} (p prime) (and other similar multiplicative groups). However, on groups coming from (general) elliptic curves nothing essentially better than baby step-giant step or Pollig-Hellman is known.

Conclusion: for a pair G, g to be secure for use in a discrete logarithm-based cryptosystem, it is desirable that the number m = ord(g) has a large prime factor. There are three methods for construction G, g, m.

(1) The Mersenne-prime method: Pick p prime such that 2^{p} − 1 is prime, pick f ∈ 𝔽_{2}[X] irreducible of degree p, and use G = 𝔽_{2^{p}}^{∗}, 𝔽_{2^{p}} = 𝔽_{2}[X]/(f), g = X, m = 2^{p} − 1. (Can also use p with 2^{p} − 1 prime up to a few small factors.) We have the following amazing fact:

Fact. If ℓ is a prime number, 2^{ℓ} − 1 also prime, and X^{ℓ} + X + 1 ∈ 𝔽_{2}[X] irreducible, then X^{2^{ℓ}} + X + 1 is irreducible in 𝔽_{2}[X].

Therefore with ℓ = 2, 2^{2}−1 = 3 is prime so X^{2}+X +1 is irreducible; now with ℓ = 3, 2^{3} − 1 = 7 is prime, so X^{3} + X + 1 is irreducible, continuing on with 2^{7} = 127 and 2^{127} − 1 = 170141183460469231731687303715884105727 prime, we find that X^{17...27} + X + 1 is irreducible!

(2) The kr + 1 method: Pick a large prime r, pick a small k such that kr + 1 has no small prime factors (so, e.g. we insist k ≡ 0 (mod 2), k ≢ −r^{−1} (mod 3), and so on). Test whether 2^{k} ≢ 1 (mod kr+1), 2^{kr} ≡ 1 (mod kr+ 1). If not, try another k, and if yes, then take p = kr + 1, which is prime if k ≤ r, and G = 𝔽_{p}^{∗}, g = 2^{k}, and m = r.

Fact. If r is a prime number and k ∈ ℤ, 0 < k ≤ r. Put p = kr + 1. Then p is prime if and only if there exists a ∈ ℤ such that a^{k} ≢ 1 (mod p), and a^{kr} ≡ 1 (mod p).

(3) Elliptic curves. To be discussed in the next lecture.