This post is about Rijndael S-box which the first stage of AES encryption. It’s substitution lookup table. AES implementation usually uses pre-computed table. I thought it would be fun to calculate it in python to see it action.

From Wiki

the input is mapped to its multiplicative inverse in GF(28) = GF(2) [x]/(x8 + x4 + x3 + x + 1), Rijndael’s finite field. Zero, as the identity, is mapped to itself. This transformation is known as the Nyberg S-box after its inventor Kaisa Nyberg.[2] The multiplicative inverse is then transformed using the following affine transformation:

There are 2 stages

  • Multiplicative inverse in GF(2^8)
  • Affine transformation

Multiplicative inverse Link to heading

I am using brute-force in GF(256) to find inverse. Basically loop and break when GF multiplication results in 1.

p . q mod 0x11b = 1

Based on Link, The calculation

def mult(a,b):
    product = 0
    for i in range(8):
        if (b & 1) == 1:
            product ^= a
        hi_bit_set = a & 0x80
        a = (a << 1) & 0xFF
        if hi_bit_set == 0x80:
            a ^= 0x1B
        b >>= 1
    return product

def get_inverse(n):
    if n == 0 :
        return 0
    e = None
    for i in range(256):
        m = mult(n, i)
        if (m == 1):
            e = i
            break
    return e

Affinity transformation Link to heading

For the Affinity transformation, It can be calculated with multiple algorithms But I implemented the formula:

S = B + (B « 1) + (B « 2) + (B « 3) + (B « 4) + 0x63

Where + is bitwise xor and << is left rotate. B here is the output is multiplicative inverse above

For rotation, I used good old concat after transforming it with int2binstr. There is probably easier pythonic way but It’s 2 AM on Saturday night.

def rot1(v):
    bb = int2binstr(v)
    br = bb[1:] + bb[0]
    br = int(br, 2)
    return br

Putting it all together Link to heading 

def int2binstr(i):
    x = (bin(i)[2:]).zfill(8)
    return x

def rot1(v):
    bb = int2binstr(v)
    br = bb[1:] + bb[0]
    br = int(br, 2)
    return br

def rot(v, count):
    p = v
    for ii in range(count):
        p = rot1(p)
    return p

def affinity(b):
    s = b ^ rot(b, 1) ^ rot(b, 2) ^ rot(b, 3) ^ rot(b, 4) ^  0x63
    return s

def mult(a,b):
    product = 0
    for i in range(8):
        if (b & 1) == 1:
            product ^= a
        hi_bit_set = a & 0x80
        a = (a << 1) & 0xFF
        if hi_bit_set == 0x80:
            a ^= 0x1B
        b >>= 1
    return product

def get_inverse(n):
    if n == 0 :
        return 0
    e = None
    for i in range(256):
        m = mult(n, i)
        if (m == 1):
            e = i
            break
    return e

for n in range(256):
    e = get_inverse(n)
    s = affinity(e)
    print(f'[{int(n/16)}][{n%16}]={hex(s)}')