AES (08) Finding Modular Multiplicative Inverse Using Lookup Table

Lookup table is just a precomputed table. So why is it here? That's easy my friend! So You can make tests for Your software. Why don't we always use a table like that? Because if we have a system that can store 256 bytes of data we can store the entire S-Box and all of this is useless anyway.

Modular Equations

You can easily create the lookup table using equations below. I don't want to make Your life to easy. You have to work with some regular expressions to get the data you need. To make everything harder I put values in hexadecimal. And just note that inverse for $\text{ 0x00 }$ does not exist.

$\text{ 0x01 } \cdot \text{ 0x01 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x02 } \cdot \text{ 0x8D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x03 } \cdot \text{ 0xF6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x04 } \cdot \text{ 0xCB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x05 } \cdot \text{ 0x52 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x06 } \cdot \text{ 0x7B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x07 } \cdot \text{ 0xD1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x08 } \cdot \text{ 0xE8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x09 } \cdot \text{ 0x4F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0A } \cdot \text{ 0x29 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0B } \cdot \text{ 0xC0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0C } \cdot \text{ 0xB0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0D } \cdot \text{ 0xE1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0E } \cdot \text{ 0xE5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x0F } \cdot \text{ 0xC7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x10 } \cdot \text{ 0x74 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x11 } \cdot \text{ 0xB4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x12 } \cdot \text{ 0xAA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x13 } \cdot \text{ 0x4B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x14 } \cdot \text{ 0x99 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x15 } \cdot \text{ 0x2B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x16 } \cdot \text{ 0x60 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x17 } \cdot \text{ 0x5F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x18 } \cdot \text{ 0x58 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x19 } \cdot \text{ 0x3F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1A } \cdot \text{ 0xFD } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1B } \cdot \text{ 0xCC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1C } \cdot \text{ 0xFF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1D } \cdot \text{ 0x40 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1E } \cdot \text{ 0xEE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x1F } \cdot \text{ 0xB2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x20 } \cdot \text{ 0x3A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x21 } \cdot \text{ 0x6E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x22 } \cdot \text{ 0x5A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x23 } \cdot \text{ 0xF1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x24 } \cdot \text{ 0x55 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x25 } \cdot \text{ 0x4D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x26 } \cdot \text{ 0xA8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x27 } \cdot \text{ 0xC9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x28 } \cdot \text{ 0xC1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x29 } \cdot \text{ 0x0A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2A } \cdot \text{ 0x98 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2B } \cdot \text{ 0x15 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2C } \cdot \text{ 0x30 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2D } \cdot \text{ 0x44 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2E } \cdot \text{ 0xA2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x2F } \cdot \text{ 0xC2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x30 } \cdot \text{ 0x2C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x31 } \cdot \text{ 0x45 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x32 } \cdot \text{ 0x92 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x33 } \cdot \text{ 0x6C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x34 } \cdot \text{ 0xF3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x35 } \cdot \text{ 0x39 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x36 } \cdot \text{ 0x66 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x37 } \cdot \text{ 0x42 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x38 } \cdot \text{ 0xF2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x39 } \cdot \text{ 0x35 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3A } \cdot \text{ 0x20 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3B } \cdot \text{ 0x6F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3C } \cdot \text{ 0x77 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3D } \cdot \text{ 0xBB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3E } \cdot \text{ 0x59 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x3F } \cdot \text{ 0x19 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x40 } \cdot \text{ 0x1D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x41 } \cdot \text{ 0xFE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x42 } \cdot \text{ 0x37 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x43 } \cdot \text{ 0x67 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x44 } \cdot \text{ 0x2D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x45 } \cdot \text{ 0x31 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x46 } \cdot \text{ 0xF5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x47 } \cdot \text{ 0x69 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x48 } \cdot \text{ 0xA7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x49 } \cdot \text{ 0x64 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4A } \cdot \text{ 0xAB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4B } \cdot \text{ 0x13 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4C } \cdot \text{ 0x54 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4D } \cdot \text{ 0x25 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4E } \cdot \text{ 0xE9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x4F } \cdot \text{ 0x09 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x50 } \cdot \text{ 0xED } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x51 } \cdot \text{ 0x5C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x52 } \cdot \text{ 0x05 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x53 } \cdot \text{ 0xCA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x54 } \cdot \text{ 0x4C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x55 } \cdot \text{ 0x24 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x56 } \cdot \text{ 0x87 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x57 } \cdot \text{ 0xBF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x58 } \cdot \text{ 0x18 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x59 } \cdot \text{ 0x3E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5A } \cdot \text{ 0x22 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5B } \cdot \text{ 0xF0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5C } \cdot \text{ 0x51 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5D } \cdot \text{ 0xEC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5E } \cdot \text{ 0x61 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x5F } \cdot \text{ 0x17 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x60 } \cdot \text{ 0x16 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x61 } \cdot \text{ 0x5E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x62 } \cdot \text{ 0xAF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x63 } \cdot \text{ 0xD3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x64 } \cdot \text{ 0x49 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x65 } \cdot \text{ 0xA6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x66 } \cdot \text{ 0x36 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x67 } \cdot \text{ 0x43 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x68 } \cdot \text{ 0xF4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x69 } \cdot \text{ 0x47 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6A } \cdot \text{ 0x91 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6B } \cdot \text{ 0xDF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6C } \cdot \text{ 0x33 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6D } \cdot \text{ 0x93 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6E } \cdot \text{ 0x21 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x6F } \cdot \text{ 0x3B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x70 } \cdot \text{ 0x79 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x71 } \cdot \text{ 0xB7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x72 } \cdot \text{ 0x97 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x73 } \cdot \text{ 0x85 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x74 } \cdot \text{ 0x10 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x75 } \cdot \text{ 0xB5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x76 } \cdot \text{ 0xBA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x77 } \cdot \text{ 0x3C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x78 } \cdot \text{ 0xB6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x79 } \cdot \text{ 0x70 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7A } \cdot \text{ 0xD0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7B } \cdot \text{ 0x06 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7C } \cdot \text{ 0xA1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7D } \cdot \text{ 0xFA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7E } \cdot \text{ 0x81 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x7F } \cdot \text{ 0x82 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x80 } \cdot \text{ 0x83 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x81 } \cdot \text{ 0x7E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x82 } \cdot \text{ 0x7F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x83 } \cdot \text{ 0x80 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x84 } \cdot \text{ 0x96 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x85 } \cdot \text{ 0x73 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x86 } \cdot \text{ 0xBE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x87 } \cdot \text{ 0x56 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x88 } \cdot \text{ 0x9B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x89 } \cdot \text{ 0x9E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8A } \cdot \text{ 0x95 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8B } \cdot \text{ 0xD9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8C } \cdot \text{ 0xF7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8D } \cdot \text{ 0x02 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8E } \cdot \text{ 0xB9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x8F } \cdot \text{ 0xA4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x90 } \cdot \text{ 0xDE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x91 } \cdot \text{ 0x6A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x92 } \cdot \text{ 0x32 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x93 } \cdot \text{ 0x6D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x94 } \cdot \text{ 0xD8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x95 } \cdot \text{ 0x8A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x96 } \cdot \text{ 0x84 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x97 } \cdot \text{ 0x72 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x98 } \cdot \text{ 0x2A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x99 } \cdot \text{ 0x14 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9A } \cdot \text{ 0x9F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9B } \cdot \text{ 0x88 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9C } \cdot \text{ 0xF9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9D } \cdot \text{ 0xDC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9E } \cdot \text{ 0x89 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0x9F } \cdot \text{ 0x9A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA0 } \cdot \text{ 0xFB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA1 } \cdot \text{ 0x7C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA2 } \cdot \text{ 0x2E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA3 } \cdot \text{ 0xC3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA4 } \cdot \text{ 0x8F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA5 } \cdot \text{ 0xB8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA6 } \cdot \text{ 0x65 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA7 } \cdot \text{ 0x48 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA8 } \cdot \text{ 0x26 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xA9 } \cdot \text{ 0xC8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAA } \cdot \text{ 0x12 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAB } \cdot \text{ 0x4A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAC } \cdot \text{ 0xCE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAD } \cdot \text{ 0xE7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAE } \cdot \text{ 0xD2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xAF } \cdot \text{ 0x62 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB0 } \cdot \text{ 0x0C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB1 } \cdot \text{ 0xE0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB2 } \cdot \text{ 0x1F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB3 } \cdot \text{ 0xEF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB4 } \cdot \text{ 0x11 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB5 } \cdot \text{ 0x75 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB6 } \cdot \text{ 0x78 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB7 } \cdot \text{ 0x71 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB8 } \cdot \text{ 0xA5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xB9 } \cdot \text{ 0x8E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBA } \cdot \text{ 0x76 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBB } \cdot \text{ 0x3D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBC } \cdot \text{ 0xBD } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBD } \cdot \text{ 0xBC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBE } \cdot \text{ 0x86 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xBF } \cdot \text{ 0x57 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC0 } \cdot \text{ 0x0B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC1 } \cdot \text{ 0x28 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC2 } \cdot \text{ 0x2F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC3 } \cdot \text{ 0xA3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC4 } \cdot \text{ 0xDA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC5 } \cdot \text{ 0xD4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC6 } \cdot \text{ 0xE4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC7 } \cdot \text{ 0x0F } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC8 } \cdot \text{ 0xA9 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xC9 } \cdot \text{ 0x27 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCA } \cdot \text{ 0x53 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCB } \cdot \text{ 0x04 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCC } \cdot \text{ 0x1B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCD } \cdot \text{ 0xFC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCE } \cdot \text{ 0xAC } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xCF } \cdot \text{ 0xE6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD0 } \cdot \text{ 0x7A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD1 } \cdot \text{ 0x07 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD2 } \cdot \text{ 0xAE } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD3 } \cdot \text{ 0x63 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD4 } \cdot \text{ 0xC5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD5 } \cdot \text{ 0xDB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD6 } \cdot \text{ 0xE2 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD7 } \cdot \text{ 0xEA } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD8 } \cdot \text{ 0x94 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xD9 } \cdot \text{ 0x8B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDA } \cdot \text{ 0xC4 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDB } \cdot \text{ 0xD5 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDC } \cdot \text{ 0x9D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDD } \cdot \text{ 0xF8 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDE } \cdot \text{ 0x90 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xDF } \cdot \text{ 0x6B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE0 } \cdot \text{ 0xB1 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE1 } \cdot \text{ 0x0D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE2 } \cdot \text{ 0xD6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE3 } \cdot \text{ 0xEB } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE4 } \cdot \text{ 0xC6 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE5 } \cdot \text{ 0x0E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE6 } \cdot \text{ 0xCF } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE7 } \cdot \text{ 0xAD } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE8 } \cdot \text{ 0x08 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xE9 } \cdot \text{ 0x4E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xEA } \cdot \text{ 0xD7 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xEB } \cdot \text{ 0xE3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xEC } \cdot \text{ 0x5D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xED } \cdot \text{ 0x50 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xEE } \cdot \text{ 0x1E } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xEF } \cdot \text{ 0xB3 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF0 } \cdot \text{ 0x5B } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF1 } \cdot \text{ 0x23 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF2 } \cdot \text{ 0x38 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF3 } \cdot \text{ 0x34 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF4 } \cdot \text{ 0x68 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF5 } \cdot \text{ 0x46 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF6 } \cdot \text{ 0x03 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF7 } \cdot \text{ 0x8C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF8 } \cdot \text{ 0xDD } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xF9 } \cdot \text{ 0x9C } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFA } \cdot \text{ 0x7D } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFB } \cdot \text{ 0xA0 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFC } \cdot \text{ 0xCD } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFD } \cdot \text{ 0x1A } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFE } \cdot \text{ 0x41 } \equiv \text{0x01} \; (\text{mod}\ 283)$
$\text{ 0xFF } \cdot \text{ 0x1C } \equiv \text{0x01} \; (\text{mod}\ 283)$

Lookup Table

Because I feel generous today.

AES (07) Galois Division

We just learned about multiplication, so there must be a division. Right? Nope! There is no division! I guess someone was to lazy to think up anything smart. Instead of dividing you just multiply by something called "Modular Multiplicative Inverse". Finding it is very easy and very hard at the same time.

Division

Imagine that someone told You in school to divide two numbers, but You totally forgot how to do that. You are smart so You will probably write something like this.

$a / b = a \cdot \frac{1}{b} = a \cdot x, \quad x = \frac{1}{b}$

Great now we don't need to divide anything. All we have to do is to find that $x$ That can't be to hard, can it? Let's call it a "Multiplicative Inverse of $b$" and write everything about it that we can think of.

$b \cdot \frac{1}{b} = b \cdot x = 1$

That's not a lot, but believe me it's enough! This means that to find $x$ we need to find a number that multiplied by $b$ will result in neutral element of multiplication.

Modular Multiplicative Inverse

Let's go back to our topic. We need to write that previous equation using Galois finite field operations that we already know.

$(b \cdot x) \;\%\; 283 = 1$

I will also change notation a bit to make future equations a little easier to write. From now on I will write everything in commonly accepted way of writing finite field arithmetic.

$b \cdot x \equiv 1 \; (\text{mod}\ 283)$

So how to calculate that pesky little $x$? There are few ways that we can do that. Each one of them has its own pros and cons.

• Using Lookup Table
• Using Extended Euclidean Algorithm
• Using Fermat's Little Theorem
• Using Logarithm Table

Why are You are still here? Click one of them!

AES (06) Galois Multiplication

Multiplication is usually based on addition. When we have to add value $x$ exactly $y$ amount of times we can just multiply $x \cdot y$ to get the same value. Can we do it here with Galois addition? No! When we add two identical values together we end up with a neutral element of addition! $x \oplus x = 0$ It's not very crypto when you can simply guess the result!

Multiplication

Inside Galois Field the multiplication is defined in a very particular way. The moment we see a "$\cdot$" we stop thinking about the number as a binary value, we think about it as a polynomial. Let's take numbers $83$ and $202$ and write them in binary.

$83 = 01010011b$
$202 = 11001010b$

We use the bit values from those numbers to create two polynomials.

$0x^7 + 1x^6 + 0x^5 + 1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$
$1x^7 + 1x^6 + 0x^5 + 0x^4 + 1x^3 + 0x^2 + 1x^1 + 0x^0$

And multiply those polynomials.

$(x^6 + x^4 + x^1 + x^0) \cdot (x^7 + x^6 + x^3 + x^1)$
$=$
\begin{align*} (x^{13} + x^{12} + x^{9} + x^{7}) + (x^{11} + x^{10} + x^{7} + x^{5}) + (x^{8} + x^{7} + x^{4} + x^{1}) + (x^{7} + x^{6} + x^{3} + x^{1}) \end{align*}
$=$
\begin{align*} 1x^{13} + 1x^{12} + 1x^{11} + 1x^{10} + 1x^{9} + 1x^{8} + 4x^{7} + 1x^{6} + 1x^{5} + 1x^{4} + 1x^{3} + 1x^{1} + 0x^{0}\end{align*}

Now we have to switch it back from the polynomial to a number. First we take all the constants write them down.

$1111114111110$

Time to make a classical "modulo two" on every digit. This means that we change every even number to $0$, and every odd number to $1$. This leaves is with a large binary number.

$1111110111110b$

The size of the value is a problem because we only have eight bits to store the solution. To solve it we need to use Galois Modulo and our old friend number $283$.

$1111110111110b \;\%\; 283$
$=$
$1111110111110b \;\%\; 100011011b$
$=$
$00000001b$

This will become very interesting in next chapter, but first I need to explain another concept.

Neutral Element

What's the neutral element of Galois Multiplication? I will prove you that it's a vector of eight bits that looks exactly like this

$00000001b$.

Now pay attention! I'm proving it by multiplying two binary values.

$a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0} \quad a_{x} \in \{0,1\}$
$00000001b$

Now we change them into polynomials.

$a_{7}x^7 + a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0$
$0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0$

And multiply them as above.

$(a_{7}x^7 + a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0)$
$\cdot$
$(0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0)$
$=$
$(a_{7}x^7 + a_{6}x^6 + a_{5}x^5 + a_{4}x^4 + a_{3}x^3 + a_{2}x^2 + a_{1}x^1 + a_{0}x^0)$

When we change it back from polynomial into binary we get again

$a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0} \quad a_{x} \in \{0,1\}$

AES (05) Galois Modulo

Remember the value $283$ I wrote few chapters ago? Now we are going to use it. Imagine that we have an operation that ends up giving us $27226$. That's way bigger than $2^8-1$. We need to make the result much smaller. Fortunately there is a method to do that. Inside our field we can define something called a modulo. Fortunately for us computers can perform it very easily. Let's start from writing that value in binary.

$27226 = 00000000000000000110101001011010b$

Now we move from left to right bit by bit. Yes, I know that the first bits can be omitted, but in software we will probably use here a thirty-two bit unsigned integer variable so just starting every time at position thirty-one makes everything much easier. To get the value of thirty-first bit all we have to do is shift the number right by thirty-one positions. Logical isn't it?

$(27226 \gg 31) = 0$

We got a binary zero. That's great, because we don't have to do anything in this case. Let's continue checking bits by decreasing length of the shift until we hit binary value $1$.

$(27226 \gg 16) = 0$
$(27226 \gg 15) = 0$
$(27226 \gg 14) = 1$

Got it! What do we do now? We take the value $283$ save it as a thirty-two bit unsigned integer variable and left shift it six times. Why exactly six times? Because we want to move the most significant bit that's not a zero to position fourteen.

$00000000000000000\color{red}{100011011}000000b$

Cool things happen when we subtract those two values. Just remember that in this world subtraction is done by using the bit by bit xor operation. Lets try it now.

$00000000000000000\color{red}{1}10101001011010b$
$\; - \;$
$00000000000000000\underline{\color{red}{1}00011011}000000b$
$\; = \;$
$00000000000000000\color{red}{0}10110010011010b$

See what happened to $1$ on position fourteen? It disappeared! This means that we can continue.

$(27226 \gg 14) = 0$
$(27226 \gg 13) = 1$

Got another $1$ this time on position thirteen! This can mean only one. We shift our $283$ left five times and subtract it from previous result!

$000000000000000000\color{red}{1}0110010011010b$
$\; - \;$
$000000000000000000\underline{\color{red}{1}00011011}00000b$
$\; = \;$
$000000000000000000\color{red}{0}0111111111010b$

This is how we got rid of our uninvited guest on position thirteen. We can continue and find next problem.

$(27226 \gg 13) = 0$
$(27226 \gg 12) = 0$
$(27226 \gg 11) = 1$

At this moment everyone smart enough probably guessed the algorithm. But just in case I'm wrong about that I'm going to show explicitly every operation we need to make.

$00000000000000000000\color{red}{1}11111111010b$
$00000000000000000000\underline{\color{red}{1}00011011}000b$
$\Downarrow$
$00000000000000000000\color{red}{0}\color{orange}{1}1100100010b$
$000000000000000000000\underline{\color{orange}{1}00011011}00b$
$\Downarrow$
$000000000000000000000\color{orange}{0}\color{blue}{1}101001110b$
$0000000000000000000000\underline{\color{blue}{1}00011011}0b$
$\Downarrow$
$0000000000000000000000\color{blue}{0}\color{green}{1}01111000b$
$00000000000000000000000\underline{\color{green}{1}00011011}b$
$\Downarrow$
$00000000000000000000000\color{green}{0}01100011b$

And we are done! We just change the binary value to decimal using windows calculator set to programmer mode and we can summarize that in Galois finite field:

$27226 \;\%\; 283 = 99$

Do you remember how they taught You addition is school? Remember how $1+1=2$? Forget all of that! From now on $1+1=0$! Why? Because now we are in Galois Field! And they have rules here young lady! Oh, and subtraction. Remember how subtraction used to be reverse of addition? It still is, but it's also the same operation. Easy huh?

From now on when we hear "add" we think "xor"! "Exclusive Or" is a very useful operation that has been used in cryptography for a long time. We will not be using it's full potential though. Just the basics. Xor is a binary operation. This means that if we want to add two numbers together we need to know their binary representations. The result is calculated by compering one by one same significant bits of two numbers and xoring them. This means writing $1$ if they are different, and $0$ when they are the same.

$174 = 10\color{red}{1}0111\color{orange}{0}b$
$+$
$113 = 01\color{red}{1}1000\color{orange}{1}b$
$=$
$223 = 11\color{red}{0}1111\color{orange}{1}b$

Explanation time! You see the three red bits? First two are the same so we write $0$ in the result. Two orange ones are different that's why the resulting binary value is $1$. If You read the previous chapter You probably expected to see somewhere a modulo. You are right. I chose to use the simplest and not formal definition of xor. The proper one uses "normal" addition and "normal" modulo.

$\forall x,y \in \{0,1\} \quad x \oplus y = (x + y) \% 2$

Subtraction

And how will subtraction work? Probably we should go bit by bit and do "normal" subtraction and "normal" modulo two like this:$(x - y) \% 2$. You don't believe me that's the same as a addition? Let me show You!

$(0 - 0) \% 2 = 0 \% 2 = 0$
$(0 - 1) \% 2 = -1 \% 2 = 1$
$(1 - 0) \% 2 = 1 \% 2 = 1$
$(1 - 1) \% 2 = 0 \% 2 = 0$

Two identical binary values give us $0$ and two different ones give us $1$. You have to admit this sounds a lot like my first definition of addition. I trust You're smart enough to deduce the rest.

Neutral Element

This is a field right? So the addition and subtraction have to have a neutral element. What is it? Addition requires us to do some xor operations. So maybe we can use the neutral element of a xor? Good thinking! Neutral element of xor is a single binary zero. When we xor any binary value with a binary zero we get that value unchanged.

$0 \oplus 0 = 0$
$0 \oplus 1 = 1$

But overall there are eight of those operations that we have to do if we want to add two values. So we probably need eight of those zeroes. Correct! The neutral element of addition and subtraction is a vector of eight binary zeroes.

$0 = 00000000b$

AES (03) Galois Finite Field

Congratulations You are now learning now about Galois Finite Field! As everything in math it has a kick-ass name! But it's pretty easy if you just read a blog post about it. Preferably a blog post from someone who understands discrete math, and does not like to write to many complicated definitions. If you need more info read a book! Damn, You are lazy!

This is a field: $(K,+,\cdot,1,0)$ Looks simple right?

• "$K$" is a set of all numbers that we can use.
• "$+$" is an operation that behaves just like addition.
• "$\cdot$" is an operation that behaves just like multiplication.
• "$1$" is an element of "$K$" that's neutral to "$\cdot$"
• "$0$" is an element of "$K$" that's neutral to "$+$"

The word "neutral" means that for every element of $K$:
$\forall x \in K \quad x + 0 = x$
$\forall x \in K \quad x \cdot 1 = x$

Imagine now that "$K$" are all Real numbers, "$+$" is addition, "$\cdot$" is multiplication, "$1$" is number one and "$0$" is number zero. Boom! We got a field which You have been using on math through all high school!

When a Field is a Finite Field? That's easy. When "$K$" is a finite set.

For our purpose let's define "$K$" as a set containing first $2^8$ natural numbers. This gives us a total of 256 elements. We can write them as decimals or hexadecimals but sometimes the most useful is the binary representation. Memorize this:

$K=(0, 1, 2,\ldots, 255)$
$K=(0x00, 0x01, 0x02,\ldots, 0xFF)$
$K=(00000000b, 00000001b,\ldots, 11111111b)$

Having a finite "$K$" created a problem with "$+$" and "$\cdot$" operations. For example if "$\cdot$" is a normal multiplication we get $250 \cdot 20 = 250 * 20 = 5000$. That's way outside of "$K$"! Fortunately we can easily fix this by changing the definition a little. Let's define "$\cdot$" as multiplication modulo $17$. This gives us $250 \cdot 20 = (250 * 20) \% 17 = 5000 \% 17 = 2$. And now the result popped right back into "$K$". We are awesome!

But why did I use $17$? Because why not! I can use any number from "$K$" for it to work. If I work a little harder, and instead of normal addition and multiplication use definitions created by Galois, I can even use a number outside of "$K$". I just have to remember in that case that I need to chose a prime number.

OK so from now on lets use $283$!

AES (02) History and Prehistory!

Because since the dawn of civilization government like to hide stuff from us in 1975 National Bureau of Standards got IBM to write the safest cipher in the world called DES or Data Encryption Standard! IBM is no Microsoft so they did good job. Unfortunately the bureaucracy as usual did its worst. Who needs 128 bits of key? I think 56 bits is enough! - said someone with no idea about cryptography. Because of that in 1997 DESCHAL Project brute forced through all combinations of the key and cracked it for the first time. Now I can brake it on my laptop while playing CoD.

Next time they got someone smarter to manage the whole standard. That smart person made a contest. Everyone could send their ciphers and also everyone could review them. From five finalists (Rijndael, RC6, Mars, Serpent and Twofish) one victorious emerged! Rijndael. It had many key lengths but for the standard they chose only 128 bits, 196 bits and 256 bits. So far even 128 bits is long enough, but it will be broken soon so it's better to use 256 bits when creating something new.

AES (01) Problems with secrecy!

Did you ever read stories about how authorities are listening to your every left click? - They know everything! - Said to me once a man on the street wearing an aluminum foil hat. Because I *know* when information source is solid I started researching. How is it possible that even though everyone know how cryptography works, just by making the key your little "secret", you can safely store your precious files? Well, I found out!

There are just two rules of cryptography!
1. You should never invent your own cipher!
2. You should never implement some one else's ciphers by yourself!

Explanation of first rule is easy. What's the title of your doctorate in abstract mathematics? What? You don't have one? Then get your console and play some Halo 4!

Accepting the second rule requires a little tough love from my side. Do You really think you are better then a team of experts working for thousands of man hours fixing bugs reported by a community of hundreds of testers? Oh. You do? Then go home Mr. Schneier! You are drunk!

But since when did something displayed on a computer screen got a control over my free will? OK, there was this one time with that cat video, but never again! Oh man that cat was soo cute... Ahh! Focus! Let's ignore those two rules and learn something about currently most commonly used cipher in the world Rijndael. Also called Advanced Encryption Standard or AES for short. This pretty much means if someone finally breaks it we all are screwed.