0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Sudhi Nov 18 '16 at 10:03
  • $\begingroup$ An extra hint: $(x^a)^b=x^{a\cdot b}$, not $x^{a^b}$! $\endgroup$ – CurveEnthusiast Nov 18 '16 at 10:17
  • $\begingroup$ Dayum! you are right. Guess I should go back to elementary school :) $\endgroup$ – Sudhi Nov 18 '16 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.