https://www.quora.com/How-is-an-S-box-constructed-in-AES

https://www.youtube.com/watch?v=shaQZg8bqUM

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

(Primitive root modulo n = generator)

A multiplicative inverse is a number that undoes multiplicative by a certain number, it is the replacement division operation in modular arithmetic. For example, if we are operating in GF(61), that is, all integers modulo 61, and we calculate some modular inverses:

modular inverse of 5 (% 61) = 49; (5 * 49) % 61 = 1

modular inverse of 29 (% 61) = 40; (29 * 40) % 61 = 1

Then we can use them to multiply and undo multiplication like so:

(5 * 29) % 61 = 23

(23 * 40) % 61 = 5

(23 * 49) % 61 = 29

By multiplying by the multiplicative inverse of each factor, we undid the multiplication.

The Rijndael s-box (substitution box; lookup table) is an array created using a generator. A generator in modular arithmetic is a value that when squared by consecutive powers continues to produce a unique value until every number in the modular field has been exhausted, thus, it is said to have a periodicity of the modulus minus one. Its purpose in AES serves to obscure the relationship between key and ciphertext.

In our code to generate the s-box, p starts out equalling 3, which means by multiplying it by 3 (over GF(2^8)) we are squaring it over and over again to generate a seemingly randomly placed but unique value <= 256. Our q value is the same thing, except we are going through its series of unique values backwards by squaring the multiplicative inverse of 3 (246 under our Galois field) over and over again. So with each unique value from the generator, we then calculate a circular left shift on q by 1, then the value by cls(q,2), then xor by cls(q,3), then xor by cls(q,4), then xor by 99. This entire design was developed with the cryptographical concept of nonlinearity in mind - obscuring the correlation between input and output. This is how it resists linear and differential cryptanalysis.

Once we have generated our s-box, we create our inverse s-box simply by switching index and value (ie s_box[0] = 99, inverse_s_box[99] = 0).

>>5860296

Correction: < 256

Correction: then xor the value by cls(q,2)

using System;namespace AES{ class AESLib { / Tables / public static byte[] s_box; public static byte[] inverse_s_box; public static byte[] inverse_s_box_hardcode = { 0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB, 0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB, 0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E, 0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25, 0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92, 0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84, 0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06, 0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B, 0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73, 0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E, 0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B, 0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4, 0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F, 0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF, 0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61, 0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D}; public static void init() { init_s_box(); } private static void init_s_box() { s_box = new byte[256]; //256 = 2^8 inverse_s_box = new byte[256]; byte p = 1, q = 1; //first values in the loop are 3 and 246 do { p = multiply(p, 3); //values of p begin as: 3, 5, 15, 17, 51, 85, 255 //Console.WriteLine("p = " + p); / dividing q by 3 = multiplying by 246 in GF(2^8) / //values of q begin as: 246, 82, 199, 180, 108, 36, 28 q = multiply(q, 246); //Console.WriteLine("q = " + q); int shift = q ^ cls(q, 1) ^ cls(q, 2) ^ cls(q, 3) ^ cls(q, 4); byte xor = (byte) (shift ^ 99); / The inverse s box is the opposite of the s-box, simply generated by switching value and index. / s_box[p] = xor; inverse_s_box[xor] = p; } while (p != 1); s_box [0] = 99; inverse_s_box [99] = 0; } / Circular left shift * returns x <<< y / private static byte cls(byte x, byte y) { y = (byte) (y % 8); byte a = (byte) (x << y); byte b = (byte) (x >(8 - y)); return (byte) (a | b); } / GF(2^8) multiplication method taken from https://en.wikipedia.org/wiki/Rijndael_MixColumns / private static byte multiply(byte a, byte b) { byte p = 0; for (int counter = 0; counter < 8; counter++) { if ((b & 1) != 0) { p ^= a; } bool hi_bit_set = (a & 128) != 0; a <<= 1; if (hi_bit_set) { a ^= 27; / x^8 + x^4 + x^3 + x + 1 / } b >>= 1; } return p; } public static void Main (string[] args) { init(); Console.WriteLine("[{0}]", string.Join(", ", inverse_s_box)); Console.WriteLine("[{0}]", string.Join(", ", inverse_s_box_hardcode)); } }}