How to teach DES using Python? The easy way… Part-2: Round function F()
This is second part of a 4-part article on DES using Python. In previous, article DES key generation is explained. This article explains about another important section of DES i.e. Round function F() or Feistel function. In each round DES uses this function to calculate value for further processing. How and where it is used is topic of next article but in this article we will what is it and how to implement using Python.
DES Round function
In simple words DES round function takes two binary strings (32-bit and 48-bit )as input and produce a 32-bit output. The two input binary strings are one half of the plaintext (each round uses half from previous round ) and the round key. As input binary strings are of unequal size so the first step should be expanding or reducing the one or another. DES chooses expansion and expand 32-bit binary string to 48-bit with the help of an expansion table. Once both input strings are of equal length then a XOR (exclusive OR) operation is performed which result into a 48-bit binary string. The next step is to pass these 48-bit string to S-boxes which turns this into 32-bit string. The final step is a permutation which provides randomness by exchanging the bit position. Please refer figure 1 as reference point.
Bits Expansion
The 32-bit binary string needs to expand upto 48-bit for further processing. This is done by using a expansion table which can be represented as Python List object for easy handling. Again, the value from expansion table will serve as index for input 32-bit string and the bit will selected and accumulated as new binary string.
XOR (Exclusive OR)
After expansion of 32-bit to 48-bit binary string, a XOR operation is performed on expanded 48-bit and input 48-bit key. The XOR is simple operation which checks the bit in both string for each index and result into ‘0’ if both are same i.e. (‘11’ and ‘00’) else result into ‘1’ for different value i.e. (‘01’ or ‘10’). For demo purpose this logic can be implemented as a simple python loop with if conditions.
S-box Calculation
The main part of this round function is the S-box calculation. In abstract view, this takes a 48-bit binary string as input and produce a 32-bit binary string as output with the help of 8 S-boxes. Each S-box has four rows and 16 columns numbered from (0–3 and 0–15) and each row has predefined value between 0 to 15. Figure 2 shows the S-boxes.
Now, to use these S-boxes, Python list can be very handy which have concept of list within list. So, a Python list will have 8 element representing each of these eight S-boxes and then each of these 8 element will further have four list, one for each row and finally each row itself will be a Python list holding row values indexed between 0–15. So to access a value, the list will have three layer index. For example, if SBOX is the list representing the S-boxes then it can be access as SBOX[boxnumber][rownumber][column_number], where boxnumber will be between 0–7, rownumber [0–3] and column_number [0–15]. The Python representation is shown in following code snippet.
To perform S-box operation the 48-bit XORed output is split into 8 part each having 6 bits. Then these 8 binary strings are passed to S-boxes one to each individual S-box. Each S-box works in similar manner and process 6 bits as follows, the first and last bit of string is treated as row number (00, 01,10,11 or 0,1,2,3 ) for the S-box and middle four value is treated as column number (0000 to 1111 or 0–15). Thus having row and column number help to access the value from the S-box which will be a decimal number between 0–15 and treating these as HEX convert it to a 4-bit binary string (0000 to 1111). So, each 8 boxes will return 4-bit as output and which combined together will form 32-bit output string. In the following code snippet the split part is carried out by the use of textwrap module which makes this kind of split very easy. Then a S-box lookup method is defined which takes three parameters (boxnumber, rownumber, column_number) and return a single value as output.
Final Permutation
To bring randomness in cipher, each round perform permutation on the output of the round function. This permutation is also carried out with the permutation table designed for the round function. Very similar to previous table operation this can be also achieved as Python list and looping operation as shown in following code snippet.
The Round Function F()
With the help of previous functions, it will easy to perform round function which will take 32-bit and 48-bit as input and will return the final 32-bit as output. Following code snippet illustrate the implementation. This function can be easily map to the steps shown in figure 1.
That’s it. This section explained and walk through the Python code for implementing the DES round function. As mentioned this is the second part of a 4-part easy learning DES series, the first part was on DES subkey generation and in the next part we will use these two section and will try to implement DES encryption.
As always, any comments, suggestions, feedbacks or criticism is welcome to improve the article further. If you are interested in English proof-reading, you are most welcome.
