Generalizing AES s-box circular shifts in bigger GF

Question

According to wikipedia:

https://en.wikipedia.org/wiki/Rijndael_S-box

AES is doing interesting thing (where $<<<$ is circular shift):

$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$

and this is equal to ($\times$ is multiplication in $GF(2^8)$):

$s = b \times 31 \mod 257$

This provides a great bit of mixing to my eye. Let's say I have 128 bit $x$ and $y$ and I want to compute something similar:

$x = y \oplus (y \lll 1) \oplus (y \lll 2) \oplus (y \lll 3) \oplus ... \oplus (y \lll 64)$

Can I do it faster using multiplication in $GF(2^{128}) \mod 2^{128}+1$? I don't know the theory behind this, so I have two types of multipliers for this:

$2^{125}-1$

and

$2^{65}-1$

I think this second one may work in the same way in $GF(2^{128})$, this is the rule. So is there a similar number that I can use? What is that number?

EDIT: It looks like there is mistake in article and circular shift could be in other direction:

$s = b \oplus (b \ggg 1) \oplus (b \ggg 2) \oplus (b \ggg 3) \oplus (b \ggg 4)$

Anyway, can we generalize it? In this document there is nothing about equality to GF multiplication of that step:

https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf

Answer 1

OK, the left vs right shift issue has to do with if the variable is represented by "big-endian" or "little-endian" convention, i.e., if the Least Significant Bit is on the left or on the right.

The operation:

$$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$$

is equivalent to the multiplication (where the shift is $\times x$ below)

$$ s(x)=b(x)(1+x+x^2+x^3+x^4)=b(x)\frac{x^5-1}{x-1} $$ but since left shift is also doubling, let $x=2,$ to get $s(x)=(2^5-1)b(x).$ In any case cyclic shift is equivalent to operating $\pmod x^n-1$ where $n$ is the wordlength in bits.

Your second operation is indeed equivalent to multiplication by $2^{65}-1.$

Since you seem mathematically capable enough, I'd suggest:

Read the document "AES Proposal" by Daemen and Rijmen in full to get familiar with these types of operations and representations. There is also the book The Design of Rijndael by the same authors. You are learning about the interplay between Galois Fields of characteristic 2, $GF(2^n)$ and integer rings $\mathbb{Z}_{2^n-1}$ which can also be "decomposed" into $\mathbb{Z}_{2^{n/2}-1} \times \mathbb{Z}_{2^{n/2}+1},$ when $n$ is even. Another place to look is documentation regarding the design of SAFER-64 by Jim Massey. More generally Number Theoretic Transforms (NTTs) which generalize the Fast Fourier Transform.

If you have recursive decompositions of the type I mentioned above, you have fast implementations. The simplest such transform is the Sylvester Hadamard matrix used in Fast Walsh-Hadamard transforms where $n$ Kronecker products of the same matrix $H_2$ is used: $$ H_n =H_2 \otimes H_2 \otimes \cdots \otimes H_2 $$ with $$ H_2=\left[\begin{array}{cc} +1 & +1 \\ +1 & -1 \end{array} \right]. $$ Since this is the Fourier transform for the binary vector space $GF(2)^n=\{0,1\}^n$ equivalently the rows of the Hadamard matrix above are the group characters of the additive group of $(\mathbb{GF(2)^n},\oplus)$ it all makes sense.

Anyway, happy reading.

Answer 2

I calculated the matrix from the Wikipedia article and independently calculated the xor-rotation sequence from the matrix.

The matrix I calculated matches the Wikipedia article

  {1, 0, 0, 0, 1, 1, 1, 1}
  {1, 1, 0, 0, 0, 1, 1, 1}
  {1, 1, 1, 0, 0, 0, 1, 1}
  {1, 1, 1, 1, 0, 0, 0, 1}
  {1, 1, 1, 1, 1, 0, 0, 0}
  {0, 1, 1, 1, 1, 1, 0, 0}
  {0, 0, 1, 1, 1, 1, 1, 0}
  {0, 0, 0, 1, 1, 1, 1, 1}

The matrix was calculated using the formula

$$s=\left(b\times 31_{10}\mod {257_{10}}\right)$$

I automatically calculated the following xor-rotation sequence from the matrix

(b <<< 0) xor (b <<< 1) xor (b <<< 2) xor (b <<< 3) xor (b <<< 4)

which matches the sequence of operations on the Wikipedia page.

I made a 128x128 matrix from the formula

$$s=\left(b\times 31_{10}\mod c\right)$$

where I chose the constant $c$ to be the bit array represented by the polynomial, $c = x^{128} - 1$. I did not change the constant $31_{10}$ from the original formula.

I cannot paste the matrix here as it is very large. It is full of zeros and is just a cyclic shift of the $31_{10}$ constant.

The xor-rotation sequence that I computed for the matrix is

(b <<< 0) xor (b <<< 1) xor (b <<< 2) xor (b <<< 3) xor (b <<< 4)

This might be slightly surprising as it is identical to the GF(2^8) case however it is just one rotation term for each nonzero component of the $31_{10}$ constant. The rotations are for a 128-bit vector, of course.

I tested 1,000,000 random inputs using both the matrix and xor-rotation versions of this GF(2^128) generalization and found that the outputs were identical.

Answer 3

There is something misleading in Wikipedia article. They wrote:

$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$

Is equal to:

$s = b \times 31 \mod 257$

where $\times$ is polynomial multiplication of $b$ and $31$ taken as bit arrays. But $\mod 257$ is not standard modulo operation, it is mod in $GF(2^8)$ and $257$ is in fact polynomial of the form $x^{9}+1$.

We can easily see that carry-less multiplication of $b \times 31$ is equal to:

$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$

in bits $7,6,5,4$, where $\ll$ is bitwise shift, not circualr sfift. But in Wikipedia example and in AES there is circular shift. So where does circular come from? It comes from reduction by the polynomial $x^9+1$. This is how multiplication with polynomial reduction works in $GF(2^8)$:

#include <cstdint>
#include <cstdio>
#include <bitset>
#include<iostream>


uint8_t multiply(uint a, uint b)
    {
        uint8_t p = 1;
        uint16_t L = 1;
        uint16_t c = 0;

        for (unsigned int i = 0; i < 8; ++i)
        {
            c ^= a & (L << i) ? (uint16_t)b << i : 0;
        }

        for (unsigned int i = 8; i-- > 0; )
        {
            if (c & (L << (i + 8)))
            {
                c ^= L << (i + 8);
                c ^= (uint16_t)p << i;
            }
        }

        return (uint8_t)c;
    }

int main()
{
    uint result = 0;
    
    result = multiply(131,31);
    std::cout << result;
    
    return 0;
}

We need polynomial of degree $9$, but we can define reducing polynomial in practical implementation by taking only its first $8$ least significant bits, so in our case $p=1$. Now if we look how carry-less multiplication works (first loop), we can see that in $7,6,5,4$ bits we would get the same result, as with shifts:

$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$

But in place of bits $11,10,9,8$ will be exactly bits shifted (canceled) out in process of bitwise shift. This is because carry-less multiplication move them to the left by $1,2,3...$ positions and then all is xored. Like here:

Since we are multiplicating by $31$ we would get always $4$ extra bits in higher significant half of our 16-bit result. And they would be xored, because this is how carry-less multiplication works. So now we got bits $7,6,5,4$ equal to the result of:

$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$

And bits $11,10,9,8$, which could be in place of bits $3,2,1,0$. To make circular shift we need to only xor back this bits. This is done by:

for (unsigned int i = 8; i-- > 0; )
        {
            if (c & (L << (i + 8)))
            {
                c ^= L << (i + 8);
                c ^= (uint16_t)p << i;
            }
        }

If $p=1$. We can see that this code is really checking is there bit equal to $1$ on the left on position $i$ of our top half, and if it is, then it xor that bit with bit $i$ on our low half. And all that algorithm is equal to xoring with circialr shift $\lll$:

$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$

Knowing this it becomes clear that this kind of equivalence holds for any $GF(2^k)$, provided we choose $p=1$ (by the convention of the posted code) as our polynomial and multiplier equal to $2^{\frac {k}{2}+1}-1$.