# Diffie-Hellman Key Exchange in $GF(2^5)$

Stuck in a question where the DHKE (Diffie-Hellman key exchange ) is done in the $GF(2^5)$. The irreducible polynomial is $P(x) = x^5+x^2+1$. The $\alpha$ value is $x^2$. If the private keys of $a = 3$ and $b = 12$ what is the session key $K_{ab}$?

Now the calculation of $K_{ab}$ = $\alpha^{ab} \bmod P(x)$. This would translate to $x^{2^{36}}$. Can anyone suggest how to further break this? Should we use the concept of cyclic groups or square-multiply algo here?

To summarize, we are considering a DHKE in $GF(2^5)\cong GF(2)[x]/(P(x))$ where $P(x)=x^5+x^2+1$. The generator element is chosen to be $\alpha=x^2$. There are two parties, let's say $A$ and $B$, with private keys $a=3$ and $b=12$.
First off, I would suggest to compute the public keys of both parties. They are, by definition, $\alpha^a$ and $\alpha^b$. Then there are two equivalent ways to compute the shared secret. That is, either $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$. Note that the result is not $x^{2^{36}}$.
Then you have to remember that you are working modulo $P(x)$. That is, $x^5=-x^2-1=x^2+1$ inside $GF(2^5)$. We can use this to "break" down polynomials. For example, $$x^6=x\cdot x^5=x\cdot(x^2+1)=x^3+x$$ or $$x^{10}=x^5\cdot x^5=(x^2+1)\cdot(x^2+1)=x^4+2\cdot x^2+1=x^4+1.$$ Applying this technique to $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$ gives you the correct result.
• Great! Found the $K_{pubA}$ as $x^{2{^3}}$ which is $x^8$ which is broken down to $x^3+x^2+1$. Now while computing $K_{pubB}$ it ends up with $x^{2{^12}}$ which is $x^4096$. Any easy way of breaking this down or should the normal division happen? – Sudhi Nov 18 '16 at 10:03
• An extra hint: $(x^a)^b=x^{a\cdot b}$, not $x^{a^b}$! – CurveEnthusiast Nov 18 '16 at 10:17