AES encryption with python step by step
W e are going to start this long series on cryptography applied with python.
We will start with AES.
What is AES Encryption?
The Advanced Encryption Standard (AES) is the most widely used symmetric cipher. Today, although the term “Standard” in its name refers only to the US government, AES bulk encryption is also mandatory in several industry standards and is used in many commercial systems. Commercial standards that AES systems include the Internet security standard IPsec, TLS, Wi-Fi encryption the IEEE 802.11i standard, SSH (Secure Shell) network protocol, Skype Internet Telephone, and many security products around the world. To date, there is no better attack than the known brute force against AES.
With AES we have blocks of 16 bytes (128 bits) and with key sizes of 16, 24, 32 bytes.
To learn more about the AES cryptosystem you can watch Christof Paar’s video in the link below.
We go through a number of processes and where we operate on 16 bytes as an input and output. Each block, known as a state, is operated on as a 4x4 matrix, such as:
01 02 03 04
05 06 06 07
08 09 0A 0B
0C 0D 0E 0F
For different key sizes, we go through a certain number of turns (N):
1. 128-bit key (16 bytes) -> N=10 turns
2. 192-bit key (24 bytes) -> N=12 turns
3. 256 bit (32 byte) key -> N=14 turns
The figure 1 below describes the 128-bit encryption process, and where we have 10 turns. For a 128-bit key, it is extended to 44 words of 33 bits each, and where each turn uses four words (128 bits) as input for each turn. With turn 0, the initial transformation is to add a turnkey. Subsequent turns (apart from the final turn) consist of:
1. Substitution bytes.
2. Shift row.
3. Mixing column.
4.Add a rounding key.
And the final turn consists of:
1.Substitute bytes.
2. Shift Row.
3.Add a rounding key.
S-box and inverted S-box
As part of the process, transforms the inputs into a new value as an output each state into a new value using an S-box array (like Table 1). In this case, the S-Box table is a 16x16 matrix that takes each input value, where the first four bits are used to define the row of the table, and the next four bits define the column (Figure 2.a). For example, if the input byte is CF, then the output will be 8A. The S-box reverses the process of the S-box, so that the DF refers to CF (Figure2.b).
Here are some examples of Python3 code that implements S-box and reverse S-box :
sbox = [
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
]
sboxInv = [
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
]def subBytes(state):
for i in range(len(state)):
state[i] = sbox[state[i]]def subBytesInv(state):
for i in range(len(state)):
state[i] = sboxInv[state[i]]state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
subBytes(state)
print("s-box: ", state)subBytesInv(state)
print("inverse of s-box: ", state)
If we run we some sample data, we can see we get the original data back when we implement the inverse S-box:
s-box: [124, 119, 123, 242, 107, s-box: [124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202]111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202]
inverse of s-box: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]Shift Row Transformation
With this process, the following transformation is applied:
1. The first line remains unchanged.
2. The second row has a circular shift of one byte to the left.
3. The third row is shifted two bytes to the left.
4. The fourth row is shifted three bytes to the left.
For example:
54 33 AB C1 54 33 AB C132 15 8D BB 15 8D BB 325A 73 D5 52->D5 52 5A 7331 91 CC 98 98 31 91 CC
For the reverse process, a right shift will be used. Here is an example of an offset code:
def rotate(word, n):
return word[n:]+word[0:n]def shiftRows(state):
for i in range(4):
state[i*4:i*4+4] = rotate(state[i*4:i*4+4],i)def shiftRowsInv(state):
for i in range(4):
state[i*4:i*4+4] = rotate(state[i*4:i*4+4],-i)state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
shiftRows(state)
print("row: ", state)shiftRowsInv(state)
print("row inverse: ", state)
A sample run gives:
row: [1, 2, 3, 4, 6, 7, 8, 5, 11, 12, 9, 10, 16, 13, 14, 15]
row inverse: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]In this transformation, each column is taken one at a time and each byte of the column is transformed into a new value based on the four bytes of the column. For each column (a0, a1, a2 and a3) we have (where we use Galois multiplication)
The Python3 code for the mix column transformation for a single column is:
from copy import copydef galoisMult(a, b):
p = 0
hiBitSet = 0
for i in range(8):
if b & 1 == 1:
p ^= a
hiBitSet = a & 0x80
a <<= 1
if hiBitSet == 0x80:
a ^= 0x1b
b >>= 1
return p % 256def mixColumn(column):
temp = copy(column)
column[0] = galoisMult(temp[0],2) ^ galoisMult(temp[3],1) ^ \
galoisMult(temp[2],1) ^ galoisMult(temp[1],3)
column[1] = galoisMult(temp[1],2) ^ galoisMult(temp[0],1) ^ \
galoisMult(temp[3],1) ^ galoisMult(temp[2],3)
column[2] = galoisMult(temp[2],2) ^ galoisMult(temp[1],1) ^ \
galoisMult(temp[0],1) ^ galoisMult(temp[3],3)
column[3] = galoisMult(temp[3],2) ^ galoisMult(temp[2],1) ^ \
galoisMult(temp[1],1) ^ galoisMult(temp[0],3)def mixColumnInv(column):
temp = copy(column)
column[0] = galoisMult(temp[0],14) ^ galoisMult(temp[3],9) ^ \
galoisMult(temp[2],13) ^ galoisMult(temp[1],11)
column[1] = galoisMult(temp[1],14) ^ galoisMult(temp[0],9) ^ \
galoisMult(temp[3],13) ^ galoisMult(temp[2],11)
column[2] = galoisMult(temp[2],14) ^ galoisMult(temp[1],9) ^ \
galoisMult(temp[0],13) ^ galoisMult(temp[3],11)
column[3] = galoisMult(temp[3],14) ^ galoisMult(temp[2],9) ^ \
galoisMult(temp[1],13) ^ galoisMult(temp[0],11)g = [1,2,3,4]mixColumn(g)
print ('Mixed: ',g)
mixColumnInv(g)
print ('Inverse mixed', g)
The result gives:
Mixed: [3, 4, 9, 10]
Inverse mixed [1, 2, 3, 4]Add round key transformation
With this transformation, we implement an XOR operation between the round key and the input bits. A Python method to implement this is:
def addRoundKey(state, roundKey):
for i in range(len(state)):
state[i] = state[i] ^ roundKey[i]state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
roundkey=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1]addRoundKey(state,roundkey)print(state)addRoundKey(state,roundkey)print(state)
A sample run does:
[3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
