This is a neat number theory problem I came across while discussing the Diffie-Hellman Key Exchange in this week’s meeting of the Theory Group of my college.

The idea of the protocol is that we choose a generator and a prime which are shared over insecure channels. The two parties who want to communicate have their own numbers and for Alice and Bob respectively. These parties share and modulo over the network respectively. The other party receives the message and raises it to the power of their own secret key.

The security of the exchange is guaranteed by the computational hardness of the Discrete Logarithm Problem.

An interesting attack that can happen here is if a party intercepts the message. They have their own key , and over the insecure channel they intercept the messages, sharing and instead.

Using Fermat’s Little Theorem we know that: is congruent to . So, if we choose a suitable , where the condition on is that should be divisible by , we confine the possible keys to a small subgroup. I.e. instead of being a generator for the whole group, it only generates the members in a small subgroup.

This can drastically reduce the computational cost and compromise the security of the channel.