Skip to main content

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

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.

Added commentary and questions for Poncho at end. Fixed duplicate edit update and a couple of typos.
Source Link

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

Update (edited in from a post below) So I am still looking for insights or suggestions. Thanks.

I should explain what I want to do in more detail andPoncho - you are the reasons. I knowonly one to answer so far that all finite fields ofappears to have a given size are isomorphic. That means that there is effectively only "one" fieldclue about this (I am new to crypto. However, they are NOTstackexchange and don't yet have the same from a different standpoint. There has been a lot of workpoints to find fields that have minimal implementation complexityeither comment or chat). Mainly because ofI am unfortunately (for the obsession with implementing them entirelytime) stuck using a library computer in very small hardwaretown every couple of days and my reference library is not available (minimum gatesand it has been 40 years since abstract algebra in college which didn't even cover this area).

However, from an encryption standpoint I have picked up and read several books in the area (abstract algebra and finite fields), a very high levelbut none of complexity is desired. You want x * y to be highly non-affinethem address this topic or even something close enough. Minimum complexityThey just address the standard theory, which except for information on bases is not optimum herevery useful. So the simple irreducible polynomials that encryption products are using areI have not suitable. They are explictly choosenbeen able to have minimum complexityfind any online references on this direct topic. ItDo you have any suggestions?

Why the 8 4 3 2 0 polynomial? Or is difficult to determinethat just the complexity offirst one you picked? As far as generating a random field from the polynomial. But, by generating random fields the odds of getting a highly complex field are very goodrandom bais for g01, g02, . 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 fiels are are all the sameg80 works fine. ButThen I only need to generate another random basis for g02, g03, (as an engineer would say) practice and theory are different. And its that difference that is important.

My algorithm above is not quite correct. It turns outg81. There are some constraints there that I don't currently have enough information to use to directly constrain the sub-algorithm for buildingrandom generator, but brute force would work. I actually think that the main basis products is not rightcompletely constrains the g02, g03, . I have solved some.. basis (the first row / column in the basis multiplication table - that sufficies to ensure distribution and all of it,the other properties) but there are dependencies that I haven't identified yet. I don't know ifdetermined an efficient way to do that approach will work or not.

  Possibly a genetic algorithm. However, other approaches mayI would like to be just as good. Since finite fields ofmore intelligent about the same sizeprocess. If you are isomorphiccorrect, an alternative is to buildI 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 isomorphismaffine mapping should also work. That appears to haveis trivial - just create a lot ofbasis to ensure that the same problemsmatrix is invertable and add a random vector.

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

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

Update (edited in from a post below)

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 fiels are are all the same. But (as an engineer would say) practice and theory are different. And its 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.

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.

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"!

added 1782 characters in body
Source Link
mikeazo
  • 38.9k
  • 9
  • 117
  • 182

Update (edited in from a post below)

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 fiels are are all the same. But (as an engineer would say) practice and theory are different. And its 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.

Update (edited in from a post below)

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 fiels are are all the same. But (as an engineer would say) practice and theory are different. And its 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.

added extra information posted as an answer
Source Link
Loading
added 21 characters in body
Source Link
Loading
retag
Link
yyyyyyy
  • 12.2k
  • 4
  • 48
  • 68
Loading
Source Link
Loading