Cryptography: Theory and Practice:Other Public-key Cryptosystems | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Example 5.5

Suppose p = 19, α = 2 and β = 6. Since the example is so small, we can tabulate the values of L₁ (γ) and L₂ (γ) for all . (In general, L₁ can be computed efficiently using Euler’s criterion and L₂ is an oracle.) These values are given in Table 5.1. The algorithm now proceeds as shown in Figure 5.7.

Hence, log₂ 6 = 1110₂ = 14, as can easily be verified.

It is possible to give formal proof of the algorithm’s correctness using mathematical induction. Denote

For i ≥ 0, define

Also, define β₀ to be the value of β in step 2 of the algorithm; and, for i ≥ 1, define β_i to be the value of β in step 11 during the ith iteration of the while loop. It can be proved by induction that

**Table 5.1** Values of L₁ and L₂ for p = 19, α = 2
γ	L₁(γ)	L₂(γ)	γ	L₁(γ)	L₂(γ)	γ	L₁(γ)	L₂(γ)
1	0	0	7	0	1	13	1	0
2	1	0	8	1	1	14	1	1
3	1	0	9	0	0	15	1	1
4	0	1	10	1	0	16	0	0
5	0	0	11	0	0	17	0	1
6	0	1	12	1	1	18	1	0

Figure 5.7 Computation of log₂ 6 in

Figure 5.8 The discrete logarithm problem in

for all i ≥ 0. Now, with the observation that

it follows that

i ≥ 0. Since

the algorithm is correct. The details are left to the reader.

5.2 Finite Field and Elliptic Curve Systems

We have spent a considerable amount of time looking at the Discrete Logarithm problem and the factoring. We will see these two problems again and again, underlying various types of cryptosystems and cryptographic protocols. So far, we have considered the Discrete Logarithm problem in the finite field , but it is also useful to consider the problem in other settings. This is the theme of this section.

The ElGamal Cryptosystem can be implemented in any group where the Discrete Log problem is intractible. We used the multiplicative group , but other groups are also suitable candidates. First, we phrase the Discrete Logarithm problem in a general (finite) group G, where we will denote the group operation by . This generalized version of the problem is presented in Figure 5.8.

It is easy to define an ElGamal Cryptosystem in the subgroup H in a similar fashion as it was originally described in . This is done in Figure 5.9. Note that encryption requires the use of a random integer k such that 0 ≤ k ≤ |H| - 1. However, if Alice does not know the order of the subgroup H, she can generate an integer k such that 0 ≤ k ≤ |G| - 1, and encryption and decryption will work without any changes. Also note that the group G need not be an abelian group (of course H is abelian since it is cyclic).

Figure 5.9 Generalized ElGamal Public-key Cryptosystem

Let’s now turn to the “generalized” Discrete Log problem. The subgroup H generated by any α ∈ G is of course a cyclic group of order |H|. So any version of the problem is equivalent, in some sense, to the Discrete Log problem in a cyclic group. However, the difficulty of the Discrete Log problem seems to depend in an essential way on the representation of the group that is used.

As an example to illustrate a representation where the problem is easy to solve, consider the additive cyclic group , and suppose gcd(α, n) = 1, so α is a generato, of . Since the group operation is addition modulo n, an “exponentiation” operation, α^a, corresponds to multiplication by a modulo n. Hence, in this setting, the Discrete Log problem is to find the integer a such that

Since gcd(α, n) = 1, α has a multiplicative inverse modulo n, and we can compute α^-1 mod n easily using the Euclidean algorithm. Then we can solve for a, obtaining

Table of Contents