In this post, we are going to find out what is AES, how its algorithm works. And in the last section using python AES modules we are going to encrypt/decrypt message.
Background
Before AES show up to the world, there was Data Encryption Standard, DES. In early 1970 IBM created DES based on Horst Feistel design so we call DES as Feistel-structure. Both AES and DES are symmetric key algorithm and block cipher. We are going to talk more about block cipher.
But nowadays DES is known as not secure to encrypt important data. In 1999, at DES Challenge III, it took only 22 hours to break ciphertext encrypted by DES, using brute force attack! The main reason that DES is not secure is because of the short key length which is only 56-bits.
For these reasons, we need more powerful cryptosystem and in 2001, Vincent Rijmen and Joan Daemon created AES. It has longer key length which is 128-bit, 192-bit and 256-bit and this is exponetially stronger than DES 56-bit key length.
AES also enables faster encryption than DES, which is opt for software applications, firmware and hardware which require low latency or high throughput. So it is used in many protocols such as SSL/TLS and can be found in modern applications and devices.
Algorithm
We can see the algorithm flow likewise:
- Add round key
- Substitute bytes
- Shift rows
- Mix columns
- Add round key
Now let’s dive into each step and see how it works.
Represent data as metrixes
But before going to first step of algorithm, let’s talk about block cipher. Block cipher is cryptosystem which encrypts data not by bit but by block which is group of bits, applying algorithm per block.
Because AES is also block cipher, we first represent data such as plaintext, ciphertext and key as block. Each block has 1byte(8bit) so in total 16x8=128bit, notice that we have 128-bit key length. And as you can see the order of p_0, p_1 …, the data represented as column by column order.
Add round key
This is the first step of AES algorithm; add round key operation, and this is simply XOR operation. We have 128-bit length plaintext and 128-bit length key so XOR operate bit by bit. And as you can see the diagram the probability of having 0 or 1 is 50% each.
Round function
We can see the red text “ROUND FUNCTION” in the flow chart of AES, which grouped several functions. And round is simply group of functions, algorithm. And we can say executing 10 rounds as executing 10 times of grouped algorithm. Basically for 128-bit length key, AES takes 10 rounds, 192-bit key for 12 rounds and 256-bit key for 14 rounds.
Substitute bytes
In the Substitute bytes step, we use S-BOX to substitute data. Simply put we can see S-BOX as lookup table. The way to substitute bytes for block is like this: each block have 8-bit data, and we can see first 4-bit as row index and the last 4-bit as column index, with these row, column index we can take the value from the S-BOX.
Shift rows
In the shift rows section, execute circular left shifting for each row. For first row of box shift 0 step to left, second row of box shift 1 step to left, and so on.
So after finishing shifting rows, first rows changes from s_0, s_4, s_8, s_12 to s_0, s_4, s_8, s_12, second rows changes from s_1, s_5, s_9, s_13 to s_5, s_9, s_13, s_1.
Mix columns
In the mix columns step, execute matrix-vector multiplication column by column. Take one column than multiply it to predefined circulant MD5 matrix.
As you can see we should addition and multiplication in bit level, and in multiplication we specifically do multiply 2 and 3. Then how we can do these operation?
We can think of addition as XOR operation on bit level, multiplying 2 as left shifting in bit level and multiplying 3? Combination of one left shift and one XOR operation.
After multiplication we do finish mix columns step. One thing to keep in mind is that mix columns step is not executed in last round.
Add round key
And the last step of the round is adding round key. At the very first of adding round key step, even before we entered into round, we use our own private key to execute step. But in each round we do not use private key instead we generate subkey and use it to add round key.
subkey generation
1 — As we talked earlier, we have private key represented as two-dimensional array, and each block has 1byte.
2 — First take the right-most column, and execute circular upward shift
3 — In the same way as we did before in substitute bytes step, substitute bytes using S-BOX
4 — Then do XOR operation with K_(i-4) columns and take the predefined value from rcon table, and do XOR operation again. The result is our first column of current round subkey.
5 — Generating 2nd, 3rd and last column of subkey is rather simple, just do XOR operation on K_(i-1) and K_(i-4) column.
Through step 1~5, we can generate subkey for adding round key in this round, then we do XOR operation with this new subkey and the data we encrypted so far.
And that’s it! These are steps AES algorithm takes for each round. And after doing same things for X rounds (10 rounds for 128-bit key length, 12 rounds for 192-bit key length, 14 rounds for 256-bit key length), we can get ciphertext encrypted by AES algorithm.
Example code
In the example, using python Crypto.Cipher module, we are going to see how plaintext can be encrypted and decrypted using AES.
Import modules
from Crypto.Cipher import AES
from Crypto import Random
import binasciiUsed Random module for simply generating our private key for this example, binascii module for encoding encrypted data to hexcode which helps to see encrypted data.
Solve padding problems
As we talked before in block cipher, data broke up into 128-bits and make metrixes for that data. But what if the data is less than 128-bit size? If length of data is not 0 (mod 128), then this is the problem. So to solve this problem, we add padding.
def append_space_padding(str, blocksize=128):
pad_len = blocksize - (len(str) % blocksize)
padding = 'a'*pad_len
return str + padding def remove_space_padding(str, blocksize=128):
pad_len = 0
for char in str[::-1]:
if char == 'a':
pad_len += 1
else:
break return str[:-pad_len]
So we defined append_space_adding and remove_space_adding functions. In append_space_padding , add padding value ‘a’ before we encrypt data, in remove_space_padding , we remove padding value ‘a’, this is going to be used after decrypt the data.
Encrypt/Decrypt
def encrypt(plaintext, key):
aes = AES.new(key, AES.MODE_ECB)
return aes.encrypt(plaintext) def decrypt(ciphertext, key):
aes = AES.new(key, AES.MODE_ECB)
return aes.decrypt(ciphertext).decode('UTF-8')
This is our encrypt, decrypt; bussiness logic. In these methods, we create new instance with MODE_ECB mode, then use its method.
What is ECB is not going to be covered in this post in detail. ECB is short for “Electronic Codebook”, we use AES on every 128 bits long plaintext block and in ECB mode these blocks are independent of each other so we use AES separately on every block. In the case of CBC mode which is one of block cipher mode of operation, uses chaining mechanisms which each block is depend on all the preceding blocks.
Entry point
if __name__ == "__main__":
# key is 128 bits - 16 bytes
key = Random.new().read(16)
print("key: %s" % key.encode('hex'))
plaintext = "Hello, AES!"
print("length of plaintext: %d" % len(plaintext))
print("plaintext: %s" % plaintext) paddedtext = append_space_padding(plaintext)
print("length of paddedtext: %d" % len(paddedtext))
print("paddedtext: %s" % paddedtext) ciphertext = encrypt(paddedtext, key)
print("hexified ciphertext: %s" % binascii.hexlify(bytearray(ciphertext))) decrypted = decrypt(ciphertext, key)
maybe_plaintext = remove_space_padding(decrypted) print("decrypted text: %s" % maybe_plaintext)
Results!
key: 8b5002efbe9cc0830cf1c18ab6237c3e
length of plaintext: 11
plaintext: Hello, AES! length of paddedtext: 128
paddedtext: Hello, AES!aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaahexified ciphertext: 1baccc35d666124f4109c448799869204c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b4c4246e423c5e7c43a153c13f53b746b
decrypted text: Hello, AES!
In the results, we can see length of paddedtext is 128 which is 0 (mod 128). hexified ciphertext is the ciphertext encrypted by AES, and decrypted text has Hello, AES! value which is same as plaintext
This example codes can be found here. Thanks a lot for reading! :)
