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

Question

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

Answer 1

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$.