The Mathematics of Communication: lecture #11

Lecture #11: Diffie-Hellman key exchange

I discussed the homework, and displayed some of the graphs that people got. I mentioned that there was an amount of randomness in what would occur, but that I would expect the 2*x=1 mod n problem to consistently get solved quickly, while the 2^x=1 mod n problem would progressively take more and more time.

I then introduced some background to the Diffie-Hellman protocol: Alice and Bob were in prison, Eve would overhear all communication between them, everyone would have lots of computer capacity but Alice and Bob would have no shared knowledge, no prearrangements. I went very slowly. I discussed this thoroughly and encouraged questions, so that people would understand it. I said that the goal was to have Alice and Bob share some knowledge, and make it very, very unlikely that Eve would also know this shared information. People found this proposal paradoxical, as they should have!

I asked people to critique some proposals for secure communication between Alice and Bob, keeping in mind these criteria:

The protocol is clearly and completely described.
Alice and Bob can do the protocols.
Alice and Bob will get some shared secret which Eve is not likely to get.

I said that the first thing we'd try to do is to get Alice and Bob to share some sort of secret that Eve did not know.

Protocol #1

First, Alice and Bob select a prime, P. Then they select another number, N. Eve knows all this. Then Alice selects a secret number, A, and B selects a secret number, B. Alice tells Bob the number N+A, and Bob tells Alice the number N+B. Alice privately then computes the sum of the number she gets from Bob and her own secret number, while Bob privately then computes the sum of the number he gets from Alice and his own secret number.

There was a considerable amount of confusion about this. Certainly the first criterion wasn't satisfied! So I inserted some numbers (perhaps P=13 and N=4 and A=2 and B=8) and went through the protocol. Alice and Bob shared the same "secret" number because (N+A)+B and (N+B)+A are equal mod P. Everyone agreed that now the first two criteria were o.k., but the third wasn't.

I then changed the first protocol to get:

Protocol #2

First, Alice and Bob select a prime, P. Then they select another number, N. Eve knows all this. Then Alice selects a secret number, A, and B selects a secret number, B. Alice tells Bob the number N*A, and Bob tells Alice the number N*B. Alice privately then computes the product of the number she gets from Bob and her own secret number, while Bob privately then computes the product of the number he gets from Alice and his own secret number.

I inserted the values for A and B and P and N which were specified above. Now things were getting a bit more difficult to compute. Alice and Bob shared the same "secret" number because (N*A)*B and (N*B)*A are equal mod P. Although the first two criteria were satisfied, we thought for a bit about the third and decided that Eve could solve certain equations in Maple (I said that we suppose that Eve has at least such computing capacity). So the third still wasn't satisfied. It is nice to note that several people seemed to guess at the third protocol, even as I was rewriting what had been #2 (the former #1).

Protocol #3

First, Alice and Bob select a prime, P. Then they select another number, N. Eve knows all this. Then Alice selects a secret number, A, and B selects a secret number, B. Alice tells Bob the number N^A, and Bob tells Alice the number N^B. Alice privately then computes the result of raising the number she gets from Bob to the power of her own secret number, while Bob privately then gets the result of raising the number he gets from Alice to the power of his own secret number.

Again I followed through the numerical example, very very slowly. We also had on the board the Maple instructions which Eve could use to break the multiplicative scheme. I changed them to allow Eve to break this scheme. But most people seemed to believe that this would be time-consuming.

So I told them that this was Diffie-Hellman key exchange. I did not get a chance to actually divide the class into several parts (an Alice, a Bob, and an Eve) and create a depth, as I did last semester. Last semester I divided the class into groups. I asked one group to play Alice, another Bob, and a third, Eve. With a laptop loaded with Maple (I still don't have that!) we could have tried to send messages. I think that technology adequately deployed in the classroom could really have helped here.

Last semester, I had Alice send Bob an animal name just by adding on one of 6 numbers from a selection of numbers on the board (DOG=513, CAT=341, etc.) and shouting out that number added to their common secret. I then had Bob try to send Alice a similar message, but the Eve group did not detect that they could have guessed the animal because Alice sent Bob their shared secret added to an animal number (and then the animal name was revealed, revealing also inferentially the shared secret!), while Bob sent out another animal number added to the same shared secret. I created a "depth". But the students last semester didn't detect this, so maybe it was better that I didn't try it this semester because I might have been disappointed again.

I handed out the Diffie-Hellman contest sheet [PDF|PS|TeX]. The empty space on the second page was occupied by a very humorous and quite appropriate Wizard of Id cartoon, showing how a prisoner was trying to communicate by tapping on the wall. After some difficulty ("... all I'm getting is gibberish"), the turnkey returns to tell the prisoner, "I've solved your problem ... you've been talking to the radiator."

Previous lecture

Table of contents

Next lecture