4 x E = D in Simplified AES how it's possible?

Question

Can anyone explain how it's possible through hexadecimal or Binary 4 x E= D

Answer 1

The Simplified AES uses the Galois field GF(16), which can be represented by polynomials over the F_2 field:

hex ... bin  ... polynomial
  1 ... 0001 ... 1
  2 ... 0010 ... x
  3 ... 0011 ... x + 1
  4 ... 0100 ... x^2
    ...      ... 
  n ... abcd ... ax^3 + bx^2 + cx + d
    ...      ...
  F ... 1111 ... x^3 + x^2 + x + 1

with multiplication defined as

a mul b := ((a_1 x^3 + a_2 x^2 + a_3 x + a_4) x (b_1 x^3 + b_2 x^2 + b_3 x + b_4)) mod x^4 + x + 1

Let's compute 4 x E:

x^2 x (x^3 + x^2 + x) = x^5 + x^4 + x^3
x^5 + x^4 + x^3 mod x^4 + x + 1 = x (x + 1) + x + 1 + x^3
                                = x^2 + x + x + 1 + x^3
                                = x^3 + x^2 + 1

Now we can use our table above to conclude:

x^3 + x^2 + 1 ... 1101 ... D

---

Extra info based on OP's request:

The whole multiplication table of GF(16) built by x^4 + x + 1:

  || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
---------------------------------------------------------------------
0 || 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
2 || 0 | 2 | 4 | 6 | 8 | A | C | E | 3 | 1 | 7 | 5 | B | 9 | F | D |
3 || 0 | 3 | 6 | 5 | C | F | A | 9 | B | 8 | D | E | 7 | 4 | 1 | 2 |
4 || 0 | 4 | 8 | C | 3 | 7 | B | F | 6 | 2 | E | A | 5 | 1 | D | 9 |
5 || 0 | 5 | A | F | 7 | 2 | D | 8 | E | B | 4 | 1 | 9 | C | 3 | 6 |
6 || 0 | 6 | C | A | B | D | 7 | 1 | 5 | 3 | 9 | F | E | 8 | 2 | 4 |
7 || 0 | 7 | E | 9 | F | 8 | 1 | 6 | D | A | 3 | 4 | 2 | 5 | C | B |
8 || 0 | 8 | 3 | B | 6 | E | 5 | D | C | 4 | F | 7 | A | 2 | 9 | 1 |
9 || 0 | 9 | 1 | 8 | 2 | B | 3 | A | 4 | D | 5 | C | 6 | F | 7 | E |
A || 0 | A | 7 | D | E | 4 | 9 | 3 | F | 5 | 8 | 2 | 1 | B | 6 | C |
B || 0 | B | 5 | E | A | 1 | F | 4 | 7 | C | 2 | 9 | D | 6 | 8 | 3 |
C || 0 | C | B | 7 | 5 | 9 | E | 2 | A | 6 | 1 | D | F | 3 | 4 | 8 |
D || 0 | D | 9 | 4 | 1 | C | 8 | 5 | 2 | F | B | 6 | 3 | E | A | 7 |
E || 0 | E | F | 1 | D | 3 | 2 | C | 9 | 7 | 6 | 8 | 4 | A | B | 5 |
F || 0 | F | D | 2 | 9 | 6 | 4 | B | 1 | E | C | 3 | 8 | 7 | 5 | A |

and my C# multiplication method:

private static readonly byte[] BITS = { 1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 };
private static byte mul(byte a, byte b)
    {
        if (a == 0 || b == 0) return 0;
        if (a == 1) return b;
        if (b == 1) return a;

        byte res = 0;
        for (int i = 0; i < 4; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                if ((a & BITS[i]) != 0 && (b & BITS[j]) != 0)
                {
                    res ^= BITS[i + j];
                }
            }
        }

        if (res >= 8)
        {
            bool ok = false;
            while (!ok)
            {
                ok = true;
                for (int i = 4; i < 7; ++i)
                {
                    if ((res & BITS[i]) != 0)
                    {
                        res ^= BITS[i];
                        int j = i - 4;
                        res ^= BITS[j];
                        res ^= BITS[j + 1];
                        ok = false;
                    }
                }
            }
        }
        return res;
    }