powers of g in $GF(256)$

Question

The finite field $GF(256)$ is usually implemented $mod$ 0x11b to keep the numbers inside that field. I understand that 0x11b was picked as it is the smallest irreducible polynomial that is greater than any number of $GF(256)$. This is sufficient for multiplication as any element of the field can be reached by multiplying two other elements from the same field and the result will also be inside that field.

Now I stumbled over powers in finite fields. By trying it myself I noticed that with $g=2$ not every element of $GF(256)$ could be expressed as $g^x$ when using $mod$ 0x11b. 0x11d has to be used instead for example. But when using $g=3$ I can use 0x11b again. And for $g=6$ I can use both. For $g=7$ I can't use either. So the choice of the irreducible polynomial depends on the generator $g$.

Does this mean unless you have tested the choice of irreducible polynomial $p$ throughly, you cannot use it for key exchange as proposed by Diffie-Hellman but you can use it for Elliptic Curves?

Is it even feasible to do both on a finite field?

Answer 1

Does this mean unless you have tested the choice of irreducible polynomial $p$ throughly, you cannot use it for key exchange as proposed by Diffie-Hellman but you can use it for Elliptic Curves?

Skipping the part about Galois fields (where you can easily map between different representations, and so the choice isn't important for security), for Diffie-Hellman, one thing that is important (if not sufficient) is the size of the subgroup that is generated by the generator.

If we pick a size that has a small factor $a$, the attacker can easily derive the values of our DH private keys modulo $a$ (with $O(\sqrt{a})$ work), and so we are leaking $\log_2 a$ bits.

Instead of targeting a generator that generates the entire group, we typically select a generator that generates a large prime subgroup of the group (in some happy cases, this prime subgroup will just happen to be the entire group; that's not the case here, unless we pick $GF(2^x)$ where $2^x-1$ is a Mersenne prime).

For $GF(2^8)$, the size of the multiplicative group is $255 = 17 \times 5 \times 3$; obviously, the largest prime-sized subgroup is 17 (and there will be 16 generators for that subgroup). This is obvious far too small to be secure, but selecting a generator of a subgroup that size would be more typical of how we use Diffie-Hellman.

Answer 2

What you need is an irreducible polynomial that is also primitive, i.e., has a root of order $2^8-1.$ You can find one by trial and error.