Discrete Logarithms and Key Exchange

Assume that in RSA only the modulus n is public but the encryption exponent e is kept secret. Assume, further, that the cryptanalyst has intercepted at least one pair (w, w^e) and tries to break the system, that is, to find the decryption exponent d by the "known plaintext" approach. The cryptanalyst then faces the problem of finding the logarithm of w to the base w^e (modn). This is a special case of computing discrete logarithms.

Many cryptosystems, public-key or otherwise, based on discrete logarithms have been proposed. When used as a basis for a cryptosystem, the computation of discrete logarithms is assumed to be intractable. If we consider the equation a^x = y for positive real numbers, the difficulty of determining x from a and y to prescribed accuracy is approximately the same as determining y from a and x. Both problems amount to multiplications, divisions and table look-up dealing with precomputed logarithms to any base. As regards discrete logarithms, the situation is entirely different. Modular exponentiations can be carried out reasonably fast-we already have discussed this and presented numerous examples. The presumable intractabil­ity of the inverse operation, taking discrete logarithms, was used already in Section 3.5.

The general notion of a discrete logarithm can be formulated as follows. Let g be an element of a finite group G and let y be another element of G. Then any integer x such that g^x = y is called a discrete logarithm of y to the base g. Clearly, every element y of G has a discrete logarithm to the base g iff G is cyclic with the generator g. For instance, in the multiplicative group of positive integers modulo 7 only the numbers 1, 2, 4 have a discrete logarithm to the base 2, whereas all numbers have a discrete logarithm to the base 3 according to the table

Tables of discrete logarithms in simple cases were considered also in Section 3.5. Of course, groups of small cardinality present no computational difficulties. There are also efficient algorithms of computing discrete logarithms in some special cases, such as the algorithm of D. Coppersmith, [Cop], for finite fields F(2^h).

However, in the general case the known algorithms for computing discrete loga­rithms in groups of order m are roughly of the same complexity in terms of m as the algorithms for factorizing m. Perhaps the best general-purpose algorithm, due to Silver, Pohlig and Hellman, [PoH] and [Odl], works very efficiently if all prime factors of m are small. The algorithm is described in the following example.

Example 4.3. Let F(q), q = r^h, be a finite field. Consider discrete logarithms to the base g, where y is a generator for F*{q).

For each prime divisor pot q- 1, we compute the numbers

a(i, p) = (g*^q-^l)'^p, mod q), 0 <i<p.

If every p dividing q — 1 is small, the size of the precomputed table consisting of the auxiliary numbers a(i, p) is manageable.

For instance, consider F(181) and g = 2. (2 is indeed a generator.) Now 180 = 2² • 3² • 5 and the table of the numbers a(i, p) looks as follows.

Let us now compute the discrete logarithm z of 62 to the base 2. In general, if q — 1 = 77p" then, to find the discrete logarithm x of y to the base g, it suffices to find (x, mod p") for each p in the prime factorization of q — 1. Using the Chinese Remainder Theorem, x is then easily computed from the values (x, mod p").

To compute (x, mod p"), we consider the representation of this number to the base p:

(x, modp^a) = x₀ + x,p 4- . . . + x^-ip"^-1 , 0 < Xj < p — 1 .

In the example we consider the factor p" = 3² and write (z, mod 9) = x₀ + 3x_r To find x₀, we compute the number modq) which equals a(i, p), for some /.

We choose x₀ = i. In the example (62⁶⁰, mod 181) = 48 and, hence, x₀ = 1. This works in general because (gmodq) = 1 and, hence,

y„- DIP _s gXto-DlP = gXOta- DIP = _{a(Xo; p) (mod} ^

To obtain x_l5 we compute first the inverse g~^xo of g^x" (modq) and consider

y i ⁼ yg ~^xo- if now

(/r^l)lp2, mod q) = a(i,_P), then x_l = I. To obtain x₂, we consider the number y₂ = yg~^xo~^x'^p and compute

(>><?-'"p³,modg). The procedure is carried on until (x, mod p") is found.

Returning to the example, we find y_l = 31. This implies that (y{^80/9 , mod 181)= 1

and, hence, x, = 0. Altogether z = 1 (mod 9).

Consider next the factor p" = 2². Now we have to determine x₀ + 2x₁. (We use the same x-notation for the unknowns.) Since (62⁹⁰, mod 181) = 1, we conclude that x₀ = 0. Now y_l = y = 62 and (62⁴⁵, mod 181) = 1, whence x_x = 0 and z = 0 (mod 4).

Consider, finally, the factor p" = 5¹. Now there is only x₀ to be determined. Since (62³⁶, 181)= 1, we conclude that x₀ = 0 and z = 0 (mod 5). The three congruences computed for z now yield the value z = 100. Hence, log 62 = 100.

The same table can be used to compute the discrete logarithm of any y, instead of the value y = 62. Consider the choice y = 30. Denote log 30 = z. For the factor 2², we obtain (30⁹⁰, mod 181) = 180 and, hence, x₀ = 1. Since further (15⁴⁵, mod 181) = 1, we obtain x, =0 and, therefore z= 1 (mod4). For the factor 3², we deduce first x₀ = 0 because (30⁶⁰, mod 181) = 1. Since (30²⁰, mod 181) = 132, we infer further x, = 2 and, consequently, z = 6 (mod9). Finally, for the factor 5, we conclude that x₀ = 3 and, consequently, z = 3 (mod 5) because (30³⁶, mod 181) = 125. The three congruences yield the result log 30 = 33.

The Silver Pohlig-Hellman algorithm is always efficient, with the possible exception that the construction of the table for the numbers a(i, p) might become intractable if q-1 has a large prime factor p. An extreme case is F(q), where q is a safe prime (see Section 4.2). To compute the (q — l)/2 entries in the column for (q — l)/2 amounts to practically the same computational effort as constructing the entire table of logarithms. □

Public-key cryptosystems are, in general, considerably slower to use than classical cryptosystems. Key management problems present in the latter can be taken care of by a suitable protocol for key exchange. Two users agree upon a secret key which is, later on, used as a basis for a classical cryptosystem such as DES or PLAYFAIR. By a suitable encoding the key can always be represented as a num­ber. The earliest and also most frequently used key exchange protocols rely on the intractability of the problem of computing discrete logarithms. We now present briefly some such protocols.

A prime number q and a generator g of F*(q) are publicized among all users. Each user A_{ chooses randomly a number k_v The users keep the numbers fe, secret but publicize the powers (g^ki, mod q). Thus, the following table is public information.

The common key between two users A₍ and Aj (who have had no previous communication) is now the number (g^k'^kj, mod q). The user A_i can compute this number using the number k₍ and the information publicized by A_y The situation is symmetric from the point of view of Aj. The key can be computed also by a cryptanalyst who is able to compute discrete logarithms and, thus, to find either kj or kj from the public information. An active eavesdropper A_m, who is able to insert in the table the number (g^km, modq) to the column for Aj, is capable of establishing a communication link with A_t who wants to communicate with Ay

As an illustration, choose q = 181 and g = 2 (see Example 4.3). Assume that A | (resp. A ₂) has chosen k_] = 100 (resp. k₂ = 33). Hence, the publicized numbers are 62 and 30, respectively. Now both A, and A ₂ are able to compute the common key 48:

(30¹⁰°, mod 181) = (62³³, mod 181) = 48 .

The described system of key exchange is due to Diffie and Hellman, [DH]. It is the oldest proposed system for eliminating the transfer of secret keys but it is still considered to be one of the most secure public-key schemes. By now it has been tested from various angles. It is also practical from the computational point of view. If q is a prime of 1000 bits, then A_i needs only about 2000 multiplications to compute the common key (g*'^kj, mod q). On the other hand, an eavesdropper has to compute discrete logarithms. This requires more than 2¹⁰⁰ operations if any of the currently known algorithms is used.

In the following simple modification of the Diffie-Hellman scheme messages are transmitted directly. Suppose that q, a prime or a power of a prime, is known to all users. Each user A selects a secret integer e_A such that 0 < e_A < q — 1 and (e_A,q — 1) = 1. Furthermore, A computes the inverse d_A of e_A (mod q — 1). The transmission of a message w, 0 < w < q — 1, is carried out in the following three steps.

Step 1: A sends to B: (w^e\ mod <7).

Step 2: B sends to A : (w^e»^p*, mod q).

Step 3: A decrypts with d_A and sends to B: (w^e\ mod q).

This protocol is, in fact, the basic one in public-key cryptography. We have already met several versions of it. It is vulnerable against an active eavesdropper intercept­ing the message in Step 1 and masquerading as B.

In the following modification, due to El Gamal, [E1G], q and a generator g of F*(q) are known to all users. Each user A selects a secret integer m_A, 0 < m_A < q — 1, and publicizes g^m" (viewed as an element of F(q)) as the encryption key. Messages w are sent to A in the form (g^k, wg^k"^A), where k is a random integer chosen by the sender. It suffices for the sender to know g^m\ whereas A can recover w by computing first g~^km*. An eavesdropper faces the problem of computing discrete logarithms.

We present, finally, a general method for key exchange. Basically, the computa­tional complexity will be 0(m) for legal users and 0(m²) for eavesdroppers.

A key space of cardinality m², as well as a one-way function / are known to all users. The inverse function is not known to any of the users. User A (resp. B) randomly chooses m keys x_u ...,x_m (resp. y_lt. .., y_m) and computes the values /(x,),. . . ,/(xJ (resp. /(>>,),. . . , f(y_m)). B sends to A the values /(y,), and A answers by sending to B a value f(xj) that lies among the values sent by B. In the unlikely event that no such f(xj) exists, A computes further values /(x) by choosing new keys x, until a match is found. In order to benefit from the situation, an eavesdropper usually has to compute/(x) for roughly m² values x.

Date: 2015-02-16; view: 708