The Advanced Encryption Standard Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In 1997, National Institute of Standards and Technology (NIST) held a contest for a new encryption standard. It is because the Data Encryption Standard (DES) was no longer good enough for security. It had been the standard since year 1976.

There were other alternatives to a new encryption standard, for example, Triple DES (3DES) and International Data Encryption Algorithm (IDEA). However, 3DES was too slow and IDEA was not implemented because of its patents. NIST wanted a free and easy to implement algorithm that could replace DES.

After 3 years, NIST finally chose the Rijndael algorithm. This algorithm was created by Belgian computer scientists, Joan Daemen and Vincent Rijmen. This algorithm is named based upon the names of themselves.

On November 26, 2001 the Rijndael algorithm was announced as the new standard for encryption by Federal Information Processing Standards Publication (FIPS) 197. This standard was called as the Advanced Encryption Standard (AES). AES is still the current standard for symmetric-key encryptions in nowadays.

2. AES Algorithm

AES is a symmetric-key encryption that uses the same key for encryption and decryption. It allows for block size in any multiple of 32 bits, with minimum of 128 bits. The maximum of block size is 256 bits. The key size is same as the block size, however, the key size has no maximum.

In AES, State is used to maintain each block, whether it is plaintext or cipher text. State is a matrix of four rows and Nb columns. Nb is calculated by dividing the block length by 32. Nk refers the number of column in the Cipher key matrix with four rows. Nk can be calculated by dividing key length by 32.

AES is a round-based cipher. The number of rounds is commonly denoted as Nr. It is required to perform encryption or decryption that depends on the values of Nk and Nb. It is described in the table that follows:

How do I get the number of rounds? This is calculated from 6 plus the maximum of (Nb, Nk). For example, Nk and Nb are both 8, the number of rounds is 6 + 8 = 14..

AES algorithm consists the four operations, which are ByteSub, ShiftRow, MixColumn and AddRoundKey. The four operations are applied to the State. The four operations are done for each round to Nr times with one exception, which is MixColumn operation is removed from the last round.

Next, I describe each of the four operations of a round.

2.1 ByteSub

In this step, each byte in the State is substituted to a new byte using a 8-bit substitution box, the Rijndael S-box. The S-box is shown in Figure 1. All values are in hexadecimal format.

Figure 1: S-Box

The S-box is built by combining the multiplicative inverse shown in Figure 3 with an affinity matrix shown in Figure 2 to prevent algebraic attacks.

For instance, now we have the plain text of one character "F". First, we translate it to hexadecimal value of 46 using ASCII table. Now, we use the S-box and find row number 4 and column number 6. Then, we find that the hexadecimal value of 5a in the S-Box table. The S-Box is used to convert the character or plaintext in bytes to cipher text.

Now, we are going to use multiplicative inverse and affinity matrix to find the answer. This is used to show that the S-box is built by combining the multiplicative inverse and the affinity matrix.

First, we take the same character "F" with the hexadecimal value of 46. However, we are going to use multiplicative inverse table instead of using S-Box. The searching way for the table is same as the S-Box. From the multiplicative inverse table, we can get value F5. F5 is 1111 0101 in binary. The value 1111 0101 can be rewritten as the polynomial 1x7 + 1x6 + 1x5 + 1x4 + 0x3+ 1x2+ 0x1+1. This can be simplified to x7 + x6 + x5 + x4 + x2 + 1. We assign a value of 1 if the power of polynomial is same with the subscript of N. For example, this makes N0 N1 N5 N6 N7 change to 10111. After that, we are going to use XOR operation for the addition. Shown below is the simplified mathematics for the entire affine transformation.

Row 1 = 1 0 0 0 1 1 1 1 => N0 + N4 + N5 + N6 + N7 => 1 + 1+ 1+ 1+ 1 = 1

Row 2 = 1 1 0 0 0 1 1 1 => N0 + N1 + N5 + N6 + N7 => 1 + 0+ 1+ 1+ 1 = 0

Row 3 = 1 1 1 0 0 0 1 1 => N0 + N1 + N2 + N6 + N7 => 1 + 0+ 1+ 1+ 1 = 0

Row 4 = 1 1 1 1 0 0 0 1 => N0 + N1 + N2 + N3 + N7 => 1 + 0+ 1+ 0+ 1 = 1

Row 5 = 1 1 1 1 1 0 0 0 => N0 + N1 + N2 + N3 + N4 => 1 + 0+ 1+ 0+ 1 = 1

Row 6 = 0 1 1 1 1 1 0 0 => N1 + N2 + N3 + N4 + N5 => 0 + 1+ 0+ 1+ 1 = 1

Row 7 = 0 0 1 1 1 1 1 0 => N2 + N3 + N4 + N5 + N6 => 1 + 0+ 1+ 1+ 1 = 0

Row 8 = 0 0 0 1 1 1 1 1 => N3 + N4 + N5 + N6 + N7 => 0 + 1+ 1+ 1+ 1 = 0

Figure 2: Affinity Matrix

The result is the vector 1001 1100. Then, we add the vector 1100 0110 to our vector. The answer is 0101 1010 The final result is converted to hexadecimal value is 5a. Now, we look back to the S-Box and check again the row number 4 and column number 6. We should get value 5a and it is same as the result we got just now. We have proved it. Next step, we are going to discuss ShiftRows.

Figure 3: Multiplicative Inverse Table GF(28)

2.2 ShiftRows

The ShiftRows is used to shift the rows of the state. It periodically shifts the bytes to the left in each row by a certain offset. This means that the first row will not be shifted, the shifting for second row, third row and fourth row are 1 bytes, 2 bytes and 3 bytes respectively. This shifting pattern is for the block of size 128 bits and 192 bits only. However, in the case of the 256 bit block, the shifting pattern is totally different. Similarly, the first row is left unchanged, second row is shifted one to the left. The only difference is the third and fourth rows are shifted by offsets three and four respectively.

Figure 5: ShiftRows

2.3 MixColumns

In this step, an invertible linear transformation is used to combine with the four bytes of each column of the State. MixColumns takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. During this operation, each column is multiplied by the known matrix that for 128 bit key is:

C:\Users\khayuen\Desktop\03608820f7bf9da224d777d3979ed4a1.png

How the multiplication operation works? Multiplication by 1 means leaving unchanged, multiplication by 2 means shifting byte to the left and multiplication by 3 means shifting byte to the left and XOR with initial unshifted value.. After shifting, if the shifted value is larger than 0xFF, then the value is XORed with 0x1B. [2]

Generally, the columns are treated as column as a four-term polynomial. The columns are recognized as polynomial over GF(28) and multiplied modulo x4+1 with a fixed polynomial a(x) given by a(x) = (03)x3+{01}x2+{01}x+{02). [4]

C:\Users\khayuen\Desktop\AES-MixColumns.png

Figure 6: MixColumns

2.4 AddRoundKey

In this operation, a Round Key will be added to the State by using bitwise XOR operation. For each round, a Round Key is made from the main key using Rijndael's key schedule. Besides that, each Round Key is same size as the State. The Round Key is added by combing each byte of the State with corresponding byte of the Round Key using bitwise XOR. [2]

C:\Users\khayuen\Desktop\AES-AddRoundKey.png

Figure 7: AddRoundKey

4. Decryption

Decryption in AES is just the inverse of the whole process. Therefore, it is fundamentally like doing everything backwards. It starts at the last round and the last round key. All the operations are inverse. After all the rounds have been completed in reverse order, finally you generate the original plain text. For more information about decryption, google it. [3]

5. Real -world Application

In today, almost all application are using the AES algorithm. This algorithm is also used in different electronic devices. For instances, PCs, PDAs, mobile phones, tablets, wireless devices and many others. The most impressive facts when discussing the AES implementations is its use on 8-bit processor used in several embedded systems.

Besides that, the other great implementation of AES algorithm is in the security of smart cards. It has been tested that AES algorithm was the fastest-performing cipher when compared to several other cipher. From this, we can know that AES algorithm was using the least amount of RAM, which also improves the effectiveness of this algorithm. [1]

The real-world applications need AES algorithm and we cannot live without it. Now, we will move to the security of the algorithm.

6. Attacks on AES

7. Conclusion