AES S-Box Cycles and Matrix Representation

Question

I would like to know how many cycles the Rijndael S-Box consists of. Ideally expressed as a product of k-cycles in standard notation.

Also, given that the AES cipher is totally linear without the permutation step, does it mean the decryption routine reduces to a simple matrix inversion?

Answer 1

The cycle notation (using hex) is:

(00,63,FB,0F,76,38,07,C5,A6,24,36,05,6B,7F,D2,B5,D5,03,7B,21,
 FD,54,20,B7,A9,D3,66,33,C3,2E,31,C7,C6,B4,8D,5D,4C,29,A5,06,
 6F,A8,C2,25,3F,75,9D,5E,58,6A,02,77,F5,E6,8E,19,D4,48,52)
(01,7C,10,CA,74,92,4F,84,5F,CF,8A,7E,F3,0D,D7,0E,AB,62,AA,AC,
 91,81,0C,FE,BB,EA,87,17,F0,8C,64,43,1A,A2,3A,80,CD,BD,7A,DA,
 57,5B,39,12,C9,DD,C1,78,BC,65,4D,E3,11,82,13,7D,FF,16,47,A0,
 E0,E1,F8,41,83,EC,CE,8B,3D,27,CC,4B,B3,6D,3C,EB,E9,1E,72,40,
 09)
(04,F2,89,A7,5C,4A,D6,F6,42,2C,71,A3,0A,67,85,97,88,C4,1C,9C,
 DE,1D,A4,49,3B,E2,98,46,5A,BE,AE,E4,69,F9,99,EE,28,34,18,AD,
 95,2A,E5,D9,35,96,90,60,D0,70,51,D1,3E,B2,37,9A,B8,6C,50,53,
 ED,55,FC,B0,E7,94,22,93,DC,86,44,1B,AF,79,B6,4E,2F,15,59,CB,
 1F,C0,BA,F4,BF,08,30)
(0B,2B,F1,A1,32,23,26,F7,68,45,6E,9F,DB,B9,56,B1,C8,E8,9B,14,
 FA,2D,D8,61,EF,DF,9E)
(73,8F)

Answer 2

You're asking two different questions, in the future please ask them separately.

As for the first question, here's the S-Box as a C array, as per Wikipedia:

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

Now take it upon yourself as an exercise to write it in cycle notation.

As for your second question, without the S-box there is a matrix $A$ of size $128\times 128$ bits and a vector $b$ of length $128$ bits such that AES performs the following transformation: $y = Ax+b$. Decryption is then $x = A^{-1}(y+b)$ (since $-b = b$ for bits). But the matrix $A$ is fixed, so it's really very similar to encryption, just with different $A,b$.

Answer 3

As to the last question (the first is already answered, and corresponds to my answer to your previous question), the matrix $A$ and the vector $b$ such that encryption corresponds to $Ax + b$ depend on the key. So assuming we have pairs $(x,y)$ of plaintext and corresponding ciphertext, we can set up equations to solve for those unknowns.... If you then have computed $A$ and $b$, decryption becomes inversion of $A$, but it's more than that.