CODEWITHSUNDEEP
ccryptographyaesencryption-symmetric
ratbald_meyer_1995
ratbald_meyer_1995

Reputation: 9

Generation of Rijndael S-box

I am doing a brief research regarding the round transformations of the AES-128 and came across the Wikipedia article describing the generation of the substitution box (https://en.wikipedia.org/wiki/Rijndael_S-box) from the mathematical point of view.

In the corresponding article, it was explained that a given element of the extension field GF(2^8) is initially inverted with respect to x⁸+x⁴+x³+x+1.

Subsequently, the result (inverse element) is undergoing an affine transformation. The transformation itself is actually comprehensible. However, I do not understand the corresponding C-implementation at all.

My naive approach to understand the below shown implementation was to think of the matrix multiplication as a linear combination of the columns of this matrix weighted with the bits of the inverse element. Since the columns of this matrix seem to be cyclicly shifted this could somehow explain the execution of ROTL8 in the affine transformation. In the end, the addition with 0x63 is actually quite clear.

#define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256]) {
    uint8_t p = 1, q = 1;
    
    /* loop invariant: p * q == 1 in the Galois field */
    do {
        /* multiply p by 3 */
        p = p ^ (p << 1) ^ (p & 0x80 ? 0x11B : 0);

        /* divide q by 3 (equals multiplication by 0xf6) */
        q ^= q << 1;
        q ^= q << 2;
        q ^= q << 4;
        q ^= q & 0x80 ? 0x09 : 0;

        /* compute the affine transformation */
        uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);

        sbox[p] = xformed ^ 0x63;
    } while (p != 1);

    /* 0 is a special case since it has no inverse */
    sbox[0] = 0x63;
}

Would it be possible to explain how the matrix multiplication in the affine transformation can be interpreted as the addition (XOR) of the rotated terms (ROTL8) of the inverse element?

Upvotes: 0

Views: 793

Answers (0)

Related Questions