0
$\begingroup$

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

$\endgroup$
0

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I have second question about number 99. I suspect this is about some sort of balancing the most significant bit problem (if I'm right, this even could be a problem), which are always equal to 1 in every number. But I can't make an equivalent of that number for my example. Do you know where the number 99 came from? What there could be in GF(2^128)? $\endgroup$
    – Tom
    May 15, 2022 at 5:57
  • $\begingroup$ I'm trying to check it by hand and this doesn't work for me. Is there reduction by some polynomial or is x 31 just carry-less multiplication? In both cases it seem doesn't work. Let's take b = 10000001. b <<< 1 = 000000011. b <<< 2 = 00000110. b <<< 3 = 00001100. b <<< 4 = 00011000. So xor = 10000001 ^ 00000011 ^ 00000110 ^ 00001100 ^ 00011000 = 10010000. This is not equal to 129 x 31 in GF(2^8), which is 111110011111. I didn't try to reduce it by some polynomial, but I don't believe it would give right result. Is there really circular shift or normal bitwise shift??? $\endgroup$
    – Tom
    May 15, 2022 at 7:59
  • $\begingroup$ I reduced it by polynomial x^9+1. And finally it works. $\endgroup$
    – Tom
    May 16, 2022 at 3:14
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How did you define b <<< 1. Let's take 8-bit number b=10000001. What is b <<< 1? $\endgroup$
    – Tom
    May 16, 2022 at 2:32
  • $\begingroup$ And is mod 257 is mod polynomial x^8+1 in GF(s^8) or is this just normal modulo operation? $\endgroup$
    – Tom
    May 16, 2022 at 2:45
1
$\begingroup$

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:

enter image description 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$.

$\endgroup$
1
  • 1
    $\begingroup$ In $\LaTeX$ there is \ll \lll \gg and \ggg to produce $\ll, \quad \lll, \quad \gg \quad \text{ and } \quad \ggg$ $\endgroup$
    – kelalaka
    May 18, 2022 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.