1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ And of course, $GF(256)$ is much too small to be usable for DH. $\endgroup$
    – fgrieu ♦
    Aug 19, 2018 at 13:03
  • $\begingroup$ @fgrieu - Yes, I know. But I just wanted to keep things small in order to understand it by some examples where I can capture the whole thing and not being too abstract. $\endgroup$
    – kwasmich
    Aug 19, 2018 at 13:52
  • $\begingroup$ @kodlu - I don't really understand your answer. An irreducible polynomial is contradictory to having a root. So I don't know what you mean by saying that the polynomial also has to be primitive. Perhaps you can write some example? $\endgroup$
    – kwasmich
    Aug 19, 2018 at 14:35
  • 2
    $\begingroup$ @kwasmich Extension fields are constructed by using a polynomial that is irreducible over the base field (and which therefore has no root in the base field). The polynomial will of course have roots in the extension field. $\endgroup$
    – fkraiem
    Aug 19, 2018 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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