Diffie-Hellman key exchange protocol with finite field GF(2^5)

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

• $(x^2+1)^6={({(x^2+1)}^2)}^3={({(x^2+1)}^2)}^2\times {(x^2+1)}^2=...$. Dec 15 '19 at 3:51
• 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. Dec 15 '19 at 15:40

1 Answer

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

$$\rm 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 $$\operatorname{GF} (2)[x]/f(x)$$[+]. An irreducible binary polynomial with degree 5 need not be unique, there is only 6 possibilities for constructing $$\operatorname{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 the 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

[+] In the general case; for for a prime $$p$$ an the prime power $$q=p^n$$, $$n \in \mathbb Z^+$$, with the irreducible polynomial $$f$$ of degree $$n$$, the quotient ring

$${\operatorname{GF}}(q)={\operatorname{GF}}(p)[X]/(f(x))$$ of the polynomial ring $$\operatorname{GF}(p)[X]$$ by the ideal generated by $$f(x)$$ is a finite field of order $$q$$.

• Note, I did most of this without a computer, so there may be calculation errors. Dec 16 '19 at 7:08
• 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.
– tylo
Dec 16 '19 at 11:49
• 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 Dec 16 '19 at 14:26
• @tylo better now? Dec 16 '19 at 20:58
• Don't you mean $q=p^n$ so GF(q)=GF(p^n)=GF(p)[x]/irredn(x)? Jun 1 at 2:59