Alternative Primitive Polynomial

[danielstreit]

First, thanks for the library! This has been very helpful!

I'm interested in using a different primitive polynomial and, while I'm able to get most alternatives to work, I'm having trouble getting Rijndael's polynomial to work: x^8 + x^4 + x^3 + x + 1 -> 283 -> 27. The initialization process fails to build the log table correctly, it seems. The resulting table has a large portion of null values.

I've tried a simple approach of replacing the primitive polynomial in defaults.primitivePolynomials[8] with 27 (or 283).

I've tried using other primitive polynomials with this approach and it has worked. I was able to generate shares and recover them successfully.

Here are some alternative polynomials that I've tried and have worked as expected:
x^8 + x^4 + x^3 + x^2 + 1 -> 285
x^8 + x^5 + x^3 + x^1 + 1 -> 299
x^8 + x^6 + x^4 + x^3 + x^2 + x^1 + 1 -> 351
x^8 + x^6 + x^5 + x^1 + 1 -> 355
x^8 + x^6 + x^5 + x^2 + 1 -> 357
x^8 + x^6 + x^5 + x^3 + 1 -> 361
x^8 + x^7 + x^6 + x^1 + 1 -> 451
x^8 + x^7 + x^6 + x^5 + x^2 + x^1 + 1 -> 487

All of these are using the default 8 bits.

I expect that I'm doing something wrong or misunderstanding something fundamental about how this works.

Any thoughts or guidance on why it doesn't work or how to get it to work would be greatly appreciated!

[grempe]

Hi. Glad you are finding this useful.

I'm sorry to say I'm probably not the right person to answer your question, and to provide alternatives that are cryptographically safe to use.

I'll leave this here though in case anyone else wants to chime in.

Cheers.

[scrovy]

@danielstreit The problem that you face is that $x^8 + x^4 + x^3 + x + 1$ is irreducible over $F_2=\lbrace0,1\rbrace$ but not a primitive polynomial. Indeed implement $GF(256)$ as $GF(256) := F_2[x]/(x^8 + x^4 + x^3 + x + 1)$, let $\alpha := [x] \in GF(256)$ be your candidate primitive element.

When we try to compute $\alpha^{51}$, we have
$\alpha^{51} = [x]^{51} = [x^{51}] = [1] = 1$,
since $x^{51} + 1$ is divisible by $x^8+x^4+x^3+x+1$. Since 51 < 255, this means that $\alpha = [x]$ does not generate the group of units $GF(256)^*$, i.e., it is not a primitive element of $GF(256)$. Hence, $x^8 + x^4 + x^3 + x + 1$ is not a primitive polynomial.

(From my home made Python polynomial division routine I have:)
$x^{51} + 1 = (x^8+x^4+x^3+x+1) (x^{43} +x^{39}+x^{38}+x^{36} + x^{33} + x^{31}+x^{30} + x^{27}+x^{26}+x^{24} +x^{23}+x^{22}+x^{21} +x^{18}+x^{17}+x^{16} + x^{14}+x^{13} +x^{10} + x^7+x^6 +x^2+x^1+1)$.

For the log tables you need a primitive polynomial, take a look at https://www.ece.unb.ca/tervo/ece4253/polyprime.shtml (red polynomials) for a list.