Jump to content
Double Fine Action Forums

Secret room

Recommended Posts

On 7/11/2018 at 11:35 PM, SmashManiac said:

if abcdefgh is a non-null byte, then it's multiplicative inverse in GF(2^8) ABCDEFGH can be found by resolving the following set of equations (addition is the XOR operator, and multiplication is the AND operator):


It's possible to solve this system of linear equations using elimination of variables or Gaussian elimination, but doing so appears to cause formulas to blow up

I just realized I previously made a mistake, and that the last sentence isn't quite accurate. Gaussian elimination is not really possible for the general case because you can at best multiply by the negation of a coefficient, which automatically eliminates the variable. So it doesn't seem like there's anything better than just feeding in values and see what sticks to come up with formulas.

So the approach I would do then is to pick an output variable and make it equal to the logical disjunction of all 128 conjunctions for which it's equal to 1, then convert all disjunctions to XORs by using the equivalence x V y <=> x + y + xy and all negations to XORs by using the equivalence ¬x <=> x+1, and then finally simplify the formula, which can go up to 256 XOR-separated clauses of up to 8 conjunctions. Of course, that needs to be repeated for each of the 8 output variables.

So unless the result turns out to be relatively simple somehow, trying to mix in 256 boolean variables (the key) and a few constants through XORs and applying the 8 resulting formulas 14 times (the number of rounds) just doesn't seem like a realistic approach to me right now.

Share this post

Link to post
Share on other sites

  • Create New...