Score:0

Crypto

Generalizing AES s-box circular shifts in bigger GF

Tom

9/14/23, 7:57 AM

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

0 + 0

s-boxes

aes

Score:3

Crypto

kodlu

9/14/23, 1:27 PM

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.

0 + 0

Tom

9/15/23, 5:57 AM

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)?

Tom

9/15/23, 7:59 AM

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

Tom

9/16/23, 3:14 AM

I reduced it by polynomial x^9+1. And finally it works.

Score:1

Crypto

Tom

9/16/23, 4:04 AM

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

0 + 0

kelalaka

9/18/23, 3:39 PM

In $\LaTeX$ there is `\ll \lll \gg` and `\ggg` to produce $\ll, \quad \lll, \quad \gg \quad \text{ and } \quad \ggg$

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Generalizing AES s-box circular shifts in bigger GF

TH: การทำให้ AES s-box เปลี่ยนไปเป็นวงกลมโดยทั่วไปใน GF ที่ใหญ่ขึ้น

RO: Generalizarea schimburilor circulare AES s-box în GF mai mare

RU: Обобщение циклических сдвигов s-box AES в больших GF

VI: Tổng quát hóa các dịch chuyển vòng tròn của hộp s AES trong GF lớn hơn

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.