Permuting Bits with GF2P8AFFINEQB

https://gist.github.com/animetosho/d3ca95da2131b5813e16b5bb1...

* A Galois Field is a mathematical structure where addition and multiplication have been redefined so that some very useful properties are retained. Galois Fields can exist with any prime number or an "extension field" where that prime-number is vectorized. In this case, the GF2 field (prime number 2) has been extended to 8-bits (aka: a GF(2^8), aka 8-bit Galois Field).

* "Addition"'s new definition is simply XOR.

* "Multiply"'s new definition is bitshift and then add. (ie: 0b10101010 x 0b00010010 == bitshift(x, 4) + bitshift(x, 1), because the 4th and 1st bits are set to 1). And remember that "addition" has been redefined to XOR in this math, so that + means XOR.

* An Affine Transformation is A * x + B, where x is the original value. As a "Galois Field Affine Transformation", A * x and + B are all done in "Galois Field" terms.

* This is an AVX512 instruction, meaning there are 32-parallel versions of this 8-bit computation happening in parallel across a 512-bit vector.

Note: operation traditionally happens modulo a particular GF(number) to create a field. The above operations are "primitives" that can eventually create a field, but aren't making a field just yet.

Perhaps the more accurate names for these operations is "GF-addition" and "GF-pseudo-multiplication". In any case, multiplication is any combination of the 8-bitshifts (bitshift0, bitshift1, bitshift2...) and the 8x such results added together (depending on the 1 or 0 on that bit). Meaning you can very easily describe bitshift-and-xor operations to other cryptographers who are operating in "GF-language".

Its actually really easy, though the terminology is a pain in the ass.

----------

Traditionally, this multiplication on Intel has been called "carryless multiplication" (clmul) and "polynomial multiplication" (pmull) on ARM. I preferred these names personally.

But if Intel wants to call this the "gfp8affineqb", then so be it, they're the ones naming this instruction not me. Its... a reasonable name, I feel like a better name exists out there but I can't think of one. But its certainly not a perfect name IMO. Maybe "clp8affineqb" ("carryless 8-bit affine") would be my preference?

Note: Remember that "x / y" division in a field is simply "x * (1/y)", because (1/y) is always uniquely defined in a field and "proper". So in practice, its actually a whole lot of multiplies.

Note2: For the 8-bit domain to become a field, you must perform a "modulo p", where p is prime (for simple fields), or an irreducible polynomial (for an extension field). For us computer-programmers, we're almost always operating on an extension field (8-vector of field(2), aka a binary vector of size 8-bits). (Though hardware designers may choose say, GF(2^5), the 5-bit numbers, for USB1.0 packets for example)

So you need to perform the operation (x modulo p) and normalize the result to return it to a field. There are different fields for each chosen p, so the first step is to choose a p. P is almost always chosen arbitrarily, but there's benefits to different p's chosen. In any case, p differs from case-to-case since they have minor benefits (this p might be slightly faster at multiplication in software, this other p might have an easier circuit layout and is related to some simple LSFR, etc. etc.). So p is arbitrary and changes from case-to-case.

After that, (x modulo p) is performed by (x / p), which results in (quotient + remainder/p). In practice, one iteration of this operation commonly results in a 9-bit number or 10-bit number or 16-bit number. Anything 9 to 16 bits in length is obviously "not in GF(2^8)", so we repeatedly perform the operation until the top-bits are zero and we only have an 8-bit result.

(remainder/p) is simply (remainder * (1/p)), because this is a field (all numbers 1/x are properly defined), so we can "implement" this in practice through multiplications only.

--------------

And that's all CRC-32 and Reed Solomon Encoding is.

EDIT: I'm not sure if what I said originally was correct. I decided to change the "modulo" algorithm to the LSFR style which was simpler for me to discuss.

I only learned of this operation from reading this blogpost. "Permuting Bits" seems like a bloody obvious use of this instruction, but honestly, anyone who is familiar with carry-less multiplication will immediately see the widespread capabilities of this instruction.

It really demonstrates to me that once again, Intel and their design of AVX512 has some very smart people in there. Its a good, flexible, operation. Albeit arcane and few people probably see how to use this instruction well, but its really exciting to see "such a good idea" from them.

GF(2^8) fields (aka: 8-bit GF operations) are used in all sorts of CRC, Error-correction Reed Solomon, Elliptical Curve, etc. etc. operations. But beyond just that, bitshifts and xors innately have a huge number of applications outside of cryptography or GF-stuffs. It makes sense to make a dedicated instruction like this.

------

EDIT: Upon rereading the end of the blogpost:

> I will probably keep using a SAT solver to solve the masks

Yeah, that's actually what's needed to generalize this.

Note: common operations like "if(a) b else c", or "min(a, b)", or such can likely be specified in terms of AVX512 operations now.

Powerful, efficient, operations like GF2P8AFFINEQB, pext, pdep, and pshufb are getting damn close to an FPGA-like parallel processor.

I mean, pshufb is already an arbitrary 4-bit truth table / 4-LUT if you think about it.