next up previous
Next: Digital Signatures Up: Mathematical Models in Public-Key Previous: Cryptosystems Based on Integer

Cryptosystems Based on Discrete Logarithms

  Let tex2html_wrap_inline1334 be a finite field of q elements so that tex2html_wrap_inline1338 for some prime p and integer n. It is well known that the multiplicative group of nonzero elements of tex2html_wrap_inline1334, denoted by tex2html_wrap_inline1346, is a cyclic group of order q-1. Thus if tex2html_wrap_inline898 is a generator of this multiplicative group, then every nonzero element tex2html_wrap_inline1352 in tex2html_wrap_inline1334 is given by tex2html_wrap_inline1356 for some integer x; in fact for each tex2html_wrap_inline1352 there is a unique integer in the range tex2html_wrap_inline1362 with this property. For a given x and tex2html_wrap_inline898, the power tex2html_wrap_inline1368 can be quickly computed by the square-and-multiply method as demonstrated in Example 9.1. The inverse problem, i.e., the problem of finding, for a given tex2html_wrap_inline898 and tex2html_wrap_inline1352, the x in the range 0 < x < q-1 satisfying tex2html_wrap_inline1356, is the discrete logarithm problem; it is believed to be hard for many fields. Thus, exponentiation in finite fields is a candidate for a one-way function.


The above discussion can be generalized to any group G (whose operation is written multiplicatively). The discrete logarithm problem for G is to find, for given tex2html_wrap_inline1418, a nonnegative integer x (if it exists) such that tex2html_wrap_inline1356. The smallest such integer x is called the discrete logarithm of tex2html_wrap_inline1352 to the base tex2html_wrap_inline898, and is written tex2html_wrap_inline1430. In Example 9.2, tex2html_wrap_inline1432. Clearly, the discrete logarithm problem for a general group G is exactly the problem of inverting the exponentiation function tex2html_wrap_inline1436 defined by tex2html_wrap_inline1438 where N is the order of tex2html_wrap_inline898.

The difficulty of this general discrete logarithm problem depends on the representation of the group. For example, consider G to be the cyclic group of order N. If G is represented as the additive group of tex2html_wrap_inline1450, then computing discrete logarithms in G is equivalent to solving the linear equation tex2html_wrap_inline1454, where a,b are given integers; this can be easily done by using the extended Euclidean algorithm. If G is represented as a subgroup of the multiplicative group of a finite field as above or as a multiplicative group of elements from tex2html_wrap_inline1460 (where m may be composite or prime), then the problem can be ``hard.'' For an elliptic curve group [14], the discrete logarithm problem seems to be harder. (As we have indicated, no one has been able to prove that these discrete logarithm problems are really hard, but they have been studied by number theorists for considerable time with only limited success.) For recent surveys and a more detailed study of the discrete logarithm problem, we refer the reader to [15, 18, 19]. We now describe two cryptosystems whose security is based on the assumption that the discrete logarithm problem is hard.

The Diffie-Hellman key exchange scheme is a protocol for establishing a common key between two users of a classical cryptosystem. As we mentioned earlier, for a large network of users of a conventional cryptosystem, the secure distribution of keys can be complicated and logistic. In 1976, Diffie and Hellman [7] gave the following simple and elegant solution for this problem.
An eavesdropper, who knows G and tex2html_wrap_inline898 from the public directory, after intercepting A and B, is then faced with the following problem.


If one can solve the discrete logarithm problem, then it is clear that one can solve the Diffie-Hellman problem; hence the latter problem is no harder than the former. It is believed that the two problems are equivalent, and in fact this equivalence has been established for some special cases. In any event, the Diffie-Hellman key exchange scheme is secure provided the Diffie-Hellman problem is hard.

The Diffie-Hellman key exchange scheme is widely used (with some variants) in practice to generate ``session keys,'' for example in secure internet transactions. This scheme itself is not a public-key cryptosystem; however, ElGamal [8] showed that it could easily be converted into one. Note that if Alice publishes tex2html_wrap_inline1500 but keeps a secret, then anyone, say Charlie, can share a common key with Alice in the same way that Bob did; i.e., Charlie can pick a random integer c, and compute tex2html_wrap_inline1506 and tex2html_wrap_inline1508. Before sending r to Alice, Charlie can encrypt any message m he wishes by simply computing the product tex2html_wrap_inline1514. Then he sends the pair tex2html_wrap_inline1516 to Alice. Alice can compute tex2html_wrap_inline1518 from r and her private key a, and so decrypt m.

It is easy to check that if tex2html_wrap_inline1562, then tex2html_wrap_inline1564 and tex2html_wrap_inline668. To obtain a random key, one just chooses tex2html_wrap_inline1568 at random and computes tex2html_wrap_inline1562. In practice, one has to be extremely careful in choosing the group G so that the discrete logarithm problem is hard. Originally, Diffie and Hellman (1976) and ElGamal (1985) used the multiplicative group of tex2html_wrap_inline1260 for a large prime p. The above description of their systems is actually a natural generalization to an arbitrary group. The most studied groups for cryptographic purposes are multiplicative subgroups of tex2html_wrap_inline1260, tex2html_wrap_inline1460 (where m is a product of two large primes), tex2html_wrap_inline1584, and elliptic curve groups over finite fields. While tex2html_wrap_inline1260 is currently the most popular choice, there is increasing interest in using elliptic curves over finite fields, particularly the fields tex2html_wrap_inline1584 [14].

Note that breaking the ElGamal cryptosystem by a ciphertext-only attack is equivalent to solving the Diffie-Hellman problem. Thus the ElGamal cryptosystem is another example with provable security if the Diffie-Hellman problem is indeed hard. The major disadvantage of the system is the message expansion by a factor of two, but there are ways to improve it in both efficiency and security as we discuss next.

Observe that the multiplicative operation tex2html_wrap_inline1590 in the encryption function tex2html_wrap_inline546 could be replaced by other operations. For example, if the elements in G are represented as binary strings of 0's and 1's, then we can let
where m is any binary string and tex2html_wrap_inline1604 is the bitwise ``exclusive or'' operation (XOR); e.g., tex2html_wrap_inline1606. In this case, m does not have to be in G. If the elements in G are represented as binary strings of length tex2html_wrap_inline1614, then the plaintext space tex2html_wrap_inline548 can be any subset of binary strings of length tex2html_wrap_inline1614. Note that in the ElGamal cryptosystem, it is required that a plaintext be in the group. This is not trivial to achieve for some groups (e.g., elliptic curves), but the above approach solves this problem. Also, tex2html_wrap_inline1604 is computationally cheaper than multiplication in a group.

However, the above alternative does not solve the problem of message expansion. One way around this is to use tex2html_wrap_inline1622 as a key in a conventional cryptosystem, say DES or IDEA [12]. That is, define
where tex2html_wrap_inline1626 is any encryption function in a conventional cryptosystem. Here m can be a message of arbitrary length and tex2html_wrap_inline1626 operates on m, say, with cipher block chaining (CBC) mode. With this modification, the cryptosystem is sometimes called a hybrid cryptosystem, which combines the advantages of both public-key and conventional cryptosystems. Such cryptosystems are practical but do not have provable security (a typical phenomenon for conventional cryptosystems). To improve security, one can use a cryptographically strong pseudo-random bit generator to expand tex2html_wrap_inline1622 to a much longer string and then XOR it with m.

It should be noted that the ElGamal cryptosystem is completely insecure against an adaptive chosen ciphertext attack, mentioned earlier. Indeed, given an encryption tex2html_wrap_inline1638 of a message m, one can ask for the decryption of tex2html_wrap_inline1642, which is tex2html_wrap_inline1644, so m can be deduced immediately.

next up previous
Next: Digital Signatures Up: Mathematical Models in Public-Key Previous: Cryptosystems Based on Integer

Shuhong Gao
Sun Oct 17 11:04:53 EDT 1999