Random Galois fields

Question

Note: I have now answered this by my own research and can generate random fields up to G(2^9) in reasonable time. I would need to find more speedups for larger fields. At this time G(2^8) takes a few seconds and G(2^9) takes a few hours (it varies widely depending on my generation options). If anyone is interested I will expand upon the process.

I would like to create random Galois fields over $G(2^8)$ with operators $(\otimes, \oplus)$ where $\oplus$ is the standard XOR and $\otimes$ is a randomly defined multiplicative operator. I have an algorithm in mind, but I suspect that it will not generate all possible fields. I know that all such fields are isomorphic, but differences are crucial! Especially for cryptography.

I know that fields have been defined (e.g. Rijndael) using polynomials but again doubt that all possible fields can be reached that way. At least not easily. Any suggestions?

I should explain what I want to do in more detail and the reasons. I know that all finite fields of a given size are isomorphic. That means that there is effectively only "one" field. However, they are NOT the same from a different standpoint. There has been a lot of work to find fields that have minimal implementation complexity. Mainly because of the obsession with implementing them entirely in very small hardware (minimum gates).

However, from an encryption standpoint, a very high level of complexity is desired. You want x * y to be highly non-affine. Minimum complexity is not optimum here. So the simple irreducible polynomials that encryption products are using are not suitable. They are explictly choosen to have minimum complexity. It is difficult to determine the complexity of a field from the polynomial. But, by generating random fields the odds of getting a highly complex field are very good. And it is a good way to make the encryption hard to break becuase the properties of a specific field cannot be directly used in cyptoanalysis.

So, yes the fields are are all the same. But (as an engineer would say) practice and theory are different. And it is that difference that is important.

My algorithm above is not quite correct. It turns out that the sub-algorithm for building the basis products is not right. I have solved some of it, but there are dependencies that I haven't identified yet. I don't know if that approach will work or not.

However, other approaches may be just as good. Since finite fields of the same size are isomorphic, an alternative is to build a random isomorphism. That appears to have a lot of the same problems.

So I am still looking for insights or suggestions. Thanks.

Poncho - you are the only one to answer so far that appears to have a clue about this (I am new to crypto.stackexchange and don't yet have the points to either comment or chat). I am unfortunately (for the time) stuck using a library computer in small town every couple of days and my reference library is not available (and it has been 40 years since abstract algebra in college which didn't even cover this area). I have picked up and read several books in the area (abstract algebra and finite fields), but none of them address this topic or even something close enough. They just address the standard theory, which except for information on bases is not very useful. I have not been able to find any online references on this direct topic. Do you have any suggestions?

Why the 8 4 3 2 0 polynomial? Or is that just the first one you picked? As far as generating a random field, generating a random bais for g01, g02, ..., g80 works fine. Then I only need to generate another random basis for g02, g03, ... g81. There are some constraints there that I don't currently have enough information to use to directly constrain the random generator, but brute force would work. I actually think that the main basis completely constrains the g02, g03, ... basis (the first row / column in the basis multiplication table - that sufficies to ensure distribution and all of the other properties) but I haven't determined an efficient way to do that. Possibly a genetic algorithm. However, I would like to be more intelligent about the process. If you are correct, I could create the basis, determine the affine mapping from the field generated by the 8 4 3 1 0 polynomial and then create the g02, g03, ... basis by applying the affine mapping. If that does, in fact, work then simply generating a random affine mapping should also work. That is trivial - just create a basis to ensure that the matrix is invertable and add a random vector.

I don't know if it will give a better non-affine result, but I suspect that it would (this is research!). Otherwise there would be no point in using different polynomials to obtain "simple" implementations. I simply want to do the opposite of "simple"!

Answer 1

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals $\mathbf 0$ if and only if all $8$ $a_i$ equal $0$. Then, every element $\gamma$ of $\mathbb F_{2^8}$ can be expressed as a $8$-bit vector $(\gamma_0, \gamma_1, \cdots, \gamma_7)$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$ meaning that $$\gamma = \gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7, ~ \gamma_i \in \mathbb F_2$$ with the property that $$\gamma + \delta = (\gamma_0, \gamma_1, \cdots, \gamma_7)\oplus (\delta_0, \delta_1, \cdots, \delta_7)$$ that is, field addition is just the XOR sum of the $8$-bit representations with respect to the chosen basis; indeed, we do not even need to know the basis at all. Multiplication is more complicated and does require knowledge of the basis. We have that $$\begin{align} \gamma\otimes \delta &= (\gamma_0\beta_0 \oplus \gamma_1\beta_1 \oplus \cdots \oplus \gamma_7\beta_7) \otimes(\delta_0\beta_0 \oplus \delta_1\beta_1 \oplus \cdots \oplus \delta_7\beta_7) \\ &= \sum_{i=0}^7\sum_{j=0}^7 \gamma_i \delta_j \beta_i\beta_j\\ &= (\gamma_0, \gamma_1, \cdots, \gamma_7)A(\delta_0, \delta_1, \cdots, \delta_7)^T \tag{1} \end{align}$$ where $A$ is a $8\times 8$ binary matrix whose entries can be figured out by expressing all the elements $\beta_i\beta_j$ with respect to the basis $\{\beta_0, \beta_1, \cdots, \beta_7\}$.

A commonly used basis (sometimes even referred to as a canonical polynomial basis) is $$\{\beta_0, \beta_1, \cdots, \beta_7\} = \{1, \alpha, \alpha^2, \cdots, \alpha^7\}$$ where $\alpha$ is a root of an irreducible binary polynomial of degree $8$. People have expended considerable effort in figuring out which degree-$8$ irreducible polynomial gives the sparsest matrix $A$ since this leads to reduced number of gates in a VLSI implementation. Multiplication can also be implemented as a process requiring several clock cycles instead of one clock cycle, in which case some different criteria may be used in figuring out which polynomial gives the cheapest or fastest implementation.

Polynomial bases are handy when one is doing calculations with paper and pencil (or on a blackboard!) because the calculations are easy to follow. But it is not necessary to stick to polynomial bases if one is interested in efficient hardware implementations. I am aware of at least one implementation where the dual of the polynomial basis is used, and several US patents have been issued for Galois field multiplications based on representations with respect to a normal basis (search for Massey-Omura multiplication). A normal basis is $$\{\alpha^{2^0}, \alpha^{2^1}, \alpha^{2^2}, \cdots, \alpha^{2^7}\}$$ where $\alpha$ is a root of a degree-$8$ irreducible binary polynomial whose degree-$7$ term is $1$ (the degree-$7$ term is the sum of all the basis elements and must not be $0$; else we do not have a basis at all). Note that squaring is a very simple operation with respect to a normal basis: the representation of $\gamma^2$ is just the right cyclic shift by one bit of the representation of $\gamma$.

I recommend the book by R.J.McEliece Finite Fields for Computer Scientists and Engineers, Kluwer Press, 1987 for lots of details on the matters described above.

Answer 2

Well, all representations of the field $GF(2^8)$ are isomorphic. What that means is that there is a mapping between one representation of that field to another, where that mapping preserves all field properties.

That is, if we had two representations $A$ and $B$, there exists a mapping $M$ from elements of $A$ to elements of $B$ such that, for any two elements $X, Y$ of $A$, we have: $$M(X +_A B) = M(X) +_B M(Y)$$ That is, if you add two mapped elements, it's exactly the same as adding them, and then doing the mapping), and $$M(X \times_A Y) = M(X) \times_B M(Y)$$ The mapping $M$ will also need to preserve identities and inverses (because those are mentioned when you list out the field properties), however it is easy to see that the above two identities imply that those are preserved as well, hence the above two identities are sufficient conditions on $M$.

Now, you insist a second condition on your representation; that addition between two elements of your representation be equivalent to exclusive-oring the bitpatterns of the represented values. Let us investigate the consequences of that.

Let us assume that the $A$ representation be some "standard" representation (such as the $x^8 + x^4 + x^3+x+1$ polynomial representation -- this is the internal representation that AES uses internally, and so can be considered the canonical representation - if you have another reasonable representation that you prefer, you can use that one), and $B$ is your representation. Now, in the $A$ representation, addition is equivalent to exclusive-or, or in other words, $+_A$ is the same as $\oplus$. If $B$ shares that property, then $+_B$ is the same as $\oplus$. Then, the first identity that we have can be rewritten as $M(X \oplus Y) = M(X) \oplus M(Y)$; this condition is equivalent to stating $M$ is bitwise linear.

In addition, it is easy to show that any $M$ that is both bitwise linear and bijective forms a representation $B$ (because the first equation is satisfied by any linear $M$, and the existence of $M^{-1}$ (which the assumption of bijectivity gives us) allows us to use the second identity to define $\times_B$.

Hence, the problem of finding such a random representation is equivalent to the problem of finding a random linear bijection over $2^8$ elements (technically, we would need to show that selecting a random linear bijection with uniform probability will give as a random representation with uniform probability - that's not that difficult to show). Finding a random linear bijection is actually a fairly easy problem, and shouldn't take seconds; microseconds is more like it.

Now, on to the reason why you're doing this; you state that you're using $GF(2^8)$ within some cipher, without stating what the cipher is, or what properties it requires from its primitive. I would suggest that, without further analysis of the cipher, or what it would require, replacing an element by a randomized one (without considering the properties that the cipher would rely on) may be foolish. You state that you hope $\times_B$ is more 'non-affine' than $\times_A$; however, as I pointed out, we always have $X \times_B Y = M( M^{-1}(A) \times_A M^{-1}(B))$, where $M$ and $M^{-1}$ are linear functions, and so it's unclear in what sense that $\times_B$ is any less affine (or linear) than $\times_A$.

In addition, for a number of the ways we use finite fields in, a random representation would perform no better than a standard one. Examples of such uses would be:

• Shamir's Secret Sharing

• Finite Fields within an elliptic curve

• Almost universal polynomial hashing (for example, within GCM)

In other places, such as within AES, it would make a difference; however within AES, the designers were careful to make sure that the AES representation would work out well; replacing that representation with another (and making no other changes) would likely weaken the cipher.

I don't know if the above applies to your cipher (which you have not mentioned). However, what I'm saying is that you need to think things through, and not just do something random, and hope it works out for the best.

Answer 3

You can begin by enumerating all the irreducible polynomials of degree 8. This gives you all the possible fields representations. If I remember Eisenstein criterium is one of the algorithm for testing irreducibility of polynomials All these field are isomorphic to each other.