Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

M_0 is interested in cryptography. Recently he learned the Advanced Encryption Standard (AES). AES operates on a 4×4 column-major order matrix of bytes and he found it that there is a step called the MixColumns step in the AES.

In the MixColumns step, there is a state matrix, the four bytes of each column of the state are combined using an invertible linear transformation. The MixColumns function takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. Together with ShiftRows, MixColumns provides diffusion in the cipher.

During this operation, each column is multiplied by the known matrix that for the 128 bit key is:

The addition operation is defined as: xor.

The multiplication operation is defined as:

multiplication by 1 means no change

multiplication by 2 means shifting to the left

multiplication by 3 means shifting to the left and then performing xor with the initial unshifted value.

Notice:After each shifting, a conditional xor with 0x1B should be performed if the shifted value is larger than 0xFF.

In the MixColumns step, there is a state matrix, the four bytes of each column of the state are combined using an invertible linear transformation. The MixColumns function takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. Together with ShiftRows, MixColumns provides diffusion in the cipher.

During this operation, each column is multiplied by the known matrix that for the 128 bit key is:

The addition operation is defined as: xor.

The multiplication operation is defined as:

multiplication by 1 means no change

multiplication by 2 means shifting to the left

multiplication by 3 means shifting to the left and then performing xor with the initial unshifted value.

Notice:After each shifting, a conditional xor with 0x1B should be performed if the shifted value is larger than 0xFF.

There are several cases.

The first line is an integer T (T <= 20000), indicating the test cases.

Then is the state matrix, each case followed by four lines, each line contains four bytes, separated by spaces.

The first line is an integer T (T <= 20000), indicating the test cases.

Then is the state matrix, each case followed by four lines, each line contains four bytes, separated by spaces.

提交代码