1
$\begingroup$

In a Diffie-Hellman key exchange protocol, the system parameters are given as follows: finite field $GF(2^5)$ defined with irreducible polynomial $f(x) = x^5 + x^2 + 1$ and primitive element $\alpha= x$ in the field.

Suppose that Alice selected random number $a = 5$ and Bob selected $b = 6$, show the steps performed by Alice and Bob to obtain their shared key. What is the key?

For Alice:

$α^a = α^5 = x^5 = (x^2 + 1)$

For Bob:

$α^b = α^6 = x*x^5 = x(x^2 + 1) = x^3 + x$

Shared Key For Alice:

$α^{ab} = (x^2 + 1)^b = (x^2 + 1)^6\ldots$

Shared Key For Bob:

$α^{ab} = (x^3 + x)^a = (x^3 + x)^5\ldots$

The answer is $x^4 + x$ but I'm not sure how to simplify to this answer from both sides either Alice or Bob which should have the same shared Key

$\endgroup$
  • 1
    $\begingroup$ $(x^2+1)^6={({(x^2+1)}^2)}^3={({(x^2+1)}^2)}^2\times {(x^2+1)}^2=...$. $\endgroup$ – Meysam Ghahramani Dec 15 '19 at 3:51
  • $\begingroup$ No this isn't homework I am studying for a final exam and these were additional problems I found in my textbook because I wanted to study extra. He didn't ask them in class but this professor is known to ask difficult problems that were not covered I just wanted to be extra prepared I can try to answer it i'm just a little stuck about how the reductions work I just don't get how you'd know to do these steps and why? I came up with a solution (60 lines so it seems like luck) and really I wouldn't have known when to stop at x^4 + x I don't get why that is the answer and not one of my previous. $\endgroup$ – user3371137 Dec 15 '19 at 15:40
2
$\begingroup$

Three words Finite Field Arithmetic. The elements of the Finite Field (Galois field) can be represented by a polynomial, like in this case. We prefer it since it gave us good computing properties.

$GF(2^5)$ is a binary field extension with the base field 2, the binary field. To construct this field we need an irreducible binary polynomial [*] of degree 5[‡]. In your case it is $f(x)=x^5+x^2+1$. The field can be constructed by $GF(2)[x]/x^5+x^2+1$. An irreducable binary poynomial with degree 5 need not be unique, there is only 6 possibilities for constructing $GF(2^5)$ [#].

  1. $f(x)=1+x^2+x^5$,
  2. $f(x)=1+x+x^2+x^3+x^5$,
  3. $f(x)=1+x^3+x^5$,
  4. $f(x)=1+x+x^3+x^4+x^5$,
  5. $f(x)=1+x^2+x^3+x^4+x^5$, and
  6. $f(x)=1+x+x^2+x^4+x^5$

For the binary field extension and we prefer the ones with small degree monomials and with fewer monomials. So, $f(x)=1+x^2+x^5$ is a good choice.

The addition is polynomial addition with the coefficients are reduced to base field. Multiplication is a bit tricky, we need modulo reduction with the irreducible polynomial. In your case, whenever you see $x^5$ replace it with $x^2+1$. In this website, you can see the table for addition and multiplication. For small cases, generating the table and hardcoding it in a table can be helpful, however, be aware of the cache attacks.

One way is multiplying all at once then reduce \begin{align} (x^2 + 1)^6 &= x^{12} + 6 x^{10} + 15 x^8 + 20 x^6 + 15 x^4 + 6 x^2 + 1 \\ &= x^{12} + x^8 + 15 x^4 + 1 \\ \vdots &= \vdots\\ \end{align}

This is not the preferred method since it can scale too much, especially for large finite fields. The better method is the multiply-and-reduce paradigm as below.

\begin{align} (x^2 + 1)^6 &= ((x^2 + 1)^2)^2 (x^2 + 1)^2 &&,\text{expand one level } \\ &= (x^4 + \color{red}{2} x^2 + 1)^2 (x^4 + \color{red}{2} x^2 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\ &= (x^4 + 1)^2 (x^4 + 1) &&,\text{work on left} \\ &= (x^8 + \color{red}{2}x + 1) (x^4 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\ &= (x^8 + 1) (x^4 + 1) && , \text{use } x^5 = x^2+1\\ &= ((x^5)x^3 + 1) (x^4 + 1) \\ &= ((x^2+1)x^3 + 1) (x^4 + 1) \\ &= (x^5 + x^3 + 1 ) (x^4 + 1)&& , \text{use } x^5 = x^2+1\\ &= (x^2+ \color{red}{1} + x^3 + \color{red}{1} ) (x^4 + 1)&& , \color{red}{2=0} \text{ in } \mathbb{F}_2\\ &= (x^3 + x^2 ) (x^4 + 1) &&, \text{multiply}\\ &= x^7 + x^6 + x^3 + x^2 &&,\text{use } x^5 = x^2+1\\ &= (x^2+1)x^2 + (x^2+1)x + x^3 + x^2 &&,\text{expand } \\ &= x^4 + \color{red}{2} x^3 + \color{red}{2} x^2 + x &&,\text{use }\color{red}{2=0} \text{ in } \mathbb{F}_2\\ &= x^4+ x && \end{align}

And, for the other equation, you can see their equality by; $$(x^3+x)^5=x^5(x^2+1)^5=(x^2+1)(x^2+1)^5=(x^2+1)^6$$

We, actually, use bit vector to process the binary polynomials:

$ (x^2+1)= [00101]$, we can represent with 5 bits since the finite field $GF(2^5)$.

Whenever we see, 1 out of size 5 we reduce it.

  • $ (x^5)= [1|00000] = [00101]$, the reduction is shift and x-or. We can say, replace the 1 with position 5 with $[0|00101]$ and x-or. Similarly, we can write formulas for
  • $x^6 = (x^5)x = [01001]$ and
  • $x^7 = (x^5)x^2 = [10100]$, and so on. In your case 6 should be enough if you multiply one by one.

\begin{align} [00101]^6 &= [00101]\cdot [00101]\cdot [00101]^4 \\ &= [10001]\cdot [00101]\cdot [00101]^3 \\ &= [10|10001]\cdot [00101]^3 \tag{use $x^6$}\\ &= [11000] \cdot [00101] \cdot [00101]^2\\ &= [11|11000] \cdot [00101]^2\\ \vdots &= \vdots \end{align}


[*] A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field. (Wolfram defn.)

[#] The list is taken from Wolfram, too.

[‡] There is a sequence on the number of binary polynomials on the degree; OEIS A059912

| improve this answer | |
$\endgroup$
  • $\begingroup$ Note, I did most of this without a computer, so there may be calculation errors. $\endgroup$ – kelalaka Dec 16 '19 at 7:08
  • 1
    $\begingroup$ Maybe you could point out, that for larger numbers, square and multiply (as in your first calculation) scales much, much better than the entire expansion in one step. $\endgroup$ – tylo Dec 16 '19 at 11:49
  • $\begingroup$ That helped a lot I think the =((x^2+1)^3+1)(x^4+1) line has an error I think rather it should be (x^2+1)*x^3 $\endgroup$ – user3371137 Dec 16 '19 at 14:26
  • $\begingroup$ @user3371137 corrected $\endgroup$ – kelalaka Dec 16 '19 at 20:57
  • 1
    $\begingroup$ @tylo better now? $\endgroup$ – kelalaka Dec 16 '19 at 20:58

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.