CSc 8370 fall '02

Key Exchange

and

Public Key Ciphers

Conventional symmetric ciphers require that both parties, the sender and the recipient have the same secret information which is the key to the cipher. Indeed while a one time system gives perfect secrecy, the problem of exchanging the keys is a major weakness. In general, key management is the fundamental weakness in cipher systems. Modern cipher systems can be constructed that are fairly immune to being directly broken, but as we saw in the last exercise if the key is chosen weakly can be compromised.

Diffie-Hellman Key Exchange.

The difficulty of solving the exponential equationfor x given a, b, p where p is a large prime and a is a primitive root is the basis of Diffie-Hellman key exchange. Diffie-Hellman key exchange is a special case El-Gamal key exchange. El-Gamal describes the use of any hard to invert, but easy to calculate function in a role similar to the exponentiation in Diffie-Hellman. This problem is known as the discrete logarithm problem. p is chosen to be a large prime because 1) it is relatively easy to find primitive roots with respect to a prime number, and 2) it is relatively easy to solve this problem with the Chinese Remainder Theorem if p has lots of small factors (the CRT is described in Cormen et al Introduction to Algorithms). It is also important that p-1 have relatively few small factors, because a number of relatively fast algorithms take advantage the structure of p-1.

To use this algorithm a pair of numbers (a,p) are chosen and made public.

Since (a^x)^y = (a^y)^x the two parties have generated the same secret number which they can then use as a key. In order to directly attack this protocol, it would be necessary to solve a^x mod p for x (or the equation for y) and then generate (a^y)^x .

Algorithms for Exponentiation.

The naïve approach to exponentiation is to simply keep multiplying a by itself x times (i.e. a² = a*a; a³ = a²*a; ....) Clearly the cost of doing this is Ø(x), and if x is large as is the modular base p, this is a very expensive proposition.

A much faster approach is to take advantage of the representation of x as a binary number and use repeated squaring to generate all of the even powers of a. The cost of this algorithm depends on the number of bits in x or Ø(lg(x)).

Neither of these algorithms is useful for finding a^x for non-trivial sizes of a,x,p. In this case non-trivial means thousands of bits. While with the repeated squaring algorithm, the lg(x) factors can be readily generated, there are 2^lg(x) = x combinations of factors so the complexity of a search is Ø(x), which is the same as the naïve algorithm.

A faster algorithm is sometimes possible. A determinative example, rather than randomized, is the Pohig-Hellman algorithm.

For a prime number, p, the order of the group of products (a^x where a,x < p) is p-1. (the order of the group is just the number of unique elements in it, for example mod 3, there are x = 1,2 and 1*1 mod 3 = 1 , 2*2 = 1 mod3, 2*1 = 2 mod 3). For (a,p) where p is prime the following results hold.

1. (Fermat's theorem)

2. If then

Therefore if we have an efficient way to find congruencies mod(p-1) then we can reduce the 2^lg(x) combinations of products in the searching algorithm and improve the performance. For the first step we solve where q is a prime factor of (p-1), e is its multiplicity and x is the unknown. If q is a small number this can be done efficiently by direct searching. The set x_i correspond to solutions to simultaneous congruencies with respect to pairwise relatively prime bases. The Chinese remainder theorem states that there is a unique solution to the x_i and efficient algorithms exist for finding that solution.

A worse problem.

IT IS NOT NECESSARY TO SOLVE THE DISCRETE LOGARITHM PROBLEM TO BREAK DIFFIE-HELLMAN!

The "man-in-the-middle" attack allows an eavesdropper to monitor communication between two parties.

Ted has now exchanged keys with Bob and Alice. Bob and Alice think they've exchanged keys with each other. All Ted has to do now is decrypt the message from Bob, re-encrypt it with Alice's key and he can monitor the communication without detection.

If the public keys are published in an insecure manner, then this "man-in-the-middle" attack can always be performed.

The current solution to this dilemma is described in Viega pp297-301. It involves the use of a trusted "certificate authority" or CA. When queried the CA returns a a digitally signed "certificate" that can be compared to one that has been transmitted by another means. For example, a list of 10-20 CA's is included with the software to install a web browser. If the certificates agree then the keys are exchanged. This is inherently weak because the CA just certifies that the CA has been paid them a fee, and/or CA certificates can be forged or ignored. One recent trouble with Microsoft IE is due improper handling of certificates.

RSA Algorithm

The RSA (Rivest Shamir, Aldelman) algorithm is a related number theoretic algorithm that is used to exchange information.

Euler's totient function. å(n) is an inverse in modular arithmetic. If x is an element in the multiplicative ring (Z) for n then x^å(n) mod n = 1. If n is prime å(n) = n-1, if n is a product of two prime p,q then å(n) = (p-1)(q-1). Note that Euler's totient function defines an inverse for all members of the ring, there are pseudo-totients that are inverses for many members of the ring. If the prime n has many small factors there are many pseudo-totients, and these can be used to recover å(n). The least common multiple of (p-1),(q-1) defines the minimum power that can be used as an inverse for all members of the ring. If (p-1), (q-1) have many factors this can be quite small (and insecure).

The algorithm is as follows:

1. choose two primes p,q that are a) big, b) p-1,q-1 don't have many factors, and c) sufficiently different that n is not approximately p*p or q*q.

2. calculate å(n) = (p-1)(q-1). select a large random number e < å(n) where the greatest common denominator of e,å(n) is 1 (i.e. they are relatively prime).

3. Use the extended Euclidean algorithm to find d such that ed \ 1 mod(å(n) )

4. d,p,q, å(n) are kept secret.

5. publish the pair e,n

6. to encrypt, the message x is taken to the e power (i.e. c = x^e mod n).

7. to decrypt the cipher c is taken to the d power (i.e. x = c^d mod n).

This works because ed = 1 + k å(n) . Therefore x^ed mod n = x^{1 + kå(n)} mod n = x.

If you can factor n, then you can calculate å(n) . Factoring is currently hard. If n is chosen badly, it is possible to find the least common multiple of (p-1),(q-1) by direct search and thus break the scheme. RSA is also susceptible to the "man in the middle" attack.

Problem (Real problems due 9/19/02)

This should be easier.

The 5 messages (cipher1,..., cipher5) are on yamacraw in the dst32 area.

These were encrypted by rc4 (but the key search algorithm done in class won't help).

Which of these were encrypted with the same keys? (we covered a test that can be used to answer this, implement it and try it out).